流水作业批调度问题优化算法研究

为解决流水作业环境作业尺寸有差异的批调度问题,建立了基于混合整数规划方法的最大时间跨度模型,分析问题的计算复杂性,给出设备数、作业数既定情况下的可行解规模.设计一种混合蚁群算法对最大时间跨度进行优化,结合算法的搜索机制和批调度启发式规则,实现了最小化最大时间跨度.利用模拟退火方法改进蚁群算法路径选择,避免算法陷入局部最优和过早收敛.实验设计随机算例,对各类不同规模的算例进行仿真实验,实验结果表明混合蚁群算法在最优解、平均运行时间和最大时间跨度等方面优于其他同类算法.

Optimization Algorithm for Batch Scheduling in Flow Shop

To solve the problem of batch processing machines with non-identical job size in the flow shop environment,the model of minimizing makespan is proposed using mixed integer programming method,and the computational complexity is analyzed.Then the bounds of the number of feasible solutions are given under fixed number of machines and jobs.A hybrid ant colony algorithm is designed to optimize makespan,and the algorithm combines with the searching mechanism and the batching heuristics rule to minimize makespan.A simulated annealing method is used to improve colony algorithm in path choice mechanism,and it avoids the defects of local optimal and slowly convergence speed.Instances with random variables are presented and used to test the algorithm,and the experimental results show that the algorithm is better than the other methods in several aspects,including the optimal solution,mean running time and makespan.