A genetic algorithm to minimise the maximum lateness on a single machine family scheduling problem

Machines Scheduling Problems are one of the classical combinatorial optimization problems which exist in many diverse areas such as transportation, manufacturing system, etc. The main focus is on the efficient allocation of one or more resources to activities over time. In this paper, we consider a Single Machine Family Scheduling Problem where jobs are partitioned into families and setup time is required between these families. Setup includes obtaining tool, positioning work in process, cleanup, etc. In most scheduling research work, the setup time has been considered as either negligible and hence ignored, or considered as part of the processing time. While these assumptions simplify the problem, they adversely affect the solution quality for many applications which require explicit treatment of setup. In this study, we propose an Optimised Crossover Genetic Algorithm (OCGA) for the problem. The objective is to find a schedule which minimises the maximum lateness of the jobs in the presence of the sequence independent family setup times.In brief, the proposed OCGA uses binary representation to encode the problem. During crossover, the OCGA selects two parents from the population and replaces them with two children by an optimized crossover mechanism which designed using an undirected bipartite graph. Various techniques are also introduced to further enhance the solution quality. The OCGA is compared with other well known local search method namely dynamic length tabu search, randomised steepest descent method, and other variants of genetic algorithms using extensive data sets collected from the literatures. All algorithms are coded in ANSI-C using Microsoft Visual C++ 6.0 as the compiler, and run on a Pentium 4, 2.0 GHz computer with 2.0 GB RAM. The results of the extensive computational experiments indicate that the proposed OCGA outperformed other local search methods. We have also found that computational difficulty as measured by relative deviation from the lower bound increases with problem size. In the case of large setup time, jobs tend to form a large batch size with more jobs in a batch to reduce the need of setup time between batches from different families. Therefore, more jobs will miss their assigned due dates. However, with a small setup time, more jobs will meet their respective due dates. Hence when setup time is small more batches are formed which means fewer jobs are to be processed per batch.The proposed OCGA effectively solve the problem with better solution quality compared to other local search methods. We will develop the proposed OCGA to solve the problem of minimising the total (weighted) completion time as future work. The development of OCGA for other optimality criterion such as minimising the total (weighted) tardiness/earliness is also worthy of future research.

Actions (login required)

View Item