A Variable Neighborhood Search Algorithm to Solve the Flow Shop-Scheduling Problem Through Blocking: Variable Neighborhood Search (VNS)

Abstract

In this chapter, we deal with the flow shop-scheduling problem through blocking known to be difficult, where there is no space and a task remains blocked on a machine until the next machine is available. For this reason, we propose the heuristic approach to minimize the delay (tardiness) as an optimization criterion. This chapter proposes a VNS-based heuristic the solutions of which are compared to those of the metaheuristic Greedy Randomized Adaptive Search Procedure (GRASP). We have developed a heuristic-based VNS to get better solutions in a reasonable time. Finally, comparisons with optimal solutions for small problems have shown that all versions can give good results; it would be interesting to extend the ideas presented in this document to the blocking flow shop at minimizing the total delay.