张宏国　宫雪

摘要：针对蚁群算法求解Job-shop调度问题，该算法考虑到利用析取图来描述工件加工关系给算法带来的复杂度，提出了一种广义蚁群算法。在综合考虑设备和工序关系约束的前提下，将信息素更新机制运用到求解Job-shop调度问题中，从而提高解的质量。为了提高搜索效率，根据蚁群算法的状态转移规则，对算法中参数的选择进行了详细的研究，设计了信息素更新策略。仿真实验结果表明，广义蚁群算法得到的解更接近最优解，该算法的收敛速度明显高于其他算法的收敛速度。

关键词：Job-shop调度问题；广义蚁群算法；信息素更新机制

中图分类号：TP391 文献标志码：A 文章编号：1007-2683（2017）01-0091-05

0 引言

现代制造业的市场竞争日益激烈，生产调度是现代制造业面临的重要问题，它的解决有利于提高企业的生产效率与经济。Job-shop调度问题（Job-shop scheduling problem，JSP）是生产调度中最基本的组合优化问题，在满足工艺路线、交货期与资源利用等约束条件下，合理安排工艺加工时间、先后顺序及使用资源，可以减小生产周期，减少库存，获得产品时间或成本的优化。因此Job-shop调度问题的优化求解具有重要的理论价值和实际意义，是学术界与工程界共同关注的热点。

目前求解Job-shop调度问题的主要方法是建立智能优化算法，以禁忌搜索、模拟退火、遗传算法为代表。蚁群算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机机制，易于与其他方法相结合等诸多优点。近年来，很多学者将蟻群算法逐渐地应用于Job-shop调度求解中。……