Geodesic
On the complexity of constructing multiprocessor little-preemptive schedules
Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics, Tome 290 (2015), pp. 178-190.

Voir la notice de l'article provenant de la source Math-Net.Ru

We present a full and correct proof of the fact that the problem of constructing an optimal schedule for the open shop problem with at most $m-3$ preemptions for an $m$‑processor system is NP-hard. We also show that the proof of this result given by E. Shchepin and N. Vakhania in Ann. Oper. Res. 159, 183–213 (2008) is incorrect. 
@article{TRSPY_2015_290_a14,
     author = {E. V. Shchepin},
     title = {On the complexity of constructing multiprocessor little-preemptive schedules},
     journal = {Informatics and Automation},
     pages = {178--190},
     publisher = {mathdoc},
     volume = {290},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a14/}
}
TY  - JOUR
AU  - E. V. Shchepin
TI  - On the complexity of constructing multiprocessor little-preemptive schedules
JO  - Informatics and Automation
PY  - 2015
SP  - 178
EP  - 190
VL  - 290
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a14/
LA  - ru
ID  - TRSPY_2015_290_a14
ER  - 
%0 Journal Article
%A E. V. Shchepin
%T On the complexity of constructing multiprocessor little-preemptive schedules
%J Informatics and Automation
%D 2015
%P 178-190
%V 290
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a14/
%G ru
%F TRSPY_2015_290_a14
E. V. Shchepin. On the complexity of constructing multiprocessor little-preemptive schedules. Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics, Tome 290 (2015), pp. 178-190. http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a14/

[1] Gonzalez T., Sahni S., “Open shop scheduling to minimize finish time”, J. Assoc. Comput. Mach., 23 (1976), 665–679 | DOI | MR | Zbl

[2] Lawler E.L., Labetoulle J., “On preemptive scheduling of unrelated parallel processors by linear programming”, J. Assoc. Comput. Mach., 25 (1978), 612–619 | DOI | MR | Zbl

[3] Shchepin E.V., Vakhania N., “On the geometry, preemptions and complexity of multiprocessor and shop scheduling”, Ann. Oper. Res., 159 (2008), 183–213 | DOI | MR | Zbl

[4] Shchepin E.V., Vakhania N., “A note on the proof of the complexity of the little-preemptive open-shop problem”, Ann. Oper. Res., 191 (2011), 251–253 | DOI | MR | Zbl

[5] Shchepin E., Vakhania N., “Little-preemptive scheduling on unrelated processors”, J. Math. Model. Algorithms, 1 (2002), 43–56 | DOI | MR | Zbl

[6] Shchepin E.V., Vakhania N., “Task distributions on multiprocessor systems”, Theoretical computer science: Exploring new frontiers of theoretical informatics, Proc. Int. Conf. IFIP TCS 2000, Sendai (Japan), 2000, Lect. Notes Comput. Sci., 1872, Springer, Berlin, 2000, 112–125 | DOI | Zbl

[7] Schepin E.V., “K geometrii mnogoprotsessornykh raspredelenii”, Tr. MIAN, 239 (2002), 323–331

[8] Shchepin E.V., Vakhania N., “An optimal rounding gives a better approximation for scheduling unrelated machines”, Oper. Res. Lett., 33 (2005), 127–133 | DOI | MR | Zbl