Title: Analysis of job insertion technique for different initial sequences in permutation flow shop scheduling problems

Authors: A. Baskar; M. Anthony Xavior

Addresses: Apollo Engineering College, Chennai-602105, Tamil Nadu, India ' SMBS, VIT University, Vellore-632014, Tamil Nadu, India

Abstract: A permutation flow shop scheduling problem involves the determination of the order of processing the required number of jobs having different processing times over different machines with an objective of minimising a performance parameter. For makespan minimisation, the problem is NP-complete and many heuristics have been developed over the years. It is generally accepted that the heuristic developed by Nawaz, Enscore and Ham (NEH heuristic) is the most efficient so far among the simple heuristics. NEH algorithm sorts the jobs in descending order of their total processing times. Initial sequence is constructed by selecting the first two jobs and other jobs are inserted one by one to obtain the makespan and the corresponding sequence. This paper analyses the powerful job insertion technique of NEH algorithm using different combinations of the total processing time and total machine idle time for different initial sequences. Taillard benchmark problems are used for the analysis.

Keywords: heuristics; permutation flow shops; flow shop scheduling; makespan; job insertion technique; initial sequences; processing time; machine idle time.

DOI: 10.1504/IJENM.2015.071131

International Journal of Enterprise Network Management, 2015 Vol.6 No.3, pp.153 - 174

Received: 02 Oct 2014
Accepted: 15 Nov 2014
Published online: 13 Aug 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article