Heuristic scheduling of parallel machines with sequence-dependent set-up times

M. E. Kurz, Ronald Askin

Research output: Contribution to journalArticlepeer-review

75 Scopus citations


In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. Likewise, in many production environments, set-up activities are required for switching between items. This work addresses scheduling in parallel machines with sequence dependent set-up times and possibly non-zero ready times with the goal of minimizing makespan. Non-zero ready times allow for application in a continuous planning environment and will also support the expansion of the current model to a multistage production environment. An integer programming formulation is presented. Several heuristics. including approaches based on MULTI-FIT, genetic algorithms and the travelling salesman problem, are then developed and compared empirically. Seven factors are identified in order to generate problem data, including the number of parallel machines, the average number of jobs per machine, set-up time distribution parameters and processing time distribution parameters. The set-up time matrix can be either symmetric or asymmetric but must satisfy the triangle inequality. A modified insertion heuristic is found to perform best for these types of problems.

Original languageEnglish (US)
Pages (from-to)3747-3769
Number of pages23
JournalInternational Journal of Production Research
Issue number16
StatePublished - Nov 10 2001

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Heuristic scheduling of parallel machines with sequence-dependent set-up times'. Together they form a unique fingerprint.

Cite this