|
Diskretnyi Analiz i Issledovanie Operatsii, 2013, Volume 20, Issue 4, Pages 3–14
(Mi da735)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
The complexity of cyclic scheduling for identical jobs
E. A. Bobrovaa, A. A. Romanovabc, V. V. Servakhab a 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.
Received: 21.11.2012 Revised: 03.04.2013
Citation:
E. A. Bobrova, A. A. Romanova, V. V. Servakh, “The complexity of cyclic scheduling for identical jobs”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 3–14
Linking options:
https://www.mathnet.ru/eng/da735 https://www.mathnet.ru/eng/da/v20/i4/p3
|
Statistics & downloads: |
Abstract page: | 301 | Full-text PDF : | 77 | References: | 41 | First page: | 4 |
|