單機(jī)分批排序和平行機(jī)在線排序問(wèn)題.pdf

1、曲阜師范大學(xué)碩士學(xué)位論文單機(jī)分批排序和平行機(jī)在線排序問(wèn)題姓名：王琳申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：張玉忠2003.3.12曲阜師范大學(xué)碩士學(xué)位畢業(yè)論文IIi1618的算法(見(jiàn)[6])在這種情形下，表面上看似所有工件一批就可加工，事實(shí)上由于工件的性能不同可能造成目標(biāo)值加大本文我們則是證明在這種情況下問(wèn)題的NP完備性定理21問(wèn)題llrj=0，B≥nI∑羔1wiv是NP一完備的為證明該問(wèn)題是NP一完備的，我們將證明著名的二劃分

2、問(wèn)題可多項(xiàng)式變換到該問(wèn)題給定二劃分問(wèn)題的一個(gè)實(shí)例如下：已知一個(gè)m個(gè)正整數(shù)組成的集合G=n，a2，n。)，問(wèn)是否存在G的一個(gè)子集x，使得∑aj=A=；∑。，jex“J=l我們構(gòu)造一個(gè)排序模型，可多項(xiàng)式變化到二劃分問(wèn)題，從而證明了問(wèn)題lh=0，B≥扎I∑n，：1％U的NP完備性第三章首次提出并研究了帶機(jī)器準(zhǔn)備時(shí)間的平行機(jī)在線(Oil—line)排序問(wèn)題，這里工件是可打斷的(preemptive)具體模型為：m臺(tái)平行機(jī)^4H一，M。需加工佗個(gè)

3、工件^，，厶，每個(gè)工件是在線到達(dá)(onebyone)且可打斷的，機(jī)器艦的準(zhǔn)備時(shí)間為口i，怎樣安排加工順序，使工件的最大完工時(shí)間(makespan)盡可能地小，稱此問(wèn)題為帶機(jī)器準(zhǔn)備時(shí)間的平行機(jī)在線排序問(wèn)題。它是帶機(jī)器準(zhǔn)備時(shí)間的平行機(jī)排序和平行機(jī)在線排序問(wèn)題的綜合和推廣，具有廣泛的應(yīng)用背景這里工件在線到達(dá)(onebyone)指的是工件的情況并不是提前知道的，只有將工件西一安排完以后我們才能知道工件以的一些情況(如工件的加工時(shí)間鰳等)工件是可