Learning and backtracking in non-preemptive scheduling of tasks under timing constraints

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.