This article is cited in 2 papers

The complexity of cyclic scheduling for identical jobs

E. A. Bobrova^a, A. A. Romanova^bc, V. V. Servakh<sup>ab

a</sup> Omsk Branch of Sobolev Institute Mathematics of SB RAS, 13 Pevtsov St., 644099 Omsk, Russia
^b Dostoyevsky Omsk State University, 55a Mir Ave., 644077 Omsk, Russia
^c Omsk Law Aсademy, 12 Korolenko St., 644010 Omsk, Russia

Abstract: We consider the Cyclic Job Shop Problem for identical jobs with the criterion for cycle time minimization when the number of simultaneously processed tasks during the cycle time is limited by a constant $H$. We prove that this problem is NP-hard in the case $H\ge4$. For the case $H=2$, we propose an exact polynomial algorithm. Ill. 7, bibliogr. 16.

Keywords: identical tasks, cyclic scheduling.

UDC: 519.854

Received: 21.11.2012
Revised: 03.04.2013

Bibliographic databases:

•