Title: Learning-based approach for multiprocessor scheduling under timing constraints and N-Queens problems

Authors: Yacine Laalaoui, Habiba Drias

Addresses: Department of Postgraduate Studies, National Computer Science School, 16000 Oued-Smar, Algiers, Algeria. ' LRIA Laboratory, Faculty of Computer Science, USTHB University, 16111, El-Alia, Banezzouar, Algiers, Algeria

Abstract: This paper presents a learning-based algorithm to address the deadline scheduling problem. This problem consists of searching for feasible schedules of n tasks on m identical processors under hard-real-time constraints. Unlike existing works, the proposed algorithm is time limited rather than time and space limited since the problem under study is NP-hard. Two learning functions are integrated to direct the search toward possible feasible schedules. Experimental results show a significant success ratio improvement of the proposed scheduling algorithm compared to plain heuristics and metaheuristics namely ACO. We propose a new look for N-Queens problem as deadline scheduling and we show how our algorithm can deal with the N-Queens problem and its possible applicability to cope with CSP problems.

Keywords: learning; timing constraints; multiprocessor scheduling; multiprocessor systems; N-Queens.

DOI: 10.1504/IJAOM.2009.031246

International Journal of Advanced Operations Management, 2009 Vol.1 No.4, pp.290 - 311

Published online: 27 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article