Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.