EN|RU

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 1
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

 © Sobolev Institute of Mathematics, 2015