Art der Publikation: Beitrag in Sammelwerk

Complexity and Approximation Results for Setup-Minimal Batch Scheduling with Deadlines on a Single Processor

Autor(en):

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

Herausgeber:

Fortz, B.; Labbé, M.

Titel des Sammelbands:

Operations Research Proceedings 2018

Seiten:

475-480

Verlag:

Springer

Ort(e):

Cham

Veröffentlichung:

2019

ISBN:

978-3-030-18499-5

Sprache:

Englisch

Schlagworte:

Batch scheduling, Setup cost, Approximation algorithm

Digital Object Identifier (DOI):

doi:10.1007/978-3-030-18500-8_59

Zitation:

Download BibTeX

Kurzfassung

We address the problem of sequencing n jobs that are partitioned into F families on a single processor. A setup operation is needed at the beginning of the schedule and whenever a job of one family is succeeded by a job of another family. These setup operations are assumed to not require time but are associated with a fixed setup cost which is identical for all setup operations. Jobs must be completed no later than by a given deadline. The objective is to schedule all jobs such that the total setup cost is minimized. This objective is identical to minimizing the number of setup operations. We provide a sketch of the proof of the problem’s strong NP-hardness as well as some 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. For details, we refer to our full paper.