Type of Publication: Article in Journal

Single-Machine Batch Scheduling to Minimize the Total Setup Cost in the Presence of Deadlines

Author(s):

Kress, D.; Barketau, M.; Pesch, E.

Title of Journal:

Journal of Scheduling

Volume (Publication Date):

21 (2018)

Number of Issue:

6

pages:

595-606

Language:

Englisch

Keywords:

Batch scheduling, Job families, Setup cost, Strong NP-hardness, Approximation algorithm, EDD-schedule, GT-schedule

Digital Object Identifier (DOI):

doi:10.1007/s10951-018-0561-5

Fulltext:

Single-Machine Batch Scheduling to Minimize the Total Setup Cost in the Presence of Deadlines (172 KB)

Citation:

Download BibTeX

Abstract

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)O(nlog⁡n+nF) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.