Application of genetic algorithms for scheduling batch-discrete production system

Abstract

In this paper, is considered the scheduling problem for a two-machine flow shop model with a batch machine followed by a discrete machine in sequence. Batch machine processes jobs in a batch, and the discrete machine handles jobs one at a time. The scheduling objective is to find the sequence of the jobs and the batch policy for minimizing the total completion time of the jobs after the discrete machine. Due to the NP-complete nature of the problem, a heuristic algorithm is proposed applying the genetic algorithms (GA) which is a stochastic neighbourhood search technique. A modified crossover technique is tested together with some existing crossover methods, and a new selection rule for GA is proposed using the 'information invariance principle'. Through the computational tests, the performance of GA is compared to a known heuristic approach for the problem. Computational experience shows that the GA-based approach can be a good alternative for solving the scheduling problem.