Scheduling jobs with release dates and tails on identical machines to minimize the makespan (Q1091256)

The problem of scheduling jobs on m identical parallel machines is considered. Each job i has a release date \(r_ i\) when it becomes available for processing, has a processing time \(p_ i\) and has a tail \(q_ i\) which represents the additional time that must elapse after processing to complete the job. The objective is to minimize the maximum completion time or makespan. A heuristic method is described in which, at each stage, an available job, chosen to have a tail as large as possible, is scheduled on the machine that completes its processing earliest. It is shown that the maximum deviation of the makespan given by this heuristic from the optimal value is less than twice the largest processing time. A branch and bound algorithm is proposed which applies the heuristic method at each node of the search tree. A special feature of the algorithm is the novel interval branching rule which is used. For this branching rule a deadline \(d_ i\) on the completion of processing is required for each job i: initially it is computed using \(d_ i=UB-q_ i\), where UB is the upper bound found from the heuristic. Branching is based on a time interval \([r_ i,d_ i]\) within which processing must be performed. Schedules are partitioned according to whether the processing for job i is performed in the interval \([r_ i,r_ i+t+p_ i-1]\) or in \([r_ i+t,d_ i]\) where, in this algorithm, \(t=\lceil (d_ i-r_ i-p_ i)/2\rceil\). A lower bounding scheme is based on the result that by considering only jobs of a chosen subset, the sum of the m smallest release dates, the m smallest tails and all processing times is a lower bound on m times the optimal makespan. Computational results with the branch and bound algorithm for problems with up to 100 jobs and 8 machines are given.