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

Dominik Kress (), Maksim Barketau (), Erwin Pesch () and David Müller ()
Additional contact information
Dominik Kress: University of Siegen
Maksim Barketau: NAS of Belarus
Erwin Pesch: University of Siegen
David Müller: University of Siegen

A chapter in Operations Research Proceedings 2018, 2019, pp 475-480 from Springer

Abstract: 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 + n F ) $$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.

Keywords: Batch scheduling; Setup cost; Approximation algorithm (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-030-18500-8_59

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

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

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().