一种基于构造型启发式算法的生产线调度方法

摘要

本发明提供一种基于构造型启发式算法的生产线调度方法，该方法包括如下步骤：S1、若n个工件在m台机器上加工，设p

说明书

技术领域

本发明涉及自动控制与信息技术领域，尤其涉及一种基于构造型启 发式算法的生产线调度方法。

背景技术

生产线调度是制造企业生产过程中非常重要的问题，良好的调度策 略将极大的提高生产效率。总完工时间(makespan)是调度过程中一个 非常重要的性能指标，总完工时间最小可使得资源更加有效利用、任务 更迅速传递及在制品库存最小。目前的生产线调度方法分为两种类型， 一种为穷举法，如动态规划法、分支定界法等，虽然可以对工件的加工 顺序得到最优的调度，但是这些方法的搜索空间会随着工件数量的增加 呈指数式急剧增长，计算复杂度高，对机器硬件的要求较高，难以应用 在大规模的生产线调度上；另一种方法为启发式算法，包括元启发式算 法与构造型启发式算法，目前提出的构造型启发式算法如(1)Palmer 算法——Palmer D S.Sequencing Jobs through a Multi-Stage Process in the  Minimum Total Time-a Quick Method of Obtaining a near Optimum[J]. Operational Research Quarterly，1965，16：101-107；(2)Gupta算法 ——Gupta J.A Functional Heuristic Algorithm for the Flowshop Scheduling  Problem[J].Operational Research Quarterly，1971，22：39-47；(3)CDS算 法——Campbell H G，Dudek R A，Smith M L.A Heuristic Algorithm for the n-Job，m-Machine Scheduling Problem.[J].Management Science，1970，16： 630-637；(4)RA算法——Dannenbring D G.An Evaluation of Flow Shop  Sequencing Heuristics[J].Management Science，1977，23(11)：1174-1182； (5)NEH算法——Nawaz M，Enscore E，Ham I.A Heuristic Algorithm for  the m Machine，n Job Flow Shop[J].OMEGA：The International Journal of  Management Sciences，1983，11(1)：91-95等，以上几种构造型启发式算法 中以NEH算法的性能最佳。然而，NEH算法在实现过程中需要通过多 次计算拟定工件序列的总完工时间并进行比较，因此，计算复杂度将远 大于其他构造型启发式算法。

发明内容

针对现有技术存在的问题，本发明的主要目的在于提供一种具有较 高的调度性能，同时计算复杂度较低的基于构造型启发式算法的生产线 调度方法。

为实现上述目的，本发明提供一种基于构造型启发式算法的生产线 调度方法的实施例，该方法包括如下步骤：

S1、若n个工件在m台机器上加工，设p_i，j为第j个工件在第i台机 器上的执行时间，构成矩阵P，其中i＝1，2，Λ，m；j＝1，2，Λ，n；

S2、任意选择矩阵P中的两列元素，即工件a，b分别在m台机器 上的执行时间P_a和P_b，其中1≤a，b≤n，a≠b；

S3、确定工件a，b的加工顺序；

S4、判断矩阵P中的n列元素是否均已两两比较，若是，则结束判 断，否则，返回步骤S2，

其中步骤S3包含如下步骤：

S31、将矩阵P中两列元素P_a，P_b的值分别代入 计算得到S_a和S_b；

S32、判断S_a*S_b＜＝0是否成立，若成立，则进入步骤S321，若不 成立，则进入步骤S33；

S321、判断S_a＞0是否成立，若成立，则将元件a的加工顺序置于 元件b之前，若不成立，则将元件b的加工顺序置于元件a之前；

S33、判断S_a，S_b＞0是否成立，若成立，则进入步骤S34，若不成立， 则进入步骤S35；

S34、将任意选择的矩阵P中的两列元素P_a，P_b的值分别代入 计算得到sum_c_a和sum_c_b；

S341、判断sum_c_a＜sum_c_b是否成立，若成立，则将元件a的加工 顺序置于元件b之前；若不成立，则进入步骤S342；

S342、判断sum_c_a＞sum_c_b是否成立，若成立，则将元件b的加工 顺序置于元件a之前，若不成立，则去掉P_a和P_b列的最末一个元素并 返回步骤S31；

S35、将任意选择的矩阵P中的两列元素P_a，P_b的值分别代入 计算得到sum_f_a和sum_f_b；

S351、判断sum_f_a＞sum_f_b是否成立，若成立，则将元件a的加工 顺序置于元件b之前，若不成立，则进入步骤S352；

S352、判断sum_f_a＜sum_f_b是否成立，若成立，则将元件b的加工 顺序置于元件a之前，若不成立，则去掉P_a和P_b列的首个元素并返回 步骤S31。

进一步地，当判断矩阵P中的n列元素均已两两比较，则按确定的 加工顺序对工件进行调整，并依次在m台机器上进行加工。

本发明以总完工时间最小为目标来实现流水车间生产线的调度，通 过对工件加工顺序的调整来减小每个工件在加工前的等待时间。相对于 现有技术，本发明计算复杂度低，计算时间短，且具有较好的调度性能。

附图说明

图1是流水车间生产线调度示意图。

图2是本发明基于构造型启发式算法的生产线调度方法流程图。

图3是本发明基于构造型启发式算法的生产线调度方法中步骤S3 的流程图。

具体实施方式

下面结合附图，详细说明本发明的具体实施方式。

如图1所示，为本发明的流水车间生产线调度示意图，表述为n个 工件在m台机器上加工，即每个工件需要经过m道工序，每道工序要求 不同的机器，但n个工件通过m台机器的顺序相同，即n个工件在每台 机器上的加工顺序相同。即工件1、工件2......工件n按顺序分别经过机 器1、机器2......机器m的加工，但这种加工顺序有可能并不是最佳的， 为了使总加工时间最短，必须调整工件的加工顺序。

定义O_i，j为第j个工件在第i台机器上操作，p_i，j为O_i，j的执行时间，c_i，j为O_i，j的完成时间，c_i，j为O_i，j加等待时间。其中i＝1，2，Λ，m；j＝1，2，Λ，n。为了确 定n个工件的加工任务在每台机器上的最优加工顺序，使所有工件的加 工任务全部完工的时间最短。在进行工件加工时，每个加工任务在机器 上的加工顺序相同，均为1，2，Λ，m；每台机器同时只能进行一个加工任务； 一个加工任务不能同时在不同的机器上进行；各加工任务在加工完后立 即送下一道工序；任务在机器上开始加工，必须一直进行到该工序完工， 中途不允许停下来插入其它任务；所有任务在0时刻已准备就绪，机器 调整时间包括在加工时间内；允许任务在工序之间等待；允许机器在任 务未到达时闲置。最大完成时间makespan(C_max)也即是最后一个工件加工的 完成时间c_m，n，找到一个工件的加工顺序，工件a，工件b......工件n，使 得总完工时间(makespan)最小。

设工件数量为i时的总完工时间(makespan)为C_i，其中1≤i≤n，当 i＝n时，定义C_i＝C_n＝C；设第j个工件在第i台机器上加工前的等待时间 为t_i，j，其中t_i，1＝0，1≤i≤m，1≤j≤n；设第n个工件在第i台机器上加工前的 等待时间为D_i，其中D₁＝0，即所有工件在第一台机器上的等待时间均为 0，1≤i≤m；设n个工件在m台机器上的加工时间矩阵为P，其中： $P=\left(\begin{array}{cccc}{p}_{\mathrm{1,1}}& p_{\mathrm{1,2}}& \Lambda & p_{1,n}\\ p_{\mathrm{2,1}}& p_{\mathrm{2,2}}& \Lambda & p_{2,n}\\ M& M& O& M\\ p_{m,1}& p_{m,2}& \Lambda & p_{m,n}\end{array}\right),$在矩阵P中，p_i，j表示第j个工件在第i台机器上的 加工时间，1≤i≤m，1≤j≤n。

当工件数量为1，即n＝1时，工件在每个机器上加工前的等待时间为 0，因此总完工时间(makespan)为该工件在所有机器上的加工时间之和： $C_1=p_{\mathrm{1,1}}+p_{\mathrm{2,1}}+\Lambda +p_{m,1}=\underset{i=1}{\overset{m}{\Sigma }}{p}_{i,1};$

当工件数量为2，即n＝2时，总完工时间(makespan)为第1个工件 在所有机器上的加工时间之和、第二个工件在最后一台机器上的加工时 间与第二个工件在最后一台机器上的加工前等待时间之和： C₂＝C₁+p_m，2+D₂，而D₂＝t_2，n，可按如下方式进行计算：t_2，2＝max(p_2，1-p_1，2，0)， t_2，3＝max(t_2，2+p_2，2-p′_1，3，0)，Λ，t_2，n＝max(t_2，n-1+p_2，n-1-p′_1，n，0)，其中 p′_i，j＝p_i，j+max(p_i-1，j-p_j，i-1，0)，2≤i≤m，1≤j≤n；

以此类推，当工件数量为n时，C_n＝C_n-1+p_m，n+D_n，而D_n＝t_m，n，可按如 下方式计算：t_m，2＝max(p_m，1-p′_m-1，2，0)，t_m，3＝max(t_m，2+p_m，2-p′_m-1，3，0)，Λ， t_m，n＝max(t_m，n-1+p_m，n-1-p′_m-1，n，0)。即：

$\mathrm{makespan}=C=$

$C_n=C_{n-1}+p_{m,n}+D_n$

$=C_{n-2}+p_{m-1,n}+p_{m,n}+D_{n-1}+D_n$

$=C_{n-3}+p_{m-2,n}+p_{m-1,n}+p_{m,n}+D_{n-2}+D_{n-1}+D_n$

$M$

$=p_{\mathrm{1,1}}+p_{\mathrm{2,1}}+\Lambda +p_{m,1}+p_{m,2}+p_{m,3}+\Lambda +p_{m,n}+D_1+D_2+\Lambda +D_n$

$=\underset{i=1}{\overset{m}{\Sigma }}{p}_{i,1}+\underset{j=2}{\overset{n}{\Sigma }}{p}_{m,j}+\underset{k=1}{\overset{n}{\Sigma }}{D}_k$

若要使总完工时间(makespan)最小，则需找一个工件加工序列， 使得第n个工件在第m台机器上的完成时间尽量接近或等于 即要缩小第一个工件在所有机器的加工时间之和、 除第一个工件之外的其他工件在最后一台机器的加工时间之和以及除第 一个工件之外的其他工件在加工前的等待时间之和。

如图2所示，为本发明基于构造型启发式算法的生产线调度方法流 程图，该方法包括如下步骤：

S1、若n个工件在m台机器上加工，设p_i，j为第j个工件在第i台机 器上的执行时间，构成矩阵P，$P=\left(\begin{array}{cccc}{p}_{\mathrm{1,1}}& p_{\mathrm{1,2}}& \Lambda & p_{1,n}\\ p_{\mathrm{2,1}}& p_{\mathrm{2,2}}& \Lambda & p_{2,n}\\ M& M& O& M\\ p_{m,1}& p_{m,2}& \Lambda & p_{m,n}\end{array}\right),$其中 i＝1，2，Λ，m；j＝1，2，Λ，n；

S2、任意选择矩阵P中的两列元素，即工件a，b分别在m台机器上 的执行时间P_a和P_b，其中1≤a，b≤n，a≠b；

S3、确定工件a，b的加工顺序；

S4、判断矩阵P中的n列元素是否均已两两比较，若是，则结束判 断，按确定的加工顺序对工件进行调整，并依次在m台机器上进行加工， 否则，返回步骤S2。

如图3所示，为本发明基于构造型启发式算法的生产线调度方法中 步骤S3的流程图。步骤S3，即确定工件a，b的加工顺序，具体包含如 下步骤：

S31、将矩阵P中两列元素P_a，P_b的值分别代入(S_j为矩阵P中第j列的加权值)，计算得到S_a和S_b；

S32、判断S_a*S_b＜＝0是否成立，若成立，则进入步骤S321，若 不成立，则进入步骤S33；

S321、判断S_a＞0是否成立，若成立，则进入步骤S322，即将元件 a的加工顺序置于元件b之前，若不成立，则进入步骤S323，即将元件 b的加工顺序置于元件a之前；

S33、判断S_a，S_b＞0是否成立，若成立，则进入步骤S34，若不成立， 则进入步骤S35；

S34、将任意选择的矩阵P中的两列元素P_a，P_b，代入 (sum_c_j为不断去掉矩阵P中第j列最后一个元素的 和)，计算得到sum_c_a和sum_c_b；

S341、判断sum_c_a＜sum_c_b是否成立，若成立，则进入步骤S343， 即将元件a的加工顺序置于元件b之前；若不成立，则进入步骤S342；

S342、判断sum_c_a＞sum_c_b是否成立，若成立，则进入步骤S345， 即将元件b的加工顺序置于元件a之前，若不成立，可知 sum_c_a＝sum_c_b，则进入步骤S344，即去掉P_a和P_b列的最末一个元 素并返回步骤S31；

S35、将任意选择的矩阵P中的两列元素P_a，P_b，代入 (sum_f_j为不断去掉矩阵P中第j列最前一个元素的 和)，计算得到sum_f_a和sum_f_b；

S351、判断sum_f_a＞sum_f_b是否成立，若成立，则进入步骤S353， 即将元件a的加工顺序置于元件b之前，若不成立，则进入步骤S352；

S352、判断sum_f_a＜sum_f_b是否成立，若成立，则进入步骤S355， 即将元件b的加工顺序置于元件a之前，若不成立，可知 sum_f_a＝sum_f_b，则进入步骤S354，即去掉P_a和P_b列的首个元素并 返回步骤S31。

通过实验结果说明本发明的基于构造型启发式算法的生产线调度方 法的实际调度性能。其中Y为最优率，即在特定样本规模中，使用某种 调度方法得出最优解占所有样本数量的比例，该数值越高，则表明使用 该调度方法得出最优解的比例越高，性能更优。另外，最优偏差率 E＝(MK-MKp)·100/MKp，其中MK为使用某种调度方法排序后工件的实际总 完工时间，MKp为该组工件在最优加工顺序时的总完工时间，最优偏差 率E越小则表明使用某种调度方法对工件加工顺序的排列越好，而E＝0 则表明某次工件的加工顺序排列为最优。

实验所用到的工件在各机器上的加工时间矩阵P中的各个元素Pi，j为 0到9的随机整数(1≤i≤m，1≤j≤n)，下表给出了多个以样本规模20为单 位的测试数据，从下表可以看出，利用本发明的基于构造型启发式算法 的生产线调度方法最优偏差率E＞10％的非常少，平均最优偏差率基本都 在5％以下，表明该方法的调度性能较优。另外，本发明的基于构造型启 发式算法的生产线调度方法算法复杂度为nlog(n)+nm，计算复杂度低，计 算时间短。

实施例一

假设5个工件在4台机器上的加工时间矩阵P如下，P_i表示P的第 i列。

$P=\left(\begin{array}{ccccc}1& 1& 3& 7& 7\\ 3& 9& 9& 2& 3\\ 9& 7& 3& 7& 7\\ 10& 6& 8& 7& 2\end{array}\right)$

任意选择矩阵P中的两列元素P₁、P₂；

将P₁、P₂的值分别代入计算得到S₁＝33，S₂＝13；

因为S₁，S₂＞0，将P₁、P₂的值分别代入计算得到 sum_C₁＝13，sum_C₂＝17；

因为sum_C₁＜sum_C₂，因此将P₁的加工顺序置于P₂之前；

任意选择矩阵P中的两列元素P₁、P₃；

将P₁、P₃的值分别代入计算得到S₁＝33，S₃＝9；

因为S₁，S₃＞0，将P₁、P₃的值分别代入计算得到 sum_C₁＝13，sum_C₃＝15；

因为sum_C₁＜sum_C₃，因此将P₁的加工顺序置于P3之前；

任意选择矩阵P中的两列元素P₁、P₄；

将P₁、P₄的值分别代入计算得到S₁＝33，S₄＝4；

因为S₁，S₄＞0，将P₁、P₄的值分别代入计算得到 sum_C₁＝13，sum_C₄＝16；

因为sum_C₁＜sum_C₄，因此将P₁的加工顺序置于P₄之前；

任意选择矩阵P中的两列元素P₁、P₅；

将P₁、P₅的值分别代入计算得到S₁＝33，S₅＝-10；

因为S₁·S₅＜＝0，且S₁＞0，因此将P₁的加工顺序置于P₅之前；

任意选择矩阵P中的两列元素P₂、P₃；

将P₂、P₃的值分别代入计算得到S₂＝13，S₃＝9；

因为S₂，S₃＞0，将P₂、P₃的值分别代入计算得到 sum_C₂＝17，sum_C₃＝15；

因为sum_C₂＞sum_C₃，因此将P₃的加工顺序置于P₂之前；

任意选择矩阵P中的两列元素P₂、P₄；

将P₂、P₄的值分别代入计算得到S₂＝13，S₄＝4；

因为S₂，S₄＞0，将P₂、P₄的值分别代入计算得到 sum_C₂＝17，sum_C₄＝16；

因为sum_C₂＞sum_C₄，因此将P₄的加工顺序置于P₂之前；

任意选择矩阵P中的两列元素P₂、P₅；

将P₂、P₅的值分别代入计算得到S₂＝13，S₅＝-10；

因为S₂·S₅＜＝0，且S₂＞0，因此将P₂的加工顺序置于P₅之前；

任意选择矩阵P中的两列元素P₃、P₄；

将P₃、P₄的值分别代入计算得到S₃＝9，S₄＝4；

因为S₃，S₄＞0，将P₃、P₄的值分别代入计算得到 sum_C₃＝15，sum_C₄＝16；

因为sum_C₃＜sum_C₄，因此将P₃的加工顺序置于P₄之前；

任意选择矩阵P中的两列元素P₃、P₅；

将P₃、P₅的值分别代入计算得到S₃＝9，S₅＝-10；

因为S₃·S₅＜＝0，且S₃＞0，因此将P₃的加工顺序置于P₅之前；

任意选择矩阵P中的两列元素P₄、P₅；

将P₄、P₅的值分别代入计算得到S₄＝4，S₅＝-10；

因为S₄·S₅＜＝0，且S₄＞0，因此将P₄的加工顺序置于P₅之前；

矩阵P中的5列元素均已两两比较，各工件的最终加工顺序为 P₁P₃P₄P₂P₅。

调整工件的加工顺序为P₁P₃P₄P₂P₅，依次在m台机器上进行加工。

以上介绍了基于构造型启发式算法的生产线调度方法。本发明并不 限定于以上实施例，任何未脱离本发明技术方案，即仅仅对其进行本领 域普通技术人员所知悉的改进或变更，均属于本发明的保护范围之内。