Scheduling a proportionate flow shop of batching machines
- PDF / 563,950 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 46 Downloads / 213 Views
Scheduling a proportionate flow shop of batching machines Christoph Hertrich1,2
· Christian Weiß3
· Heiner Ackermann3
· Sandy Heydrich3 · Sven O. Krumke1
Published online: 17 September 2020 © The Author(s) 2020
Abstract In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number m ≥ 2 of machines. The scheduling problem has so far barely received any attention in the literature, but recently its importance has increased significantly, due to applications in the industrial scaling of modern bio-medicine production processes. We show that for any fixed number of machines, the makespan and the sum of completion times can be minimized in polynomial time. Furthermore, we show that the obtained algorithm can also be used to minimize the weighted total completion time, maximum lateness, total tardiness and (weighted) number of late jobs in polynomial time if all release dates are 0. Previously, polynomial time algorithms have only been known for two machines. Keywords Planning of pharmaceutical production · Proportionate flow shop · Batching machines · Permutation schedules · Dynamic programming
1 Introduction Modern medicine can treat some serious illnesses using individualized drugs, which are produced to order for a specific patient and adapted to work only for that unique patient and nobody else. Manufacturing such a drug often involves a complex production line, consisting of many different steps. If each step of the process is performed manually, by a laboratory worker, then each laboratory worker can only handle materials for one patient at a time. However, in the industrial
B
Christian Weiß [email protected] Christoph Hertrich [email protected] Heiner Ackermann [email protected] Sandy Heydrich [email protected] Sven O. Krumke [email protected]
1
Department of Mathematics, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany
2
Institute of Mathematics, Technische Universität Berlin, 10623 Berlin, Germany
3
Department of Optimization, Fraunhofer Institute for Industrial Mathematics ITWM, 67663 Kaiserslautern, Germany
application which motivates our study, some steps are instead performed by actual machines, like pipetting robots. Such high-end machines can typically handle materials for multiple patients in one go. If scheduled efficiently, this special feature can drastically increase the throughput of the production line. Clearly, in such an environment efficient operative planning is crucial in order to optimize the performance of the manufacturing process and treat as many patients as possible. In this paper, we present – as part of a larger study of an industrial application – new theoretical results for scheduling problems arising from a manufacturing process as described above. Formally, the manufacturing process we consider is structured in a flow shop manner, where each step is handled by a single, dedicated machine. A job J j , j = 1, 2, . . . , n, representing
Data Loading...
