Title: Effects of dummy machines on make span in a few classical heuristics using Taillard bench mark problems

Authors: A. Baskar; M. Anthony Xavior

Addresses: School of Mechanical and Building Sciences, VIT University, Vellore-632014, Tamil Nadu, India ' School of Mechanical and Building Sciences, VIT University, Vellore-632014, Tamil Nadu, India

Abstract: Finding an optimal sequence in terms of total completion time for processing 'n' jobs in 'm' processing centres in the shop floor is an important job for a shop floor supervisor. The problem is NP hard as the total number of sequences is (n!) for a permutation flow shop scheduling problem. After the invention of evolutionary algorithms and meta heuristics, finding an optimal sequence becomes comparatively easier. However, in the shop floor, due to the limitation in the computing capabilities and computer knowledge, still the classical heuristics are popular because of their simplicity. However, in most of the cases, only one sequence is obtained except in CDS algorithm where the best sequence is selected from (m-1) alternatives. This paper deals with finding more than one sequence having optimal/near optimal make span in a permutation flow shop scheduling problem using the concept of dummy machine. The concept is used with some of the classical heuristics like CDS, Palmer slope index method, RA method. The effect of dummy machine is analysed using the well known Taillard bench mark problems. The codes are generated in MATLAB and the results are satisfactory.

Keywords: flow shop scheduling; makespan; heuristics; dummy machines; benchmarking; sequencing optimisation; optimal sequences.

DOI: 10.1504/IJMPT.2012.051349

International Journal of Materials and Product Technology, 2012 Vol.45 No.1/2/3/4, pp.145 - 162

Published online: 18 Sep 2014 *

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