A boundle of on-line algorithms for scheduling computational tasks

• Autorzy: Dorota Dariusz , Smutnicki Czeslaw

Identyfikatory

DOI

10.24425/ijet.2025.153585

• Języki publikacji: EN

Abstrakty

EN

We deal with the problem of scheduling the set of computational tasks on parallel identical processors. Each task needs a predefined number of processors to perform. The problem is known in scheduling theory and has been considered up to now by a few authors. Starting from the formal original description of the problem, we provide a mathematical model and then propose, at first, the solution method in the deterministic case. In fact, the paper focuses chiefly on the non-deterministic variant of the problem. We have proposed several online algorithms for this case. These algorithms are evaluated through competitive analysis and experiments. The practical application of the problem can be found in embedded systems with increased dependability obtained through hardware and software redundancy.

Słowa kluczowe

EN

Multiprocessor tasks; online scheduling

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 2
• Strony: 397--402
• Opis fizyczny: Bibliogr. 28 poz., rys., tab.

Twórcy

autor

Dorota Dariusz

• Cracow University of Technology, Poland

autor

Smutnicki Czeslaw

• Wrocław University of Science and Technology, Poland

Bibliografia

• [1] S. Albers, “Online Scheduling. Introduction to scheduling”, CRC Press, 2009.
• [2] J. Błażewicz et al. “Handbook on scheduling: from theory to applications”, Springer Science & Business Media, 2007.
• [3] J. Błażewicz and Z. Liu, “Scheduling multiprocessor tasks with chain constraints”, European Journal of Operational Research, 94(2), 231-241, 1996.
• [4] W. Bożejko and E. Gawlińska, “Algorytmy szeregowania online”. In: W. Bożejko and J. Pempera (eds.): “Optymalizacja dyskretna w informatyce, automatyce i robotyce” (Polish) Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław, 2012.
• [5] B. Chen, A. Van Vliet and G. J. Woeginger, “An optimal algorithm for preemptive on-line scheduling” Second Annual European Symposium on Algorithms, Utrecht, The Netherlands, September 26-28, 1994, Proceedings 2. Springer Berlin Heidelberg, 1994.
• [6] X. Chen, “ Selected problems of online scheduling on parallel machines”, PhD dissertation, Politechnika Poznańska, Poznań, 2014.
• [7] R. Davis and A. Burns, “A survey of hard real-time scheduling for multiprocessor systems”, ACM Computing Surveys (CSUR), 43(4), 1-44, New York, NY, USA, 2011.
• [8] D. Dorota, “Scheduling Tasks in a System with a Higher Level of Dependability”. In: International Conference on Dependability and Complex Systems. Springer, Cham, 2019.
• [9] D. Dorota, “Scheduling tasks with uncertain times of duration”. In: International Conference on Dependability and Complex Systems. Springer, Cham, 2020.
• [10] D. Dorota and C. Smutnicki, “ On-line scheduling multiprocessor tasks in the non-predictive environment”, LNCS, 2024.
• [11] D. Dorota, “Szeregowanie zada´n wieloprocesorowych w warunkach niepewności”, Ph. Thesis (Polish), Politechnika Wrocławska, 2023.
• [12] M. Drozdowski, “Scheduling for parallel processing”, Springer, London, 2009.
• [13] M. Drozdowski, “Scheduling multiprocessor tasks - an overview”, European Journal of Operational Research 94(2), 215-230, 1996.
• [14] R. Fleischer and M. Wahl, “Online scheduling revisited”. European Symposium on Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000.
• [15] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics 5, 287-326, 1979.
• [16] R. Graham, “Bounds for certain multiprocessing anomalies”, Bell System Technical Journal, 45, 1563-1581, Wiley Online Library, 1966.
• [17] W. Herroelen, B. De Reyck and E. Demeulemeester, “Resource-constrained project scheduling: A survey of recent developments”, Computers & Operations Research 25.4, 279-302, 1998.
• [18] J. Hurink and J. Paulus, “Online algorithm for parallel job scheduling and strip packing”, International Workshop on Approximation and Online Algorithms, Springer, 2007.
• [19] S. Im, “Online scheduling algorithms for average flow time and its variants”, University of Illinois at Urbana-Champaign, 2012.
• [20] B. Johannes, “Scheduling parallel jobs to minimize the makespan”, Journal of Scheduling 9, 433-452, 2006.
• [21] R. M. Karp, “On-Line Algorithms Versus Off-Line Algorithms: How Much, Algorithms, Software, Architecture”, Information Processing 92: Proceedings of the IFIP 12th World Computer Congress, Madrid, Spain, 7-11 September 1992.
• [22] M. Makuchowski, “Problemy gniazdowe z operacjami wielomaszynowymi. Własno´sci i algorytmy”, PhD thesis. (Polish) Raporty Instytutu Cybernetyki Technicznej PWr. 2004, Ser. PRE; nr 37. 196 s.
• [23] R. McNaughton, “Scheduling with deadlines and loss functions”, Management Science, INFORMS, 1959.
• [24] R. R. Muntz and E. G. Jr Cofmann, “Preemptive scheduling of real-time tasks on multiprocessors systems”, Journal of the ACM, 17(2), 324-338, 1970.
• [25] M. Pinedo, “Scheduling”, Springer, New York, NY, 2015.
• [26] K. Pruhs, S. Jiri and E. Torng, “Online scheduling”, 2004.
• [27] C. Smutnicki, “Algorytmy szeregowania zadań” (Polish), Oficyna Wydawnicza Politechniki Wrocławskiej, 2012.
• [28] D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization”, IEEE Transactions on Evolutionary Computation, 1(1), 67-82, 1997.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).