中国科技论文在线 http://www.paper.edu.cn 基于蜂群算法的作业车间调度问题# 孙瑞萍1，姚宝珍2，于滨1* （1. 大连海事大学交通运输管理学院，辽宁大连 116026； 2. 北京交通大学土木建筑学院，北京 100044） 摘要：作业车间调度问题（JSP）在生产管理和组合优化领域扮演着重要的角色。本文中提 出了一种结合交叉操作算法的改进的人工蜂群算法（IABC）来解决作业车间调度问题。然 后通过一些经典实例对该算法进行了检验，结果显示，该算法是一种作业车间调度问题的有 效求解工具。 关键词： 作业车间调度问题；人工蜂群算法；交叉操作 中图分类号：U121 Job Shop Problem Based on Artificial Bee Colony Algorithm SUN Ruiping1, YAO Baozhen2, YU Bin1 (1. Transportation management College, Dalian Maritime University, Dalian, 116026, China; 2. School of Civil Engineering & Architecture, Beijing Jiaotong University, Beijing 100044) Abstract: Job shop problem (JSP), known as a well-known combinatorial optimization problem, is very important in fields of production management. This paper presented an improved artificial bee colony (IABC) algorithm with crossover operation for JSP. The performance of the proposed algorithm was validated by some benchmark problems. The results showed that the IABC seems to be a powerful tool for JSP compared with other heuristic algorithms. Key words: job shop scheduling problem, artificial bee colony, Crossover operation 0 引言 全球市场竞争的加剧产生了一个具有挑战性的生产环境，它要求更低的生产成本和更 短的产品生命周期的。JSP 是要确定用有限数量的机器来处理作业的次序和时间。作业车间 调度问题的完工时间是所有作业完成时间的最大值。JSP 的目标就是完工时间的最小化。JSP 作为现实生活中的应用在过去的四十年中已经得到了广泛的研究。Ponnambalam 等[1]提出了 一种通过改进遗传算法的控制参数来优化 JSP 的遗传算法。Wang 等[2]运用霍普菲尔德人工 神经网络老解决任务调度问题。Huang 和 Xiong[3]提出了一种先进的蚁群算法来优化 JSP， 该算法采用了一种新的状态转换规则来优化其的性能。 众所周知，JSP 是最困难的 NP 难解问题之一，甚至一个很简单的例子都很难用精确地 方法来解决它。近期，有很多文献致力于用启发式算法来解决该问题。人工蜂群（ABC）的 算法，作为一种新型的启发式算法，是一种模拟蜂群的组织模式和智能管理的非数值优化算 法。Karaboga[4]首次将蜂群算法应用于函数的数值优化并提出了系统的人工蜂群算法。ABC 已经被广泛应用于许多数值函数和现实世界问题，而且也被证明与 GA 和其他启发式算法相 比人工蜂群算法具有更好的性能。本文即是应用人工蜂群算法（ABC）来解决 Job Shop 调 基金项目：中国博士后科学基金面上资助（20080440168）；高学博士学科点新教师基金（20070151013）； 中国博士后科学基金特别资助（201003611 ）；教育部人文社会科学研究一般项目青年基金项目 （10YJC630357） 作者简介：硕士. E-mail: ybzhyb@163.com - 1 - 

中国科技论文在线 http://www.paper.edu.cn 度问题。在 GA 算法中引入了交叉操作来提高人工蜂群算法的搜索性能。本文的结构如下： 第二部分对 Jop Shop 调度问题进行了描述。第三部分提出了人工蜂群算法（ABC）和一些 改善的措施。第四部分对计算结果进行了讨论，最后第五部分是结论。 1 问题描述 一个标准的作业车间调度问题可以看做是用有限数量的机器来处理有限数量的作业。 JSP 的目标是找到能最小化所有作业完成时间的方案，但该方案必须同时满足某些限制：（a） 每个作业在机器上的处理顺序是一定的；（b）每台机器在同一时间最多只能处理一个作业， 并且处理过程不能中断；（c）任何作业都没有优先被处理的权利，必须按照预设的机器处 理顺序进行操作。令 J=｛j1，j2，…，jn｝代表作业序列，M={m1，m2，…，mn}代表机器组， O = {Oi1，Oi2，...，Oin}代表工序集，这里的 Oij 表示的是作业 i 的 j 操作。同时 Ai 表示的是 由约束条件（a）限制的操作对，EX 对表示的是机器 k 上的工序对序列，操作 Oij 的最早开 始时间是 tij。JSP 的公式可以描述如下： ntmin t ⎧ ⎪ ts .. ⎨ ⎪ ⎩ − t ij ≥ τ ij i ( j )1 + ( ∀ OO ij , i ( j )1 + ) ∈ A i (1) t − t kl ij ≥ τ kl or t kl − t ij ≥ τ ij ( ∀ OO kl ij , ) ∈ E x 约束条件确保了在任一时间每台机器最多处理一项作业并且处理过程不会被中断，同时 也确保了所有工作都遵循预定的机器处理顺序和并且拥有确定的处理时间。 2 改进的人工蜂群算法（IABC） 2.1 方案构造 人工蜂群优化法是一种新的启发式算法，该算法的灵感来源于蜜蜂的觅食行为。食源i被选 择的概率Pi可以由下式计算得出： p i = f i / SN ∑ n 1 = （2） f n 其中，SN是食源（如被雇佣的蜜蜂）的数量，fi为食物源的适合度。然而，对于JSP来说， 应该用利润率来反映目标函数。令Jpi代表方案i的盈利能力。 （3） i M i max /1= Jp iM max 表示方案i的完工时间 其中 2.2 交叉操作 引入交叉操作通过探索研究空间并阻止局部优化来提高人工蜂群算法的性能，这一点与 遗传算法很相似。本文中交叉操作的目的是交换随机操作。交叉操作的步骤如下： 第一步：选择一台机器的操作序列，然后从每台机器中选择交叉操作。图2显示了Oki和Okj因 为在Mk的操作序列中交叉而被选择出来。 第二步：交换同一台机器的操作，产生子系方案。 因此，对交叉的操作可能会在对于相应的机器的最佳可用处理时间内被重新分配。解决 - 2 - 

中国科技论文在线 http://www.paper.edu.cn 方案的每台机器都具有一定的概率Pm因突变而被选择，具体可参考文献 [5-7]。通常，一个解 的多样性在开始时较大并随搜索而减少。因此，我们将能够快速收敛的交叉率应用到第一代 中一个好的解决方案里，并应用于稍后阶段中为避免局部最优的更多的多样性中。在当前的 第t代中交叉的概率可由下述公式描述： = min p tp )( (4) m m mp 和 max mp 分别代表了在开始和结束阶段较低和较高交叉率。T是给定的最大数量 其中： min 1min ) m max m − + − Tt / ( p p 的代数。根据初步测试，我们提出较低的交叉率 pm max = 3 实例研究 SN /1 ，其中MCN是ABC的最大周期数，SN是食物来源的数量。 pm min = /1 MCN 和较高交叉率 在本文算法中， IABC算法的参数设置如下：MCN=140, SN=20。为了研究论文中提出 的人工蜂群算法的可行性和有效性，本文通过一些经典实例（ORLIB， ftp://mscmga.ms.ic.ac.uk/pub/jobshop1.txt )，实例的一些参数值如表1所示。为了检验本文算 法的性能，我们将其与标准ABC进行对比。这里，认为完工时间可以作为衡量这些算法的指 标。结果显示如表2，粗体的数字是三种算法中的最佳解决方案。 表1 实例的基本参数 Table 1 The parameters in the instances 实例 MT06 MT10 MT20 LA01 实例 已知最优 ABC IABC 实例 已知最优 ABC IABC n, m 6, 6 10, 10 20, 5 10, 5 实例 LA06 LA11 LA16 LA21 n, m 15, 5 20, 5 10, 10 15, 10 实例 LA26 LA31 LA36 表2 结果分析 Table 2 The results of ABC and IABC MT10 930 930 930 LA21 1046 1197 1055 MT20 1165 1165 1165 LA26 1218 1326 1218 LA01 666 666 666 LA31 1784 1784 1784 LA06 926 926 926 LA36 1268 1380 1344 MT06 55 55 55 LA16 945 990 979 n, m 20, 10 30, 10 15, 15 LA11 1222 1222 1222 从表2中可以看出我们的算法可以得出近似的最优解，而且通过将我们的算法（IABC）同标 准ABC比较，很明显对于该问题IABC比简单的ABC提供了更优的方案。这可以归因于交叉 操作的引入通过使人工蜂群多样化提高了该算法的搜索效率，从而探索出新的可能的方案空 间并避免了陷入局部最优的算法。 4 结论 最著名的机器调度问题—JSP属于NP-hard问题中的一类。根据JSP的特点，一个新的启 发式算法——人工蜂群算法在论文中被提出。此外，交叉操作被应用来更进一步挖掘最优解。 - 3 - 

中国科技论文在线 http://www.paper.edu.cn 而且，本文通过一些基准问题来检验算法并通过对比标准的ABC，测试的结果表明所提出的 IABC在求解JSP具有比标准的ABC具有更强的求解性能，同时也表明了IABC是解决JSP问题 一个有效的方法。 [参考文献] (References) [1] PONNAMBALAM S G, ARAVINDAN P, RAJESH S V. A Tabu Search Algorithm for Job Shop Scheduling. The International Journal of Advanced Manufacturing Technology, 2000, 16(10):765-771. [2] WANG W L, WU Q D, XU X L. Hopfield Neural Network Approach For Job-Shop Scheduling Problems. Acta Automatica Sinica, 2002, 28 (5): 838- 844. [3] HUANG Y P, XIONG J. A Study of Job-shop Scheduling Problem Based on Improved Ant Colony Algorithm and Its Simulations. Computer Simulation, 2009, 26(8):278-282. [4] ZHOU H, FENG Y, HAN L. The hybrid heuristic genetic algorithm for job shop scheduling. Computers and Industrial Engineering, 2001, 40(3):191-200. [5] YU B, YANG, Z Z, YAO B Z. An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal Of Operational Research, 2009, 196(1):171-176. [6] HOLLAND J H. Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, Mich. 1975. [7]TOM V M, MOHAN S. Transit route network design using frequency coded genetic algorithm. J. Transp. Eng., 2003, 129(2): 186–195. - 4 -