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

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

3、按dj非減順序排列可以得到最優(yōu)排序.其中退化因子α(t)≥0為t的非減凸函數(shù),r表示工件在序列中所處的位置,a表示學習因子.
　　2.具有學習與退化效應的資源限制排序問題對于問題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是正值嚴格遞減的函數(shù).U是連

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