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

Yiyo Kuo (), Sheng-I Chen and Yen-Hung Yeh
Additional contact information
Yiyo Kuo: Ming Chi University of Technology
Sheng-I Chen: National Chiao Tung University
Yen-Hung Yeh: Ming Chi University of Technology

Operational Research, 2020, vol. 20, issue 2, No 18, 927-942

Abstract: Abstract 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.

Keywords: Single machine scheduling; Sequence-dependent setup times; Delayed precedence constraints; Variable neighbourhood search (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-017-0349-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:20:y:2020:i:2:d:10.1007_s12351-017-0349-y

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-017-0349-y

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().