 Multiprocessor Open ShopsWieslaw Kubiak
Chapter Chapter 8 in A Book of Open Shop Scheduling, 2022, pp 193-203 from Springer Abstract: Abstract Two models of open shops with multiprocessors have been evolved: the single-operation machine and multiple-operation machine models. The former replaces a single machine in each stage by parallel machines, typically identical, but limits processing of an operation to machines from one stage. The latter permits processing an operation on a set of machines possibly from different stages. The research has focused mainly on makespan minimization. For the preemptive schedules the makespan minimization is done by a two-phase approach in polynomial time. The first phase optimally allocates operations to machines. The second phase applies algorithms for makespan minimization for preemptive open shops to find optimal schedules for the allocations. The approach gives polynomial-time algorithms for both models. The non-preemptive case is NP-hard in the strong sense. The chapter presents a 2-approximation algorithm for an arbitrary number of machines and reviews approximation schemes for a fixed number of stages for the case. Those approximation algorithms have been obtained for the single-operation machine model. Finally, the chapter reviews applications of multiprocessors to health care and other areas. Date: 2022 There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-030-91025-9_8 Ordering information: This item can be ordered from DOI: 10.1007/978-3-030-91025-9_8 Access Statistics for this chapter More chapters in International Series in Operations Research & Management Science from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.