Volltext-Downloads (blau) und Frontdoor-Views (grau)

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

  • We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an O(nlogn+nF) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Dominik KressORCiD, Maksim Barketau, Erwin PeschORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):Journal of Scheduling
Year of Completion:2018
First Page:595
Last Page:606
Content Focus:Academic Audience
Peer Reviewed:Yes
Rankings:AJG Ranking / 3
VHB Ranking / B
SJR Ranking / Q1
Licence (German):License LogoUrheberrechtlich gesch├╝tzt