批加工时间受总重量和最大尺寸双重约束的车间调度方法

摘要

本发明提供批加工时间受总重量和最大尺寸双重约束的车间调度方法，包括步骤Q1—Q6，将工件序列标记为L，取最先空闲的机器并开启一个新的批次，将该机器的空闲时刻作为该批次的开始加工时间；按序列L的次序组批，转到Q6，否则，将待加工工件放到当前批次，转到Q4，设置机器最大空闲等待时间为1/2装载时间s，如果当前批次是空的，那么将当前批次的最晚开始时间设置为下一工件的到达时间加上s/2；否则，当前批次的最晚开始时间设置为机器的空闲时刻加上s/2；如果所有工件都已经组批完毕，计算最大完成时间并返回调度结果；本发明提出的具有针对性的本发明技术方案，与其他典型批调度方法相比，具有较好的运算性能，计算速度更快并且平均误差率更低的优点。

权利要求

1.批加工时间受总重量和最大尺寸双重约束的车间调度方法，其特征在于：包括步骤：Q1：按工件尺寸非增排序，并将工件序列标记为L；

Q2：读取最先空闲的机器并开启一个新的批次，将该机器的空闲时刻作为该批次的开始加工时间；

Q3：如果在机器空闲时刻，已到达的待加工工件总重量大于机器容量，那么按序列L的次序组批，转到Q6，否则，将待加工工件放到当前批次，转到Q4；

Q4：设置机器最大空闲等待时间为1/2装载时间s，如果当前批次是空的，那么将当前批次的最晚开始时间设置为下一工件的到达时间加上s/2；否则，当前批次的最晚开始时间设置为机器的空闲时刻加上s/2；

Q5：按照序列L中的顺序检索所有后续工件，如果工件的到达时间小于当前批次的最晚开始时间，并且当前批次能够容纳该工件，则将工件放到该批次中，并更新该批次在机器上的开始加工时间；

Q6：将当前批次安排到当前机器上，如果所有工件都已经组批完毕，计算最大完成时间并返回调度结果；否则，转到Q2。

2.根据权利要求1所述批加工时间受总重量和最大尺寸双重约束的车间调度方法，其特征在于：所述批加工时间受总重量和最大尺寸双重约束的车间调度方法的描述为Pm|batch,rj,wj,sj,c|Cmax数学模型如下：

Min Cmax 公式1

Xji,Yik＝0 or 1                                          公式10所述数学模型用到的变量和参数：集合:

J：工件集{j∈J},J＝{1,2,...,n}，n表示工件总数量；

B：批次集{i∈B},B＝{1,2,...,d}，d表示分批数量上届；

M:机器集{k∈M},M＝{1,2,...,m}，m表示机器总数量；

参数：

c:设备容量；

s:装载时间；

wj:第j个工件的重量；

sj:第j个工件的尺寸；

rj:第j个工件的到达时间；

BigM:数值较大的整数；

α：装载量权重系数；

β：工件尺寸权重系数；

决策变量：

因变量：

Pi:第i个批次的加工时间；

Sik:第i个批次在第k台设备上的开始加工时间；

Cmax：最大完成时间。

说明书

批加工时间受总重量和最大尺寸双重约束的车间调度方法

技术领域

[0001] 本发明属于加工技术领域，尤其涉及用于车间生产调度使用的批加工时间受总重量和最大尺寸双重约束的车间调度方法。

背景技术

[0002] 批调度是车间生产调度的重要分支，现有技术中传统批调度问题可以分成两大类：串行批处理机调度和平行批处理机调度。在串行批处理机调度中，批加工时间等于批内所有工件在批处理机内的加工时间之和，典型生产背景是钢铁的连铸工序；在平行批处理机调度中，批加工时间由批内最大工件所需要的加工时间决定，典型生产背景是半导体制造过程的老化测试工序，在模具热处理的生产过程中，同时具有串行批和平行批的加工特征，热处理炉允许多个工件在炉中同时加工，每个批次的加工时间由加热时间和保温时间组成，加热时间由批中工件的总重量决定，具有串行批调度的特征；而保温时间由最大尺寸工件所需要的保温时间决定，具有平行批调度的特征。虽然近年来两种批调度问题分别出现了很多具有针对性的生产调度方法，然而都尚未考虑到同时具有串行批调度和平行批调度特征的调度方法，特别在车间具有多台同等批处理机的情况下，需要新的具有针对性的技术方法才能提高生产效率。

发明内容

[0003] 针对上述背景技术的阐述，本发明提供批加工时间受总重量和最大尺寸双重约束的车间调度方法，同时考虑串行批调度和平行批调度特征，解决了现有技术具有多台同等批处理的调度的技术问题。

[0004] 为了达到上述目的，本发明提供如下技术方案：

[0005] 批加工时间受总重量和最大尺寸双重约束的车间调度方法，包括步骤：

[0006] Q1：按工件尺寸非增排序，并将工件序列标记为L；

[0007] Q2：读取最先空闲的机器并开启一个新的批次，将该机器的空闲时刻作为该批次的开始加工时间；

[0008] Q3：如果在机器空闲时刻，已到达的待加工工件总重量大于机器容量，那么按序列L的次序组批，转到Q6，否则，将待加工工件放到当前批次，转到Q4；

[0009] Q4：设置机器最大空闲等待时间为1/2装载时间s，如果当前批次是空的，那么将当前批次的最晚开始时间设置为下一工件的到达时间加上s/2；否则，当前批次的最晚开始时间设置为机器的空闲时刻加上s/2；

[0010] Q5：按照序列L中的顺序检索所有后续工件，如果工件的到达时间小于当前批次的最晚开始时间，并且当前批次能够容纳该工件，则将工件放到该批次中，并更新该批次在机器上的开始加工时间；

[0011] Q6：将当前批次安排到当前机器上，如果所有工件都已经组批完毕，计算最大完成时间并返回调度结果；否则，转到Q2。

[0012] 上述技术方案中，所述批加工时间受总重量和最大尺寸双重约束的车间调度方法的描述为Pm|batch,rj,wj,sj,c|Cmax

[0013] 数学模型如下：

[0014] Min Cmax 公式1

[0015] Subject to:

[0016]

[0017]

[0018]

[0019]

[0020]

[0021]

[0022]

[0023]

[0024] Xji,Yik＝0 or 1   公式10

[0025] 所述数学模型用到的变量和参数：

[0026] 集合:

[0027] J：工件集{j∈J},J＝{1,2,...,n}，n表示工件总数量；

[0028] B：批次集{i∈B},B＝{1,2,...,d}，d表示分批数量上届；

[0029] M:机器集{k∈M},M＝{1,2,...,m}，m表示机器总数量；

[0030] 参数：

[0031] c:设备容量；

[0032] s:装载时间；

[0033] wj:第j个工件的重量；

[0034] sj:第j个工件的尺寸；

[0035] rj:第j个工件的到达时间；

[0036] BigM:数值较大的整数；

[0037] α：装载量权重系数；

[0038] β：工件尺寸权重系数；

[0039] 决策变量：

[0040]

[0041]

[0042] 因变量：

[0043] Pi:第i个批次的加工时间；

[0044] Sik:第i个批次在第k台设备上的开始加工时间；

[0045] Cmax：最大完成时间。

[0046] 本发明提出的具有针对性的本发明技术方案，与其他典型批调度方法相比，具有较好的运算性能，计算速度更快并且平均误差率更低的优点。

具体实施方式

[0047] 下面将结合本发明的实施例，对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0048] 作为实施例所示的批加工时间受总重量和最大尺寸双重约束的车间调度方法，工件首先按尺寸排序而不是到达时间，然后根据机器的空闲时刻为工件组批。当机器出现空闲时，如果到达的待加工工件重量超过机器容量，那么为工件组批并立即加工；否则，等待更多即将到达的工件组批，设置机器最大空闲等待时间为1/2装载时间，具体包括步骤：

[0049] Q1：按工件尺寸非增排序，并将工件序列标记为L；

[0050] Q2：读取最先空闲的机器并开启一个新的批次，将该机器的空闲时刻作为该批次的开始加工时间；

[0051] Q3：如果在机器空闲时刻，已到达的待加工工件总重量大于机器容量，那么按序列L的次序组批，转到Q6，否则，将待加工工件放到当前批次，转到Q4；

[0052] Q4：设置机器最大空闲等待时间为1/2装载时间s，如果当前批次是空的，那么将当前批次的最晚开始时间设置为下一工件的到达时间加上s/2；否则，当前批次的最晚开始时间设置为机器的空闲时刻加上s/2；

[0053] Q5：按照序列L中的顺序检索所有后续工件，如果工件的到达时间小于当前批次的最晚开始时间，并且当前批次能够容纳该工件，则将工件放到该批次中，并更新该批次在机器上的开始加工时间；

[0054] Q6：将当前批次安排到当前机器上，如果所有工件都已经组批完毕，计算最大完成时间并返回调度结果；否则，转到Q2。

[0055] 为具体说明使用批加工时间受总重量和最大尺寸双重约束的车间调度方法，假设的实施例如下：

[0056] 有n个工件需要经过热处理加工，车间有m台相同型号的热处理炉，工件的到达时间rj、重量wj和尺寸sj存在差异。热处理炉可以容纳多个工件同时加工，每一批次装载的工件总重量不能超过热处理炉的容量c。第Bi个批次的加工时间Pi受到该批次的总重量和批中工件最大尺寸的双重约束，用数学式表述为 这里α和β分别装载量权重系数和工件尺寸权重系数.在各批次加工前，需要设备一个工件装载时间s。如果第Bi个批次的开始加工时间用Si表示，那么该批次的完成时间可以表示为Ci＝Si+s+Pi。各批次一旦在热处理炉上开始加工，不允许中途停下来或者插入其他批次。采用调度问题的通用表示方法，求解最小化最大完成时间的车间批调度问题描述为Pm|batch,rj,wj,sj,c|Cmax。

[0057] 建立的数学模型如下：

[0058] Min Cmax 公式1

[0059] Subject to:

[0060]

[0061]

[0062]

[0063]

[0064]

[0065]

[0066]

[0067]

[0068] Xji,Yik＝0 or 1   公式10

[0069] 所述数学模型用到的变量和参数：

[0070] 集合:

[0071] J：工件集{j∈J},J＝{1,2,...,n}，n表示工件总数量；

[0072] B：批次集{i∈B},B＝{1,2,...,d}，d表示分批数量上届；

[0073] M:机器集{k∈M},M＝{1,2,...,m}，m表示机器总数量；

[0074] 参数：

[0075] c:设备容量；

[0076] s:装载时间；

[0077] wj:第j个工件的重量；

[0078] sj:第j个工件的尺寸；

[0079] rj:第j个工件的到达时间；

[0080] BigM:数值较大的整数；

[0081] α：装载量权重系数；

[0082] β：工件尺寸权重系数；

[0083] 决策变量：

[0084]

[0085]

[0086] 因变量：

[0087] Pi:第i个批次的加工时间；

[0088] Sik:第i个批次在第k台设备上的开始加工时间；

[0089] Cmax：最大完成时间；

[0090] 公式1表示目标函数为最小化最大完成时间；公式2表示每个工件必须属于并且只能属于一个批次；公式3表示各批次中工件的总重量不得超过机器的容量；公式4表示各批次加工时间取决于装载量和批中工件最大尺寸；公式5表示每个批次只能属于并且必须属于一台机器；公式6表示各批次的开始加工时间不小于批中工件的到达时间；公式7和公式8表示在同一台机器上，前一批次加工完成后才能开始后一批次的加工；公式9表示所有工件的完成时间必须大于最后一批的完成时间；公式10表示决策变量的取值范围。

[0091] Pm|batch,rj,wj,sj,c|Cmax问题最优解的下界可以通过以下数学式计算出来:

[0092]

[0093] 公式11中的第一项表示最大完成时间Cmax必须不小于所有工件的最早完成时间，第j个工件的最早完成时间我们可以通过表达式rj+s+α*wj+β*sj计算出来；公式11中的第二项表示所有批次的最早开始时间不小于minj∈J{rj}。如果只有一台机器，那么在这台设备上的加工时间至少为α∑j∈Jwj+[∑j∈Jwj/c]{s+βminj∈J{sj}}。在理想情况下，各台机器的加工时间刚好相同，这时各台机器的加工时间为

[0094] 在步骤Q1中，按尺寸为所有工件排序计算复杂度为O(n logn)；步骤Q2到步骤Q6，为工件组批计算复杂度为O(n^2)，因为n个工件最多分成n个批次，在最坏情形下，步骤Q3到步骤Q5需要检索整个工件序列1次。

[0095] 对于Pm|batch,rj,wj,sj,c|Cmax问题的最坏情形界为2(m+maxj∈J{sj}/minj∈J{sj})。

[0096] 假设在本发明技术方案中所有工件被分成b个批次，设Si为第Bi个批次的开始加工时间，Pi为第Bi个批次的加工时间， 为调度方法得到的最大完成时间， 为最大完成时间的最优解，调度方法得到的调度结果可以分成以下三种情形：

[0097] (1)如果在最后一个批次开始加工前机器刚好出现空闲等待，在这种情况下，说明在最后一个批次Bb的开始加工时刻刚好有工件到达。显然， 并且因此，

[0098] (2)假设除了最后一个批次，每次机器出现空闲时已到达的待加工工件重量都超过机器容量。那么在调度方法中，所有机器将会连续加工，并且分批数量不会多于最少分批数量的两倍，因为任何两个相邻批次的重量之和超过机器容量。

[0099] 设T为最优调度方案的总加工时间，显然可以得到，Pb

[0100] (3)假设批次Bi到Bb-1满足每次机器出现空闲时，已到达待加工工件的重量超过机器容量，但是Bi-1不满足这一条件；假设从第Bi-1个批次的开始加工时刻Si-1起，经过时间T1，每台机器至少空闲一次。假设批次Bi到Bb中的工件在最优调度方案中需要总加工时间T2。

[0101] 那 么 显 然 可 以 得 到 ， P b < T 2 和因此，
如果批次Bi到Bb-1不存在，即没任何批
次满足上述条件，在这种情况下， 将会变为 此时，

[0102] 结合以上三种情形，调度方法能够保证Pm|batch,rj,wj,sj,c|Cmax问题的最坏情形界为2(m+maxj∈J{sj}/minj∈J{sj})。

[0103] 实施例仿真及结果分析

[0104] 1、小规模调度问题

[0105] 通过8个工件的小规模算例验证数学模型的运算性能，工件的到达时间(rj),重量(wj)和尺寸(sj)如表1所示。批次装载时间为2，重量权重系数和尺寸权重系数分别为1和3，即 有两台同等批处理机，机器容量都为15，分别命名为M1和M2。通过公式11求解，最大完成时间的下界为35。MWT规则算法的最大完成时间是59。

[0106] 表1.工件J1-J8的到达时间(rj),重量(wj)和尺寸(sj)

[0107]

[0108] 2、大规模调度问题

[0109] 通过大规模算例验证所提启发式算法的有效性，使用MATLAB进行编程仿真，算例参数通过以下方式产生：

[0110] 工件数量(n):50,100,200,400,1000 and 2000；

[0111] 机器数量(m):3,4 and 5；

[0112] 工件Jj的重量(wj):rand int(10,50)；

[0113] 工件Jj的尺寸(sj):2wj；

[0114] 机器容量(c):200,300 and 400；

[0115] 装载时间(s):randint(60,100)；

[0116] 第Bi批次的加工时间:

[0117] 时间强度(ρ)表示加工需求与加工能力之间的关系。假设机器容量为300，所有工件尺寸都为30，所有批次都装满，那么当时间强度为0.026时，加工需求刚好达到最大加工能力。时间强度越小，加工需求也就越少。时间强度这里假设三个等级：0.07、0.1和0.2。

[0118] 工件Jj的到达时间(rj):randint(0,n/(ρ*m)).

[0119] 每一种参数组合分别产生40组算例进行求解，调度方法的运算时间少于4.5秒。

[0120] 表2.不同工件数量下各种启发式算法的平均运算速度(秒)

[0121]

[0122] 以下通过误差率(Dev)来对比各种算法的运算性能。例如，本发明的误差率定义如下：

[0123]

[0124] 上式中, 表示由本发明得到的解， 表示由公式11计算得到的最优解下界，当c＝300,m＝4和n＝1000时，三种时间强度的误差率均小于40％。

[0125] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。