Learning and backtracking in non-preemptive scheduling of tasks under timing constraintsSpecial issue on machine learning and cybernetics

We propose two novel heuristic search techniques to address the problem of scheduling tasks under hard timing constraints on a single processor architecture. The underlying problem is NP-hard in the strong sense and it is a fundamental challenge in feedback-control theory and automated cybernetics. The proposed techniques are a learning-based approaches and they take much less memory space. A partial feasible schedule is maintained and extended over a repeated problem solving trials, previously assigned priorities are refined according to the gained information about the problem to lead the convergence to a complete feasible schedule if one exists. First, we present the learning in hard-real-time with single learning (LHRTS-SL) algorithm where a single learning function is utilized, then we discuss its drawback and we propose the LHRTS with double learning algorithm in which a second learning function is integrated to cope up with LHRTS-SL drawback. Experimental results show the efficiency of the proposed techniques in terms of success ratio when used to schedule randomly generated problem instances.