Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility

In this paper, we propose a reformulation for the flowshop problem based on the concept of operation to workstation flexibility. While we assume a fixed sequence of operations in the reformulation, the “location” of each operation within the flow is not fixed. The proposed flowshop problem is important because the effective use of this flexibility can lead to significant changes in production performance. Solving the proposed problem involves two sub-problems: assignment of operations to workstations and sequencing of the jobs. We present a lower bound procedure and efficient solution approaches to solve each sub-problem. Furthermore, an improvement method based on neighborhood search and simulated annealing is implemented. A set of experiments is analyzed under different combinations of the proposed heuristics achieving high quality results. These experiments demonstrate that the heuristic factor is of significance for the problem.