A Reactive Search-Based Algorithm for Scheduling Multiprocessor Tasks on Two Dedicated Processors

• Autorzy: Aïder Méziane , Baatout Fatma Zohra , Hifi Mhand

Identyfikatory

DOI

10.15439/2020F134

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose a reactive search-based algorithm for solving the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is characterized by a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to determine the scheduling of all tasks minimizing the execution of the last assigned task. The proposed reactive search starts with a starting greedy solution. Next, a series of local operators combined with a tabu list are introduced in order to intensify the search process. The method is also reinforced with a drop and rebuild operator that is applied for diversifying the search process. Finally, the performance of the proposed method is evaluated on a set of benchmark instances, where its provided results are compared to those achieved by a recent method available in the literature. Encouraging results have been reached.

Słowa kluczowe

EN

greedy algorithm; multiprocessing system; search problems

PL

algorytm zachłanny; systemy wieloprocesowe; problemy wyszukiwawcze

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 257--261
• Opis fizyczny: Bibliogr. 11 poz., wz., il., tab.

Twórcy

autor

Aïder Méziane

• LaROMaD, USTHB BP 32 El Alia, 16111 Alger, Algérie

autor

Baatout Fatma Zohra

• LaROMaD, USTHB BP 32 El Alia, 16111 Alger, Algérie

autor

Hifi Mhand

• EPROAD, UPJV 7, rue du Moulin Neuf, 80000 Amiens, France

Bibliografia

• 1. Bianco, L., Blazewicz, J., Dell’Olmo, P. and Drozdowski, M. (1997). ’Preemptive multiprocessor task scheduling with release times and time windows’, Annals of Operations Research,Vol. 70, No. 1, pp.43-55, https://doi.org/10.1023/A:1018994726051.
• 2. Blazewicz, J., Dell’Olmo, P., Drozdowski, M. and Speranza, M.G (1992). ’Scheduling multiprocessor tasks on three dedicated processors’. Information Processing Letters 41 (1992) 275-280, https://doi.org/10.1016/0020-0190(92)90172-R.
• 3. P. Brucker. Scheduling algorithms. Springer, ISBN 978-3-540-20524-1 4th ed. Springer Berlin Heidelberg New York, 2007.
• 4. Buffet. O, Cucu. L, Idoumghar. L and Schott. R. (2010). ’Tabu Search Type Algorithms for the Multiprocessor Scheduling Problem’. Conference: Artificial Intelligence and Applications, https://hal.archives-ouvertes.fr/hal-00435241.
• 5. Graham, R.L., Lower, E.L, Lenstra, J.K., Rinnoy, A.H.G. (1979) ’Optimization and Approximation in Deterministic Sequencing and Scheduling Theory’: A Survey. Annals of Discrete Mathematics.V5, p287-326, https://doi.org/10.1016/S0167-5060(08)70356-X.
• 6. Hifi, M. (2014). An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem. Engineering Optimization. 46(8), 1109–1122, https://doi.org/10.1080/0305215X.2013.819096.
• 7. Hifi M. and Michrafy M. (2006). A reactive local search-based algorithm for the disjunctively constrained knapsack problem. Journal of the Operational Research Society. 57(6), 718-726, https://doi.org/10.1057/palgrave.jors.2602046.
• 8. Hoogeveen, J.A., van de Velde, S.L. and Veltman, B. (1994) ’Complexity of scheduling multiprocessor tasks with prespecified processor allocations’, Discrete Applied Mathematics, Vol. 55, pp.259-272, https://doi.org/10.1016/0166-218X(94)90012-4.
• 9. Kacem, A., Dammak, A. (2014)’A genetic algorithm to minimize the makespan on two dedicated processors’, In IEEE, International Conference on Control, Decision and Information Technologies (CoDIT), pp.400-404, 3-5 Nov. 2014 Metz, France, doi: 10.1109/CoDIT.2014.6996927.
• 10. Manaa, A., Chu, C. (2010) ’Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors’. European Journal of Industrial Engineering, 4(3), https://dx.doi.org/10.1504/EJIE.2010.033331.
• 11. Thesen. A. (1998) ’Design and evaluation of tabu search algorithms for multiprocessor scheduling’. Journal of Heuristics, 4: 141-160, https://doi.org/10.1023/A:1009625629722

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).