Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem

cited authors

  • Kunnathur, AS; Gupta, SK

fiu authors


  • 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 upto 7 jobs to identify the best heuristic. The detailed computational results for the branch-and-bound and the best heuristic rule are then obtained for problems with up to 15 jobs. © 1990.

publication date

  • July 5, 1990

Digital Object Identifier (DOI)

start page

  • 56

end page

  • 64


  • 47


  • 1