Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/312241 
Erscheinungsjahr: 
2022
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 25 [Issue:] 6 [Publisher:] Springer US [Place:] New York, NY [Year:] 2022 [Pages:] 643-657
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing processes of individualized medicaments, which are used in modern medicine to treat some serious illnesses. We provide two different online algorithms, proving also lower bounds for the offline problem to compute their competitive ratios. The first algorithm is an easy-to-implement, general local scheduling heuristic. It is 2-competitive for PFFBs with an arbitrary number of stages and for several natural scheduling objectives. We also show that for total/average flow time, no deterministic algorithm with better competitive ratio exists. For the special case with two stages and the makespan or total completion time objective, we describe an improved algorithm that achieves the best possible competitive ratio φ=1+52, the golden ratio. All our results also hold for proportionate (non-flexible) flow shops of batching machines (PFB) for which this is also the first paper to study online algorithms.
Schlagwörter: 
Planning of pharmaceutical production
Proportionate flow shop
Flexible flow shop
Batching machines
Online algorithms
Competitive analysis
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.