Appling Metaheuristic Algorithms on a Two Stage Hybrid Flowshop Scheduling Problem with Serial Batching

In this paper the problem of serial batch scheduling in a two-stage hybrid flow shop environment with minimizing Makesapn is studied. In serial batching, it is assumed that jobs in a batch are processed serially, and their completion time is defined to be equal to the finishing time of the last job in the batch. The analysis and implementation of the prohibited transference of jobs among machines of stage one in serial batch is the main contribution of this study. Machine set-up and ready time for all jobs are assumed to be zero and no Preemption is allowed. Machines may not breakdown, but at times they may be idle. As the problem is NP-hard, a simulated annealing and genetic algorithm are proposed to provide near-optimal solutions. Since this problem has not been studied previously, therefore, a lower bound is developed for evaluating the performance of the proposed SA and GA solutions. Many test problems have been solved using SA and GA; results show both solving procedures provide near-optimum solutions regarding the lower bound solution. In the case of large scale problems, solutions provided by GA overcome those from SA algorithm.