𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of cyclic scheduling problems: A state-of-the-art survey

✍ Scribed by Eugene Levner; Vladimir Kats; David Alcaide López de Pablo; T.C.E. Cheng

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
325 KB
Volume
59
Category
Article
ISSN
0360-8352

No coin nor oath required. For personal study only.

✦ Synopsis

a b s t r a c t

In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells.

📜 SIMILAR VOLUMES

The complexity of cyclic shop scheduling
The complexity of cyclic shop scheduling problems
✍ Nicholas G. Hall; Tae-Eog Lee; Marc E. Posner 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 190 KB

We consider scheduling problems for shops in which a job set is manufactured repetitively. Jobs are scheduled to minimize the cycle time of the job set, which is equivalent to maximizing the throughput rate. We characterize the complexity of the scheduling problem for several types of job shops. Pol

The complexity of two group scheduling p
The complexity of two group scheduling problems
✍ Jacek Blazewicz; Mikhail Y. Kovalyov 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 94 KB

The problems of scheduling groups of jobs under the group technology assumption are studied. The two remaining open questions posed in the literature a decade ago about the computational complexity of these problems (J. Oper. Res. Soc., 1992; 43:395 -406), are answered. The parallel machine problem