Scheduling a Proportionate Flow Shop of Batching Machines

Christoph Hertrich ()
Additional contact information
Christoph Hertrich: Technische Universität Berlin

A chapter in Operations Research Proceedings 2019, 2020, pp 27-33 from Springer

Abstract: Abstract In this paper we investigate the problem to schedule a proportionate flow shop of batching machines (PFB). We consider exact and approximate algorithms for tackling different variants of the problem. Our research is motivated by planning the production process for individualized medicine. Among other results we present the first polynomial time algorithm to schedule a PFB for any fixed number of machines. We also study the online case where each job is unknown until its release date. We show that a simple scheduling rule is two-competitive. For the special case of two machines we propose an algorithm that achieves the best possible competitive ratio, namely the golden section.

Keywords: Proportionate flow shop; Batching machines; Permutation schedules; Dynamic programming; Online algorithms (search for similar items in EconPapers)
Date: 2020
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-48439-2_4

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

DOI: 10.1007/978-3-030-48439-2_4

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 ().