Learning-based approach for multiprocessor scheduling under timing constraints and N-Queens problems
Yacine Laalaoui, Habiba Drias · International Journal of Advanced Operations Management · 2009
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.