On VNS-GRASP and Iterated Greedy Metaheuristics for Solving Hybrid Flow Shop Scheduling Problem with Uniform Parallel Machines and Sequence Independent Setup Time

摘要

In this paper, we present some effective metaheuristics for solving hybrid flow shop scheduling with uniform parallel machines and sequence independent setup time. We implement three metaheuristics, the variable neighborhood search algorithm, the greedy randomized adaptive search procedure and the iterative greedy algorithm. The objective function is the minimization of the total flow time taking into account the availability constraints of the machines during scheduling. For each metaheuristic we choose the appropriate parameters to obtain the optimal solution by exploring the space of the neighborhood of the current solution. We conducted a simulation study on a set of randomly generated instances in order to test the effectiveness of different metaheuristics. We found that the iterative greedy algorithm gives good results compared to the other two metaheuristics.