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.