1. 引言
在经典排序中,假设工件的加工时间为常数,但有很多的实际生产过程,工件的加工时间可能与其开工时间有关。如在钢铁制造企业的连铸–轧制生产过程中,炼钢的基本单元是炉次,它是指同一座转炉一次共同冶炼的钢水。在炼钢的连铸阶段,高温熔融钢水在连铸机底部连续凝固成钢坯。当等待时间增加时(即加工开始时间延后),在连铸机上加工的炉次的温度将会降低,从而造成炉次加工时间的恶化(刘鹏等 [1] )。关于具有恶化效应的问题,读者可以参考文献Ng等 [2],Sun等 [3],Pei等 [4],Gawiejnowicz [5],王吉波等 [6]。随着市场的发展,为适应顾客多品种小批量生产方式的需求,成组技术应运而生。在成组排序问题中,工件可以分成“类似”工件的工件组。同组的工件连续加工时,不需要或需要较少的安装时间;不同组的工件接连加工时,需要一定的或需要较多的安装时间(Potts和Van Wassenhove [7],Webster和Baker [8],Neufeld等 [9] )。
Wu等 [10] 研究了单机成组排序问题,其中组内工件加工时间和组间安装时间都为简单线性恶化效应。对最大完工时间问题和加权总完工时间问题,他们分别给出了多项式时间最优算法。Wu和Lee [11] 研究了单机成组排序问题,其中组内工件加工时间和组间调整时间都为开工时间的线性恶化函数,其中组内工件和组间安装时间的恶化率都相同。他们证明了最大完工时间极小化问题是多项式时间可解的。他们也证明总完工时间极小化问题在每组工件个数都相同时的情况是多项式时间可解的。Lee 和Lu [12] 研究了单机成组排序问题,其中组内工件加工时间和组间安装时间都为简单恶化函数。对加权误工数问题,他们提出了启发式算法和分支定界法。Wang等 [13] 研究了带有准备时间的单机成组排序问题,其中组内工件是简单线性恶化函数,组间的安装时间为独立的常数。对一种特殊情况,他们证明了最大完工时间极小化问题是多项式时间可解的。Xu等 [14] 研究了同Wang等 [13] 类似的问题,只是组内工件的加工时间为开工时间的成比例恶化函数。对最大完工时间极小化问题的一种特殊情况,他们给出了多项式时间最优算法,他们还对一般情况给出了启发式算法。王吉波等 [15] 研究了同Wang等 [13] 一样的模型,对最大完工时间极小化问题的一般情况,他们给出了两个下界,从而提出了启发式算法和分支定界算法。
Wei和Wang [16] 研究了具有简单线性恶化函数的单机成组排序问题,对加权完工(等待)时间的平方和极小化问题给出了多项式时间最优算法。本文将继续研究Wei和Wang [16] 的排序模型,对所有工件的加权完工(等待)时间的k次幂和极小化问题进行分析,证明了这个问题是多项式时间可解的,并给出了求解算法。
2. 提出描述
有n个工件要在一台机器上进行加工,它们分为m个组,组
中包含
个工件,即
。所有组的调整时间在
时刻开始,工件
的实际加工时间为
(1)
其中t为开工时间,其中
是工件
的恶化率。假设同组工件必须放在一起连续加工,组
有一个安装时间,即
,其中
是组
的恶化率。令
表示工件
的完工时间,
表示工件
的等待时间(
),
表示工件
的权重(也就是它的重要程度),目标是确定各组之间的排列顺序和同组
内工件的排列顺序,使所有工件的加权完工(等待)时间的k次幂和最小,即
(
),其中k > 0是给定常数。利用三参数表示法,这个排序问题可表示为
和
,其中,1表示一台机器,GT表示成组技术,
(
)表示目标函数。
3. 主要结论
引理1对于问题
,则在最优排序中把同组内的工件按照
非减的顺序排列,即对组
,满足
,
(2)
证明 (反证法)假设组
内存在一个最优排序
,满足相邻的两个工件
和
,
,其中
排在
的前面。设t为
中工件
的开始加工时间,交换工件
和
得到另一个排序
,则
,
,
.
在两个排序下的目标函数差为
这违反了
是一个最优的排序,引理得证。
引理2对于问题
,则在最优排序中把同组内的工件按照
非减的顺序排列。
证明 类似于引理1。
引理3对于问题
,各组之间按照
非减
顺序排列得到最优组间排序。
证明 (反证法)假设存在一个最优组间排序
,满足相邻的两组工件
和
,
,其中
排在
的前面。设t为
中
的
开始加工时间,交换
和
得到另一个排序
,则
,
,
,
.
在两个排序下的目标函数差为
这违反了
是一个最优的组间排序,引理得证。
引理4对于问题
,各组之间按照
非减
顺序排列得到最优组间排序。
由引理1和引理3,我们可以给出问题
的最优算法。
算法1
1) 各组内的工件顺序按照
非减的顺序排列,
。
2) 各组之间按照
非减的顺序排列,
。
定理1对于问题
,最优解可由算法1得到,并且该算法的时间复
杂度为
。
证明:由引理1和2可知算法1的正确性。步骤1的时间复杂度分别为
,
步骤2的时间复杂度为
。因此,算法1的总时间复杂度为
。
由引理2和引理4,我们可以给出问题
的最优算法。
算法2
1) 各组内的工件顺序按照
非减的顺序排列,
。
2) 各组之间按照
非减的顺序排列,
。
定理2对于问题
,最优解可由算法2得到,并且该算法的时间复
杂度为
。
证明:类似于定理1。
下面我们举个例子来说明算法1是如何实现的(我们只给出问题
的
求解算法)。
例1:已知
,
,
,
,
,
,
,
,
,
;
,
,
,
,
,
,
,
;
,
,
,
,
,
,
,
。
解:由算法1得:
1) 组内工件排序按照
非减的顺序排列得
2) 对
组,
,对
组,
,对
组,
,即最优组间排序为
,最优目标函数值为
。
4. 结论
本文研究了工件具有恶化效应和成组技术的单机排序问题,其中组内工件和组间的调整时间都为简
单线性恶化函数。目的是求组内工件和组间工件的加工顺序使加权完工时间的k次幂和(即
)
最小,本文证明了此问题多项式时间可解。本文只是研究简单线性恶化函数,将来可以研究更一般的恶化函数情况,或者将其延伸到平行机或流水作业等问题。
基金项目
沈阳航空航天大学大学生创新创业训练计划项目(201810143272)。
NOTES
*通讯作者。