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

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

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

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

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