24159.有新工件到達(dá)的帶有優(yōu)先約束及錯(cuò)位指標(biāo)的重新排序

1、Master’sThesis，ZhengzhouUniversityNo201112141596ReschedulingforNewOrderswithPrecedenceConstraintsandDisruptionIndicatorsCandidate：WangXingxingSupervisor：ProfJinjiangYuanSpeciality：OperationsResearchandCyberneticsSchoolof

2、MathematicsandStatistics，ZhengzhouUniversityZhengzhou，450001，PRChinaApril，2014摘要重新排序是人們十分關(guān)注的現(xiàn)代排序模型，它廣泛存在于人類的生活中例如在制造業(yè)中由于新訂單的到達(dá)，訂單的取消，訂單優(yōu)先性能的改變，工件到達(dá)時(shí)間的改變，機(jī)器的故障等突然的錯(cuò)位使得我們不得不對(duì)未加工的工件進(jìn)行重新排序在對(duì)有新工件到達(dá)的重新排序研究中，Hall和Ports(2004)引入了

3、原始工件的序列錯(cuò)位和時(shí)間錯(cuò)位，并研究了在錯(cuò)位限制下最小化排序費(fèi)用的多個(gè)重新排序問題此后，這一模型的研究十分活躍本文的研究是在Hall和Ports的工作的基礎(chǔ)上引入了原始工件的錯(cuò)位指標(biāo)數(shù)，并約定工件之間具有雙全序約束或者單全序約束我們用prec(O，N)表示雙全序約束，用prec(O，仍)表示原始工件單全序約束，并用prec(0，N)表示新工件單全序約束我們研究的內(nèi)容是按照序約束的不同，錯(cuò)位限制的不同，以及目標(biāo)函數(shù)的不同，對(duì)由此產(chǎn)生的多個(gè)

4、重新排序問題的計(jì)算復(fù)雜性進(jìn)行分析本文的主要結(jié)果如下：對(duì)于11∈Dmax71“4)，Am。z71“’))，7∈[∑辦(q)，廠max]，重新排序問題llprec(O，Ⅳ)，r≤kIY在多項(xiàng)式時(shí)間O(nong)內(nèi)可解對(duì)于r=∑DJTr)，7∈[∑辦(G)，厶蟻)，重新排序問題llprec(O：Ⅳ)，r≤尼17在多項(xiàng)式時(shí)間o(扎芻幾南)內(nèi)可解對(duì)于r=∑AJ71“)，7∈[∑乃(q)：厶ax)，重新排序問題1盼ec(0，Ⅳ)，r≤七17在擬多項(xiàng)

5、式時(shí)間o(n為禮Ⅳ硝甕’)內(nèi)可解對(duì)于r∈CE哆A尹7l“)，∑％A筍(7r)】，7∈∑如(cA：知ax】，重新排序問題1Iprec(O，Ⅳ)，r≤尼17在多項(xiàng)式時(shí)間O(nor齒)內(nèi)可解重新排序問題11prec(o，D)，∑A尹(萬’)≤kI∑G在多項(xiàng)式時(shí)間D(仡onⅣ)內(nèi)可解而當(dāng)prec(O)是以SPT序給出時(shí)，該問題在多項(xiàng)式時(shí)間o(nnNlognN)內(nèi)可解。重新排序問題1Iprec(o，0)，∑人尹(7r)≤kILmax在多項(xiàng)式時(shí)間o