1. 引言
在带有交货期窗口的排序问题中,若工件在交货期窗口外完工,则会产生相应的惩罚;若工件在交货期窗口内完工,则不会产生惩罚。Mosheiov和Sarig [1] 研究了带有交货期窗口和维修活动的单机排序问题,通过对不同情况的讨论,给出了多项式时间算法。Liu等 [2] 考虑了带有交货期窗口和加工时间是关于资源的凸函数模型的单机排序问题。Yang等 [3] 研究了带有可控加工时间和多窗口的排序问题。
近年来,对加工时间分别可控的问题的研究越来越多。Chen等 [4] 研究了加工时间分别可控的单机排序问题,通过对几个不同目标函数的分析,分别给出了多项式时间算法。Li等 [5] 对带有维修活动的加工时间分别可控的单机排序问题进行了研究,证明了该问题是多项式时间可解的。
本文考虑了带有交货期窗口和退化维修的加工时间分别可控的单机排序问题。目标是确定最优的工件加工顺序、交货期窗口位置、维修活动位置以及极小化总费用函数。
2. 问题描述
设有个工件在一台机器上加工,所有工件零时刻到达,机器在同一时间只可加工一个工件。工件有个可能加工时间,其中,是基本加工时间,是最小可能加工时间。是可能加工时间对应的费用,我们规定。为了提高机器的加工效率,进行一次退化维修,维修时间是关于开始维修时间的线性函数,其中是开始维修时间,是维修率。若工件在维修活动后进行加工,可能加工时间为,其中。
对于一个给定的排序,定义为工件的完工时间。若工件在维修活动前进行加工,定义为工件的实际加工时间。若工件在维修活动后进行加工,定义为工件的实际加工时间。所以有,。当工件的实际加工时间为或者时,则会产生相应的费用。现在有两种情况,第一种情况,所有工件有一个共同的交货期窗口,。第二种情况,每个工件都有自己的交货期窗口,,,,,其中,是固定的,且。在这两种情况中,工件的提前、延误完工时间分别定义为:,,。定义二元函数,为:
如果,则,否则。
我们需要确定工件的加工顺序、最优的窗口位置和窗口大小、维修位置以及维修时间费用函数:,。目标函数为和。其中,分别为提前、延误、窗口开始时间、窗口大小单位费用。
引用三参数表示法将两个问题分别表示成:
。
表示退化维修活动,表示加工时间分别可控。
3. 问题
本节中,所有工件有一个共同的交货期窗口,为了提高机器的生产效率,可进行一次维修活动。经过以下的计算、分析,可以极小化总费用函数,确定最优的工件加工顺序、窗口位置、维修位置。
引理1:由文献 [6] 问题最优排序具有以下性质:
(1) 每个工件的加工不可中断,机器无空闲状态,第一个工件在零时刻开始加工;
(2)的最优值等于,的最优值等于,其中,。
引理2:由文献 [1] 最优排序存在于以下几种情况:
情况1:维修活动并未发生;
情况2:维修活动发生在开始时间;
情况3:维修活动发生在第个工件完工后。
设排序为,定义为工件排在第个位置,我们分三种情况讨论问题。
情况一维修活动并未发生,定义为目标函数
其中。
定义为工件放在位置处所产生的费用:
则该问题可以转化为指派问题:
情况二维修发生在开始时间,定义为目标函数
情况三维修活动发生在第个工件完工后,定义为目标函数
其中,。
定理1:问题在情况一、情况二中的计算复杂性为,在情况三中的计算复杂性为。
证明:在情况一、情况二中,每个工件有个可能的加工时间,对于每个可能的加工时间,该问题都可以转化为指派问题,指派问题的计算复杂性为,因此整个过程的计算复杂性为。情况三中,在以上两种情况的基础上,最多存在个可能的维修位置,因此整个过程的计算复杂性为。
4. 问题
本节中,每个工件都有属于自己的交货期窗口,为了提高机器的生产效率,进行一次维修活动,经过本节的计算、分析,可以确定最优的工件加工顺序、窗口位置、维修位置以及极小化总费用函数。Mosheiov和Oron [7] 、Mor和Mosheiov [8] 和Wu等 [9] 给出了一些引理,容易验证,这些引理依然适用于本节的问题。
引理3:问题最优排序具有以下性质:
(2) 如果,则,。
如果,则,。
(3) 在最优排序中,,,,,其中,。
引理4:最优排序存在于以下几种情况:
情况3:维修活动发生在第个工件完工之后,其中。
情况三维修活动发生在第个工件完工之后,其中,定义为目标函数
定理2:问题在情况一、情况二中的计算复杂性为,在情况三中的计算复杂性为。
5. 结论
本文讨论了带有交货期窗口和维修活动的加工时间分别可控的单机排序问题。研究了两种不同类型的交货期窗口,分别从三种不同的维修位置进行了计算、分析,证明了这些问题在多项式时间内是可解的。
参考文献