An ant colony system approach for scheduling problems

Over the past 50 years, researchers have developed many simple constructive heuristics for the scheduling problem. A major defect of these heuristics is the non-robustness of their solutions. An ant colony system (ACS) approach is presented to continuously improve the constructive heuristics. To verify the developed ACS approach, a computational study is conducted on the single machine total weighted tardiness problem. The results show that the proposed approach can effectively improve the robustness of various constructive heuristics, and outperform the existing heuristics for a well-known benchmark problem set. From the viewpoints of both the solution quality and computational expenses, the proposed ACS approach is an efficient and effective method for scheduling problems.