Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

F Jin (), J N D Gupta, S Song () and Chin-Chia Wu
Additional contact information
F Jin: IBM China Research Lab
J N D Gupta: University of Alabama in Huntsville
S Song: Tsinghua University

Journal of the Operational Research Society, 2010, vol. 61, issue 7, 1181-1189

Abstract: Abstract Motivated by a real-life scheduling problem in a steel wire factory in China, this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood) properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search. Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.

Keywords: single machine; sequence-dependent family setup times; maximum lateness or tardiness; structural properties; tabu search; empirical results (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1057/jors.2009.63 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:61:y:2010:i:7:d:10.1057_jors.2009.63

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2009.63

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().