Computational Study of N-Job M-Machine Flow Shop Scheduling Problems: SPT, EDD, NEH, NEH-EDD, and Modified-NEH Algorithms

This paper discusses about the flow shop scheduling problems using shortest processing time, earliest due date (EDD), Nawaz, Enscore, and Ham (NEH), NEH-EDD, and modified-NEH methods. The objective of this research is to determine the performance of these methods in minimizing makespan and total tardiness. Processing times and due dates were randomly generated, and computational studies were performed in Microsoft Visual Basic 6.0. The experiments are performed for small and medium data sets. Efficiency index, relative error, and run time measure the performance of each method. Experimental results showed that NEH has the best performance in minimizing the makespan in both data sets; these are 53.35 time unit for small data sets and 83.803 time unit for medium data sets. NEH-EDD has the best performance in minimizing total tardiness with 9.37 time unit for small data sets and 231.02 time unit for medium data sets. Modified-NEH, as the proposed method for minimizing makespan and total tardiness at the same time, has good enough result. For minimizing the makespan, modified-NEH results in 57.15 time unit for small data sets and 88.107 time unit for medium data sets. For minimizing total tardiness, the modified-NEH results in 14.21 time unit for small data sets and 246.57 time unit for medium sets.