Solving unrestricted parallel machine scheduling problems via evolutionary algorithms

Abstract

Parallel machine scheduling, also known as parallel task scheduling, involves the assignment of multiple tasks onto the system architecture’s processing components (a bank of machines in parallel). A basic model involving m machines and n independent jobs is the foundation of more complex models. Here, the jobs are allocated according to resource availability following some allocation rule. The completion time of the last job to leave the system, known as the makespan (Cmax), is one of the most important objective functions to be minimized, because it usually implies high utilization of resources, but other important objectives must be also considered. These problems are known in the literature [9, 11] as unrestricted parallel machine scheduling problems. Many of these problems are NP-hard for 2≤ m ≤ n, and conventional heuristics and evolutionary algorithms (EAs) have been developed to provide acceptable schedules as solutions. This presentation shows the problem of allocating a number of non-identical independent tasks in a production system. The model assumes that the system consists of a number of identical machines and only one task may execute on a machine at a time. All schedules and tasks are non-preemptive. A set of well-known conventional heuristics will be contrasted with evolutionary approaches using multiple recombination and indirect representations.