关键词: 批调度, 工件尺寸, 总完工时间, 蚁群算法, 启发式算法

Abstract: Aiming at the problem of minimizing the total completion time for a single batch processing machine with non-identical job sizes, considering different coding methods, Job Sequence based Ant Colony Algorithm(JSACA)and Batch Sequence based Ant Colony Algorithm(BSACA)were proposed. JSACA used traditional coding method based on job sequence, batching jobs with heuristic; BSACA took advantages of constructive coding method of ACA without depending on the heuristics. It batched jobs directly and played its own optimization ability. Aiming at the optimization objective of total completion time, BSACA introduced batch-weight to construct heuristics. To overcome the disadvantages of lower convergence speed and trapping in local optimum in the traditional ACA, BSACA added a new pheromone update variable, set different pheromone initial value and adopted local optimization, which were based on the characteristics of batch scheduling. The effectiveness of the proposed algorithms was verified by comparative experiment.

Key words: batch scheduling, job size, total completion time, ant colony algorithms