关键词: 工件, 批调度, 差异尺寸, 到达时间, 混合整数规划模型, 蚁群算法

Abstract: A single batch scheduling problem with different release time and non-identical job sizes was studied. The optimization objective was minimize Cmax. A mixed integer programming model was established and solved by operational research software CPLEX. Based on the constructive characteristic of the problem, an Ant Colony Optimization (ACO) was proposed. By analyzing the influence of release time and job sizes'constraint on the optimization objective, the concept of Idle Space (IS) was proposed and proved that minimizing IS was equivalent to minimize Cmax. Based on the analysis, dynamic heuristic information was designed to guide ants behavior more accurately. Meanwhile, a candidate list strategy was employed to reduce ants'search space and to speed up the convergence rate of algorithm. In the experimental section, test instances from literature were selected. The effectiveness of proposed ACO algorithm was validated by comparative analysis with CPLEX, heuristic, and Genetic Algorithm (GA) in literature.

Key words: workpiece, batch scheduling, non-identical job sizes, release time, mixed integer programming model, ant colony optimization