A note on hardness of multiprocessor scheduling with scheduling solution space tree

• Autorzy: Dwibedy Debasis , Mohanty Rakesh

Identyfikatory

DOI

10.7494/csci.2023.24.1.4656

• Języki publikacji: EN

Abstrakty

EN

We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.

Słowa kluczowe

EN

combinatorial structures; computational complexity; hardness; makespan; multiprocessor scheduling; multiuser; NP-completeness; nondeterministic algorithms; reduction; scheduling solution space tree

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2023
• Tom: T. 24 (1)
• Strony: 53--74
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Dwibedy Debasis

• Veer Surendra Sai University of Technology, Burla, Odisha, India

autor

Mohanty Rakesh

• Veer Surendra Sai University of Technology, Burla, Odisha, India

Bibliografia

• [1] Aaronson S.: P ?= N P. In: J. Nash, Jr., M. Rassias (eds.), Open Problems in Mathematics, pp. 1–122, Springer, Cham, 2016.
• [2] Aho A.V., Hopcroft J.E., Ullman J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
• [3] Ambuhl C., Mastrolilli M., Mutsanas M., Svensson O.: On the Approximability of Single-Machine Scheduling with Precedence Constraints, Mathematics of Operations Research, pp. 653–669, 2011.
• [4] Bellenguez-Morineau O., Chrobak M., D¨urr C., Prot D.: A note on NP-Hardness of preemptive mean flow-time scheduling for parallel machines, Journal of Scheduling, vol. 18, pp. 299–304, 2015.
• [5] Bevern van R., Bredereck R., Bulteau L., Komusiewicz C., Talmon N., Woeginger G.J.: Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width. In: Discrete Optimization and Operations Research. 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016, Proceedings, pp. 105–120, 2016.
• [6] Blazewicz J., Ecker K., Kis T., Tanas M.: A note on the complexity of scheduling coupled tasks on a single processor, Journal of Brazilian Computer Society, pp. 23–26, 2001.
• [7] Bodlaender H.L., Fellows M.R.: W[2]-hardness of precedence constrained Kprocessor scheduling, Operations Research Letters, vol. 18, pp. 93–97, 1995.
• [8] Bruno J., Coffman E.G., Sethi R.: Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, pp. 382–387, 1974.
• [9] Cook S.A.: The complexity of theorem-proving procedures. In: STOC’71: Proceedings of the third annual ACM symposium on Theory of computing, pp. 151–158, 1971.
• [10] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, MIT Press, 3rd ed., 2009.
• [11] Davies S., Kulkarni J., Rothvoss T., Sandeep S., Tarnawski J., Zhang Y.: On the Hardness of Scheduling With Non-Uniform Communication Delays, CoRR abs/210901064, 2021.
• [12] Garey M.R., Johnson D.S.: Complexity results for multiprocessors scheduling under resource constraints. In: Proceedings of the 8th Annual Princeton Conference on Information Sciences and Systems, pp. 384–393, 1974.
• [13] Garey M.R., Johnson D.S.: Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman & Co., New York, USA, 2nd ed., 1990.
• [14] Garg N., Kumar A., Pandit V.: Order scheduling models: Hardness and algorithms. In: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science. 27th International Conference, New Delhi, India, December 12–14, 2007, Proceedings, pp. 96–107, 2007.
• [15] Goldwasser S., Micali S., Rackoff C.: The knowledge complexity of interactive proof systems, SIAM Journal of Computing, pp. 186–208, 1989.
• [16] Horowitz E., Sahni S., Anderson-Freed S.: Fundamentals of Data Structures in C, Universities Press, 2nd ed., 2008.
• [17] Karp R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations. Proceedings of a symposium on the Complexity of Computer Computations, held March 2022, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, Department of Computer Science, University of Califormia at Berkeley, 1972.
• [18] Lenstra J.K., Rinnooy Kan A.H.G., Brucker P.: Complexity of machine scheduling problems, Annals of Discrete Mathematics, vol. 1, pp. 343–362, 1977.
• [19] McNaughton R.: Scheduling with deadlines and loss functions, Management Science, vol. 6, pp. 1–12, 1959.
• [20] Mnich M., Wiese A.: Scheduling and fixed-parameter tractability, Mathematical Programming, vol. 154, pp. 533–562, 2015.
• [21] Saule E., Trystram D.: Multi-users scheduling in parallel systems. In: 2009 IEEE International Symposium on Parallel & Distributed Processing, pp. 1–9, Washington DC, USA, 2009.
• [22] Svensson O.: Hardness of precedence constrained scheduling on identical machines, SIAM Journal of Computing, vol. 40, pp. 1258–1274, 2011.
• [23] Ullman J.D.: N P-Complete Scheduling Problems, Journal of Computer and System Sciences, vol. 10, pp. 384–393, 1975.
• [24] Zhang A., Chen Y., Chen L., Chen G.: On the NP-hardness of scheduling with time restrictions, Discrete Optimization, pp. 54–62, 2018.

Uwagi

PL

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).