Multi-Agent systems scheduler in a dynamic environment using a load optimizing strategy

Abstract

The problem of finding an optimal schedule of n jobs to be processed on m machines is classic. In its general form the jobs have several components called operations that can be processed in different ways on the available machines. In this thesis, the jobs are assumed to have only one operation and any job can be processed on any of the available machines. The task is to find an optimal or near optimal assignment of jobs to machines so that the makespan is minimal. The makespan is the total time it takes all the jobs to be processed. The smaller the makespan of a schedule, the better the schedule. This problem has had no satisfactory solution due Lo the huge sizes of the schedule spaces that arise in practical situations and it is also NP-hard. Its solution, however, has relevance in many areas including: job shop scheduling, resource allocation, manufacturing and distributed systems. The problem that is addressed in this thesis is to find a way of guaranteeing generating a good schedule using minimal effort. The effort, here, refers to the number of steps or schedules that must be generated and examined before a good schedule is obtained from a given schedule space. Mathematics, operations research, economics, distributed computing and artificial intelligence are disciplines that have had interests in the solution to the classic scheduling problem. They have approached the problem using gradient-based and search-based techniques. The gradient-based approaches arc rigid and do not scale well for large, real-world scenarios. The sc arch- based methods are not able to cope with the large schedule spaces that arise out of the many real-world situations. This thesis presents an approach that used artificial intelligence. Ideas from game theory and multi-agent systems were used to formulate models in which the behavior of agents generated the schedules [78, 140, 130J. The proposition that guided the inquiry in this work was that some strategic behavior of agents exists that leads to the generation of optimal or near optimal schedules using reasonable effort in XXI u cuncivtc schedule spares. '1 he various existing agent behaviors wereexplored. The random, potential and dispersion strategic behaviors were explored in influencing the actions of agents in selecting the machines. The resulting schedules were evaluated based on the makespan. It was found that none of these strategic behavior of agents could individually guarantee getting a good schedule. Apart from the dispersion strategic behavior, the random and potential strategic behaviors were vulnerable to the size of the schedule space. The dispersion strategic behavior was, however, generating poorer schedules compared to the other strategies. It however, pre-empted the load optimization strategy. It was shown that when the agents act by selecting the machines so that the overall load is minimized, then better schedules were obtained using minimal search effort. This was the load optimization strategy, which was the main contribution in this work. It wras also shown that the load optimization strategy can be used to solve some dynamic and static scheduling problems. The other contributions include demonstrating that the strategic behavior of agents can be used to generate good schedules; opening new directions of research that can be pursued later, and gathering into one place a range of ideas from dynamic computing environments, game theory, multi-agent systems and reinforcement learning, making it easier for future researchers to extend this work. The conclusion is that agent behavior can be used to generate good schedules and the load optimization strategy is the evidence. Future work however can continue wuth exploring the theoretical analytic methods to prove the general cases. Areas for future wrork include: the implementation of the full agent grid or cloud computing model; the exploration of use of the evolutionary game theory to produce optimal or near optimal schedules; conducting further investigation on the games that are suggested for the dynamic computing environments.