Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F134

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 257–261 (2020)

Full text

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

References

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