一种柔性作业车间带准备工序的自适应分批调度方法

摘要

本发明公开了一种柔性作业车间带准备工序的自适应分批调度方法，其将分批问题与柔性作业车间调度问题同时考虑，在遗传算法迭代处理过程中，通过内循环借助动态调整贪婪解码对作业过程的作业工序调度方式进行调整和优化，并以调度优化结果作为自适应分批的依据，通过外循环借助自适应分批策略对作业过程的批次、批量划分方式进行调整和优化，从而实现了分批问题与柔性作业车间调度问题的同时优化，能够有效增加加工设备间隙时段的利用率、提高遗传算法的求解质量，并解决了分批中存在的搜索空间大、效率低等问题，对于求解考虑准备工序与不等批次、批量的柔性作业车间分批调度问题具有可行性与有效性，能够优化其分批调度的效率。

说明书

技术领域

本发明涉及任务调度技术领域，具体涉及一种柔性作业车间带准备工序的自适应分批调度方法。

背景技术

在用户定制化与市场多元化的背景下，多品种小批量生产模式应运而生并得以迅速发展。柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是实际生产中的一类具有NP-hard特性的组合优化问题，其将工件处理为整批进行生产，故很难适应当前生产模式。批量生产将整批工件划分为若干批次，各批次在不同应用场合可按照等量一致或不等量一致策略进行批量划分。分批对于缩短完工时间、促进企业生产资源合理分配、提高生产效率有着重要意义。由于传统的大批量流动柔性作业车间分批调度问题(Flexible Job-shop Scheduling Problem with Lot Streaming,FJSP-LS)不考虑工件装夹等准备工序或将准备工序与加工工序合并。而在实际生产中，随着批次的增加，完成准备工序的时间会随之增加。同时若同种工件不同批次的同道工序在同一加工设备上先后加工，中途无需更换夹具，即可省去后道准备工序的时间，实现连续加工，因此有必要在FJSP-LS中引入准备工序。考虑准备工序与不等批次、批量的FJSP-LS作为FJSP的拓展，包含批次、批量划分与FJSP两个子问题，在同时引入不等批次、批量以及准备工序后，极大提升了问题复杂度并拓展了搜索空间，同时也更加贴近多品种小批量的生产模式，因此具有重要的理论价值与工程意义。

近年来，国内外学者针对FJSP-LS开展了大量研究，多采用线性规划、约束规划以及元启发式算法进行求解。目前针对同时考虑准备工序与不等批次、批量的FJSP-LS的研究相对较少，尤其体现在对于分批策略、分批与调度问题同时优化等方面的研究不足，高效可行的算法亟待提出。鉴于遗传算法操作简单、通用性强且有良好的鲁棒性，本发明在遗传算法的基础上提出了一种基于动态调整贪婪解码的柔性作业车间带准备工序的自适应分批调度方法。

发明内容

针对现有技术存在的上述不足，本发明要解决的技术问题是如何提供一种柔性作业车间带准备工序的自适应分批调度方法的解决新方案，以有效实现针对柔性作业车间带准备工序的作业过程的分批调度方案求解，优化对柔性作业车间带准备工序的作业过程进行分批调度的效率。

为解决上述技术问题，本发明采用了如下的技术方案：

一种柔性作业车间带准备工序的自适应分批调度方法，包括如下步骤：

获取柔性作业车间带准备工序的作业过程的分批调度任务参数；

按照预设定的初始分批策略，根据所述分批调度任务参数对作业过程中的每个作业工序分别进行染色体编码处理形成遗传算法的基因，从而由作业过程中各作业工序各自对应的基因的集合构成遗传算法的一个染色体；根据预设定的种群规模N分别按照初始分批策略生成N个染色体，组成遗传算法的染色体群组，每个染色体对应一种分批调度方案；

采用遗传算法对染色体群组进行交叉、变异迭代处理，在迭代过程中对染色体种群中各染色体进行动态调整贪婪解码，并采用自适应分批策略对染色体群组进行批次、批量更新划分，通过遗传算法迭代选择出最优染色体对应的分批调度方案；

根据获得染色体对应的分批调度方案对柔性作业车间带准备工序的作业过程进行分批调度。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述作业分批调度任务参数包括作业分批调度任务中涉及的加工设备总数、工件总数，以及每种工件的加工工序总数、批次总数、及加工批量总数信息。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，该方法的具体流程为：

A)获取柔性作业车间带准备工序的作业过程的分批调度任务参数，以及遗传算法初始化的群规模N、最大批次数l

B)基于最大批次数l

C)在当前分批策略下，通过对作业过程中的每个作业工序分别进行染色体编码处理，生成遗传算法的具有N个染色体规模的染色体群组，染色体群组中的每个染色体对应一种分批调度方案；

D)对染色体种群中各染色体进行动态调整贪婪解码，并评价染色体种群中各染色体的适应度；

E)启动遗传算法，根据交叉率P

F)判断当前一轮内循环次数是否达到内层迭代次数N

G)将当前一轮的N

H)采用自适应分批策略对染色体种群进行批次、批量划分，得到更新批次、批量划分后的染色体种群；

I)判断外循环次数是否达到外层迭代次数N

J)从经过N

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述染色体中，每个作业工序所对应基因的染色体编码包括工件批次码段、批量码段、以及加工设备码段，所述工件批次码段用于指示该作业工序对应的工件编号及相应工件的批次编号，所述批量码段用于指示该作业工序中与所述工件批次码段中所指示工件编号及批次编号相对应的加工批量数，所述加工设备码段用于指示该作业工序中与所述工件批次码段中所指示工件编号及批次编号相对应的加工设备编号；且在一个染色体中，具有相同工件批次码段的基因出现的重复次序，用以指示针对相应工件批次码段中工件编号及批次编号所对应的工件批次的加工工序。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述遗传算法中，交叉处理的交叉算子包括POX交叉算子和均匀交叉算子；在交叉处理时，对于基因中的工件批次码段和批量码段采用POX交叉算子进行交叉，对于基因中的加工设备码段采用均匀交叉算子进行交叉。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述遗传算法中，变异处理的变异算子包括插入变异算子和单点变异算子；在变异处理时，对于基因中的工件批次码段和批量码段采用插入变异算子进行变异，对于基因中的加工设备码段采用单点变异算子进行变异。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，对各染色体进行动态调整贪婪解码的具体流程包括如下步骤：

1)获取染色体中包含的基因总数O

2)将染色体中排列顺序的第d个基因作为当前解码基因，根据当前解码基因的染色体编码确定其对应作业工序的工件编号i、批次编号b、工件i第b批次的加工批量数B

3)统计加工设备k上当前已排布的各个作业工序各自前后的各间隙时段，且设置间隙时段位置参数p＝1；

4)此时，如果p

5)针对当前的加工设备k上第p个间隙时段，按下式计算加工设备k上第p个间隙时段的空闲时长TF

TF

其中，tS

6)若tD

7)此时，若TM

8)搜索染色体中排列顺序在当前解码基因之后、且加工设备编号同样为k的所有基因，将这些基因对应的作业工序的集合标记为后续插入工序集O

9)判断后续插入工序集O

10)根据后续作业工序O

其中，tFP

11)此时，若tD

12)此时，如果h

13)此时，如果N

14)此时，如果d

15)对染色体的动态调整贪婪解码完成。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述步骤9)中，判断后续作业工序O

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，采用自适应分批策略对染色体群组进行批次、批量更新划分的具体流程包括如下步骤：

h1)计算当前分批策略下各个工件的自适应权重，找到自适应权重最大的工件作为当前批次调整工件；

h2)判断当前是否首次外循环；若是，则执行步骤h3)；若不是，执行步骤h4)；

h3)令当前批次调整工件的批次总数减1，并在保持当前批次调整工件的加工批量总数不变的情况下对当前批次调整工件进行重新分批；然后，随机选择当前分批策略下除当前批次调整工件以外的一个批次总数大于1的工件作为当前批量调整工件，随机选择当前批量调整工件的两个批次分别进行批量加1与批量减1，保持当前批量调整工件的加工批量总数不变；跳转至步骤h6)；

h4)判断当前批次调整工件前次是否已进行过批次总数减1调整；若是，则执行步骤h5)；否则，令当前批次调整工件的批次总数减1，然后跳转至步骤h6)；

h5)随机选择当前分批策略下除当前批次调整工件以外的一个批次总数大于1、且前次未进行过批量加1与批量减1调整的工件作为当前批量调整工件，随机选择当前批量调整工件的两个批次分别进行批量加1与批量减1，保持当前批量调整工件的加工批量总数不变；跳转至步骤h6)；

h6)本次对染色体群组的批次、批量更新划分处理完成。

上述柔性作业车间带准备工序的自适应分批调度方法中，作为优选，所述工件的自适应权重w

其中，i表示工件编号，n表示柔性作业车间带准备工序的作业过程的分批调度任务参数中包含的工件总数，i＝1,2,…,n；O

相比于现有技术，本发明的有益效果在于：

1、本发明柔性作业车间带准备工序的自适应分批调度方法，将分批问题与柔性作业车间调度问题同时考虑，在遗传算法迭代处理过程中，通过内循环借助动态调整贪婪解码对作业过程的作业工序调度方式进行调整和优化，并以调度优化结果作为自适应分批的依据，通过外循环借助自适应分批策略对作业过程的批次、批量划分方式进行调整和优化，从而实现了分批问题与柔性作业车间调度问题的同时优化。

2、在本发明柔性作业车间带准备工序的自适应分批调度方法中，针对染色体的解码采用了一种基于动态调整贪婪解码策略的贪婪解码方式，相较于传统贪婪解码方式，该解码方式能够有效增加加工设备间隙时段的利用率、提高遗传算法的求解质量。

3、在本发明柔性作业车间带准备工序的自适应分批调度方法中，针对分批方式的更新调整采用了一种基于自适应权重的批次、批量划分策略，以调度优化的结果作为分批依据，使批次与批量划分均具有一定的方向性，解决了分批中存在的搜索空间大、效率低等问题。

4、在本发明柔性作业车间带准备工序的自适应分批调度方法中，通过对遗传算法进行改进，实现了分批问题与调度问题的同时优化，对于求解考虑准备工序与不等批次、批量的柔性作业车间分批调度问题具有可行性与有效性。

附图说明

图1为本发明柔性作业车间带准备工序的自适应分批调度方法的一种具体方案流程图。

图2为本发明方法中优选采用的染色体编码方式示例图。

图3为本发明方法中优选采用的交叉操作示意图。

图4为本发明方法中优选采用的变异操作示意图。

图5为本发明方法中采用的动态调整贪婪解码与现有贪婪解码的对比分析图。

图6为本发明方法中采用的动态调整贪婪解码流程图。

图7为本发明方法中采用的自适应分批策略流程图。

图8为本发明的问题实例图。

图9为本发明的调度甘特图。

具体实施方式

下面结合附图与实例对本发明作进一步说明。

本发明提出了一种柔性作业车间带准备工序的自适应分批调度方法，其将分批问题与柔性作业车间调度问题同时考虑，以调度优化结果作为自适应分批的依据，实现分批问题与柔性作业车间调度问题的同时优化。

本发明柔性作业车间带准备工序的自适应分批调度方法，包括如下步骤：

获取柔性作业车间带准备工序的作业过程的分批调度任务参数。这里获取到的作业分批调度任务参数，包括作业分批调度任务中涉及的加工设备总数、工件总数，以及每种工件的加工工序总数、批次总数、及加工批量总数等信息。

按照预设定的初始分批策略，根据所述分批调度任务参数对作业过程中的每个作业工序分别进行染色体编码处理形成遗传算法的基因，从而由作业过程中各作业工序各自对应的基因的集合构成遗传算法的一个染色体；根据预设定的种群规模N分别按照初始分批策略生成N个染色体，组成遗传算法的染色体群组，每个染色体对应一种分批调度方案。

采用遗传算法对染色体群组进行交叉、变异迭代处理，在迭代过程中对染色体种群中各染色体进行动态调整贪婪解码，并采用自适应分批策略对染色体群组进行批次、批量更新划分，通过遗传算法迭代选择出最优染色体对应的分批调度方案。

根据获得染色体对应的分批调度方案对柔性作业车间带准备工序的作业过程进行分批调度。

采用遗传算法时，其遗传算法的初始化参数包括种群规模N、最大批次数l

对于初始分批策略的设置，是以最大批次数l

其中，b为加工批次编号，B

具体而言，如图1所示，本发明柔性作业车间带准备工序的自适应分批调度方法的具体流程具体如下：

A)获取柔性作业车间带准备工序的作业过程的分批调度任务参数，以及遗传算法初始化的群规模N、最大批次数l

B)基于最大批次数l

C)在当前分批策略下，通过对作业过程中的每个作业工序分别进行染色体编码处理，生成遗传算法的具有N个染色体规模的染色体群组，染色体群组中的每个染色体对应一种分批调度方案。

D)对染色体种群中各染色体进行动态调整贪婪解码，并评价染色体种群中各染色体的适应度。

E)启动遗传算法，根据交叉率P

F)判断当前一轮内循环次数是否达到内层迭代次数N

G)将当前一轮的N

H)采用自适应分批策略对染色体种群进行批次、批量划分，得到更新批次、批量划分后的染色体种群。

I)判断外循环次数是否达到外层迭代次数N

J)从经过N

在上述迭代处理过程中，将分批问题与柔性作业车间调度问题同时考虑，通过内循环借助动态调整贪婪解码对作业过程的作业工序调度方式进行调整和优化，并以调度优化结果作为自适应分批的依据，通过外循环借助自适应分批策略对作业过程的批次、批量划分方式进行调整和优化，从而实现了分批问题与柔性作业车间调度问题的同时优化。

针对染色体的编码，每个作业工序所对应基因的染色体编码包括工件批次码段、批量码段、以及加工设备码段；工件批次码段用于指示该作业工序对应的工件编号及相应工件的批次编号；批量码段用于指示该作业工序中与所述工件批次码段中所指示工件编号及批次编号相对应的加工批量数；加工设备码段用于指示该作业工序中与所述工件批次码段中所指示工件编号及批次编号相对应的加工设备编号。并且，在一个染色体中，具有相同工件批次码段的基因出现的重复次序，用以指示针对相应工件批次码段中工件编号及批次编号所对应的工件批次的加工工序；也就是说，具有相同工件批次码段的基因在染色体中出现的第n次，即指示针对相应工件批次码段中工件编号及批次编号所对应的工件批次执行其第n个加工工序。

为方便描述编码，现给出一个简单实例进行说明；例如，该实例的作业工序中包括3种工件(如标记为工件1、工件2、工件3)，有4台加工设备(如标记为设备1、设备2、设备3、设备4)；工件1、工件2、工件3分别需要经过2道工序、2道工序、3道工序，即3种工件各自的加工工序总数分别为2道、2道、3道；各工序均可在加工设备1到4上进行加工，种工件各自的加工批量总数分别为3批、9批、2批；工件1和3都各自分为1批处理，工件2分为2批处理，第1批的批量为5、第2批的批量为4。据此，按照上述的染色体编码方法，所得到的一个分批调度方案的染色体编码如图2所示；例如其中的基因7，其工件批次码段“22”表示工件2的第2批次，并且由于这是工件批次码段“22”在该染色体中第2次出现(前一次出现是在基因5中)，因此基因7对应的是工件2第2批次的第2道加工工序；批量码段“4”表示工件2的第2批次中的批量数为4批；加工设备码段“3”表示该作业工序针对工件2第2批次的第2道加工工序选择在设备3上进行加工。

在遗传算法的选择操作处理中，可采用轮盘赌选择与精英保留策略结合的选择算子，使优秀个体以更大的概率生存，从而防止优秀基因的丢失。

针对交叉算子的选择，如图3所示，结合三段式编码的特点，为防止交叉操作产生非法解，本发明在遗传算法中交叉处理的交叉算子可以选择POX交叉算子(precedenceoperation crossover，基于工序编码的交叉算子)和均匀交叉算子两种交叉算子；在交叉处理时，对于基因中的工件批次码段和批量码段采用POX交叉算子进行交叉，对于基因中的加工设备码段采用均匀交叉算子进行交叉；这样，可有效增加种群多样性以保证算法的全局搜索能力

针对变异算子的选择，如图4所示，结合三段式编码的特点，本发明在遗传算法中变异处理的变异算子可以选择插入变异算子和单点变异算子；在变异处理时，对于基因中的工件批次码段和批量码段采用插入变异算子进行变异，对于基因中的加工设备码段采用单点变异算子进行变异，用于改善算法的局部搜索能力以防止出现早熟现象。

对于动态调整贪婪解码的设计，是针对传统贪婪解码在解决考虑准备工序的FJSP-LS时，会导致同加工设备上部分后续工序滞后的问题，本发明在插入式贪婪解码的基础上引入后续插入工序集O

图5为本发明所提的动态调整贪婪解码与现有贪婪解码在三种情况下的解码对比分析图，图5(a)、5(b)、5(c)的左图为已有的贪婪解码的解码情况，右图则为动态调整贪婪解码的解码情况。其中，图5(a)对应情况(1)：

p＝p

图5(b)对应情况(2)：

1＜p≤p

图5(c)对应情况(3)：

1＜p≤p

相关符号与定义如下：p为解码过程中加工设备k上的间隙时段位置编号，p≤p

在本发明方案中，是将加工设备k上每个已排的作业工序的前后位置都作为一个间隙时段(即使相邻两个已排的作业工序之间的间隙时长为零，也认为存在一个间隙时段，只是改间隙时段的空闲时长TF

基于上述动态调整贪婪解码的设计思路，本发明中，对各染色体进行动态调整贪婪解码的具体流程如图6所示，包括如下步骤：

1)获取染色体中包含的基因总数O

2)将染色体中排列顺序的第d个基因作为当前解码基因，根据当前解码基因的染色体编码确定其对应作业工序的工件编号i、批次编号b、工件i第b批次的加工批量数B

3)统计加工设备k上当前已排布的各个作业工序各自前后的各间隙时段，且设置间隙时段位置参数p＝1。

4)此时，如果p

5)针对当前的加工设备k上第p个间隙时段，按下式计算加工设备k上第p个间隙时段的空闲时长TF

TF

其中，tS

6)若tD

7)此时，若TM

8)搜索染色体中排列顺序在当前解码基因之后、且加工设备编号同样为k的所有基因，将这些基因对应的作业工序的集合标记为后续插入工序集O

9)判断后续插入工序集O

这里，判断后续作业工序O

10)根据后续作业工序O

其中，tFP

11)此时，若tD

12)此时，如果h

13)此时，如果N

14)此时，如果d

15)对染色体的动态调整贪婪解码完成。

按照此方法，对染色体群组中的各个染色体分别进行动态调整贪婪解码。相较于传统贪婪解码方式，该解码方式能够有效增加加工设备间隙时段的利用率、提高算法的求解质量。

而在对染色体群组进行批次、批量更新划分时，本发明也采用了自适应分批策略，该策略需要解决批次划分与批量划分两个子问题。由于生产批次与生产周期存在U型关系，即过大或过小的批次均会导致较长的生产周期，故在考虑不等批次与批量的情况下，FJSP-LS变得更加复杂，导致搜索空间显著增大、算法搜索效率降低。基于上述特点，本发明在试探法的基础上提出一种可同时解决不等批次与批量的自适应分批策略，使批次与批量划分均具有一定的方向性。

采用自适应分批策略对染色体群组进行批次、批量更新划分的具体流程如图7所示，包括如下步骤：

h1)计算当前分批策略下各个工件的自适应权重，找到自适应权重最大的工件作为当前批次调整工件；

h2)判断当前是否首次外循环；若是，则执行步骤h3)；若不是，执行步骤h4)；

h3)令当前批次调整工件的批次总数减1，并在保持当前批次调整工件的加工批量总数不变的情况下对当前批次调整工件进行重新分批；然后，随机选择当前分批策略下除当前批次调整工件以外的一个批次总数大于1的工件作为当前批量调整工件，随机选择当前批量调整工件的两个批次分别进行批量加1与批量减1，保持当前批量调整工件的加工批量总数不变；跳转至步骤h6)；

h4)判断当前批次调整工件前次是否已进行过批次总数减1调整；若是，则执行步骤h5)；否则，令当前批次调整工件的批次总数减1，然后跳转至步骤h6)；

h5)随机选择当前分批策略下除当前批次调整工件以外的一个批次总数大于1、且前次未进行过批量加1与批量减1调整的工件作为当前批量调整工件，随机选择当前批量调整工件的两个批次分别进行批量加1与批量减1，保持当前批量调整工件的加工批量总数不变；跳转至步骤h6)；

h6)本次对染色体群组的批次、批量更新划分处理完成。

在图7中，将每次执行批次、批量更新划分时的当前批次调整工件标记为i

在批次、批量更新划分调整中，本发明引入自适应权重来引导批次划分的方向，将自适应权重w

其中，i表示工件编号，n表示柔性作业车间带准备工序的作业过程的分批调度任务参数中包含的工件总数，i＝1,2,…,n；O

在批次、批量更新划分调整中，本发明随机选取除i

下面通过举例来说明。图8为一个考虑准备工序与不等批次、批量的FJSP-LS的实例，包括5种工件(分别记为J

图9为该实例在等量一致与不等量一致两种分批策略下的调度甘特图，其中白色方框表示加工工序，其上数字为基于批次工序的编码；灰色方框表示准备工序。

在等量一致分批策略下，本发明所提方法得到的最优解为80.1，对应的各工件批次与批量分别为{2(6,6),3(12,12,12),3(16,16,16),2(12,12),2(6,6)}，调度甘特图如图9(a)所示。

在不等量一致分批策略下，本发明所提方法得到的最优解为78.4，对应的各工件批次与批量分别为{2(6,6),2(18,18),3(13,16,19),1(24),2(6,6)}，调度甘特图如图9(b)所示。

针对分批方式的更新调整，本发明采用了上述基于自适应权重的批次、批量划分策略，以调度优化的结果作为分批依据，使批次与批量划分均具有一定的方向性，解决了分批中存在的搜索空间大、效率低等问题。

综上所述，可以看到，在本发明柔性作业车间带准备工序的自适应分批调度方法中，通过对遗传算法进行改进，实现了分批问题与调度问题的同时优化，对于求解考虑准备工序与不等批次、批量的柔性作业车间分批调度问题具有可行性与有效性。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管通过参照本发明的优选实施例已经对本发明进行了描述，但本领域的普通技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离所附权利要求书所限定的本发明的精神和范围。