最小化最大加權完工時間重新排序研究.pdf

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

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

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

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