Bottleneck Focused Heuristic Algorithm for Hybrid Flow Shop Scheduling Problem

For the complex shop scheduling problem of hybrid flow shop with makespan minimization criterion, a heuristic algorithm cooperating the characters of machine configuration and job processing time intensively is proposed. Firstly, the bottleneck stage is identified using the character that the average processing time is not equal at every stage, and then an initial job sequence is constructed. Secondly, a job is given higher priority at the first stage when it takes shorter processing time before the bottleneck stage and longer processing time after the bottleneck stage. Meanwhile, at every stage before the bottleneck, if there are jobs waiting for processing or completed simultaneously, the priority is given to the job with shortest remain processing time before the bottleneck; at or after the bottleneck stage, it is given to the job with longest remaining processing time. Finally, pairwise interchange and insert operation are used to improve the initial scheduling. The performance of the proposed heuristic algorithm is tested using Carlier and Neron's benchmark problems. The computational results show that compared with the well-known NEH heuristic algorithm, the average deviation is reduced 0.0555%, which verifies the effectiveness of the proposed heuristic algorithm.