This article is cited in 1 paper

On the complexity of constructing multiprocessor little-preemptive schedules

E. V. Shchepin

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia

Abstract: 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.

UDC: 519.854.1

Received: March 15, 2015

DOI: 10.1134/S0371968515030152

 English version: Proceedings of the Steklov Institute of Mathematics, 2015, 290:1, 166–177

Bibliographic databases:

• 
• 
• 
•