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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Gonzalez and S. Sahni, “Open shop scheduling to minimize finish time,” J. Assoc. Comput. Mach. 23, 665–679 (1976).
E. L. Lawler and J. Labetoulle, “On preemptive scheduling of unrelated parallel processors by linear programming,” J. Assoc. Comput. Mach. 25, 612–619 (1978).
E. V. Shchepin and N. Vakhania, “On the geometry, preemptions and complexity of multiprocessor and shop scheduling,” Ann. Oper. Res. 159, 183–213 (2008).
E. V. Shchepin and N. Vakhania, “A note on the proof of the complexity of the little-preemptive open-shop problem,” Ann. Oper. Res. 191, 251–253 (2011).
E. Shchepin and N. Vakhania, “Little-preemptive scheduling on unrelated processors,” J. Math. Model. Algorithms 1, 43–56 (2002).
E. V. Shchepin and N. Vakhania, “Task distributions on multiprocessor systems,” in Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics: Proc. Int. Conf. IFIP TCS 2000, Sendai (Japan), 2000 (Springer, Berlin, 2000)
E. V. Shchepin, Lect. Notes Comput. Sci. 1872, pp. 112–125.
E. V. Shchepin, “On the geometry of multiprocessor distributions,” Tr. Mat. Inst. im. V.A. Steklova, Ross. Akad. Nauk 239, 323–331 (2002)
E. V. Shchepin, Proc. Steklov Inst. Math. 239, 306–314 (2002)].
E. V. Shchepin and N. Vakhania, “An optimal rounding gives a better approximation for scheduling unrelated machines,” Oper. Res. Lett. 33, 127–133 (2005).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © E.V. Shchepin, 2015, published in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2015, Vol. 290, pp. 178–190.
Rights and permissions
About this article
Cite this article
Shchepin, E.V. On the complexity of constructing multiprocessor little-preemptive schedules. Proc. Steklov Inst. Math. 290, 166–177 (2015). https://doi.org/10.1134/S0081543815060152
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0081543815060152