Bottleneck-based heuristic for re-entrant flow shop with two potential dominant machines

The problem illustrated in this paper is a special type of scheduling problem found in a re-entrant flow shop where two of its processes has high tendency of exhibiting bottleneck characteristics. The processes scheduling resembles a four machine permutation re-entrant flow shop with the process routing of M1, M2, M3, M4, M3, M4 where M1 and M4 have high tendency of being the dominant machines. Due to the re-entrant and permutation nature of the process routing, the actual bottlenecks were identified as M1 and combinations of M4+M3+M4. Two makespan algorithms using absolute bottleneck analysis were developed for the identified bottleneck categories. Each algorithm was only valid under several conditions identified as absolute bottleneck conditions. Using these conditions, a constructive heuristic was then developed to solve for near-optimal scheduling sequence. The heuristic performance was evaluated for small, medium and large job numbers using random data. For small job numbers, the heuristic results were compared with the optimum makespan generated from complete enumeration. For medium and large job numbers, the heuristic performance is measured by comparing its makespan with the one generated by the NEH. At strong M1 and M4+M3+M4 dominance level, this heuristic shows slightly better makespan performance compared to the NEH for problems with large job numbers. For smaller job numbers, NEH shows its superiority.