Searching for Optimal Schedule for Parallel Machines Using an Agent-based Technique

Abstract

In this paper the scheduling of n independent jobs on m non-identical machines is considered for a large concrete schedule space for 30 jobs and 6 machines. The schedule space is about 1023 which is large enough to render exhaustive systematic search for the optimal schedule limited. The schedules are generated by agents that represent the jobs as they randomly select the machines on which the jobs should be processed. The schedules that are generated are evaluated using the makespan which is the total time taken for all the jobs to be processed. The optimal schedule, which is also the best schedule, is the one with the minimum or least makespan for any given set of job and machine properties. It is shown that the empirical best schedules that are generated are optimal when the job and machine properties are held to some uniform constant values. It is also shown that even when the job and machine properties are not uniform the empirical best schedules closely approximate the optimal schedules. This makes the agent-based approach to optimal schedule generation viable.