Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

Shih Wei Lin, Zne Jung Lee, Kuo Ching Ying*, Chung-Cheng Lu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.

Original languageEnglish
Pages (from-to)809-815
Number of pages7
JournalComputers and Operations Research
Volume38
Issue number5
DOIs
StatePublished - 1 May 2011

Keywords

  • Iterated greedy heuristic
  • Maximum lateness
  • Parallel machines scheduling problems
  • Sequence-dependent setup times

Fingerprint

Dive into the research topics of 'Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates'. Together they form a unique fingerprint.

Cite this