一种玻璃缓存落架次序的优化方法

摘要

本发明公开了一种玻璃缓存落架次序的优化方法，应用于玻璃生产系统，所述玻璃生产系统包括流程卡和加工设备，每个加工设备对应一个设备号，所述流程卡用于记录每道工序的加工设备的设备号，每个控制段内包括多个加工工序，包括以下步骤：A，对当前工序所有流程卡的加工队列，根据在上一工序加工的设备号进行流程卡分类，在上一个控制段加工的设备号相同的流程卡为同一类；B，通过基于二叉树搜索分类算法找到流程卡分类后在单台设备的加工次序；C，根据流程卡是否可放置同一L架的规则，计算移动步长，确定流程卡加工次序调整的位置，对单台设备的流程卡加工次序进行调整。本发明有效地提高L架的流转率和装载率，以及工序设备的利用率。

说明书

技术领域

本发明涉及玻璃加工领域，尤其涉及一种玻璃缓存落架次序的优化方法。

背景技术

在玻璃生产车间中，由于其特有的生产特点，如在各工艺段间的玻璃产品在加工过程中需要不断落架，其中落架存在一定的落架规则，选取不同的落架方案会影响整个车间的加工效率，另外由于加工工艺的特殊性，各个工艺段都具有多重约束，如玻璃在钢化阶段是批处理，需要考虑玻璃产品的厚度、加工温度等因素，这些因素使得目前卫浴玻璃生产车间的生产计划和生产调度都是依靠计划员的经验进行手工计划，然而，在实际的计划过程中会涉及大量的资源平衡和人工协调问题，凭借有限的人力是很难进行计算和保证资源协调的准确性，并且在多变的生产环境中会经常面临着已经做好的生产计划要进行重计划的可能，严重影响了企业的生产效率，亟需一种适用于卫浴玻璃生产车间的调度方法。

发明内容

本发明的目的在于提出一种玻璃缓存落架次序的优化方法，以解决上述问题。

为达此目的，本发明采用以下技术方案：

一种玻璃缓存落架次序的优化方法，应用于玻璃生产系统，所述玻璃生产系统包括流程卡和加工设备，每个加工设备对应一个设备号，所述流程卡用于记录每道工序的加工设备的设备号，每个控制段内包括多个加工工序，所述优化方法包括以下步骤：

A，对当前工序所有流程卡的加工队列，根据在上一工序加工的设备号进行流程卡分类，在上一个控制段加工的设备号相同的流程卡为同一类；

B，通过基于二叉树搜索分类算法找到流程卡分类后在单台设备的加工次序；

C，根据流程卡是否可放置同一L架的规则，计算移动步长，确定流程卡加工次序调整的位置，对单台设备的流程卡加工次序进行调整；

在步骤A中，当前控制段不进行加工的流程卡，其加工的设备号记为0号；当前控制段不进行加工的流程卡根据前一控制段的设备号进行分类，如当前不加工的控制段为首道工序，则不再进行分类，此时流程卡归为同一类。

在所述步骤B中，所述二叉树搜索分类算法包括以下步骤：

B1：首先获取第k道工序中，任一加工设备上的流程卡的初始加工队列，将该加工设备的设备号定义为i，初始加工队列按FCFS原则排序得到，将初始加工队列放到ProcessList中；

B2：按ProcessList的加工队列取出对应流程卡的上一控制段使用的设备号，并存放至DeviceNoList；

B3：取出在DeviceNoList中不为0的设备号，并存放至IndexList1中；

B4：根据ProcessList对应取出第k-1道工序对应使用的设备号，并存放到DeviceNoList；

B5：判断递归次数，如果递归次数大于1，执行步骤B6，否则执行步骤B7；

B6：将IndexList1与DeviceNoList对应的设备号设置为无穷大，避免在递归时重复搜索；

B7：从DeviceNoList中取出一个设备号，并记为a，然后存放到IndexList2中；

B8：判断在设备号为a的加工设备上所加工的流程卡数量，即判断IndexList2的长度，如果IndexList2的长度大于等于1，执行步骤B9，否则执行步骤B11；

B9：判断设备号a是否等于0，如果等于0，执行B10，如果不等于0，需要根据非零设备号再继续分类，对详细分类后的单台设备加工队列执行单台设备流程卡次序调整算法，算法执行完毕则转至B11

B10：判断在设备号为a的加工设备上所加工的流程卡数量是否大于等于2并且工序k是否大于2，如果两个条件都满足，工序k自减1，递归次数增加1，重复B3，否则执行B11；

B11：设备号a自增1；

B12：取出第k-1个控制段的总设备数,记为D(k-1),判断设备号a是否大于D(k-1)，条件成立则结束算法，否则重复B4。

在所述步骤C中，每个所述流程卡分别记为π⁽ⁱ⁾(n)，其中n表示流程卡在初始加工队列中的位置，i表示加工设备的设备号，若流程卡π⁽ⁱ⁾(n₁)与流程卡π⁽ⁱ⁾(n₂)满足先进后出约束，则需要调整流程卡π⁽ⁱ⁾(n₁)的位置至n₂，流程卡π⁽ⁱ⁾(n₂)移至位置n₂-1，流程卡π⁽ⁱ⁾(n₁)需要移动的次数为移动步长，则移动步长为：steplength＝n₂-n₁。

在进行单台设备流程卡次序调整的过程的过程中，还应满足L架流转率优选策略：定义设备号为i的加工设备的初始加工队列为π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}，对于满足落至同一L架的流程卡集合Ω＝{π⁽ⁱ⁾(t),π⁽ⁱ⁾(h),...,π⁽ⁱ⁾(m)}(t＜h＜...＜m)进行判断，将不满足maxC_j,n≤C_π(t-1),i(j∈Ω)的流程卡maxC_j,n(j∈Ω)则从集合Ω去除；直到当满足maxC_j,n≤C_π(t-1),i(j∈Ω)的流程卡集合Ω为确认落至同一L架。

在进行单台设备流程卡次序调整的过程的过程中，还应满足首位空闲装载优选策略：定义设备号为i的加工设备的初始加工队列为π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}，对于满足落至同一L架的流程卡Ω＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(h),...,π⁽ⁱ⁾(m)}(1＜h＜...＜m)，集合Ω中包含设备号为i的加工设备的首个加工流程卡，即加工设备的初始状态为空闲；当有多个流程卡满足落至同一L架规则时，则集合Ω中的所有流程卡确认为落至同一L架，落架完成后才送至下一控制段进行加工；否则立即送至下一控制段加工。

单台加工设备上的流程卡次序调整方法包括以下步骤：

C1：根据第k道工序中，任一加工设备的流程卡的加工队列ProcessList得到完工时间队列，并将对应的完工时间队列放到TList；

C2：从ProcessList取出对应第k-1道工序中，任一加工设备上的流程卡在ProcessLis的位置下标记为r放到rList，以及对应的完工时间放至T_finish；

C3：取出rList所有元素的下标记为s并放到sList；

C4：判断T_finish的第s个元素是否比TList中第r-1个流程卡完工时间小，若是则执行C5，否则转至C6；

C5：判断在第k-1道工序设备号为a的加工设备中所加工的数量为x的全部流程卡是否满足落至同一L架的条件，满足条件则可落至同一L架的流程卡的数量x自增1，下标s自增1，转至执行C3，不满足条件时执行C6；

C6：x个流程卡绑定落至同一架子，即根据式1可以得到移动步长，进而对x个流程卡的排序进行调整，调整完毕后，x置0；

C7：更新加工队列ProcessList及对应的完工时间Tlist；

C8：判断是否遍历完在第k-1道工序中，设备号为a的加工设备的所有流程卡队列，是则结束算法，否则，下标r自增1，重复执行C2。

附图说明

附图对本发明做进一步说明，但附图中的内容不构成对本发明的任何限制。

图1是本发明其中一个实施例的整体流程示意图；

图2是本发明其中一个实施例的流程卡分类示意图；

图3是本发明其中一个实施例的流程卡分类二叉树示意图；

图4是本发明其中一个实施例的流程卡分类处理算法流程示意图；

图5是本发明其中一个实施例的移动步长示意图；

图6是本发明其中一个实施例的L架流转率优先策略示意图；

图7是本发明其中一个实施例的首位空闲装载率优先策略示意图；

图8是本发明其中一个实施例的单台设备流程卡次序调整算法流程图。

具体实施方式

下面结合附图并通过具体实施方式来进一步说明本发明的技术方案。

本实施例的一种玻璃缓存落架次序的优化方法，应用于玻璃生产系统，所述玻璃生产系统包括流程卡和加工设备，每个加工设备对应一个设备号，所述流程卡用于记录每道工序的加工设备的设备号，每个控制段内包括多个加工工序，如图1所示，包括以下步骤：

A，对当前工序所有流程卡的加工队列，根据在上一工序加工的设备号进行流程卡分类，在上一个控制段加工的设备号相同的流程卡为同一类；

B，通过基于二叉树搜索分类算法找到流程卡分类后在单台设备的加工次序；

C，根据流程卡是否可放置同一L架的规则，计算移动步长，确定流程卡加工次序调整的位置，对单台设备的流程卡加工次序进行调整；

在步骤A中，当前控制段不进行加工的流程卡，其加工的设备号记为0号；当前控制段不进行加工的流程卡根据前一控制段的设备号进行分类，如当前不加工的控制段为首道工序，则不再进行分类，此时流程卡归为同一类。

本发明针对玻璃缓存落架次序优化问题，考虑L架流程卡先进后出的约束，并以最大化L架流转率和装载率为优化目标，提出了一种基于设备利用率优先的玻璃缓存落架次序优化算法，在提高其流转率和装载率的同时，提高了工序设备的利用率。

由于卫浴玻璃生产车间中工件的流转都是以流程卡为单位，以流程卡为最小管理单位，因此本发明中对工件的处理都是以流程卡为处理单位，即生产订单的流程卡生成以后，对流程卡作为一个整体处理，视流程卡为一个工件处理。因此每个控制段的每台设备或每条流水线都有一个由流程卡排序组成的加工队列，设备的加工流程卡按先来先服务(first come first service，FCFS)原则排序，得到初始加工队列π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}(0＜i≤m)。

由于流程卡玻璃在上一控制段进行落架操作之后，在当前控制段加工时放置同一L架的流程卡有先进后出加工约束；并且放置在同一L架的流程卡在上一控制段的加工只能在同一台设备或同一流水线加工，由于当前控制段中设备的初始加工队列的流程卡来自上一控制段中各个设备或流水线，因此为了判断当前控制段中哪些流程卡具有先进后出约束，需要先对初始加工队列的流程卡根据上一个控制段的加工设备是否一致进行分类，定义上一个控制段的加工设备相同的流程卡为一类。

如图2所示，表示设备i的初始加工队列为π⁽ⁱ⁾＝{2,4,1,9,12,18,13,26,27,21}，其中流程卡号{2,5}为一类，表示在上一控制段0号设备加工的流程卡集合；流程卡号{9,12,13}为一类，表示上一控制段1号设备加工的流程卡集合，以此类推，直至设备上的初始加工队列的所有流程卡分类完成。

在所述步骤B中，如图4所示，所述二叉树搜索分类算法包括以下步骤：

B1：首先获取第k道工序中，任一加工设备上的流程卡的初始加工队列，将该加工设备的设备号定义为i，初始加工队列按FCFS(先来先服务)原则排序得到，将初始加工队列放到ProcessList中；

B2：按ProcessList的加工队列取出对应流程卡的上一控制段使用的设备号，并存放至DeviceNoList；

B3：取出在DeviceNoList中设备号不为0所对应的索引号，并存放至IndexList1中；

B4：根据ProcessList对应取出第k-1道工序对应使用的设备号，并存放到DeviceNoList；

B5：判断递归次数，如果递归次数大于1，执行步骤B6，否则执行步骤B7；

B6：把在DeviceNoList内，且与IndexList1与对应的设备号设置为无穷大，避免在递归时重复搜索；

B7：从DeviceNoList中取出一个设备号，并记为a，并存放到IndexList2中；

B8：判断在设备号为a的加工设备上所加工的流程卡数量，即判断IndexList2的长度，如果IndexList2的长度大于等于1，执行步骤B9，否则执行步骤B11；

B9：判断设备号a是否等于0，如果等于0，执行B10，如果不等于0，需要根据非零设备号再继续分类，对详细分类后的单台设备加工队列执行单台设备流程卡次序调整算法，算法执行完毕则转至B11

B10：判断在设备号为a的加工设备上所加工的流程卡数量是否大于等于2并且工序k是否大于2，如果两个条件都满足，工序k自减1，递归次数增加1，重复B3，否则执行B11；

B11：设备号a自增1；

B12：取出第k-1个控制段的总设备数,记为D(k-1),判断设备号a是否大于D(k-1)，条件成立则结束算法，否则重复B4。

如图3所示，通过对流程卡分类规则的描述，将当前控制段记为w_j，可以把当前控制段的初始流程卡队列v分为两个大类，当上一控制段w_j-1加工时的流程卡集合分为一大类，记为v₁，此时集合v₁中包含了在上一控制段w_j-1的各个设备加工的流程卡，则可根据设备号细分集合v₁中的流程卡；将上一控制段w_j-1不加工时的流程卡集合分为另外一大类，记为O₁，此时集合O₁中只包含了在上一控制段w_j-1在0号设备加工的流程卡，需要继续判断上一控制段w_j-1的上一控制段w_j-1的加工设备号，此时的设备号又包括0号设备和非零号设备，因此又可对集合O₁分为两类处理，以此类推；

因此，可以建立以u为根节点，O_k为左节点，v_k为右节点的完满非完全二叉树(Full>

在所述步骤C中，每个所述流程卡分别记为π⁽ⁱ⁾(n)，其中n表示流程卡在初始加工队列中的位置，i表示加工设备的设备号，若流程卡π⁽ⁱ⁾(n₁)与流程卡π⁽ⁱ⁾(n₂)满足先进后出约束，则需要调整流程卡π⁽ⁱ⁾(n₁)的位置至n₂，流程卡π⁽ⁱ⁾(n₂)移至位置n₂-1，流程卡π⁽ⁱ⁾(n₁)需要移动的次数为移动步长，则移动步长为：steplength＝n₂-n₁。

如图5(a)所示为设备号为i的加工设备的初始加工队列，每个方形表示一个流程卡，填充相同颜色的方形的代表经过流程卡分类处理算法后划分的同一类流程卡，流程卡的次序调整只能限制在同一类流程卡的位置的调整；在图5(a)中，假设流程卡π⁽ⁱ⁾(2)与流程卡π⁽ⁱ⁾(3)在上一控制段中满足落至同一L架规则，则移动流程卡π⁽ⁱ⁾(2)至流程卡π⁽ⁱ⁾(3)的位置，假设放置了流程卡π⁽ⁱ⁾(2)和流程卡π⁽ⁱ⁾(3)的L架继续可以放置流程卡π⁽ⁱ⁾(5)，则需要将调整位置后的流程卡π⁽ⁱ⁾(3)、π⁽ⁱ⁾(2)绑定一起移动至π⁽ⁱ⁾(5)的位置。

因此，当出现多个(大于2个)流程卡{π⁽ⁱ⁾(n_t),...,π⁽ⁱ⁾(n_g),π⁽ⁱ⁾(n_h)}(n_t＜...＜n_g＜n_h)在上一控制段中落至同一L架时，其流程卡{π⁽ⁱ⁾(n_t),...,π⁽ⁱ⁾(n_g),π⁽ⁱ⁾(n_h)}移动的先后次序为：n_g满足(n_g＞n_t)时流程卡π⁽ⁱ⁾(n_g)优先移动。如图5(b)所示，流程卡π⁽ⁱ⁾(2)、π⁽ⁱ⁾(3)、π⁽ⁱ⁾(5)在上一控制段落至同一L架，则可以先移动流程卡π⁽ⁱ⁾(3)，移动步长由式1计算可得steplength＝2，移动完毕则移动流程卡π⁽ⁱ⁾(2)，移动步长steplength＝3，以此类推，直到所有放置在同一L架的流程卡移动完毕，如图5(c)所示，一个L架的所有流程卡移动完成后的次序排列，移动完成后便可继续移动下一L架的流程卡。

在进行单台设备流程卡次序调整的过程的过程中，还应满足L架流转率优选策略：定义设备号为i的加工设备的初始加工队列为π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}，对于满足落至同一L架的流程卡集合Ω＝{π⁽ⁱ⁾(n_t),...,π⁽ⁱ⁾(n_g),π⁽ⁱ⁾(n_h)}(n_t＜...＜n_g＜n_h)进行判断，将不满足的流程卡maxC_j,n(j∈Ω)从集合Ω中去除；直到当满足的流程卡集合Ω为确认落至同一L架。

如图6所示，每个方形表示一个流程卡，填充相同颜色的方形的代表经过流程卡分类处理算法后划分的同一类流程卡，设备号为i的加工设备是当前控制段的某一加工设备，设备号分别为p、q的加工设备是上一控制段的加工设备,各加工设备的加工队列如图6的方形所示，假设流程卡Ω＝{π⁽ⁱ⁾(2),π⁽ⁱ⁾(3),π⁽ⁱ⁾(5)}在上一控制段满足落至同一L架规则，其在上一控制段的完工时间分别为t1，t2，t4，另外判断maxC_j,n＝π⁽ⁱ⁾(5)＝t4＞t3，不满足则去除流程卡π⁽ⁱ⁾(5)，去除后的流程卡集合maxC_j,n＝π⁽ⁱ⁾(3)＝t2＜t3，满足因此最终可以落至同一L架的流程卡集合为Ω＝{π⁽ⁱ⁾(2),π⁽ⁱ⁾(3)}；利用L架流转率优先策略对流程卡集合Ω调整后，可以保证设备i在时间段t3～t4间连续加工，提高设备的利用率。

在进行单台设备流程卡次序调整的过程的过程中，还应满足首位空闲装载优选策略：定义设备号为i的加工设备的初始加工队列为π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}，对于满足落至同一L架的流程卡Ω＝{π⁽ⁱ⁾(n_t),...,π⁽ⁱ⁾(n_g),π⁽ⁱ⁾(n_h)}(n_t＜...＜n_g＜n_h)，集合Ω中包含设备i的首个加工流程卡，即设备的初始状态为空闲；当有多个流程卡满足落至同一L架规则时，则集合Ω中的所有流程卡确认为落至同一L架，落架完成后才送至下一控制段进行加工；否则立即送至下一控制段加工。

如图7(a)所示，机器i的初始加工队列为π⁽ⁱ⁾＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(2),...,π⁽ⁱ⁾(n)}，假设流程卡集合Ω＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(4)}满足落至同一L架，由于集合Ω中的流程卡π⁽ⁱ⁾(1)属于集合π⁽ⁱ⁾的首个流程卡，因此可采用首位空闲装载率优先策略，集合Ω的所有流程卡都绑定在同一L架，落至同一L架的流程卡集合Ω在设备i的排序则根据先进后出约束进行次序调整，调整后如图7(b)所示，Ω＝{π⁽ⁱ⁾(1),π⁽ⁱ⁾(4)}放置在同一L架，此时再采用L架流转率优先策略对图6的流程卡集合Ω₂＝{π⁽ⁱ⁾(2),π⁽ⁱ⁾(3),π⁽ⁱ⁾(5)}进行排序，则集合Ω₂的所有流程卡也可确认为放置同一L架，并且设备i可以保持连续加工。

单台设备流程卡次序调整方法包括以下步骤：

C1：根据第k道工序中，任一加工设备的流程卡的加工队列ProcessList得到完工时间队列，并将对应的完工时间队列放到TList；

C2：从ProcessList取出对应第k-1道工序中，任一加工设备上的流程卡在ProcessLis的位置下标记为r放到rList，以及对应的完工时间放至T_finish；

C3：取出rList所有元素的下标记为s并放到sList；

C4：判断T_finish的第s个元素是否比TList中第r-1个流程卡完工时间小，若是则执行C5，否则转至C6；

C5：判断在第k-1道工序设备号为a的加工设备中所加工的数量为x的全部流程卡是否满足落至同一L架的条件，满足条件则可落至同一L架的流程卡的数量x自增1，下标s自增1，转至执行C3，不满足条件时执行C6；

C6：x个流程卡绑定落至同一架子，即根据式1可以得到移动步长，进而对x个流程卡的排序进行调整，调整完毕后，x置0；

C7：更新加工队列ProcessList及对应的完工时间Tlist；

C8：判断是否遍历完在第k-1道工序中，设备号为a的加工设备的所有流程卡队列，是则结束算法，否则，下标r自增1，重复执行C2。

在单台设备流程卡次序调整算法中，采用L架流转率优先策略，可以进一步确定落至同一L架的流程卡，通过对移动步长的计算可以确定调整流程卡排序移动的位置，该策略可以保证L架的流转率，提高设备的利用率，但是该策略有可能降低L架的装载率，因此采用首位空闲装载率优先策略，通过在设备空闲时优先考虑装载率，从而保证L的装载率。

以上结合具体实施例描述了本发明的技术原理。这些描述只是为了解释本发明的原理，而不能以任何方式解释为对本发明保护范围的限制。基于此处的解释，本领域的技术人员不需要付出创造性的劳动即可联想到本发明的其它具体实施方式，这些方式都将落入本发明的保护范围之内。