A new multi-objective genetic algorithm for job shop scheduling with limited resources

The job shop scheduling problem is one of the most frequently analysed problems in classical scheduling theory. Since, generally it is an intractable problem, different ways for solving it are subject of wide interest. This paper presents a new approach to multi-objective job shop scheduling problems based on priority dispatching rules. The objectives considered are to minimise the makespan and to minimise the resource consumption "utilised". The dispatching rules used are some standard dispatching rules related to makespan minimisation. A multi-objeclive genetic algorithm based on a chromosome that is divided into two components is developed. The first component uses the Giffler and Thompson algorithm to determine scheduling coefficients (weights) assigned to each of the dispatching rules for the makespan objective in order to determine the job shop schedule. The second component represents proportions of the resources that are assigned to each operation that need resources. The genetic algorithm's fitness function is defined as the two objectives linearly combined into one objective. The results obtained are encouraging and demonstrate that this approach is useful when the operations performed on different machines require different and limited resources.