Complexity and approximation results for setup-minimal batch scheduling with deadlines on a single processor
Publication date
2019-08-30
Document type
Konferenzbeitrag
Author
Organisational unit
Universität Siegen
Conference
Annual International Conference of the German Operations Research Society e.V. (OR 2018) ; Brussels, Belgium ; September 12–14, 2018
Publisher
Springer
Series or journal
Operations Research Proceedings
Book title
Operations Research Proceedings 2018
First page
475
Last page
480
Peer-reviewed
✅
Part of the university bibliography
Nein
Language
English
Abstract
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(n log n + nF) algorithm that approximates the cost of an optimal schedule by a factor of F. For details, we refer to our full paper.
Version
Published version
Access right on openHSU
Metadata only access