双资源约束作业车间调度算法研究

Algorithm for Dual Resource Constrained Job Shop Scheduling

针对存在差异性工人的双资源约束作业车间调度问题,提出一种混合蚁群算法进行求解。该算法借鉴禁忌搜索思想,基于工艺约束为每只蚂蚁建立候选解空间,通过压缩蚂蚁搜索空间提高解搜索效率;引入各种启发式资源选配策略,在蚂蚁寻径过程中渐进地为各工序配置最优的设备、工人双资源组合;以模拟退火算法作为局部搜索机制,对每次迭代的最优解进行退火优化,增强算法全局收敛能力。证明了该混合算法的搜索过程是一个有限非齐次不可约马尔科夫链后,基于马尔科夫链知识对其全局收敛性进行理论分析。最后采用仿真试验及统计分析方法确定最优的参数组合和资源选配策略,通过该混合蚁群算法与其他算法对随机算例运算结果的对比分析,表明所提算法搜索性能较强且鲁棒性较优。

A hybrid ant colony algorithm is proposed to solve the dual resource constrained job shop scheduling problem with heterogeneous workers.Based on technological constraints and tabu search ideas,a candidate aggregate of result is built for every ant to contract the search space and improve the search efficiency.Some heuristic policies for resource allocation are imposed to actualize the best collocating of the machines and the worker forces during the ant routing process.Meanwhile,the simulated annealing algorithm is taken as a local search mechanism to improve the global convergence ability of the algorithm.After the theoretical analysis of the global convergence via Markov chain,according to the experiments and statistical analysis,the optimal combination of parameters and the optimal resource allocation policy are chosen.The hybrid ant colony algorithm has strong search ability and good robustness for this problem based on the result of comparing experiment on random benchmarks.