本文關(guān)鍵詞：兩類平行機(jī)排序問題的在線算法

  更多相關(guān)文章： 在線排序 服務(wù)等級(jí) 最壞情況界 總完工時(shí)間 最大完工時(shí)間

【摘要】：本文主要研究?jī)深惼叫袡C(jī)在線排序問題：第一類是帶服務(wù)等級(jí)約束的m臺(tái)機(jī)在線排序，目標(biāo)是極小化總完工時(shí)間。第二類是帶單臺(tái)服務(wù)器的兩臺(tái)機(jī)在線排序，目標(biāo)是極小化最大完工時(shí)間。 全文共分四章。 第一章簡(jiǎn)要的介紹排序的基本理論。 第二章主要研究帶兩個(gè)服務(wù)等級(jí)的m臺(tái)平行機(jī)在線排序，其中加工的工件均是單位長(zhǎng)度。本章分兩種情形，目標(biāo)均是極小化總完工時(shí)間。情形一：機(jī)器為m臺(tái)，其中第1臺(tái)機(jī)器服務(wù)等級(jí)為1，剩余的m1臺(tái)的等級(jí)為2，本章提出一個(gè)比貪婪算法更好的近似算法，并證明其競(jìng)爭(zhēng)比為1+√2(m1)(16m+19)(m1)2+1+3m2；情形二：考慮更一般的情況，機(jī)器為m臺(tái)，其中前k臺(tái)服務(wù)等級(jí)為1，剩余m k臺(tái)機(jī)器的服務(wù)等級(jí)為2，我們證明其貪婪算法的競(jìng)爭(zhēng)比為1+√2k(m k)m(4km3k2+k)。最后，我們對(duì)問題的后續(xù)研究做出一些預(yù)測(cè)。 第三章主要研究帶一臺(tái)服務(wù)器的兩臺(tái)平行機(jī)在線排序，具體分兩種情形考慮，目標(biāo)均是極小化最大完工時(shí)間。第一種，同時(shí)考慮裝載、加工和卸載的情形，本章提出一個(gè)競(jìng)爭(zhēng)比為5/3的在線算法；第二，對(duì)只考慮裝載和加工的情形，，我們首先證明這個(gè)問題的貪婪算法的競(jìng)爭(zhēng)比至少是8/5，接下來提出一個(gè)競(jìng)爭(zhēng)比為11/7的在線算法。最后證明這兩個(gè)問題的下界均至少為3/2。此外，對(duì)第一種情形，本章還說明當(dāng)滿足某個(gè)特殊限制條件時(shí)，它的下界至少為8/5。 第四章總結(jié)全文并提出相關(guān)問題進(jìn)一步的研究方向。
【關(guān)鍵詞】：在線排序 服務(wù)等級(jí) 最壞情況界 總完工時(shí)間 最大完工時(shí)間
【學(xué)位授予單位】：浙江理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O223
【目錄】：

• 摘要4-5
• Abstract5-7
• 第1章 緒論7-11
• 1.1 排序問題概述7-8
• 1.2 在線算法8-9
• 1.3 兩類平行機(jī)排序問題在線排序模型9
• 1.4 論文結(jié)構(gòu)9-11
• 第2章 帶服務(wù)等級(jí)的m臺(tái)平行機(jī)排序的在線算法11-22
• 2.1 引言11-12
• 2.2 相關(guān)知識(shí)12-13
• 2.3 問題P_m|1,m-1,Gos|∑C_j的在線算法13-17
• 2.4 問題P_m|k,m-k,Gos|∑C_j的貪婪算法17-20
• 2.5 小結(jié)20-22
• 第3章 帶服務(wù)器的2臺(tái)平行機(jī)排序的在線算法22-35
• 3.1 引言22-23
• 3.2 相關(guān)知識(shí)23-24
• 3.3 問題P_2,S_1|s_j=t_j=1|C_(max)的在線算法24-29
• 3.4 問題P_2,S_1|s_j=1|C_(max)的在線算法29-32
• 3.5 問題P_1和P_2的下界32-34
• 3.6 小結(jié)34-35
• 第4章 總結(jié)與展望35-36
• 參考文獻(xiàn)36-42
• 附錄42-43
• 致謝43

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 蔣義偉;何勇;唐春梅;;Optimal online algorithms for scheduling on two identical machines under a grade of service[J];Journal of Zhejiang University Science A(Science in Engineering);2006年03期

本文編號(hào)：668000