求解车间调度问题的离散粒子群优化算法

　　摘要：提出了求解车间调度问题的离散粒子群优化算法，该方法综合考虑最小化平均完成时间、最小化完成时间以及作业安装时间的作业性能指标。采用离散粒子群算法进行求解最小化平均完成时间和最小化完成时间，并对作业安装时间进行分离出来单独处理。仿真实验数据表明该算法能较好的解决作业调度问题，具有一定的有效性和实用性。
　　关键词：粒子群；车间调度；安装时间
　　中图分类号：TP399 文献标识码：A 文章编号：1009-3044（2012）28-6787-03
　　1 概述
　　车间调度和控制是提高企业生产效率的有效手段。车间调度和车间计划是实现生产任务和生产计划的重要手段。通常车间调度是指在有效计划时间内将满足 多个性能指标的待加工作业按照一定的工序安排到多台机器上加工和处理。一般车间调度问题分为两大类即作业车间调度和流水线车间调度。在车间调度问题中，有许多性能指标，如平均完成时间、完成时间以及延迟时间等。其中完成时间是最能反映客户的需求，也是反映资源利用效率。许多学者对车间调度的不同标准进行了研究，如Birbil S I， Fang S 等[1]采用最小化延迟时间来提高车间调度效率。Allahverdi，Al-Anzi等[2]采用最小化平均完成时间和 最小化完成时间双重标准进行车间调度问题。以上这些研究都集中单一目标或未考虑加工过程中作业安装时间。这在实际中一般不存在。
　　在粒子群算法中，已有的粒子群算法针对连续型空间进行求解的，无法直接应用于离散型数据。Qian B， Wang L等[3]提出一个随机键实现连续空间与离散空间的转换。周驰， 高亮等[4]针对连续空间和离散空间转换问题提出最小位置值来进行求解车间调度问题。以上算法都是通过转换进行直接使用已有粒子群算法，但这种随机键或最小位置值变换都存在一个明显的弊端，即粒子位置的轻微变化 可能会导致对应的 作业加工顺序产生很大的变化。针对以上问题，本文将作业加工顺序进行编码，每个作业对应一种编码。同理在求解粒子群体最优和个体最优时也采用相同的编码方式[4]。这种编码方式 直观、表述简单，且容易理解。针对已有的最小化平均完成时间和最小化完成时间双重标准，以及考虑单一标准的作业安装时间。本文将最小化平均完成时间和最小化完成时间双重标准采用离散粒子群算法进行求解，并对作业安装时间 进行分离出来 单独处理。
　　2 问题描述
　　3 离散粒子群算法
　　在已有粒子群算法的基础上，根据粒子的速度进行实时修改粒子的移动。采用对粒子的变异和强度来控制粒子发生自适应变异。其算法的描述如下：
　　离散粒子群算法伪代码描述：
　　输入：测试数据；粒子群体大小K 及其参数；
　　输出：作业最佳排列和 最小完成时间[FOmax]
　　4 实验仿真与结果分析
　　本文的实验数据采用均匀分布的随机生成。计算机配置为windows xp，处理器2.8Ghz，内存1G，实验中作业的处理时间由U[1，80]生成。作业个数n取20，40，60，80。不是一般性将作业第一阶段机器数 设置为2，4，6，8。作业安装时间 系数K设置0.3，0.6，0.9，1.2。加权 系数[α]设置为0.2，0.5，0.8。作业加工 由机器数、作业数、安装时间进行组合，若每种组合测试用例为10，则共有1920个测试用例。用[n_m_k_α_u]来表示一个具体的测试用例，其中n表示作业个数，m表示机器数，u表示第u个测试用例。采用相对误差（PE）、平均相对误差（APE）以及局部搜索次数（LSC）来测试算法的性能。其中相对误差的公式为：
　　其中[soli]表示第i次获得的最优解，[bestsol]表示算法执行中获得的最优解。则停滞代数（maxstop）取不同值时的实验数据如下：
　　从表2可以得到如下结论：停滞代数 与局部搜索次数 成反比即停滞代数 越大则局部搜索次数 越少，表明 所求解的质量越低。这里因为求解问题规模越大，停滞代数相对减少，则局部搜索的次数也相对减少的缘故。从表1的数据也发现在停滞代数为20、30时，局部搜索的次数下降的幅度最大，而解的质量没有明显的下降，综合解的质量和局部搜索的次数，我们可以得出当停滞代数=30时可以得到群体最优解。
　　5 结束语
　　本文综合考虑最小化平均完成时间、最小化完成时间以及作业安装时间的作业性能指标。采用离散粒子群算法进行求解最小化平均完成时间和最小化完成时间，并对作业安装时间进行分离出来单独处理。实验仿真数据可以得出，当停滞代数=30时，综合解的质量和局部搜索的次数得到群体最优解即为最优调度的作业顺序。因此所提出的离散粒子群算法能较好解决作业调度问题。下阶段要解决的是将更多作业性能指标标准加入进来，如作业等待时间，作业惩罚时间等。
　　参考文献：
　　[1] Birbil S I，Fang S.Differential evolution algorithm for permutation flowshop sequencing problem with makespan criterion[C].Proceedings of the 4th International symposium on intelligent manufacturing systems （IMS2004）， Sakarya，Turkey， 2004：442-452.
　　[2] Allahverdi A，Al-Anzi.A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times[J].European Journal of Operational Research（Discrete Optimization）， 2007，182（1）：80-94.
　　[3] Qian B，Wang L，Hu R，Wang W L，Huang D X，Wang X.A hybrid differential evolution method forpermutation flow-shop scheduling[J].International Journal Advanced Manufacturing Technology，2008，38（7-8）：757-777.
　　[4] 周驰，高亮，高海兵.基于 PSO 的置换流水车间调度算法[J].电子学报，2006， 34（11）：2008-2011.
　　[5] 张长胜，孙吉贵，欧阳丹彤.一种自适应离散粒子群算法及其应用研究[J].电子学报， 2009，37（2）：299-30