An Improved NEH Algorithm Applied to Permutation Flow Shop Scheduling

Flowshop Scheduling is used to determine the optimal sequence of n jobs to be processed on m machines in the same order.The permutation flowshop represents a particular case of the flowshop scheduling problem having as goal the deployment of an optimal schedule for N jobs on M machines. Solving the flowshop problem consists in scheduling n jobs (i= 1…..n) on m machines (j=1….m). A job consists in m operations and the jth operation of each job must be processed on machine j. So, one job can start on machine j if it is completed on machine j-1 and if machine j is free. Each operation has a known processing time pij. For the permutation flowshop the operating sequences of the jobs are the same on every machine. If one job is at the ith position on machine 1, then this job will be at the ith position on all the machines. Such problems are NP-Complete and hence optimal solutions are not guaranteed but heuristics have been shown to produce good working solutions. NEH (Nawaz, Enscore, Ham) Algorithm is an efficient algorithm that works by minimizing the makespan for Permutation flowshop Scheduling Problems PFSP. The proposed algorithm is obtained by modifying the NEH algorithm and produces improved quality solutions (i.e. makespan) with algorithmic complexity same as the original algorithm.