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

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

Dalel Bouzidi (Sfax University, Tunisia)
DOI: 10.4018/978-1-7998-0268-6.ch004

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.
Chapter Preview
Top

Problem Description

Let J1, J2,…,Ji,…,Jn be the sequence to be evaluated, where Ji represents the task that occupies position i in the considered sequence, the, M1, M2,…, Mj,…Mm the ordered sequence of machines, Pk,j the processing time of task k on machine Mj, and dk the due date of task k, 978-1-7998-0268-6.ch004.m01 the starting date of the task Ji on the first machine and 978-1-7998-0268-6.ch004.m02 the starting date of the ask Ji on machine Mj. The departure dates of each task on each machine are given by the following expressions:

978-1-7998-0268-6.ch004.m03
(1)
978-1-7998-0268-6.ch004.m04
(2)
978-1-7998-0268-6.ch004.m05
(3)
978-1-7998-0268-6.ch004.m06
(4)
978-1-7998-0268-6.ch004.m07
(5)
978-1-7998-0268-6.ch004.m08
(6)

Complete Chapter List

Search this Book:
Reset