资源描述：
《工件加工时间是开工时间线性函数的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第39卷第3期数学的实践与认识Vol139No132009年2月MATHEMATICSINPRACTICEANDTHEORYFeb.,2009工件加工时间是开工时间线性函数的单机排序问题高文军,王吉波,王晓远,殷娜,黄雪(沈阳航空工业学院理学院,沈阳110136)摘要:研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法.关键词:排序;单机;线性函数;完工时间平方
2、和;总误工数;最大完工时间1引言在经典的排序问题中,通常假设工件的加工时间为常数.但在某些实际问题中,工件的加工时间可能并非常数,这类问题在钢铁工业,塑料工业,军事以及医疗等方面有着广泛的应用.如在军事方面,当天气渐渐变坏或者天色渐渐变黑时,探测目标开始的时间越晚则所花费的时间就越长;在消防工程中,救火的开始时间一旦被耽搁,火势就会难以控制,这样救火的时间将会变长,所付出的代价也会变大.所以工件的加工时间是开工时间函数的排序问[1,2]题近来备受关注.这类问题比经典问题更复杂.在通常情况下,只有相应的经典问题有多项式算法,这类问题才有可能有多项式算法.Browne
3、和Yechiali在[3]中对涉及到随机变量的单机问题进行了讨论,对最大完工时间问题给出了最优算法.Mosheiov在[4]中对工件的加工时间是开工时间的简单线性函数的单机问题进行了讨论,目标函数为最大完工时间、总完工时间、加权总完工时间、总延误时间、最大延误与总误工数.他对这些正则目标函数分别给出了最优算法.Mosheiov在[5]中对工件的基本加工时间相同,恶化率不同的单机问题进行了讨论,证明了完工时间和问题具有V型性质.Mosheiov在[6]中对工件的加工时间是开工时间的简单线性函数的FlowShop、OpenShop与JobShop问题问题进行了[7]讨
4、论,得到了类似于经典问题的结论.Kononov与Gawiejnowicz讨论了一般线性加工时间的FlowShop与OpenShop问题,证明了两台机器最大完工时间FlowShop与OpenShop问题都是强NP2难的.[8]讨论了工件的基本加工时间与恶化率有关的线性加工时间问题,对单机情况,目标函数分别为最大完工时间,加权完工时间和,最大费用与最大延误,对这些目标函数分别给出了最优算法.[9]讨论了工件的加工时间是开工时间的简单线性函数,机器间满足某种优势关系的FlowShop排序问题.当目标函数是极小化最大完工时间时,对三种特殊情况分别给出了多项式时间算法.对于
5、目标函数为加权完工时间和与最大延误,对[10]一种特殊情况给出了多项式时间算法.Wang和Xia研究了工件的加工时间是开工时间的简单线性函数,机器间满足某种优势关系的FlowShop排序问题.目标函数分别为最大完工时间,加权完工时间和与最大延误.对于机器有不等待约束(no2idle)与工件有无等待约束收稿日期:2006206201基金项目:辽宁省教育厅科技研究项目资助(20060662)3期王吉波,等:工件加工时间是开工时间线性函数的单机排序问题147(no2wait)问题分别给出了多项式时间算法.[11]讨论了工件加工时间是开工时间的分段线性函数情况,对最大完工
6、时间问题给出了一些性质.关于工件加工时间是开工时间函数方面的综述读者可参见[1,2].本文第二节将研究与[8]同样的问题,既:将讨论具有线性恶化工件(工件的基本加工时间与恶化率有关)的单机排序问题,但目标函数为极小化完工时间平方和与总误工数.对这两个目标函数我们分别给出了多项式时间最优算法.第三节将研究分段情况,即工件的加工时间在开工时间大于给定常数时不再恶化情况,目标函数为极小化最大完工时间,对此问题也给出了多项式时间最优算法.2一般情况先给出具有线性恶化工件的单机排序问题的一般描述.设有n个工件J={J1,J2,⋯,Jn}要在一台机器上加工,所有工件在时刻t0
7、(E0)之后k-1aa可加工,工件CS(k)(R)-CR(k)(S)=t0-∏(1+bpS(j))-+pS(k)(a+bT)-bj=1bkaat0-∏(1+bpR(j))+的加工时间为pj(t)=pj(a+bt),其中pj称为工件CS(k)(R)bj=1bk-1kaaa-CR(k)(S)=t0-∏(1+bpS(j))-+pS(k)(a+bT)-t0-∏(1+bpR(j))bj=1bbj=1a+的基本加工时间,a,b为非负常数,j=1,2,⋯,n,a+bt称为增长(恶化)函数,t(Et0)bk-1aa是工件CS(k)(R)-CR(k)(S)=t0-∏(1+bpS(j
8、))-+p
