OPTIMIZATION OF NEW CONSTRUCTIVE HEURISTIC ALGORITHMS FOR PERMUTATION FLOW SHOP SCHEDULING PROBLEM

Abstract

This paper presents a new heuristic designed specifically for minimizing makespan in scheduling problems. The proposed approach incorporates a dual bottleneck phase combined with a pre-initial arrangement to enhance optimization of new heuristic. By introducing both major and minor bottleneck identification phases, the heuristic effectively identifies critical processing machines with significant completion times. To evaluate the performance, this study employed the Taillard benchmark and the upper bound (UB) makespan as comparative tools, assessing the new heuristic against the well-known NEH heuristic. Computational results clearly demonstrate that the new heuristic significantly outperforms the NEH heuristic in reducing the total completion time. The consistent lower RPD values and negative percentage errors indicate that ICHA is more effective in approaching the optimal makespan as indicated by the Taillard UB.