1. 引言
在实际的生产过程中,工件的加工时间可能与工件所排位置和其开始加工时间有着某种联系,即工件具有学习和恶化效应。学习效应产生的背景是工件的加工时间会随着机器(比如技术工人)熟练度的提升、机器磨合度的增加等因素而使后来加工的工件实际加工时间变短(Biskup [1],王吉波等 [2],王雪茹等 [3] )。恶化效应产生的背景是在钢铁制造业,钢坯在加工的过程中需要温度的限制,如果钢坯不能马上加工,即需要等待,则它的温度会降低,从而导致开始加工时间越晚,加工时间越长(Gawiejnowicz [4],王吉波等 [5],王吉波和赵伯来 [6] )。Lee [7] 首次考虑了工件同时具有学习与恶化效应的排序问题,即工件
的实际加工时间为
和
,
,其中
为工件
的恶化率,
为正常加工时间,r为工件所排的位置,
为所有工件的学习因子,t为工件
的开始加工时间。在单机情况下,他证明了一些正则目标函数是多项式时间可解的。Wang [8] 也考虑了工件同时具有学习与恶化效应的排序问题,即工件
的实际加工时间为
,其中
为工件的正常加工时间,
为恶化率。在单机情况下,他证明了最大完工时间和总完工时间极小化问题都是多项式时间可解的,加权总完工时间和最大延误极小化问题在一些特殊情况下是多项式时间可解的。在流水作业情况下,他对一些特殊情况,证明了最大完工时间、总完工时间,加权总完工时间和最大延误极小化问题也都是多项式时间可解的。Yang和Kuo [9] 考虑了工件同时具有学习与恶化效应的排序问题,即工件
的实际加工时间为
,其中
为工件
的学习因子。他们证明了一些正则和非正则目标函数是多项式时间可解的。
最近,王吉波等 [10] 研究了同文献 [9] 一样的加工时间模型,在工件具有共同工期(CON)指派下,他们证明了在共同工期指派下的独立位置权重问题是多项式时间可解的。在准时制生产模式下,比较重要的工期指派模型有三类,即共同工期指派模型,松弛工期(SLK)指派模型(参见Liu等 [11] )和不同工期指派模型(参见王吉波等 [12] )。本文考虑在松弛工期指派模型下,工件加工时间具有学习与恶化效应的单机排序问题,对工件的准时制成本和最大完工时间的线性组合最小问题给出了最优解满足的性质,并证明这个问题也是多项式时间可解的。
2. 问题描述
n个工件
要在一台机器上加工,同一时刻这台机器最多加工一个工件,且不允许中断。假设工件
的正常加工时间为
,则工件
的实际加工时间为
,
,
其中r为工件所排的位置,
为工件
的学习因子,
为恶化率,t为工件
的开始加工时间。我们考虑松弛工期指派,即工件
的工期为
(其中
为共同松弛流,是一个决策变量),
。令
表示工件
的完工时间,目标是确定一个最优排序
(
代表在排序中的第i个位置加工的工件)和最优的
,使目标函数
最小,其中
为最大完工时间,
是一个给定常数,
为位置权重,
为
的权重。用三参数表示法(Graham等 [13] ),我们研究的问题可表示为
Liu等 [11] 证明了工件加工时间为常数下的问题
是多项式时间可解的,下面我们证明问题
仍然多项式时
间可解。
3. 主要结论
对于问题
,显然存在一个最优排序,
从第一个工件开始加工到最后一个工件结束,机器加工无空闲,且第一个工件在零时刻开始加工。
引理1对于给定的序列
,决策变量
等于某个任务的完工时间,即
,其中l是序列
的中位数,并使下面不等式成立
(1)
证明:与文献Liu等 [11] 的证明方法类似。
引理2问题
的目标函数可以写为
,其中
(2)
证明:假设给定最优排序为
和
,可知
其中
。
对于给定排序
,由王吉波等 [10] 得工件
的完工时间和实际加工时间分别为
又由引理2,可得:
(3)
令和
,其中
(4)
则问题
可以转化为如下指派问题:
(5)
s.t.
(6)
(7)
(8)
问题
的具体求解算法如下:
算法1
步骤1:根据引理1计算出中位数l;
步骤2:根据(3),(4)计算出
;
步骤3:求解指派问题(5)~(8),确定工件的最优排序;
步骤4:由
得到共同松弛流。
定理1. 算法1可以解决问题
,且
算法的时间复杂度为
。
证明 由引理1,2和上面的分析,可得算法的正确性。算法1中步骤1和步骤4的时间复杂度分别为
,步骤2的时间复杂度为
,步骤3指派问题的时间复杂度为
,因此算法1总的时间复杂度为
。
显然,当
时,我们有
(9)
由HLP规则(Hardy等 [14] ),式子
可按照最小的
与最大的
匹配,第二小的
与第二
大的
匹配,依次进行下去,直到结束,从而求得最优排序,该算法的时间复杂度为
。因此,我们得到如下结论:
定理2. 问题
可以在
时间内解决。
4. 结论
本文研究了在SLK工期指派下的单机排序问题,其中工件同时具有学习与恶化效应。目标是确定最优排序及共同松弛流使一个非正则目标函数(包括提前时间、延迟时间和共同松弛流的加权和,其中这里的权重为位置权重)和最大完工时间的线性组合最小。我们证明了这个问题在引入学习与恶化效应后仍然具有多项式时间算法。在以后的研究中,可以考虑这种模型在多机(包括流水作业和平行机)情况下如何求解。
基金项目
沈阳航空航天大学大学生创新创业训练计划项目(201810143273)。
NOTES
*通讯作者。