06-49
Sequencing Algorithms for Flexible Flow Shop Problems with Unrelated Parallel Machines, Setup Times, and Dual Criteria
by Jungwattanakit, J.; Reodecha, M.; Chaovalitwongse, P.; Werner, F.
Preprint series: 06-49, Preprints
The paper is published: Computers & Operations Research, Vol. 36, No. 2, 2009, 358 - 378 (under the title: A Comparison of Scheduling Algorithms for Flexible Flow Shop Problems with Unrelated Parallel Machines, Setup Times and Dual Criteria).
Abstract: This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a positively weighted convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0-1 mixed integer program is formulated. The problem is however to difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operation time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing, tabu search and genetic algorithms. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion based approach is superior to the others, whereas the proposed simulated annealing algorithms are better than tabu search and genetic algorithms among the iterative metaheuristic algorithms.
Keywords: Scheduling, Flexible Flow Shops, Constructive Algorithms, Simulated Annealing, Tabu Search, Genetic Algorithms
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.