具有學(xué)習(xí)與退化效應(yīng)的排序問題.pdf

1、排序問題是一類重要的組合優(yōu)化問題.在經(jīng)典排序模型中通常假設(shè)工件的加工時(shí)間為常數(shù).但在許多實(shí)際問題中,工件的加工時(shí)間可能與其開工時(shí)間、所用資源或所處的位置有著某種聯(lián)系。由此產(chǎn)生一類現(xiàn)代排序問題:具有學(xué)習(xí)與退化效應(yīng)的排序問題.例如,產(chǎn)業(yè)工人由于連續(xù)重復(fù)做相似的工作,效率會(huì)越來越高,這種現(xiàn)象在文獻(xiàn)中稱之為“學(xué)習(xí)效應(yīng)”;由于機(jī)器的老化,會(huì)使機(jī)器的運(yùn)行速度慢下來,工件的實(shí)際加工時(shí)間會(huì)變長(zhǎng),這種現(xiàn)象在文獻(xiàn)中稱之為“退化現(xiàn)象”(Pinedo,2002

2、[31]).
　　本文研究了具有學(xué)習(xí)效應(yīng)與退化現(xiàn)象的排序問題,主要結(jié)果如下:
　　1.具有學(xué)習(xí)與退化效應(yīng)的單機(jī)排序問題,(a)對(duì)于問題1|Pj[r]=pjα(t)ra|Cmax,證明了工件按pj非減順序排列可以得到最優(yōu)排序(即SPT序).(b)對(duì)于問題(?),證明當(dāng)pi≤pj有wj≤wi時(shí),工件按(?)非減的順序排列可以得到最優(yōu)序.(c)對(duì)于問題1|Pj[r]=pjα(t)ra|Lmax,證明當(dāng)di≤dj有pi≤pj時(shí),工件

3、按dj非減順序排列可以得到最優(yōu)排序.其中退化因子α(t)≥0為t的非減凸函數(shù),r表示工件在序列中所處的位置,a表示學(xué)習(xí)因子.
　　2.具有學(xué)習(xí)與退化效應(yīng)的資源限制排序問題對(duì)于問題1|pj[r]=(pj+βt)ra,rj=f(uj),Cmax≤C|(?)和1|Pj[r]=(pj+βt)ra,rj=f(uj),(?)≤U|Cmax,分別給出了最優(yōu)算法,并證明了算法的正確性.其中uj是分配工件Jj的資源量,f是正值嚴(yán)格遞減的函數(shù).U是連

4、續(xù)可分配的資源總數(shù),C滿足(?)的常數(shù).
　　3.具有學(xué)習(xí)效應(yīng)的排序問題(a)對(duì)于問題(?)給出了最優(yōu)算法;對(duì)于問題(?)在某些特殊情形下給出最優(yōu)算法.(b)對(duì)于排序模型證明了SPT規(guī)則能夠得到最優(yōu)序.其中ord表示工件滿足下列條件:對(duì)任一工件j有aj≤bj,且對(duì)于兩個(gè)工件j,k,若aj≤ak,則有bj≤bk.這里的aj,bj表示工件j的分別在第一臺(tái)機(jī)器和第二臺(tái)機(jī)器上的基本加工時(shí)間; prp表示工件滿足:bj=caj(這里c≥1是