Article ID: | iaor1992949 |
Country: | Netherlands |
Volume: | 47 |
Issue: | 1 |
Start Page Number: | 56 |
End Page Number: | 64 |
Publication Date: | Jul 1990 |
Journal: | European Journal of Operational Research |
Authors: | Kunnathur Anand S., Gupta Sushil K. |
Keywords: | heuristics, programming: dynamic |
This paper considers the following scheduling problem: Minimize the makespan in a single facility problem where the processing time of a job consists of a fixed and a variable part. The variable part depends on the start time of the job. The objective is to minimize makespan. Two optimizing algorithms based on dynamic programming and branch-and-bound techniques and five heuristic rules have been proposed. The heuristic solutions have been compared with the optimal solution for up to 7 jobs to identify the best heuristic. The detailed computational results for the branch-and-bound and the best heuristic rules are then obtained for problems with up to 15 jobs.