求解差异工件批调度问题的改进型蚁群算法

Improved ant colony algorithm for solving batch scheduling problem with non-identical job sizes

针对最小化制造跨度的差异工件尺寸单批处理机调度问题,通过将其转化为最小化浪费空间的问题,采用候选集策略构建分批以减少搜索空间,利用基于浪费空间的启发式更新信息素,提出一种改进的最大最小蚁群算法.此外,在算法中还引入了一种局部优化策略,以进一步提高算法的性能.仿真实验结果表明,所提出的算法优于其他几种已有算法,验证了所提出算法的有效性和鲁棒性.

By formulating the problem of minimizing the makespan on a single batch machine with non-identical job sizes as a problem of minimizing the wasted space minimization, a candidate set strategy is designed to narrow the search space when constructing the batches, combined with a heuristic based on the wasted space to update the pheromone information. Incorporated with a local optimization method to further improve the performance, an improved max-min ant system algorithm is presented. Moreover, the parameter setting in the proposed algorithm is analyzed by experimental designs to determine the appropriate parameter values. The simulation results show the effectiveness and robustness of the proposed algorithm that outperforms several previously studied algorithms.