无等待流水车间调度问题优化

《无等待流水车间调度问题优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、无等待流水车间调度问题的优化*国家自然科学基金重大项目（90104010），博士后科学基金（20070410791）。潘全科，1971年生，男，教授，博士后。主要研究方向：计算智能及其应用。E-mail:qkpan@lcu.edu.cn赵保华，1947年生，男，教授，博士生导师。主要研究方向：软件工程、协议理论与协议工程和无线传感器网络。E-mail:bhzhao@ustc.edu.cn屈玉贵，1945年生，女，教授，博士生导师。主要研究方向：通信与信息系统、计算机体系结构和通信协议工程等。E-mail:ygqu@ustc.edu.cn潘全科1，2赵保华1屈玉贵1（1中国科学

2、技术大学计算机科学系，合肥，2300262聊城大学计算学院，聊城，252059）摘要:研究以生产周期为目标的无等待流水车间调度问题。首先，结合问题特征，提出了一种复杂度为O(n)的快速生产周期算法。其次，研究了两种插入邻域结构：基本插入邻域和多重插入邻域，并提出了快速基本插入邻域算法和最大多重插入移动算法。在此基础上，将离散粒子群算法与上述两种邻域搜索算法相结合，得到了离散粒子群优化调度算法。第三，根据问题生产周期的不规则性，给出了一种通过延长工序加工时间进一步改进调度方案的方法。最后，仿真试验表明了所得算法的可行性和有效性。关键词无等待流水车间生产周期粒子群算法邻域搜索算法

3、不规则性1引言无等待流水车间（no-waitflowshop，NWFS）调度问题是一类十分重要的调度问题[1-5]，它广泛存在于炼钢、食品加工、化工和制药等领域。已经证明机床数量大于2的NWFS是强NP难题[3]。新发展起来的粒子群算法（particleswarmoptimization，PSO）为解决该类问题提供了新思路。与进化算法相比，PSO具有结构简单、容易实现、快速聚合和鲁棒性强等优势[4]。但连续本质决定了它难以直接求解生产调度这类复杂的离散问题。于是，文献[5-7]结合PSO的优化机理和调度问题的特点，提出了一种离散PSO（DiscretePSO,DPSO）。该D

4、PSO采用自然数编码，在离散的解空间内执行粒子更新操作，非常适合于调度问题的求解。在此基础上，本文针对NWFS提出了一种高性能的DPSO调度算法，并结合其不规则特性，提出了通过延长工序加工时间进一步改进调度方案的方法。仿真试验表明了所得算法的可行性和优越性。2调度模型2.1问题描述NWFS可描述为：给定m台机床和n个工件，所有工件在各机床上的加工顺序均相同。同时约定，一个工件在某一时刻只能够在一台机床上加工，一台机床在某一时刻只能够加工一个工件。由于技术条件的限制，同一工件的加工必须连续完成，即同一工件的相邻工序之间没有等待时间。各工序的加工时间已知。问题是如何安排生产，在满

5、足上述要求的条件下得到最小生产周期。142.2生产周期的计算由于同一工件的工序必须连续生产的限制，计算NWFS的生产周期不同于一般流水车间调度问题。文献[3]给出了NWFS生产周期的计算公式：令为工件i在机床k上的加工时间，为一个调度，为相邻两工件i-1和i的开工时间之差（如图1a)所示）；则为图1两工件的NWFS调度和流水车间调度（1）的生产周期为（2）上述和的算法复杂度分别为O(m2)、O(nm2)。2.3生产周期的快速算法结合问题特征，可简化的计算。如图1所示，两个工件的NWFS和流水车间调度问题有相同的生产周期。因此，可先按照流水车间调度问题求得生产周期，再根据连续生

6、产的要求从后向前依次求得NWFS的各工序开工时间，进而得到。令、分别为工序的开工、完工时间，求的算法如下：1），；令y从2到m，分别计算，2），；令y从2到m，分别计算，。3）令y从m-1到1，分别调整，。4）上述算法的复杂度为O(m)。若将得到的代入式（2），容易求得生产周期，其复杂度为O(nm)。14因为共有个，为了提高算法效率，可预先求出所有。这样，在计算生产周期时，就可视为常数。同样的，也可看作常数。于是，式（2）的复杂度就可降低为O(n)。3DPSO调度算法3.1PSO算法PSO是KENNEDY和EBRHART于1995年提出的。在PSO中，粒子代表候选解，具有位置

7、和速度两个特征。从初始群体出发，粒子根据自己和同伴的飞行经验不断调整位置和速度，使整个群体逐渐接近最佳解。PSO的基本步骤为[4]：1)初始化算法参数：惯性系数、社会系数和认知系数。2)初始化粒子群：粒子、个体极值和全体极值。3)循环步骤4）—5）直到满足停止条件4)对所有粒子执行下列操作：i.产生新粒子。ii.更新该粒子的个体极值。5)更新全体极值。6)输出全体极值。3.2DPSO算法PSO是针对连续函数的优化提出的，其位置矢量和速度矢量的编码以及新粒子的产生策略均具有连续本质，而NWFS是复杂的离散