A comparison between Ant colony and Tabu search algorithms for job shop scheduling with sequence-dependent setups

摘要

In this paper the problem of scheduling a single machine with sequence-dependent setup times is investigated. Among all penalty mechanisms, weighted tardiness and earliness are the criteria employed to be minimized in four randomly generated 8-, 20-, and 50, and 80-job problems. In addition, the tabu search method (TS) has been applied on the same problems and its deterministic behavior is compared with the biased randomness implemented in ACO. In order to increase the performance of ACO, two heuristics namely ATCS and SPD are applied and the results are compared with each other. It is shown that a well-tuned ACO which requires trimmed parameter setting, next-step evaluation mechanism and proper definition of heuristic function can outperform TS in spite of taking considerably longer CPU time.