A New Constructive Based Algorithm for Permutation Flow Shop Scheduling with Minimizing Makespan

DOI: 10.5176/2251-2179_ATAI4

Authors: Shahul Hamid Khan .B

Abstract:

In this paper we address the problem of minimizing makespan in m-machine flow shop environment. This is a NP-hard problem. An attempt has been made to solve this problem using a Metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) with new local search algorithm. We consider well-known algorithms such as NEH algorithm [1] CDS algorithms [2] for comparison. This algorithm is evaluated by the benchmark problems taken from Taillard [3]. The average percentage deviations for 90 benchmark instances are tabulated.

Keywords: Flow shop scheduling, Makespan, GRASP, Metaheuristic