Minimizing the makespan on a single machine subject to modular setups

Dirk Briskorn (), Konrad Stephan () and Nils Boysen ()
Additional contact information
Dirk Briskorn: Bergische Universität Wuppertal, Professur für BWL, insbesondere Produktion und Logistik
Konrad Stephan: Friedrich-Schiller-Universität Jena, Lehrstuhl für Operations Management
Nils Boysen: Friedrich-Schiller-Universität Jena, Lehrstuhl für Operations Management

Journal of Scheduling, 2022, vol. 25, issue 1, No 7, 125-137

Abstract: Abstract Single machine scheduling with sequence-dependent setup times is one of the classical problems of production planning with widespread applications in many industries. Solving this problem under the min-makespan objective is well known to be strongly NP-hard. We consider a special case of the problem arising from products having a modular design. This means that product characteristics, (mass-)customizable by customers, are realized by separate components that can freely be combined. If consecutive products differ by a component, then a setup is necessary. This results in a specially structured setup matrix that depends on the similarities of product characteristics. We differentiate alternative problem cases where, for instance, the setup operations for multiple components either have to be executed sequentially or are allowed to be conducted in parallel. We analyze the computational complexity of various problem settings. Our findings reveal some special cases that are solvable in polynomial time, whereas most problem settings are shown to remain strongly NP-hard.

Keywords: Scheduling; Modular products; Sequence-dependent setups; Complexity (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00704-8 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:jsched:v:25:y:2022:i:1:d:10.1007_s10951-021-00704-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00704-8

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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