Bi-criteria group scheduling with sequence-dependent setup time in a flow shop

Abstract

A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this paper. Manufacturing cell and flow shop are two popular scenarios in industry. Dynamic job releases and machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which are aimed at satisfying the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two objectives. Two different initial solution finding mechanisms are proposed, and a tabu-search-based two-level search algorithm is deve1loped to find optimal/near-optimal solutions for the problem. A mathematical model is also developed and implemented to evaluate the optimality of the results from search algorithms for small problem instances. To further uncover the difference in performance of initial solutions and algorithms, an experimental design is performed and results are reported.

Keywords:

• bi-criteria
• sequence-dependent setup times
• mixed-integer programming
• tabu search