Indian Journal of Science and Technology

Abstract

Objectives: This paper analyzes the impact of a few new initial partial sequences on the makespan in a permutation flow shop scheduling problem. Taillard benchmark problems are used for the purpose of validation. Methods/Statistical Analysis: The popular NEH heuristic considers the first two jobs as its initial partial sequence after arranging them in descending order of their total processing times. The algorithms using different partial sequences are coded in MATLAB and a total of 120 number problem instances are used for the analysis which fall under twelve sets of 10 instances each. One-way ANOVA has been conducted for validating the results. Findings: It has been found that the initial partial sequences other than the first two jobs considered by the original NEH can also yield better makespans. Also, initial ordering of jobs according to the decreasing order of the average processing time and standard deviation of the processing times proposed by in. perform relatively better. In all the cases, job insertion technique is proved to be more powerful. The random algorithm that uses the job insertion technique do perform well with a deviation of 3.4342% which is better than many other known simple algorithms. The ANOVA confirms that the variants are statically not different from the NEH algorithm. But, it shows that a few variants perform better than the NEH for the Taillard benchmark problems. Application/Improvements: The results can be used as a seed solution and could be improved using metaheuristics. Further, the authors are working on other benchmarks and using tie breaking rules to know the impact.. 

Keywords: Initial Partial Sequence, Makespan, NEH Heuristic, Permutation Flow Shop, Scheduling