Purdue University Calumet, Department of Mathematics, Computer Science & Statistics, Hammond, IN 46323
Flow shop is one of the most classic scheduling models that have been studied since 1950's. In the past, most research about flow shop is done under the assumption that the time needed to move a job from one machine to another is negligible. But this may not be true in real life. In this research, we study the scheduling problems in the two-machine flow shop with exact delays model. This problem arises in chemistry manufacturing where there often may be an exact technological delay between the completion time of some operation and the initial time of the next operation.
Formally, our scheduling model can be stated as follows. There are two machines, the upstream machine and the downstream machine. There are n jobs. Each job has two operations: the first operation has to be processed on the upstream machine and the second operation has to be scheduled on the downstream machine after the first operation finishes. Furthermore, the interval between the start time of the second operation and the completion time of the first operation has to be exactly equal to a predefined parameter of the particular job.
We assume that both machines are available from time 0 and that at any time a machine can only process one operation. The problem is to find a permutation schedule of the jobs, so that the total completion time is minimized. It has been shown that this problem is hard and there is no hope to find the best schedule in polynomial time in general. Two metaheuriscs, Simulated Annealing and Tabu Search have been designed for this problem.
In this research, we design a totally different metaheuristic, Genetic Algorithm, to solve the problem. Genetic Algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as mutation, selection and crossover. We measure the performance of the algorithm by experiments. We compare this metaheuristic with Tabu Search and Simulated Annealing in terms of time and relative error.
[Abstract (DOC)]