2. 问题描述
考虑如下的问题:n个独立且在零时刻到达的工件需要在一台机器上加工,在同一时刻机器最多只能加工一个工件,所有工件必须连续加工不能中断。本文中凸资源消耗模型中工件的实际加工时间表达式为
其中是一个表示分配给工件工作量的正参数,m表示一个恒定的正值,表示学习指数,为分配给工件的不可再生的资源数量,r为工件所在位置,工件的开始加工时间为,为公共退化率。
对于给定排序,令表示工件在排序π下的完工时间,,分别表示最大完工时间和总完工时间。所有的工件有一个公共工期窗口,和分别表示工期窗口开始时间和结束时间,表示工期窗口的大小。如果一个工件在工期窗口开始时间d之前完成,则会导致提前惩罚,另一方面,如果一个工件在工期窗口结束时间ω之后完工,则会造成延误惩罚。对于给定排序,我们用和分别表示提前量和延误量,即,,其中表示工件在排序π下的第j个位置。决策变量为π,d,u,ω。
问题1:目标是求出最优资源分配和最优工件排序,最优交货期窗口位置d,ω,使带有提前、延误、工期窗口位置、工期窗口大小、资源总费用,最大完工时间以及总完工时间的总和最小,即目标函数为
其中为给定常数。
问题2:目标是在资源消耗总费用不大于常数的前提下,求出最优资源分配方案和最优工件排序,最优交货期窗口位置d,ω,使带有提前、延误、工期窗口位置、工期窗口大小、总完工时间、完工时间绝对差的总和最小,即目标函数为
问题3:目标是在不大于常数的前提下,决定最优工期窗口和的位置,最优资源分配及最优排序使总资源消耗量最小,所以目标函数为
使用文献 [16] 的三参数表示法,可将上述问题分别表示为:
(1)
(2)
(3)
3. 最优算法
3.1. 最优解性质
首先在最优排序下,首个工件在0时刻开始加工,工件之间无空闲时间。
引理1:对于排序,工件的完工时间和实际加工时间分别为
(4)
(5)
引理2:对于任何给定排序,存在一个最优公共工期窗口,其中工期窗口的开始时间d和结束时间ω与某些工件的完工时间一致。
证明存在一个排序π,从0时刻开始加工,,,其中,令,,则,。和分别表示和的实际加工时间。
工件提前的总费用为
工件延误的总费用为
工期窗口开始时间费用为
工期窗口大小费用为
最大完工时间费用为
完工总时间费用为
因此,总费用可以表示为,
其中,,
,为恒定常数,与无关。为了最小化总成本,下列条件之一成立:
1) 如果且,则,;
2) 如果且,则,;
3) 如果且,则,;
4) 如果且,则,。
故我们得到结论:存在一个最优排序,工期窗口的开始时间d和结束时间ω与某些工件的完工时间一致。引理2证毕。
引理3:存在一个最优排序,工期窗口的开始时间,其中,工期窗口结束时间,其中。表示不超过x的最大整数。
证明:详细证明见文献 [17] ,略。
3.2. 最优算法
问题1对于公共工期排序问题,显然,k是独立于排序π与实际加工时间的,因此,对于问题1我们有
,
,
(6)
其中
(7)
且
(8)
引理4:问题(1)中对于给定的工件排序,最优资源分配为(9)
引理5:参考文献 [17] 给定两个数列和,。其中一个数列按递增顺序排列,另一个数列按递减顺序排列,则对应元素乘积和最小。
将等式(9)代入到等式(6)中,得到
(10)
其中由等式(8)中结果,显然,若使等式(10)中所给的极小化等价于极小化的值。根据分析以及引理2-5,得到问题(1)的一个算法。
算法1
第一步 根据引理2,计算出k与q的值;
第二步 对于,计算出和的值,由等式确定;
第三步 根据引理5得到,最优排序;
第四步 根据等式(9)计算出最优资源分配;
第五步 应用等式(5)计算出最优排序中每个工件的加工时间;
第六步 令,;
第七步 通过等式(10)计算最优值。
定理1:对于问题1):可以通过求解匹配问题在时间内求得最优解。
证明:定理结论的正确性由上述分析保证。第一、二、四、五、六步可以在线性时间内完成,
第三步需要时间内完成,所以算法的时间复杂性为。证毕。
问题2):在本部分中,求出问题(2)的最优解
引理6:问题2)对于给定排序最优资源分配如下:
(11)
证明:对于给定排序,拉格朗日函数为
其中λ为拉格朗日乘子。分别对求偏导,令其为零,得
(12)
(13)
利用(12)和(13)得到
, , (14)
(15)
由(14)和(15)我们得到(11)。证毕。
将等式(11)带入到目标函数中,得到
(16)
根据上述分析以及引理2-5,得到问题(2)的一个算法。
算法2
第二步 对于。计算出和的值,由等式(8)计算得到;
第三步 由引理5得,最优排序;
第七步 通过等式(16)计算最优值。
定理2:对于问题(2)可以通过求解匹配问题在时间内求得最优解。
证明:类似于定理1证明,从略。
问题(3) 在这个部分里,求出问题(3)的最优解。首先,与引理6类似,有
引理7:问题(3)对于给定排序可以得到最优资源分配如下:
(17)
将式(17)代入中,得
(18)
根据上述分析以及引理2-5,得到问题(3)的一个算法。
算法3
第三步 根据引理5得,最优排序;
第四步 根据等式(17)计算出最优资源分配;
第七步 通过等式(18)计算最优值。
定理3:对于问题(3)可以通过求解匹配问题在时间内求得最优解。
4. 结论
本文研究的是具有学习效应和退化效应且加工时间是关于资源的凸函数并且带有公共工期窗口的问题。本文列举了三种问题,第一种是使带有提前,延误,公共工期开始时间,工期窗口大小,资源成本费用,最大完工时间以及总完工时间和最小的问题;第二种是资源费用受限的情况下,极小化带有提前,延误,公共工期开始时间,工期窗口大小,资源成本费用,最大完工时间以及总完工时间和问题。第三种是在带有提前,延误等总费用受限的情况下,极小化总资源量。我们分别给出了目标函数求得最小值的最优算法,并证明问题是多项式时间可解的,并确定最优排序及最优资源分配,将问题转化为匹配问题证明问题在多项式时间內可解,并给出了相应的多项式时间算法。
基金项目
国家自然科学基金资助项目(11171050)。
参考文献