Minimizing the Makespan in Permutation Flow Shop Scheduling Problems using Simulation

Background/Objectives: Permutation flow shop scheduling deals with finding a sequence and makespan for the jobs, the same for each machine, so that all the jobs are to be finished at the earliest. This paper tries to improve the makespan. Methods/Statistical Analysis: Using differentinitial partial sequences, job insertion technique ofNEHalgorithm is used in combination with simulation for a fixed number of runs. The popular NEH algorithm is considered as the parent algorithm to find the initial solution, and the makespan is minimized in two stages of simulation. 120 numbers of benchmark problems proposed by Taillard have been used. Codes were generated in MATLAB 2008a, and run in an i5 PC with 4 GB RAM. Findings: The computational results show that in about 67% of the cases, the makespan is minimized. The improvement is up to 4.67%. One way ANOVA has been carried out to assess the means of the out puts using MINITAB software. In the analysis, the F value is small (0.41) and the P value is > 0.05 (0.661) and hence, the Null Hypothesis is accepted. Application/Improvements: In addition to the improved makespan, another advantage is that, additional sequences are obtained which can help in efficient scheduling or re-scheduling the jobs. It is also simple, easy to understand and use. Further improvements are possible by changing the initial partial sequences.Keywords: Makespan, NEH Algorithm, Permutation Flow Shop, Scheduling, Simulation