The cyclic compact open-shop scheduling problem
type: Item
instance of: scholarly article
title: The cyclic compact open-shop scheduling problem
zbMATH Open document ID: 0797.90045
DOI: 10.1016/0012-365X(93)90171-O
author: N. V. R. Mahadev
author: Ph. Solot
author: Dominique De Werra
published in: Discrete Mathematics
publication date: 1994-10-27T00:00:00Z
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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 428329
zbMATH Keywords: cylindrical scheduling
zbMATH Keywords: nonpreemptive open shop scheduling
zbMATH Keywords: automated production systems
zbMATH Keywords: graph-theoretic model
zbMATH Keywords: cyclic schedules
MaRDI profile type: Publication
cites work: Q5615282
cites work: Q3821925
cites work: On cyclic sequence types for constructing cyclic schedules
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: On the Flow-Shop Sequencing Problem with No Wait in Process†
full work available at URL: 0012-365x(93)90171-o
OpenAlex ID: W1971413514
description: scientific article; zbMATH DE number 428329