具有退化维护和资源分配的单机排序问题

罗成新, 王亚男

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

0 引 言

排序作为一门应用科学,有着深刻的实际背景,它主要产生于机器制造,后来被广泛应用于管理科学、运输业、计算机科学和工程技术等众多领域。排序对提高效率、资源的开发和配置、工程的进展安排及经济运行方面都起到辅助科学决策作用。

在实际中,由于工人或机器的工作时间较长,其工作效率降低,也就产生了所谓的退化效应。Browne和Yechiali[1]首先对具有退化效应的排序问题进行了研究,其中工件的加工时间是与开始加工时间有关的线性不减函数;文献[2-3]分别对具有简单线性退化和线性递减退化效应的单机排序问题进行了研究;Oron[4]在退化环境中排列具有可控加工时间的工件。

在实际情形中,交货期的设定会对生产活动产生一定的惩罚费用,因而如何去设定交货期,使得支付的费用尽可能少成了需要探讨的问题。Seidmann等[5]研究了单机排序问题中的最优交货期指派;Panwalker等[6]采用公共交货期指派来极小化单机排序问题中的总惩罚;Cheng等[7]研究了具有退化效应的交货期指派问题,假设所有工件的退化率和交货期都相同;Wang等[8]讨论了带有退化工件和依赖于资源的加工时间的单机交货期指派问题;王吉波等[9]对同时具有学习和恶化效应的不同工期指派问题进行了研究;Li等[10]讨论了带有学习效应和与资源有关的加工时间的最优交货期指派问题。

维护活动主要可以提高生产加工的工作效率,避免由于加工时间过长而多支付一些费用。Mosheiov和Oron[11]研究交货期指派和维护活动排序问题;Mosheiov和Sidney[12]讨论了在单机上排列一个退化的维护活动;Yang等[13]与Zhao和Tang[14]都研究了具有退化效应和维护活动的单机排序问题;在此基础上,Yang等[15]讨论了具有退化效应和退化维护的单机排序问题与松弛交货期指派问题,提出实际加工时间pjr=pjraj,j=1,2,…,n,但如果第r个位置的工件被排在了维护之后,它的实际加工时间就变为pjr=pj(r-i)aj,目的是极小化总费用函数;Luo和Ji[16]探讨在单机中排列一个可变的维护活动和线性退化工件。

本文在上述文献的基础上,研究具有退化维护和资源分配的单机松弛交货期指派排序问题。目标是在资源总量有限的条件下,确定最优公共松弛时间、最优维护位置、最优资源分配方案和最优工件排序,使得目标函数的总费用最小。根据凸优化相关知识,将问题转化为指派问题,证明了该问题在多项式时间内是可解的,给出了多项式时间最优算法。

1 问题描述

其中:l>0;pj为工件Jj的基本加工时间,即Jj排在第1个位置时的加工时间;aj≥0为工件Jj与位置有关的退化因子;c为退化速率;工件Jj的开始加工时间为t(t≥0);uj为分配给工件Jj的不可再生资源数量。

最小,其中α>0,β>0,γ>0,δ1>0,δ2>0为给定的常数。使用三参数表示法可将上述问题表示为

(1)

其中β域中的ma表示维护。

2 初步分析

下面,就问题的最优排序提出了一些引理。一个重要的性质:最优排序中第一个工件从零时刻开始加工且2个相邻的工件之间没有空闲。为了简便,假设在工件J[i]加工完成之后立即进行维护,即排在维护之前的工件数为i。

引理1 令J[j]表示在一个工件序列中,被排在第j个位置的工件。如果工件J[j]被排在维护之前,它的等待时间和完工时间分别为

其中C[0]=0。

证明 用归纳法进行证明。此处省略,证毕。

引理2 令J[j]表示在一个工件序列中,被排在第j个位置的工件。如果工件J[j]被排在维护之后,它的等待时间和完工时间分别为

证明 与引理1证明类似

引理3 如果C[j]≤d[j],那么C[j-1]≤d[j-1],j=2,3,…,n;如果C[j]≥d[j],那么C[j+1]≥d[j+1],j=1,2,…,n-1。

引理4 对于任意指定的序列π,都存在一个最优的松弛交货期,它的公共松弛时间q等于某工件的等待时间。

接下来,确定其等待时间等于公共松弛时间q的工件J[k]的k值。要证明工件J[k]的位置是费用参数的一个函数且与维护活动无关。

证明 考虑一个最优排序和最优公共松弛时间,使得对某工件J[k]有q=C[k-1]=W[k],利用经典扰动技术,研究当移动松弛时间时总费用的变化。当松弛时间左移ε个单位时间,总费用的改变值为

-α(k-1)ε+β(n-k+1)ε-nγε

(2)

相反地,当松弛时间右移ε个单位时间,总费用的改变值为

αkε-β(n-k)ε+nγε

(3)

3 问题的最优解

引理6 在问题(1)中,第k个工件的实际加工时间为

由上边引理可得下述结论:

1) 如果在工件J[k]加工之前进行维护,即i

其中

2) 如果在工件J[k]完工之后进行维护,即i≥k,总费用为

其中

引理7 对于问题(1),工件排序π=(J[1],J[2],…,J[n]可以得到最优资源分配如下:

对于i

其中Ωj由式(5)给出。

另外,对于i≥k的情况:

(9)

其中Φj由式(7)给出。

证明 下面只证i

其中λ是拉格朗日乘数。式(10)分别对u[j]和λ求导,并令导数为0,得

由式(12)得

(13)

由式(11)和式(13)得

(14)

由式(13)和式(14)得式(8)。证毕。

对于i

为了求出最优解,将问题化为指派问题。对于r=1,2,…,n,引入

考虑指派问题如下,令

则可转化为如下指派问题:

对于i≥k的情况,将式(9)代入式(6),得到目标函数Z在最优资源分配下的一个新的统一表达式:

为了求出最优解,将问题化为指派问题。对于r=1,2,…,n,引入

考虑指派问题如下,令

则可转化为如下指派问题:

因此,对于问题(1)可以给出如下最优算法:

算法

第2步 令维护位置j=1;

第3步 求解指派问题式(15)～式(18)或式(19)～式(22),得到一个局部最优排序和总费用;

第4步j=j+1,如果j≤n,那么执行第三步;否则,执行第五步;

第5步 全局的最优排序是局部最优排序中总费用最小的排序;

定理对于问题(1),利用算法可以通过求解指派问题在O(n4)时间内得到最优解。

证明 定理的正确性由上述分析保证。第1步的时间复杂度为O(1),第3步的时间复杂度为O(n3)。因为任何一个工件完工之后都可以立即进行维护,所以必须对n个不同的维护位置进行评估进而得到全局最优解。因此求解问题(1)的时间复杂度为O(n4)。证毕。

4 结 论

本文研究了具有退化维护和资源分配的单机松弛交货期指派排序问题。在资源总量有限的条件下确定最优公共松弛时间、最优维护位置、最优资源分配方案和最优工件排序,使得由工件的提前惩罚、延误惩罚、交货期公共松弛时间、最大完工时间、总完工时间构成的总费用最小。根据凸优化的相关知识,将问题转化为指派问题,证明了该问题在多项式时间内是可解的,给出了多项式时间最优算法。