基于离散量子微粒群算法的机器零件加工流水线调度方法

摘要

本发明公开了一种基于离散量子微粒群算法的机械零件加工流水线调度方法,该方法包括如下步骤：读入机器零件加工的过程操作时间；微粒种群初始化；计算每个微粒的适应值；更新每个粒子的个体最优位置及全局最优位置；基于离散量子微粒群优化的全局搜索；局部搜索；根据全局最优调度方案绘制零件加工次序甘特图。通过本发明提供的方法，改进传统量子微粒群优化在生产调度领域的局限性，克服了微粒群优化容易陷入局部最优的缺陷，具有寻优精度高、速度快的特点。本发明方法应用于机械零件加工流水线调度，能够在更短时间内求解得到更优的调度方案，操作简洁方便。原理适用范围广，可推广到制造业和流程工业等生产加工领域。

说明书

技术领域

本发明涉及机器零件加工流水线调度方法，特别地，涉及一种基于离散量子微粒群算法的机器零件加工流水线调度方法。

背景技术

机器零件加工流水线调度从属于流水线调度，是目前研究和应用最广泛的一类典型生产调度问题，同时它又是一个具有很多变量和强NP难的复杂组合优化问题。也是生产管理的核心内容。随着生产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此对其研究具有重要的理论和工程价值。

流水线调度问题研究                                                台机器上个工件的流水加工过程，每个零件在各台机器上的加工顺序相同，同时每个工件在每台机器上只加工一次，每台机器在某一时刻只能加工一个工件，各工件在各机器上所需的加工时间已知。调度问题的目标函数是求个工件的最优加工顺序，使最大流程时间最小。

流水线调度问题经过50多年的研究和发展，其求解方法已经形成了一定体系，总的来说，可以划分为三个分支：（1）精确方法，如分支定界，动态规划等，此类方法简单但只对小规模问题有效；（2）构造性方法，NEH方法是其中的典型代表，目前此方法常用于产生初始解；（3）混合启发式算法，就是融合了各类算法的组合算法。如结合模拟退火，遗传算法，禁忌搜索，蚁群和微粒群优化等智能优化方法的混合启发式算法，在近十多年来得到快速发展和成功应用。

微粒群优化算法是一种简单而有效的智能优化算法，其在调度领域的研究才刚刚起步。然而该算法不能保证搜索的全局收敛性，常常陷入局部最优解。在微粒群优化和量子理论基础上，孙俊于2004年提出了量子微粒群优化算法。该算法通过引入几何中心位置的概念，对微粒位置更新提供了更多的信息，并且只需要计算位置向量从而降低了计算复杂度。最重要的是，量子微粒群优化算法是一种全局最优的算法，保证了算法的有效性。但是该算法只能用于连续空间的搜索，对组合优化问题无法求解。

离散量子微粒群优化算法是一种用于求解流水线调度的优化算法。它受量子微粒群优化算法启发，将遗传算法中交叉概念和向量元素的对换操作应用于微粒位置更新。使传统量子微粒群优化原理可以适用于最小化最大流程时间的流水线调度问题。

发明内容

本发明的目的是为有效解决机器零件加工流水线调度的优化问题，提供一种基于量子微粒群优化和遗传算法交叉与向量元素对换操作的流水线方法。使该进后的算法填补了传统量子微粒群优化在组合优化领域的空白，能够有效求解具有典型NP难特性的流水线调度问题。

本发明的技术解决方案为：

基于离散量子微粒群算法的机械零件加工流水线调度方法的步骤包括：

1)读入机器零件加工的过程操作时间；

2)种群初始化，设置种群规模为，解空间问题维数为；

3)计算每个微粒的适应值，即流水线调度问题中的最大流程时间makespan；同时更新每个粒子的个体最优位置及全局最优位置；

4)基于离散量子微粒群优化的全局搜索，按照离散量子微粒群优化的位置进化公式更新种群位置、适应值、个体最优位置，全局最优位置，和种群位置的几何中心；

5)基于插入邻域结构的局部搜索；

6)判断终止条件，若未达到足够好的适应值或一个预设的最大代数，则返回步骤3)，否则执行步骤7)；

7)根据全局最优调度方案绘制零件加工次序甘特图。

所述的一种基于离散量子微粒群算法的机械零件加工流水线调度方法，其特征在于所述的基于离散量子微粒群优化的全局搜索，按照离散量子微粒群优化的位置进化公式更新种群位置、适应值、个体最优位置，全局最优位置，和种群位置的几何中心步骤，包括：

(1)计算种群位置的几何中心；

(2)对每个微粒按照如下离散量子微粒群优化的位置进化公式进行计算：

   

其中，表示该微粒经历的最佳位置，为种群中所有微粒经历的最佳位置，为种群当前位置的几何中心，为该微粒当前位置，是区间(0,1)上均匀分布的随机数，所述的离散量子微粒群优化的位置进化公式包括以下算子：

a)速度向量：，是一个代表对换操作的二元组集合，每个二元组的元素表示对换操作的作用索引。如表示对目标向量做两次对换操作，依次对换索引2,4上的元素，和索引1,2上的元素；

b)减法算子：令和是两个位置向量，则两个位置向量的差是速度向量， 是代表置换序列的速度向量；

c) 位置位置加法算子：对位置向量做两点交叉操作，得到子代位置向量；

d)乘法算子：令为系数，为速度向量，则表示选取序列的前个二元组，成为新的速度向量；若，，则；

e)位置速度加法算子：令为位置向量，为速度向量，将速度向量的二元组序列依次对位置向量执行对换操作，得到迭代更新的微粒位置；

若，

则：；

(3)评价每个微粒的适应值；更新每个微粒的当前最好位置，种群的最好位置及其对应的适应值。

所述的一种基于离散量子微粒群算法的机械零件加工流水线调度方法，其特征在于所述的基于插入邻域结构的局部搜索步骤，包括：

(1)在区间[1,n]随机产生两个整数；

(2)从种群最优位置向量中抽取第个元素，将其插入到元素之后，得到新的位置向量；

(3)计算排序的适应值。若，则更新种群最优位置向量为，对应的种群最优适应值。

本发明与现有技术相比具有的有益效果：

1)本发明方法应用于机械零件加工流水线调度，能够在更短时间内求解得到更优的调度方案，操作简洁方便。原理适用范围广，可推广到制造业和流程工业等生产加工领域。

2)通过本发明提供的方法，改进传统量子微粒群优化在生产调度领域的局限性，克服了微粒群优化容易陷入局部最优的缺陷，具有寻优精度高、速度快的特点。

附图说明

图1是本发明所提出的流水线调度方法的流程图；

图2是两点交叉操作的示意图；

图3位置向量减法算子的示意图；

图4(a)是执行插入邻域结构前的示意图；

图4(b)是执行插入邻域结构过程的示意图；

图4(c)是执行插入邻域结构后的示意图；

图5(a)是实施例执行本发明的流水线调度方法前的效果图；

图5(b)是实施例执行本发明的流水线调度方法后的效果图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图1、图2、图3、图4和图5，

基于离散量子微粒群算法的机械零件加工流水线调度方法的步骤包括：

1)读入机器零件加工的过程操作时间；

2)种群初始化，设置种群规模为，解空间问题维数为；所述的种群初始化步骤为：

(1)将NEH方法用于种群中一个微粒的初始化；所述的NEH方法步骤为：

a)计算各工件在个机器上的总加工时间：

其中，代表工件在机器上的加工时间；

b)将按降序排列；

c)取前两个工件，以最小化完成时间来排序；

d)执行步骤v；

e)将工件插入到个可行的位置中，使新序列满足最小化完成时间。

(2)对其余个微粒，随机生成初始位置向量；

(3)利用基于随机键编码规则的转换操作，将上述个微粒在连续空间的位置向量转换为离散值，即获得新的工件排序。所述的基于随机键编码规则的转换操作步骤如下：

a)将微粒位置向量的各维元素按升序排列；

b)依次记录升序排列过程中，各元素对应维数的索引值，将其填入离散排序向量，得到可应用于流水线问题的新的种群位置向量。

例如，初始化微粒的位置向量为：，则通过随机键编码规则转换得到的离散排序为：。

3)计算每个微粒的适应值，即流水线调度问题中的最大流程时间makespan；同时更新每个粒子的个体最优位置及全局最优位置；其计算公式如下：

其中，表示工件在机器上完成加工后的时刻，得到目标函数：

在计算完每个微粒的适应度后，更新每个粒子的个体最优位置及全局最优位置。对每个微粒，若适应值小于其最好位置，则将其作为当前的最好位置；若其适应值小于整个种群的最好位置，则将其作为当前种群最好位置；

4)基于离散量子微粒群优化的全局搜索，按照离散量子微粒群优化的位置进化公式更新种群位置、适应值、个体最优位置，全局最优位置，和种群位置的几何中心；具体步骤如下：

(1)计算种群当前位置的几何中心：

                    

上式计算得到的分布在连续空间，再次利用基于随机键编码规则的对换操作将转换为离散的位置向量。

(2)对每个微粒按照下式执行离散量子微粒群优化的位置进化计算：

   

式中，表示该微粒经历的最佳位置，为种群中所有微粒当前经历的最佳位置，为种群当前位置的几何中心，为该微粒当前位置，为区间(0,1)上均匀分布的随机数；

所述的离散量子微粒群优化的位置进化公式包括如下算子：

a)速度向量：，是一个代表对换操作的二元组集合，每个二元组的元素表示对换操作的作用索引。如表示对目标向量做两次对换操作，依次对换位置2,4上的元素，和位置1,2上的元素。

b)减法（位置 - 位置）算子：令和是两个位置向量，代表不同的排序。则它们的差代表一个速度向量。例如，，，则：

其原理示意如图3所示。所以在等式中，的结果是一个代表置换序列的速度向量；

c)加法（位置 + 位置）算子：对位置向量做两点交叉操作，得到一对新的子代位置向量；例如，两个位置向量分别为：和，随机产生两个交叉点。经过两点交叉操作后的子代个体为：。原理见图2；

d)乘法（系数  速度）算子：令为系数，为速度向量，则表示选取序列的前个二元组，成为新的速度向量；例如，若，，则；

e)加法（位置 + 速度）算子：令为位置向量，为速度向量。此操作是将速度向量的二元组序列依次对位置向量执行对换操作。最后得到的结果就是此轮迭代中更新的微粒位置；例如，，则：

5)基于插入邻域结构的局部搜索；所述的局部搜索步骤如下：

(1)    在区间[1,n]随机产生两个整数；

(2)    从全局最优位置向量中抽取第个元素，将其插入到元素之后，得到新的位置向量；

(3)    计算排序的适应度。若，则更新种群最优位置向量为，对应的种群最优适应度；

6)判断终止条件，若未达到足够好的适应值或一个预设的最大代数，则返回步骤3)，否则执行步骤7)；

7)根据全局最优调度方案绘制零件加工次序甘特图。

 

实施例

以下将本发明方法用于轴承加工次序的调度，进一步详细描述：

加工A,B,C,D四种轴承（即工件），按照加工工艺都需要进行先车后铣，其加工时间如下表所示。现有一台车床和一台铣床，需要确定这四个轴承的最优加工次序

工件名称车床工时/h铣床工时/hA154B810C65D127合计4126

。[0023] 基于离散量子微粒群算法对轴承加工流水线调度方法如下：

1)读入轴承加工的过程操作时间作为已知条件：

令轴承在机器上的加工时间为，则轴承A在车床上的加工时间表示为，同理读入；

2)种群初始化，设置种群规模为，解空间问题维数即工件数；所述的种群初始化步骤为：

(1)将NEH方法用于种群中一个微粒的初始化；所述的NEH方法步骤为：

a)计算各工件在个机器上的总加工时间：

其中，代表工件在机器上的加工时间；

b)将按降序排列；

c)取前两个工件，以最小化完成时间来排序；

d)执行步骤v；

e)将工件插入到个可行的位置中，使新序列满足最小化完成时间。

(2)对其余个微粒，随机生成初始位置向量；

(3)利用基于随机键编码规则的转换操作，将上述个微粒在连续空间的位置向量转换为离散值，即获得新的工件排序。所述的基于随机键编码规则的转换操作步骤如下：

a)将微粒位置向量的各维元素按升序排列；

b)依次记录升序排列过程中，各元素对应维数的索引值，将其填入离散排序向量，得到可应用于流水线问题的新的种群位置向量。

例如，初始化微粒的位置向量为：，则通过随机键编码规则转换得到的离散排序为：。

3)计算每个微粒的适应值，即流水线调度问题中的最大流程时间，其计算公式如下：

其中，表示工件在机器上完成加工后的时刻，得到目标函数：

                             

在计算完每个微粒的适应度后，更新每个粒子的个体最优位置及全局最优位置。对每个微粒，若适应值小于其最好位置，则将其作为当前的最好位置；若其适应值小于整个种群的最好位置，则将其作为当前种群最好位置；

4)基于离散量子微粒群优化的全局搜索：按照离散量子微粒群优化的位置进化公式更新种群位置、适应值、个体最优位置，全局最优位置和种群位置的几何中心；具体步骤如下：

(1)    计算种群当前位置的几何中心：

                    

上式计算得到的分布在连续空间，再次利用基于随机键编码规则的对换操作将转换为离散的位置向量。

(2)             对每个微粒按照下式执行离散量子微粒群优化的位置进化计算：

   

式中，表示该微粒经历的最佳位置，为种群中所有微粒当前经历的最佳位置，为种群当前位置的几何中心，为该微粒当前位置，为区间(0,1)上均匀分布的随机数；

所述的离散量子微粒群优化的位置进化公式包括如下算子：

a)速度向量：，是一个代表对换操作的二元组集合，每个二元组的元素表示对换操作的作用索引。如表示对目标向量做两次对换操作，依次对换位置2,4上的元素，和位置1,2上的元素。

b)减法（位置 - 位置）算子：令和是两个位置向量，代表不同的排序。则它们的差代表一个速度向量。例如，，，则：

其原理示意如图3所示。所以在等式中，的结果是一个代表置换序列的速度向量；

c)加法（位置 + 位置）算子：对位置向量做两点交叉操作，得到一对新的子代位置向量；例如，两个位置向量分别为：和，随机产生两个交叉点。经过两点交叉操作后的子代个体为：。

d)乘法（系数  速度）算子：令为系数，为速度向量，则表示选取序列的前个二元组，成为新的速度向量；例如，若，，则；

e)加法（位置 + 速度）算子：令为位置向量，为速度向量。此操作是将速度向量的二元组序列依次对位置向量执行对换操作。最后得到的结果就是此轮迭代中更新的微粒位置；例如，，则：

(3)评价每个微粒的适应值；更新每个微粒的当前最好位置，种群的最好位置及其对应的适应度。对每个微粒，若适应值小于其最好位置，则将其作为当前的最好位置；若其适应值小于整个种群的最好位置，则将其作为当前种群最好位置。

5)基于插入邻域结构的局部搜索：借鉴遗传算法交叉概念和向量元素的对换操作，对全局搜索更新后的种群最优位置向量执行插入邻域结构搜索；所述的局部搜索步骤如下：

(1)在区间[1,n]随机产生两个整数；

(2)从全局最优位置向量中抽取第个元素，将其插入到元素之后，得到新的位置向量；

(3)计算排序的适应度。若，则更新种群最优位置向量为，对应的种群最优适应度；

6)判断终止条件，若未达到足够好的适应值或一个预设的最大代数，则返回步骤3)，否则执行步骤7)；

7)根据全局最优调度方案绘制零件加工次序甘特图：

重复执行本发明方法20次，每次运行都得到最优最大流程时间为：45h，对应的可行轴承加工顺序有6种方案。分别为：

；

；

；

；

；

；

取其中一种加工方案，绘制其甘特图如图5(b)所示。