Computation model and improved ACO algorithm for p//T

Scheduling jobs on parallel machines to minimize the total tardiness (p//T) is proved to be NP hard. A new ant colony algorithm to deal with p//T (p//T ACO) is addressed, and the computing model of mapping p//T to the ant colony optimization environment is designed. Besides, based on the academic researches on p//T, some new properties used in the evolutionary computation are analyzed and proved. The theoretical analysis and comparative experiments demonstrate that p//T ACO has much better performance and can be used to solve practical large scale problems efficiently.