工件可選擇的平行機(jī)在線排序.pdf

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

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

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