單機分批排序和平行機在線排序問題.pdf

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

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

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