《1987 Scheduling jobs with release dates and tails on identical machines to minimize the makespan》.pdf

298 European Journal of Operational Research 29 (1987) 298-306 North-Holland Scheduling jobs with release dates and tails on identical machines to minimize the makespan Jacques CARLIER Institut de Programmation, UniversitC Paris VI, Paris, France Abstract: This paper considers the problem of scheduling independent jobs with release dates and tails on m identical machines to minimize the makespan. This m-machines problem is NP-hard in the strong sense. Jackson’s schedule is defined as the list schedule built by giving priority to the available job with the largest tail. It is proved that the deviation of Jackson’s schedule from the optimum is smaller than twice the largest processing time. Next, a new branching scheme is proposed by associating with each job an interval of time during which it has to be processed. To branch, the interval for a particular job is divided into two smaller ones. This is a general scheme which can be applied to many scheduling problems. Finally, a branch and bound algorithm is explained in detail and computational results are given. Keywords: Schedule, job, interval, machine, makespan Introduction smaller than twice the largest processing time.