工件可選擇的平行機在線排序.pdf

1、鄭碩士論文題目：作者姓名：學科門類：專業(yè)名稱：研究方向：導師姓名、職稱：州大學位授予單位代碼研究生學號密級堂一論文104590430088l工件可選擇的平行機在線排序郭首瑋理學運籌學與控制論圖論與組合最優(yōu)化林詒勛教授二零零七年四月中一些較為特殊的情形：工件的利潤辦與加工時間功呈線性關系本文的內容主要分兩大部分：第一章，我們主要給出了排序論的介紹、一些用到的基本概念、排序的記號以及模型的介紹等第二章中，我們首先在第一節(jié)中給出了該模型中乃=

2、1情形的所有在線算法競爭比的上界l／2，力=Pj的一般情形(工件加工時間任意)不具有競爭比為常數階的在線算法，進而可知模型中^與砌呈線性關系乃=心如功(腳，～0)的一般情形也不具有競爭比為常數階的在線算法然后在第二節(jié)里，給出了厶=1且工件序列只包含兩類工件情形(小工件加工時間為1，大工件加工時間為d)的在線算法包括：只有兩臺機器，大工件加工時間d≥2時，找到了一個競爭比為1／2的在線算法41，且此算法為最具競爭性的；當有任意m臺平行機時

3、，找到了一個在線算法42，證明了對于m=2k(仇為偶數)，d≥k1的模型此算法的競爭比為1／2，且為最有競爭性的；對于m=2k1(m為奇數)，d≥2k2的模型，此算法的競爭比為k／(2k1)，為漸近意義下最優(yōu)的最后在第三節(jié)中，對于fj=乃，工件的加工時間只有兩種(小工件加工時間為1，大工件加工時間為d)，有任意m臺平行機的情形，找到了一個在線算法∥同樣證明了對于m=2k(m為偶數)，d≥k1的模型此算法的競爭比為1／2，且為最有競爭性的