最小化最大加權(quán)完工時間重新排序研究.pdf

1、Master’SThesis，ZhengzhouUniversityReschedulingtominimizethemaximumweightedcompletiontimeCandidate：XijieZangSupervisor：ProfJinjiangYuanSpeciality：OperationsResearchandCyberneticsSchoolofMathematicsandStatistics，ZhengzhouU

2、niversityZhengzhou，450001，PRChinaApril，2014摘要重新排序模型可以描述如下：一組原始工件已經(jīng)按照某個準則做好最優(yōu)加工(排序)方案，但是還沒有開始加工此時，另一組新工件突然到達，需要與原始工件一起加工生產(chǎn)部門需要調(diào)整已有的加工方案，使得在原始工件不打亂太多的情形下得到一個合理的排序本文沿用Hall和Potts(2004)提出來的序列錯位(sequencedisruption)和時間錯位(timedi

3、sruption)的概念來刻畫原始排序被打亂的程度本文研究最大加權(quán)完工時間的重新排序問題問題的目標是：(1)在原始排序錯位限制的條件下最小化最大加權(quán)完工時間；(2)最小化最大加權(quán)完工時間與原始排序的錯位的加權(quán)和在第二章的研究中我們假設(shè)所有工件在0時刻到達；在第三章的研究中我們假設(shè)工件具有不同的到達時間，但與其他參數(shù)具有反一致性本文的主要結(jié)果如下：對于F∈D。ax(7r)，△。。(丌))，問題1Ir≤七ImaxwjG可以在多項式時間Dm禮

4、Ⅳ109nN)內(nèi)求解對于r∈D。。(丌)：△。ax(7r‘))，問題1|lmaxwjGpF可以在多項式時間0(27％N)內(nèi)求解問題1lEAj(r’)≤七Imaxwj0是強NP一困難的問題11ImaxqGp∑△j(7r‘)是強NP一困難的對于F∈(D。ax(7r)，△。。(7r’)，∑功(礦))，問題llanti一(勺，嘶)：乃=P，F(xiàn)≤klmaxwjCj可以在多項式時間內(nèi)求解對于F∈(D。ax(礦)：∑B(7r)】，問題lIanti一(