ANT COLONY OPTIMIZATION FOR SINGLE MACHINE TOTAL WEIGHTED EARLINESS/TARDINESS PROBLEM

摘要

This paper addresses the problem of scheduling a set of independent jobs on one machine with distinct job release times and due dates, so as to minimize a total weighted earliness and tardiness penalty. This problem has been shown to be NP-hard, even when all job weights are identical and all release times are zero. ACO algorithm is presented to solve this problem, using an extended adjacent pair-wise interchange neighborhood. The algorithm has been tested by using 90 instances and compared it to Branch and Bound method and Tabu search method. The results indicate the proposed approach is quite efficient.