| A flow shop problem has n jobs (i = 1.... , n) on m machines (j = 1, . . . , m) and a job consists two operations and the jth operation of each job must be processed on machine j. Any job can start only on machine j if it is completed on machine j-1 and if machine j is free. Each operation has a known processing time pij. The work here focuses on the case m = 2 where the objective is to minimize (1) the makespan (Cmax) and (2) the average completion time (sumCi).; We first review an efficient greedy algorithm by Johnson for Cmax and give detailed proofs.; The we note that in the case of sumCi the problem is harder, in fact it is NP-hard. To tackle this problem we have implemented a branch and bound algorithm to find the optimal schedules in some cases. We also constructed a genetic algorithm under MIT's GALib C++ package. Solutions from the branch and bound algorithm are used as benchmarks for the solutions found by the genetic algorithm. |
