Minimizing Makespan and Mean Flow Time in Two-Versatile-Machine Flow-Shop with Alternative Operations

摘要

This study addresses the two-machine flow-shop scheduling problems in which both machines are versatile and thus alternative operations are possible. The performance measures are the mean flow time and makespan of jobs, respectively. The problem is formulated as two integer programming models and two heuristics are developed. Computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The integer programming technique is inefficient even for small problems. For the set of problems with known optimal solutions, the average percentage errors of heuristics H_1 and H_2 are within 10%, respectively. For the set of problems with unknown optimal solutions, the average percentage errors of heuristic H_1 for solving the mean flow time is 20.09%, while the average percentage errors of heuristic H_2 for solving the makespan is 20.84%.