Total views : 225

Impact of Initial Partial Sequence in the Makespan, in Permutation Flow Shop Scheduling Heuristic Algorithms – An Analysis


  • Panimalar Institute of Technology, Chennai - 600123, Tamil Nadu, India
  • SMBS, VIT University, Vellore – 632014, Tamil Nadu, India


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..


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

Full Text:

 |  (PDF views: 194)


  • Johnson SM. Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics. 1954 Mar; 1(1):61–8.
  • Palmer DS. Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society. 1965 Mar; 16(1):101–17.
  • Campbell HG, Dudek RA, Smith ML. A heuristic algorithm for the n job, m machine sequencing problem. Management Science. 1970 Jun; 16(10):B 630–7.
  • Dannenbring DG. An evaluation of flow shop sequencing heuristics. Management Science. 1977 Jul; 23(11):1174–82.
  • Nawaz M, Enscore EE, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega. 1983 Dec; 11(1):91–5.
  • Ruiz R, Maroto C. A comprehensive review and evaluation of permutation flow shop heuristics. European Journal of Operational Research. 2005 Sep; 165(2):479–94.
  • Chakraborty UK, Laha D. An improved heuristic for permutation flow shop scheduling. International Journal of Information and Communication Technology. 2007 Apr; 1(1):89–97.
  • Baskar A, Xavior MA. Effects of dummy machines on make span in a few classical heuristics using Taillard bench mark problems. International Journal of Materials and Product Technology. 2012 Jan; 45(1–4):145–62.
  • Dalfard VM. A simulated annealing algorithm for JIT single machine scheduling with preemption and machine idle time. Indian Journal of Science and Technology. 2011 May; 4(5):1–7.
  • Nailwal KK, Gupta D, Sharma S. Two stage flow shop scheduling under fuzzy environment. Indian Journal of Science and Technology. 2015 Jul; 8(16):1–8.
  • Sayadi M, Ramezanian R, Ghaffari-Nasab N. A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations. 2010 Jul; 1(1):1–10.
  • Rohini V, Natarajan AM. Comparison of genetic algorithm with particle swarm optimisation, ant colony optimisation and tabu search based on university course scheduling system. Indian Journal of Science and Technology. 2016 Jun; 9(21):1–5.
  • Bhongade A, Khodke P. Heuristics for production scheduling problem with machining and assembly operations. International Journal of Industrial Engineering Computations. 2012; 3(2):185–98.
  • Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research. 1993 Jan; 64(2):278–85.
  • Baskar A, Xavior MA. Analysis of job insertion technique for different initial sequences in permutation flow shop scheduling problems. International Journal of Enterprise Network Management. 2015; 6(3):153–74.
  • Dong X, Huang H, Chen P. An improved NEH-based heuristic for the permutation flow shop problem. Computers and Operations Research. 2008 Dec; 35(12):3962–8.
  • Fernandez-Viagas V, Framinan JM. On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers and Operations Research. 2014 May; 45:60–7.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.