Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan

This paper presents an efficient meta-heuristic algorithm based on electromagnetism-like mechanism (EM), in which has been successfully implemented in a few combinatorial problems. We propose the EM for scheduling the flow shop problem that minimizes the makespan and total weighted tardiness and considers transportation times between machines and stage skipping (i.e., some jobs may not need to be processed on all the machines). To show the efficiency of this proposed algorithm, we also apply simulated annealing (SA) and some other well-recognized constructive heuristics, such as SPT, NEH, (g/2, g/2) Johnson' rule, EWDD, SLACK,and NEH_EWDD for the given problems. To evaluate the performance and robustness of our proposed EM, we experiment a number of test problems. Our computational results show that our proposed EM in almost all cases outperforms SA and other foregoing heuristics applied to this paper. (C) 2009 Elsevier B.V. All rights reserved.