 Compact Scheduling of Open ShopsWieslaw Kubiak
Chapter Chapter 9 in A Book of Open Shop Scheduling, 2022, pp 205-232 from Springer Abstract: Abstract This chapter concentrates on compact and cyclic compact open shop scheduling. Compact scheduling is motivated by timetabling and cyclic compact scheduling by just-in-time systems. A compact schedule requires each job to be processed in a no-wait fashion and each machine to process operations without idle time. Compact schedules do not always exist. The chapter presents smallest instances for which compact schedules do not exist and tests to determine whether compact schedules exist for a given degree Δ. Such tests run in polynomial time for open shop instances with Δ ≤ 4 but become NP-complete for Δ = 5. The minimization of makespan over all compact schedules has polynomial-time solution only for Δ ≤ 3, and it is open even for (3, 4)-biregular open shops where every job has length equal 3 and each machine workload equal 4. Deficiency has been proposed as a measure of deviation from compactness. However, the problem of minimizing deficiency is not only NP-hard in the strong sense but also the existing integer programming (IP) and constraint programming (CP) models can hardly solve problems of size n + m = 10 in reasonable time. 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_9 Ordering information: This item can be ordered from DOI: 10.1007/978-3-030-91025-9_9 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.