E. Balas et al., THE ONE-MACHINE PROBLEM WITH DELAYED PRECEDENCE CONSTRAINTS AND ITS USE IN JOB-SHOP SCHEDULING, Management science, 41(1), 1995, pp. 94-109
Citations number
14
Categorie Soggetti
Management,"Operatione Research & Management Science
We study the one machine scheduling problem with release and delivery
times and the minimum makespan objective, in the presence of constrain
ts that for certain pairs of jobs require a delay between the completi
on of the first job and the start of the second (delayed precedence co
nstraints). This problem arises naturally in the context of the Shifti
ng Bottleneck Procedure for the general job shop scheduling problem, a
s a relaxation of the latter, tighter than the standard one-machine re
laxation. The paper first highlights the difference between the two re
laxations through some relevant complexity results. Then it introduces
a modified Longest Tail Heuristic whose analysis identifies those sit
uations that permit efficient branching. As a result, an optimization
algorithm is developed whose performance is comparable to that of the
best algorithms for the standard one-machine problem. Embedding this a
lgorithm into a modified version of the Shifting Bottleneck Procedure
that uses the tighter one-machine relaxation discussed here results in
a considerable overall improvement in performance on all classes of j
ob shop scheduling problems.