Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support

摘要

The paper presents cellular automata (CA)-based multiprocessor scheduling system, in which an extraction of knowledge about scheduling process occurs and this knowledge is used while solving new instances of the scheduling problem. There are three modes of the scheduler: learning, normal operating, and reusing. In the learning mode, a genetic algorithm is used to discover CA rules suitable for solving instances of a scheduling problem. In the normal operating mode, discovered rules are able to find automatically, without a calculation of a cost function, an optimal or suboptimal solution of the scheduling problem for any initial allocation of program tasks in a multiprocessor system. In the third mode, previously discovered rules are reused with support of an artificial immune system (AIS) to solve new instances of the problem. We present a number of experimental results showing the performance of the CA-based scheduler.