Randomized reinforcement based scheduling in parallel processor systems

Task scheduling is important for the proper functioning of parallel processor systems. The static scheduling of tasks onto networks of parallel processors is well defined and documented in the literature. However, in many practical situations, a priori information about the tasks that need to be scheduled is not available. In such situations tasks usually arrive dynamically and the scheduling should be performed online or “on the fly”. We present a framework based on stochastic reinforcement learning which is usually used to solve optimization problems in a simple and efficient way. The use of reinforcement learning reduces the dynamic scheduling problem to that of learning a stochastic approximation of an unknown average error surface. The learning system develops an association between the best action (schedule) and the current state of the environment (parallel system)