一种基于关键机器的流水车间成组调度快速评价方法

1.本发明涉及车间调度技术领域，特别是涉及一种基于关键机器的流水车间成组调度快速评价方法。


背景技术：

2.随着经济的发展，制造业已成为国民经济的重要支柱。单元制造和成组技术的发展和应用对高效的批量制造系统有很大的影响。在单元制造系统中，资源被划分为更小的组织单元，称为制造单元。一个制造单元通常由一系列专门的机器组成，组是由在工具、设置和操作顺序等方面具有相似要求的工件组成这就形成了组调度问题。成组调度已被证明与单元制造开发的各个领域相关，反映在各种实际应用中，如汽车油漆、家具生产、半导体行业、金属零件冲床、离心泵制造、印刷电路板或一般电子制造等。制造单元可以简化物料流程，缩短生产时间，提高生产系统的灵活性，尤其适用于高度自动化的系统。随着生产线结构的优化，越来越多的企业采用单元制造系统生产模式，如华为、富士康科技、汽车装配行业等。
3.对于流水车间成组调度问题在现有的研究中，基于插入的邻域搜索操作通常被认为是获得高质量调度序列的方法。但是，在执行插入操作后对目标值的求解会导致大量的计算，耗费大量的优化调度时间，使得优化调度方法不能得到充分的利用，从而导致调度序列的不合理，可能会导致生产线出现空闲，增加生产时间，降低生产效率。可能会导致资源利用不充分或浪费，增加生产成本。还可能会导致某些工序的加工精度下降，影响产品质量。然而，很少有研究考虑到针对这一问题设计相应的快速评价方法来降低目标值求解的时间复杂度。所以是一个具有重要的现实意义，亟待解决的问题。
4.基于上述分析，为了更好地解决流水车间成组调度问题目标值的快速评价问题，本发明挖掘隐性的问题特征，分析组和工件在插入过程中的关系，定义了关键机器的概念，分别提出基于关键机器针对组和工件的插入加速准则。与传统的计算方式相比，本发明所提供的方法降低了计算的时间复杂度，大大缩短了计算时间，提高了计算效率充分挖掘优化调度方法的潜力，在相同的优化时间内能够对调度方案进行多次迭代优化，从而得到更加精准的调度方案，避免调度过程中的误差；能够高效的根据生产需求对车间任务进行调度优化，帮助企业提高生产效率；同时，优化后的调度方案可以降低物料和设备的闲置时间，提高了生产线的稳定性和可靠性，减少资源浪费，从而降低生产成本。


技术实现要素：

5.为了解决现有技术的不足，本发明提供了基于关键机器的插入邻域成组调度快速评价方法，以带准备时间的分布式流水车间为例，改进组和组内工件的计算方式，减少了目标值计算或评估的时间，提高车间调度的效率。
6.本发明提供了一种基于关键机器的流水车间成组调度快速评价方法，包括以下步骤：
7.根据成组问题的特性将基于关键机器的插入邻域快速评价方法分为组插入加速准则和工件插入加速准则；
8.进一步的，组插入加速准则描述如下：
9.在工厂k中，从组序列πk中移除第l'位置的组得到新的组序列和新的工厂k完整的调度序列尝试插入组到工厂中所有δk个位置上得到δk个调度序列，所有δk个序列的快速评价步骤如下；
10.步骤1：对于调度序列σ'k，前向计算得到前向完工时间
11.步骤2：对于调度序列σ'k，后向计算得到后向完工时间
12.步骤3：假设组插入到t位置，得到新的组序列插入到t位置，得到新的组序列和新的工厂k完整的调度序列完整的调度序列对于调度序列σ
″k，前向计算得到前向完工时间
13.步骤4：得到位置的关键机器计算工厂k的最大完工时间
14.步骤5：对于调度序列σ
″k，计算插入组后每个组中的每个工件在最后一台机器上的完工时间；
15.步骤6：在调度序列σ
″k中，第l位置组的截止日期为计算调度序列σ
″k的总延迟时间；
16.步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。
17.进一步的，工件插入加速准则描述如下：
18.在工厂k中，从工件序列中移除第j'个位置的工件得到新的工件调度序列和新的工厂k完整的调度序列尝试插入工件到组中所有个位置上，得到得到个调度序列，所有个序列的快速评价步骤如下；
19.步骤1：对于调度序列σ'k，前向计算得到前向完工时间
20.步骤2：对于调度序列σ'k，后向计算得到后向完工时间
21.步骤3：假设工件插入到q位置，得到新的工件序列插入到q位置，得到新的工件序列和新的工厂k完整的调度序列工厂k完整的调度序列对于调度序列σ
″k，前向计算得到前向完工时
间
22.步骤4：得到位置的关键机器计算工厂k的最大完工时间
23.步骤5：对于调度序列σ
″k，计算插入工件后每个组中的每个工件在最后一台机器上的完工时间；
24.步骤6：在调度序列σ
″k中，第l位置组的截止日期为计算调度序列σ
″k的总延迟时间；
25.步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。
26.本发明所提供的一种基于关键机器的流水车间成组调度快速评价方法，具有如下的技术效果：
27.(1)与传统的计算方式相比，本发明所提供的方法降低了计算的时间复杂度，大大缩短了计算时间，提高了计算效率；
28.(2)在相同的优化时间内能够对调度方案进行多次迭代优化，充分挖掘优化调度方法的潜力从而得到更加精准的调度方案，避免调度过程中的误差；
29.(3)能够高效的根据生产需求对车间任务进行调度优化，帮助企业提高生产效率；
30.(4)优化后的调度方案可以降低物料和设备的闲置时间，提高了生产线的稳定性和可靠性，减少资源浪费，从而降低生产成本。
31.综上所述，本发明可以很好的解决成组问题中目标值的计算过程，能够为流水车间成组调度快速计算目标值提供良好的解决方案。
附图说明
32.图1本发明的置信区间对比图。
具体实施方式
33.现在将在下文中参考示出了本发明的实施例的附图来更全面地描述本发明的实施例。然而，本发明可以以许多不同的形式来实施,并且不应被解释为限于在此阐述的实施例。而是，提供这些实施例以使得本公开将是彻底和完整的，并且将本发明的范围充分传达给本领域技术人员。贯穿全文,相同的数字表示相同的元素。
34.除非另有定义，否则本文使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域的普通技术人员通常所理解的相同含义。将进一步理解的是，除非在此明确地定义，否则本文中使用的术语应被解释为具有与本说明书和相关领域的上下文中的含义一致的含义，并且将不以理想化或过度正式的意义来解释。
35.下面参考根据本发明实施例的方法，系统和计算机程序产品的流程图和/或框图描述本发明。将理解的是，可以通过计算机程序指令来实现流程图图示和/或框图的一些框以及流程图图示和/或框图中的一些框的组合。这些计算机程序指令可以存储或实现在微控制器，微处理器，数字信号处理器(dsp)，现场可编程门阵列(fpga)，状态机，可编程逻辑控制器(plc)或其他处理电路,通用计算机,专用计算机中。用途计算机或其他可编程数据
处理设备(例如生产机器)，以便通过计算机或其他可编程数据处理设备的处理器执行的指令创建用于实现流程图和/或中指定的功能/动作的装置或方框图块。
36.这些计算机程序指令还可以存储在计算机可读存储器中，该计算机可读存储器可以指导计算机或其他可编程数据处理设备以特定方式工作，从而使得存储在计算机可读存储器中的指令产生包括指令装置的制品。实现流程图和/或框图中指定的功能/动作。
37.也可以将计算机程序指令加载到计算机或其他可编程数据处理设备上，以使一系列操作步骤在计算机或其他可编程设备上执行以产生计算机实现的过程，从而使得在计算机或其他可编程设备上执行的指令成为可能。其他可编程装置提供用于实现流程图和/或框图方框中指定的功能/动作的步骤。应当理解,方框中指出的功能/动作可以不按照操作图中指出的顺序发生。例如，取决于所涉及的功能/动作，实际上可以基本上同时执行连续示出的两个框,或者有时可以以相反的顺序执行这些框。尽管一些图在通信路径上包括箭头以示出通信的主要方向，但是应当理解，通信可以在与所描绘的箭头相反的方向上发生。
38.本发明具体实施过程如下：
39.以印刷电路板pcb为例，pcb是电子产品中的重要组成部分。在pcb制造过程中，需要对不同的类型的pcb零件进行调度。首先，按照类型对pcb零件进行分组，例如将pcb零件分成第一pcb组和第二pcb组，且加工这两个不同的pcb组需要在机器上装载的芯片数量也是不同的。具体来讲，在加工第一pcb组时机器上装载的芯片数量是不变的，当第一pcb组加工完需要切换第二pcb组进行加工时，就要先对机器进行清理和维护来满足处理第二pcb组所需要的条件，因此，切换的时间取决于pcb组的顺序，不同的pcb组之间所需要的切换时间也是不同的。在这种情况下，调度问题为一个带有序列相关准备时间的流水车间成组调度问题。
40.因此提供一种基于关键机器的流水车间成组调度快速评价方法，包括以下实现过程：
41.在工厂k中，对于工件序列总共有个位置，定义工件序列中第q个位置为列中第q个位置为定义位置的关键机器为关键机器满足下面的计算公式；
[0042][0043]
同时，通过下面的计算公式可以更快的得到工厂k的最大完工时间
[0044][0045]
根据成组问题的特性将基于关键机器插入邻域的快速评价方法分为组插入加速准则和工件插入加速准则；
[0046]
组插入加速准则描述如下：
[0047]
在工厂k中，从组序列∏k中移除第l'位置的组得到新的组序列和新的工厂k完整的调度序列尝试插入组到工厂中所有δk个位置上得到δk个调度序列，所有δk个序列的快速评价步骤如下；
[0048]
步骤1：对于调度序列σ'k，前向计算得到前向完工时间计算公式如下：
[0049][0050]
步骤2：对于调度序列σ'k，后向计算得到后向完工时间计算公式如下：
[0051][0052]
步骤3：假设组插入到t位置，得到新的组序列插入到t位置，得到新的组序列和新的工厂k完整的调度序列完整的调度序列对于调度序列σ
″k，前向计算得到前向完工时间计算公式如下：
[0053][0054]
步骤4：得到位置的关键机器计算工厂k的最大完工时间计算公式如下：
[0055][0056][0057]
步骤5：对于调度序列σ
″k，计算插入组后每个组中的每个工件在最后一台机器上的完工时间，计算步骤如下：
[0058]
步骤5.1：从第t+1个位置的组开始依次遍历剩下的组；
[0059]
步骤5.2：对当前组的所有工件依次进行遍历；
[0060]
步骤5.3：从关键机器开始到最后一台机器；
[0061]
步骤5.4：计算当前工件的完工时间；
[0062]
步骤5.5：根据在某台序号最大的机器上的工厂最大完工时间等于前向完工时间与后向完工时间之和，来找到下一个位置的关键机器；
[0063]
步骤5.6：按步骤5.3、5.4、5.5的方式依次对当前组中的剩余工件和剩余组进行遍历直到剩余工件都遍历完成；
[0064]
步骤6：在调度序列σ
″k中，第l位置组的截止日期为计算调度序列σ
″k的总延迟时间，计算公式如下：
[0065][0066]
步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。
[0067]
工件插入加速准则描述如下：
[0068]
在工厂k中，从工件序列中移除第j'个位置的工件得到新的工件调度序列和新的工厂k完整的调度序列尝试插入工件到组中所有个位置上，得到得到个调度序列，所有个序列的快速评价步骤如下；
[0069]
步骤1：对于调度序列σ'k，前向计算得到前向完工时间计算公式如下：
[0070][0071]
步骤2：对于调度序列σ'k，后向计算得到后向完工时间计算公式如下：
[0072][0073]
步骤3：假设工件插入到q位置，得到新的工件序列插入到q位置，得到新的工件序列和新的工厂k完整的调度序列工厂k完整的调度序列对于调度序列σ
″k，前向计算得到前向完工时间计算公式如下：
[0074][0075]
步骤4：得到位置的关键机器计算工厂k的最大完工时间计算公式如下：
[0076]
[0077][0078]
步骤5：对于调度序列σ
″k，计算插入工件后每个组中的每个工件在最后一台机器上的完工时间，计算步骤如下：
[0079]
步骤5.1：从第l'个位置的组开始依次遍历剩下的组；
[0080]
步骤5.2：若当前组为l'则从q+1位置开始对剩下的工件依次进行遍历，若不是则对组中所有工件依次进行遍历；
[0081]
步骤5.3：从关键机器开始到最后一台机器；
[0082]
步骤5.4：计算当前工件的完工时间；
[0083]
步骤5.5：根据在某台序号最大的机器上的工厂最大完工时间等于前向完工时间与后向完工时间之和，来找到下一个位置的关键机器；
[0084]
步骤5.6：按步骤5.3、5.4、5.5的方式依次对当前组中的剩余工件和剩余组进行遍历直到剩余工件都遍历完成；
[0085]
步骤6：在调度序列σ
″k中，第l位置组的截止日期为计算调度序列σ
″k的总延迟时间，计算公式如下：
[0086][0087]
步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。
[0088]
通过记录前向完工时间和后向完工时间，在插入组或工件操作后计算最大完工时间时，根据前向完工时间和后向完工时间求和得到，同时，通过对插入的位置及其之后位置的关键机器更新，从而减少计算量，降低时间复杂度，从而高效的求解目标值，在相同的优化时间内能够对调度方案进行多次迭代优化，充分挖掘优化调度方法的潜力从而得到更加精准的调度方案，提高了车间调度的效率。
[0089]
图1是本发明的置信区间对比图，其中，ig应用了所提出的快速评价方法，ig_nr没有应用所提出的快速评价方法；相对偏差指数relative deviation indexrdi作为性能的评价指标，rdi的计算公式为rdii＝(tt
i-tt
best
)/(tt
worst-tt
best
),其中，tti表示某一具体算法解决一个具体算例时得到的总延迟时间，而tt
best
和tt
worst
则分别表示所使用的全部算法中，解决上述同一算例时得到的最小和最大的总延迟时间；具体地，从图1的rdi值可以看出，ig的rdi结果均明显优于ig_nr。说明本发明方法加快了目标值的计算时间，使优化调度方法性能充分发挥，能够以较快的收敛速度收敛到最好值。

技术特征：
1.一种基于关键机器的流水车间成组调度快速评价方法，其特征在于，包括以下步骤：步骤1：计算所有组中的所有工件在机器上的前向完工时间；步骤2：计算所有组中的所有工件在机器上的后向完工时间；步骤3：插入组或工件并得到关键机器；步骤4：根据关键机器得到工件在最后一台机器上的完工时间；步骤5：根据步骤4的结果计算总延迟时间。2.根据权利要求1所述的基于关键机器的流水车间成组调度快速评价方法，其特征还在于，根据成组问题的特性将基于关键机器插入邻域的快速评价方法分为组插入加速准则和工件插入加速准则，并且采取了特定的编号方式进行描述，工厂k中包含δ
k
个组，调度序列为其中为第l位置加工的组，l∈{1,2,
…
,δ
k
}，定义为第l位置加工的组中工件的数量，组中的个工件调度序列为个工件调度序列为其中为第j位置加工的工件，为第j位置加工的工件，结合组调度序列和工件调度序列，得到工厂k完整的调度序列在调度序列σ
k
中，第l组中的第j位置的工件在机器m
i
上最早的完工时间定义为最晚开始时间到最大完工时间之间的持续时间定义为组l和组l+1在机器m
i
之间的准备时间定义为其中，代表第一个加工的组的准备时间，第l组第j位置的工件在机器m
i
上的处理时间定义为在工厂k中，对于工件序列总共有个位置，定义工件序列中第q个位置为第q个位置为而和明显为一个位置，定义位置的关键机器为3.根据权利要求2所述的基于关键机器的流水车间成组调度的快速评价方法，所述组插入加速准则描述如下：在工厂k中，从组序列π
k
中移除第l'位置的组得到新的组序列和新的工厂k完整的调度序列尝试插入组到工厂中所有δ
k
个位置上得到δ
k
个调度序列，所有δ
k
个序列的快速评价步骤如下；步骤1：对于调度序列σ'
k
，前向计算得到前向完工时间步骤2：对于调度序列σ'
k
，后向计算得到后向完工时间步骤3：假设组插入到t位置，得到新的组序列插入到t位置，得到新的组序列和新的工厂k完整
的调度序列的调度序列对于调度序列σ
″
k
，前向计算得到前向完工时间步骤4：得到位置的关键机器计算工厂k的最大完工时间步骤5：对于调度序列σ
″
k
，计算插入组后每个组中的每个工件在最后一台机器上的完工时间；步骤6：在调度序列σ
″
k
中，第l位置组的截止日期为计算调度序列σ
″
k
的总延迟时间；步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。4.根据权利要求2所述的基于关键机器的流水车间成组调度的快速评价方法，所述工件插入加速准则描述如下：在工厂k中，从工件序列中移除第j'个位置的工件得到新的工件调度序列和新的工厂k完整的调度序列尝试插入工件到组中所有个位置上，得到得到个调度序列，所有个序列的快速评价步骤如下；步骤1：对于调度序列σ'
k
，前向计算得到前向完工时间步骤2：对于调度序列σ'
k
，后向计算得到后向完工时间步骤3：假设工件步骤3：假设工件步骤3：假设工件和新的工厂k完整的调度序列和新的工厂k完整的调度序列对于调度序列σ
″
k
，前向计算得到前向完工时间步骤4：得到位置的关键机器计算工厂k的最大完工时间步骤5：对于调度序列σ
″
k
，计算插入工件后每个组中的每个工件在最后一台机器上的完工时间；步骤6：在调度序列σ
″
k
中，第l位置组的截止日期为计算调度序列σ
″
k
的总延迟时间；步骤7：重复步骤3，4，5，6直到所有的位置都被考虑。

技术总结
本发明公开了一种基于关键机器的流水车间成组调度快速评价方法，涉及车间调度技术领域，以带准备时间的分布式流水车间为例，根据成组调度的问题特点，构建了一种基于关键机器插入邻域的组和组内工件快速评价方法；包括：步骤1：计算所有组中的所有工件在机器上的前向完工时间；步骤2：计算所有组中的所有工件在机器上的后向完工时间；步骤3：插入组或工件并得到关键机器；步骤4：根据关键机器得到工件在最后一台机器上的完工时间；步骤5：根据步骤4的结果计算总延迟时间。本发明解决了流水车间成组调度问题快速评价目标值为总延迟时间问题，减少了计算时间，可有效避免重复评价，节约计算成本，提高了优化调度效率。提高了优化调度效率。提高了优化调度效率。


技术研发人员：王玉亭 韩玉艳 王宇航 李寰 贾保先
受保护的技术使用者：聊城大学
技术研发日：2023.04.07
技术公布日：2023/8/24