考虑工期指派的最小化误工损失优化方法

1.本发明涉及产品生产过程的调度优化领域，具体为一种考虑工期指派的最小化误工损失优化方法。


背景技术：

2.工期指派问题(due date assignment)拓展了经典调度问题中工期为已知参数的假设，将工期作为一个决策变量，连同调度方案一起进行优化决策，以最小化误工损失(late work)、提前(earliness)和拖期(tardiness)等工期相关的惩罚。一个典型应用场景为准时制生产(just-in-time,jit)，若工期承诺越近越能吸引订单，但存在订单延误而支付拖期费用的风险；若工期承诺越远越能保证加工完成度，但存在增加库存成本的风险。因此，工期指派需要均衡工期承诺收益及拖期惩罚两个目标，尽可能缩短订单工期并避免拖期费用。工期指派问题根据工期与工件的相关性分为共同工期指派模型和不同工期指派模型：不同工期指派(different due date assignment)指每个工件都有不同的工期且工期的分配不受任何限制；共同工期指派(common due date assignment)指所有工件具有相同的工期。
3.在生产系统中，误工损失用来衡量工件在工期后完工部分的加工损失，其本质是在传统延误(tardiness)惩罚定义了上界，该上界等于工件加工时间。与延误(tardiness)不同，误工损失最多为工件加工长度且不随完工时间增大而增大，而延误则会随着完工时间的增大一直增大。误工损失应用的典型场景有：(1)生产交付中误工订单赔偿。逾期完工的订单需要支付一定的惩罚费用。该惩罚费用会随着逾期延长而增加，但不超过逾期订单本身价值；(2)计算机控制系统(computer control system，ccs)中的延迟信息损失。传感器采集信息在控制计算开始前到达视为有效信息，若出现输入延迟信息则视为无效信息。延迟信息导致计算信息的损失，其损失量不超过其本身信息的承载量。(3)易腐品销售中过期产品损失。超过保质期的产品会被直接下架，造成的经济损失为过期产品的价值。


技术实现要素：

4.为解决现有技术存在的问题，本发明提出一种考虑工期指派的最小化误工损失优化方法，在给定排产顺序π下，确定最优工期指派方案，并针对共同工期情形和等加工时间情形，分别给出最优的工期指派和工件排产方案。
5.本发明的技术方案为：
6.所述一种考虑工期指派的最小化误工损失优化方法，包括以下步骤：
7.步骤1：建立考虑工期指派的最小化误工损失优化模型：
8.给定n个独立的工件j＝{j1,j2,
…
,jn}在一台机器上进行加工；每一个工件jj，都具有固定的加工时间pj，顾客提交订单时的可接受工期aj，以及生产商根据生产能力反馈的承诺工期dj，j＝1,
…
,n；当承诺工期超过顾客可接受工期时，会因无法满足顾客需求造成信誉损失，产生工期指派成本rj＝max{d
j-aj,0}；如果承诺的工期过小，则会造成工件无法
在预定工期内完成，造成误工损失yj＝min{max{c
j-dj,0},pj}；模型的优化目标是最小化加权总工期指派成本和误工损失；cj为工件jj的完工时间；
9.步骤2：在给定排产方案π下，确定最优工期指派方案：
10.对于给定排产方案π，存在最优的工期指派方案使得任一工件jj∈j的最优工期dj为0,aj或cj；其中
11.如果cj≤aj，那么工件jj的最优工期dj＝cj；
12.如果aj《cj《aj+pj，那么若αj≥βj，工件jj的最优工期dj＝aj，若αj《βj，工件jj的最优工期dj＝cj；其中αj为工件jj的工期指派费用权重，βj为工件jj的误工损失权重；
13.如果aj+pj≤cj，那么若工件jj的最优工期dj＝0，若工件jj的最优工期dj＝cj；
14.合并不同情形下的工期指派方案，得到最优的工期指派方案d
*
(π)：
15.如果αj≥βj，工件jj的最优工期为
[0016][0017]
如果αj《βj，工件jj的最优工期为
[0018][0019]
步骤3：针对共同工期情形：
[0020]
对于给定的共同工期d，工件排产的最优顺序π
*
为βj非增的顺序；
[0021]
并针对最优的工件排产顺序π
*
，如果则最优共同工期否则，d
*
＝lk为最优共同工期，其中lk满足f(l
k-1
)+g(l
k-1
)≤0和f(lk)+g(lk)≥0；
[0022]
f(d)代表的斜率，g(d)代表的斜率，记a
′1,
…
,a
′n为a1,
…
,an非减的顺序，α
′j为a
′j对应工件的权重，则：
[0023][0024]
和
[0025][0026]
针对等加工时间情形：
[0027]
采用线型指派模型求解问题：如果工件jj在第i个位置加工，则其完工时间为cj＝ip，相应的目标函数值为w
ij
＝min{max{αj(ip-aj),0},βjpj}；定义决策变量x
ij
：
[0028][0029]
线型指派模型：
[0030][0031]
s.t.
[0032][0033][0034]
通过求解线型指派模型，得到等加工时间情形的最优工件排产顺序。
[0035]
有益效果
[0036]
本发明提出了一种考虑工期指派的最小化误工损失方法，通过建立考虑工期指派的最小化误工损失调度模型，剖析问题最优解特性，缩小了最优工期指派的取值范围，得到了给定排产方案下的最优工期指派方案。基于最优工期指派方案，判定了问题复杂性，并针对共同工期情形和等加工时间情形，分别给出了多项式时间的最优算法。本发明从实际需求出发，将工期已知拓展到了工期决策，将传统的拖期惩罚拓展到了误工损失惩罚，为实际生产中的工期决策和误工损失优化提供了理论依据。
[0037]
本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0038]
本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：
[0039]
图1：z(π
*
,d)与工期d的v-形关系。
具体实施方式
[0040]
在生产系统中，为了最小化误工损失，需要考虑以下优化过程：
[0041]
如何得到合理的承诺工期：如果企业承诺的工期远超客户的可接受工期，则会存
在失去客户的风险；如果企业承诺工期过小，则能吸引客户，但同时面临无法按时交付误工损失惩罚；对应就是如何优化工件排产方案，以最小化误工损失。在实际优化工件排产方案过程中，为实现较小的误工损失，直观上承诺工期小的工件适合尽早加工，承诺工期大的可以适当延后，但为量化权衡标准，还需考虑的众多影响因素，如工件加工时间、客户可接受工期、承诺工期大小等。对于该优化问题，还要判定问题复杂性，即要从理论上判断问题是否是np-困难的，然后考虑设计近似/最优求解算法。
[0042]
具体的，本发明提出的考虑工期指派的最小化误工损失优化方法，从实际需求出发，将工期已知拓展到了工期决策，将传统的拖期惩罚拓展到了误工损失惩罚，以解决实际生产中的工期决策和误工损失优化的难题，针对考虑工期指派决策和工件加工排产的双层调度优化问题，建立考虑工期指派成本的最小化误工损失调度模型，建立考虑工期指派成本的最小化误工损失调度模型；通过对问题特性分析，给出最优的工期指派方案，并判断问题复杂性；针对共同工期情形和等加工时间情形，分别给出最优工件排产方案。
[0043]
具体问题模型描述如下：
[0044]
给定n个独立的工件j＝{j1,j2,
…
,jn}在一台机器上进行加工。每一个工件jj，都具有固定的加工时间pj，顾客提交订单时的可接受工期aj，以及生产商根据生产能力反馈的承诺工期dj，j＝1,
…
,n。当承诺工期超过顾客可接受工期时，会因无法满足顾客需求造成信誉损失，产生工期指派成本rj＝max{d
j-aj,0}。然而，如果承诺的工期过小，则会造成工件无法在预定工期内完成，造成误工损失yj＝min{max{c
j-dj,0},pj}。目标是最小化加权总工期指派成本和误工损失。
[0045]
具体的，对于工期决策问题，针对任意给定的排产方案，分析完全提前工件(即cj≤dj)、部分提前工件(即dj《cj《dj+pj)和完全误工工件(即dj+pj≤cj)的工期的指派极值，得到问题1|dif|z(π,d)最优的工期指派方案d
*
。
[0046]
进而将问题转化为最小化加权总拖期惩罚的问题，判断问题1|dif|z(π,d)的复杂性。
[0047]
最后对于工件排产问题，针对共同工期问题1|dj＝d|z(π,d)和等加工时间的问题1|pj＝p|z(π,d)，分别给出最优的工期指派和工件排产方案。
[0048]
本文中的所需的符号说明如表1所示。
[0049]
表1符号说明
[0050]
[0051][0052]
下面给出具体分析过程：
[0053]
(一)给出理论依据：
[0054]
任一给定排产方案，存在最优的工期指派方案使得任一工件jj∈j的最优工期dj为0,aj或cj。
[0055]
证明：令π是任一给定的排产方案。令d＝(d1,
…
,dn)为最优的工期指派方案。我们分别讨论jj为一个完全提前工件(在dj之前完工)，部分提前工件(在dj和dj+pj之间完工)和完全误工工件(在dj之后完工)三种情形。
[0056]
情形1.工件jj为一个完全提前工件。
[0057]
如果工件jj为一个完全提前工件(cj《dj)，则d
j-cj＝δ》0。令d
′
为仅修改工件jj后的新的工期指派方案，新工期d
′
＝cj。我们有z(π,d)-z(π,d
′
)＝zj(dj＝cj+δ)-zj(dj＝cj)＝α
j max{cj+δ-aj,0}-max{c
j-aj,0}。如果cj≥aj，z(π,d)-z(π,d
′
)＝αjδ≥0.如果cj《aj，则z
(π,d)-z(π,d
′
)＝α
j max{cj+δ-aj,0}≥0。以上两种情形中，z(π,d)-z(π,d
′
)均为非负，因此我们令dj＝cj不会增加目标函数值。
[0058]
情形2.工件jj为一个部分提前工件。
[0059]
如果工件jj为一个部分完全提前工件，则dj∈[0,c
j-pj]。工期指派惩罚α
j max{d
j-aj,0}关于dj在[0,c
j-pj]内非减。又因为当dj在[0,c
j-pj]，误工损失yj＝β
j min{max{c
j-dj},0},pj}是一个常数，所以我们令dj＝0不会增加目标函数值。
[0060]
情形3.工件jj为一个完全误工工件。
[0061]
如果工件jj为一个完全误工工件(cj》dj+pj)，使得0《c
j-dj＝δ《pj，我们断言c
j-pj≤aj《cj。我们采用反证法证明。如果aj≥cj，我们有zj(dj＝cj)＝0《zj(dj＝c
j-δ)＝βjδ，与d是最优的工期指派方案矛盾。如果aj《cj，我们有zj(dj＝aj)＝βjpj,zj(dj＝c
j-δ)＝αj(c
j-δ-aj)+βjδ和zj(dj＝cj)＝αj(c
j-aj)。当βj≤αj，zj(dj＝c
j-δ)≥βj(c
j-δ-aj)+βjδ＝βj(c
j-aj)》βjpj＝zj(dj＝aj)，与d是最优的工期指派方案矛盾。当βj》αj，zj(dj＝c
j-δ)＝αj(c
j-δ-aj)+βjδ》αj(c
j-aj)＝zj(dj＝aj)，与d是最优的工期指派方案矛盾。
[0062]
因此断言成立。
[0063]
此外，我们断言，对于部分提前的工件βj≤αj。通过反证法，如果βj》αj，那么zj(dj)在区间[c
j-pj,cj]之内关于dj递减，因而z(dj＝cj)《zj(dj＝c
j-δ)，与d是最优的工期指派方案矛盾。
[0064]
因此我们有c
j-pj≤aj《cj和βj≤αj，zj(dj)在区间[c
j-pj,aj]之内关于dj递减，在区间[aj,cj]之内关于dj非减。这样我们令dj＝aj不会增加目标函数值。
[0065]
根据上述理论依据，对比zj(dj＝0)，zj(dj＝aj)和zj(dj＝cj)的值，即可得到最优工期指派。
[0066]
(二)在给定排产方案下，通过讨论完工时间cj与aj和aj+pj不同关系下的zj(dj＝0)，zj(dj＝aj)和zj(dj＝cj)的值，给出相应的工期指派方案：
[0067]
(1)如果cj≤aj，那么工件jj的最优工期dj＝cj。
[0068]
(2)如果aj《cj《aj+pj，那么若αj≥βj，工件jj的最优工期dj＝aj；若αj《βj，工件jj的最优工期dj＝cj。
[0069]
(3)如果aj+pj≤cj，那么若工件jj的最优工期dj＝0；若工件jj的最优工期dj＝cj。
[0070]
证明：
[0071]
性质(1)。当cj≤aj，我们有zj(dj＝0)＝βjpj，zj(dj＝cj)＝0和zj(dj＝aj)＝0。因为zj(dj＝cj)＝zj(dj＝aj)《zj(dj＝0)，所以令dj＝cj是最优的。
[0072]
性质(2)。当aj≤cj≤aj+pj，我们有zj(dj＝0)＝βjpj，zj(dj＝cj)＝βj(c
j-aj)和zj(dj＝cj)＝αj(c
j-aj)。
[0073]
若αj≥βj，zj(dj＝aj)《zj(dj＝0)和zj(dj＝aj)≤zj(dj＝cj)，因此令dj＝aj最优。
[0074]
若αj《βj，zj(dj＝cj)≤zj(dj＝aj)《zj(dj＝0)，因此令dj＝cj最优。
[0075]
性质(3)。当aj+pj≤cj，我们有zj(dj＝0)＝zj(dj＝aj)＝βjpj，zj(dj＝cj)＝αj(c
j-aj)。
[0076]
若zj(dj＝0)＝zj(dj＝aj)《zj(dj＝cj)，因此令dj＝0最优。
[0077]
若αj《βj，zj(dj＝cj)≤zj(dj＝0)《zj(dj＝aj)，因此令dj＝cj最优。
[0078]
(三)基于第(二)步的分析，合并不同情形下的工期指派方案，可以得到对于问题1|dif|z(π,d)，任一给定工件排产方案π，存在最优工期指派方案|dif|z(π,d)，任一给定工件排产方案π，存在最优工期指派方案
[0079]
如果αj≥βj，工件jj的最优指派工期为
[0080][0081]
如果αj《βj，工件jj的最优指派工期为
[0082][0083]
(四)基于第(三)步的最优工期指派方案d
*
(π)，我们可以得到目标函数值其中，
[0084]
如果αj≥βj，
[0085][0086]
如果αj《βj，
[0087][0088]
(五)将问题转化为其中或写成分段函数：
[0089]
[0090]
证明：在第(四)步中，观察到对于αj≥βj的工件，αj的值不影响目标值，因此我们可以对所有αj≥βj的工件重新设定αj′
＝βj。这样我们就得到了一个新的实例，该实例满足αj′
≤βj，对于j＝1,
…
,n。因为这两个问题具有相同的目标函数值，所以可以简写为步骤5中的公式。
[0091]
(六)因为问题是强np-困难的，作为推论问题1|dif|z(π,d)也是强np-困难的。
[0092]
证明：考虑问题的实例：我们有这样，
[0093][0094]
因为这种情况下的实例，该问题等价于单机上最小化加权拖期惩罚的问题，即其中tj＝max{0,c
j-dj}。因为是强np-困难的，所以我们的问题也是np-困难的。
[0095]
(七)研究共同工期情形1|dj＝d|z(π,d)，即dj＝d,j＝1,
…
,n，并给出o(nlog n)时间的最优算法。
[0096]
(1)最优排产方案：
[0097]
对于任一给定的共同工期d，工件排产的最优顺序π
*
为βj非增的顺序。
[0098]
证明：我们考虑的目标函数证明：我们考虑的目标函数对于任一给定的共同工期d，为常数，因此我们的目标为最小化因为问题的最优顺序为βj非增的顺序，所以工件排产的最优顺序为βj非增的顺序。
[0099]
(2)问题性质：
[0100]
如果工件排产按照βj非增的顺序排产，则z(π
*
,d)在区间内关于d递减，或如图1所示呈先递减后递增的v-形，其中，l1,
…
,l
p
(p≤2n)为c1,
…
,cn,a1,
…
,an的非减顺序。
[0101]
证明：假设工件按照βj非减的顺序进行重新标号，f(d)代表非减的顺序进行重新标号，f(d)代表的斜率，g(d)代表的斜率。记a
′1,
…
,a
′n为a1,
…
,an非减的顺序，α
′j为a
′j对应工件的权重。我们有性质1：
[0102][0103]
性质2：
[0104][0105]
针对性质1，如果d∈[a
′j,a
′
j+1
),j＝1,
…
,n-1，那么1，那么因此，对于d∈[a
′j,a
′
j+1
),j＝1,
…
,n-1，有如果d∈[0,a
′1)，f(d)＝0。如果d∈[a
′n,∞)，因此性质1成立。
[0106]
针对性质2，如果d∈[cj,c
j+1
),j＝1,
…
,n-1，那么1，那么因此，对于d∈[cj,c
j+1
),j＝1,
…
,n-1，有g(d)＝-β
j+1
。如果d∈[0,c1)，g(d)＝-β1。如果d∈[cn,∞)，g(d)＝0。因此性质2成立。
[0107]
根据性质1和2，我们有f(0)+g(0)＝-β1，以及f(d)+g(d)在区间内关于d非减。因此如果则z(π
*
,d)在区间内关于d递减；如果则z(π
*
,d)在区间内关于d呈v-形。
[0108]
(3)最优指派工期。
[0109]
针对最优的工件排产顺序π
*
，如果则最优共同工期否则，d
*
＝lk为最优共同工期，其中lk满足f(l
k-1
)+g(l
k-1
)≤0和f(lk)+g(lk)≥0。
[0110]
(4)算法复杂度分析。
[0111]
在(1)中确定的最优排产方案，按照非增顺序排列βj耗时o(nlog n)，在(2)和(3)中确定最优共同工期，这里用二分法寻找最优共同工期耗时o(logn)，所以问题求解的时间复杂度为o(nlog n)。
[0112]
(八)研究工件等加工时间情形1|pj＝p|z(π,d)，即pj＝p,j＝1,
…
,n，并给出o(n3)时间的最优算法。
[0113]
(1)问题转化。
[0114]
根据第(五)步，我们将问题转化到
进行求解。
[0115]
(2)将问题刻画为线型指派模型。
[0116]
由于所有的工件加工时间均为p，所以工件的完工时间cj∈{p,2p,
…
,(n-1)p,np}。如果工件jj在第i个位置加工，则其完工时间为cj＝ip，相应的目标函数值为w
ij
＝min{max{αj(ip-aj),0},βjpj}。定义决策变量x
ij
:
[0117][0118]
问题转化为线型指派模型：
[0119][0120]
满足
[0121][0122][0123]
x
ji
∈{0,1},1≤j≤n,1≤i≤n.
[0124]
(3)因为线型指派模型能够在o(n3)之间内解决，所以问题1|pj＝p|z(π,d)也能在o(n3)时间内解决。即通过在(n3)之间内求解线型指派模型，得到问题)之间内求解线型指派模型，得到问题的最优工件排产顺序。
[0125]
通过上述研究过程，本发明主要实现了：
[0126]
(1)给定排产顺序π下，最优工期指派方案；
[0127]
(2)判定问题属于强np-困难的；
[0128]
(3)针对共同工期情形和等加工时间情形，分别给出了o(nlog n)时间和o(n3)时间的最优算法。
[0129]
具体地，针对(1)，可以根据排产顺序π计算每个工件的完工时间cj,j＝1,
…
,n，然后依据第三步中公式执行最优工期分配。
[0130]
针对(2)，通过将问题归结到已知的强np-困难的最小化加权拖期惩罚的问题，即并据此判定了1||z(π,d)是强np-困难的。
[0131]
针对(3)，对于同工期情形1|dj＝d|z(π,d)，首先按照βj非增的顺序排序，然后按照二分法确定最优的共同工期大小，并且证明了其正确性；对于等加工时间情形1|pj＝p|z(π,d)，首先将其转化到然后再将问题归结到线型指派模型进行求解，并且证明了其正确性。
[0132]
尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例
性的，不能理解为对本发明的限制，本领域的普通技术人员在不脱离本发明的原理和宗旨的情况下在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。

技术特征：
1.一种考虑工期指派的最小化误工损失优化方法，其特征在于：包括以下步骤：步骤1：建立考虑工期指派的最小化误工损失优化模型：给定n个独立的工件j＝{j1,j2,
…
,j
n
}在一台机器上进行加工；每一个工件j
j
，都具有固定的加工时间p
j
，顾客提交订单时的可接受工期a
j
，以及生产商根据生产能力反馈的承诺工期d
j
，j＝1,
…
,n；当承诺工期超过顾客可接受工期时，会因无法满足顾客需求造成信誉损失，产生工期指派成本r
j
＝max{d
j-a
j
,0}；如果承诺的工期过小，则会造成工件无法在预定工期内完成，造成误工损失y
j
＝min{max{c
j-d
j
,0},p
j
}；模型的优化目标是最小化加权总工期指派成本和误工损失；c
j
为工件j
j
的完工时间；步骤2：在给定排产方案π下，确定最优工期指派方案：对于给定排产方案π，存在最优的工期指派方案使得任一工件j
j
∈j的最优工期d
j
为0,a
j
或c
j
；其中如果c
j
≤a
j
，那么工件j
j
的最优工期d
j
＝c
j
；如果a
j
<c
j
<a
j
+p
j
，那么若α
j
≥β
j
，工件j
j
的最优工期d
j
＝a
j
，若α
j
<β
j
，工件j
j
的最优工期d
j
＝c
j
；其中α
j
为工件j
j
的工期指派费用权重，β
j
为工件j
j
的误工损失权重；如果a
j
+p
j
≤c
j
，那么若工件j
j
的最优工期d
j
＝0，若工件j
j
的最优工期d
j
＝c
j
；合并工期指派方案，得到最优的工期指派方案d
*
(π)；步骤3：针对共同工期情形：对于给定的共同工期d，工件排产的最优顺序π
*
为β
j
非增的顺序；并针对最优的工件排产顺序π
*
，如果则最优共同工期否则，d
*
＝l
k
为最优共同工期，其中l
k
满足f(l
k-1
)+g(l
k-1
)≤0和f(l
k
)+g(l
k
)≥0；f(d)代表的斜率，g(d)代表的斜率，记a
′1,
…
,a
′
n
为a1,
…
,a
n
非减的顺序，α
′
j
为a
′
j
对应工件的权重，则：和针对等加工时间情形：
采用线型指派模型求解问题：如果工件j
j
在第i个位置加工，则其完工时间为c
j
＝ip，相应的目标函数值为w
ij
＝min{max{α
j
(ip-a
j
),0},β
j
p
j
}；定义决策变量x
ij
：线型指派模型：s.t.s.t.通过求解线型指派模型，得到等加工时间情形的最优工件排产顺序。2.根据权利要求1所述一种考虑工期指派的最小化误工损失优化方法，其特征在于：步骤2中，最优的工期指派方案d
*
(π)为：如果α
j
≥β
j
，工件j
j
的最优工期为如果α
j
<β
j
，工件j
j
的最优工期为

技术总结
本发明提出一种考虑工期指派的最小化误工损失优化方法，通过建立考虑工期指派的最小化误工损失调度模型，剖析问题最优解特性，缩小了最优工期指派的取值范围，得到了给定排产方案下的最优工期指派方案。基于最优工期指派方案，判定了问题复杂性，并针对共同工期情形和等加工时间情形，分别给出了多项式时间的最优算法。本发明从实际需求出发，将工期已知拓展到了工期决策，将传统的拖期惩罚拓展到了误工损失惩罚，为实际生产中的工期决策和误工损失优化提供了理论依据。失优化提供了理论依据。失优化提供了理论依据。


技术研发人员：王军强 桑耀文 孙涛 林冉
受保护的技术使用者：西北工业大学
技术研发日：2023.06.24
技术公布日：2023/10/15