Single machine scheduling with sequence-dependent setup times and delayed precedence constraints

Yiyo Kuo*, Sheng-I Chen, Yen Hung Yeh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


This research deals with the single machine scheduling problem of minimizing the makespan with sequence dependent setup times and delayed precedence constraints. A makespan calculation model is first proposed. When given a feasible job sequence, the proposed model can calculate the makespan. Then a variable neighbourhood search (VNS) with four phases is proposed for optimizing the job sequence. The proposed VNS adopts five operations to search for new solutions, and modifies all solutions to satisfy precedence constraints. The proposed VNS will accept a worse solution over a better solution with a certain probability, in order to escape from a local optimum. The experimental results show that the proposed VNS provides the best results with less than 10 s of computation time. Therefore it is efficient and effective in solving the single machine scheduling problems.

Original languageEnglish
Pages (from-to)1-16
Number of pages16
JournalOperational Research
StateAccepted/In press - 21 Sep 2017


  • Delayed precedence constraints
  • Sequence-dependent setup times
  • Single machine scheduling
  • Variable neighbourhood search

Fingerprint Dive into the research topics of 'Single machine scheduling with sequence-dependent setup times and delayed precedence constraints'. Together they form a unique fingerprint.

Cite this