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

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.