Ant Colony Optimization Method for Time Window Constrained Batching and Scheduling Problem
Date Issued
2007
Date
2007
Author(s)
Hung, Yu Hui
DOI
en-US
Abstract
The mathematical model of a time window constrained batching and scheduling problem is rigorously defined. This problem is subject to process type constraints between operations and machines, precedence constraints between operations of a job, machine batch capacity limits, and the time window constraints between two successive operations. Three Ant Colony Optimization (ACO) solution construction procedures are developed for finding the maximum machine utilization in the time window constrained batching and scheduling problem. The first is the TW-SOFT computation mode that regards time window constraints as soft constraints. The second is the TW-HARD computation mode that regards time window constraints as hard constraints. The third is the TW-semiHARD computation mode that treats time window constraints as soft constraint, but considers them hard constraints in candidate set construction process. Four heuristic terms are proposed to guide the ACO solution search. Among them, the MSD aims to start an operation right after its predecessor is completed; the MPD aims to fully utilize time capacities of machines; the MSPD is a hybrid of the MSD and MPD; and the MSCmax aims to minimize the maximum completion time of machines. A software prototype system is developed to implement the proposed computation modes and heuristic terms. In the system, five ACO methods are implemented with the proposed ACO technique for the discussed problem. Several numerical tests are conducted to evaluate performances of the five implemented ACO methods, including the AS, ACS, ASelite, ASrank, and SDAS. Combinations of the proposed computation modes and heuristic terms are tested to evaluate their performances. Numerical results show that the TW-semiHARD mode and MSCmax heuristic term outperforms others. In addition, the ACS, SDAS, ASelite, and ASrank are better choices for the problem.
Subjects
具時窗限制的併批暨排程優化問題
時窗限制排程問題
批次機台排程
蟻拓最佳化演算法
time window constrained batching and scheduling problem
scheduling of batch processor
Ant Colony Optimization
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94546003-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):2361030d34c567f18aaab2a732e42a9e