Volume 20, No 4, 2013, P. 3-14

UDC 519.854
Bobrova E. A., Romanova A. A., Servakh V. V. 
The complexity of cyclic scheduling for identical jobs

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 ≥ 4. For the case H = 2, we propose an exact polynomial algorithm.
Ill. 7, bibliogr. 16.

Keywords: identical tasks, cyclic scheduling.

Bobrova Ekaterina Alexandrovna ¹
Romanova Anna Anatol’evna ^2,3
Servakh Vladimir Vicent’evich ^1,3
1. Omsk Branch of Sobolev Institute Mathematics of SB RAS,
13 Pevtsov St., 644099 Omsk, Russia
2. Omsk Law Aсademy,
12 Korolenko St., 644010 Omsk, Russia
3. Dostoyevsky Omsk State University,
55a Mir Ave., 644077 Omsk, Russia
e-mail: eabobrova88@gmail.com, anuta81@bk.ru, svv_usa@rambler.ru