Scheduling jobs on parallel machines with sequence-dependent setup times

Young Hoon Lee, Michael Pinedo

Research output: Contribution to journalArticlepeer-review

229 Citations (Scopus)


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 through parameters determined by the factors. In the third phase, as a post-processing procedure, a simulated annealing method is applied starting from a seed solution which is the result of the second phase. In the dispatching rule of the second phase there are two parameters of which the values are dependent on the particular problem instance at hand. Through extensive experiments rules are developed for determining the values of the two parameters which make the priority rule work effectively. The performance of the simulated annealing procedure in the third phase is evaluated for various values of the factors.

Original languageEnglish
Pages (from-to)464-474
Number of pages11
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1997 Aug 1

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Scheduling jobs on parallel machines with sequence-dependent setup times'. Together they form a unique fingerprint.

Cite this