《1997 Scheduling jobs on parallel machines with sequence-dependent setup times》.pdf

~_- , -~ ,~ .= ~,~, . EUROPEAN JOURNAL OF OPERATIONAL J RESEARCH ELSEVIER European Joumal of Operational Research 100 (1997) 464-474 Theory and Methodology Scheduling jobs on parallel machines with sequence-dependent setup times Young Hoon Lee a, *, Michael Pinedo b a Samsung Electronics, Semiconductor Division, System Support Group, P.O. Box 37, Suwon 449-900, South Korea b Department of Industrial Engineering and Operations Research, Columbia University, New York, IVY 10027, USA Received 27 September 1994; accepted 23 November 1995 Abstract Consider a number of jobs to be processed on a number of identical machines in parallel. A job has a processing time, a weight and a due date. If a job is followed by another job, a setup time independent of the machine is incurred. A three phase heuristic is presented for minimizing the sum of the weighted tardinesses. In the first phase, as a pre-processing procedure, factors or statistics which characterize an instance are computed. The second phase consists of constructing a sequence by a dispatching rule which is controlled