The cyclic compact open-shop scheduling problem

DOI10.1016/0012-365X(93)90171-OMaRDI QIDQ686491zbMATH OpenOpenAlexFDO

Authors N. V. R. Mahadev, Ph. Solot, Dominique De Werra

Publication date 27 October 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90171-o

zbMATH Keywords

automated production systemscyclic schedulescylindrical schedulinggraph-theoretic modelnonpreemptive open shop scheduling

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35)

Review text

We consider a variation of the classical nonpreemptive open shop scheduling problem. For the normal open shop, finding whether a schedule exists in \(T\) time units is NP-complete. The main difference with the classical model is that we consider so- called periodical or cyclic schedules; this means that the schedule obtained is repeated periodically. If the length of a period is \(k\) time units, then a job which is on a processor during the first \(p\) time units of a period and the last \(q\) time units of a period is considered as being processed without preemptions on that processor during \(q+ p\) consecutive time units. Such scheduling problems are sometimes called cylindrical (instead of cyclic); this name stems frm the fact that we take the processor schedules (and the job schedules) for one period and make a cylinder by gluing together the \(t= 0\) and \(t= k\) axes. Cyclic problems occur more and more frequently in automated production systems; some types of cyclic problems are discussed. Another difference from the classical models is that we consider compact schedules only. In a cyclic schedule, this means that if we consider the cylinder representing the job (processor) schedules in each period, each job (processor) at most one idle time interval on the cylinder. We give a complete formulation of the cyclic compact open shop scheduling problem and derive a graph-theoretic model. A characterization in terms of graphs is given for problems which have cyclic schedules with some additional requirements.

Recommendations

• Open shop cyclic scheduling
• Chromatic scheduling in a cyclic open shop
• Scheduling Periodic Jobs Compactly Within A Fixed Time Period In Open Shops
• Compact Cylindrical Chromatic Scheduling
• Open shop scheduling with synchronization

Cites work

• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• On cyclic sequence types for constructing cyclic schedules
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited in

(13)

• The combinatorics of timetabling
• Open shop scheduling with synchronization
• Open shop cyclic scheduling
• Chromatic scheduling in a cyclic open shop
• Open shop scheduling with some additional constraints
• Cyclic flow-shop scheduling with no-wait constraints and missing operations
• Efficient scheduling of periodic information monitoring requests
• Applying circular coloring to open shop scheduling
• Compact Cylindrical Chromatic Scheduling
• Scheduling Periodic Jobs Compactly Within A Fixed Time Period In Open Shops
• scientific article; zbMATH DE number 7141490 (Why is no real title available?)
• Compact Scheduling In Open Shop With Zero-One Time Operations
• NP-hardness of compact scheduling in simplified open and flow shops.

This page was built for publication: The cyclic compact open-shop scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686491)