帶等級平行機調(diào)度和MapReduce調(diào)度問題的算法研究.pdf

1、排序是一類重要的組合優(yōu)化問題，它廣泛應(yīng)用于管理科學(xué)、計算機科學(xué)和工程技術(shù)等眾多領(lǐng)域。本文主要研究兩類排序問題：第一類是帶服務(wù)等級約束的兩臺同類機在線排序問題，目標是極小化總完工時間(∑nj=1Cj)。第二類是MapReduce流水作業(yè)調(diào)度問題的算法研究，目標是極小化最大完工時間(Cmax)。
　　全文共分四章。
　　第一章簡要的介紹排序的基本理論以及MapReduce的相關(guān)知識。
　　第二章主要研究帶兩個服務(wù)等級的兩臺

2、同類機在線排序，目標是極小化總完工時間。加工的工件均是單位長度且具有服務(wù)等級。等級低的工件只能在第一臺機器上加工，等級高的工件可在兩臺機器中任意一臺加工。本章分兩種情形討論。情形一：第一臺機器速度為1，第二臺速度為s(s≥1)，我們給出問題的常數(shù)下界至少為20/√41+9≈1.299，并給出最優(yōu)常數(shù)界算法；情形二：第一臺機器速度為s(s≥1)，第二臺速度為1，我們也同樣的給出問題的常數(shù)下界至少為√33.3/2≈1.372和最優(yōu)常數(shù)界算法

3、。最后，我們對問題的后續(xù)研究做出一些討論。
　　第三章主要研究兩階段流水作業(yè)(flow shop)環(huán)境下的MapReduce調(diào)度問題，目標是極小化最大完工時間。MapReduce加工主要包括Map和Reduce兩階段。相應(yīng)的，每個工件有Map和Reduce兩道加工工序，每道工序有一個任務(wù)集，記為Map任務(wù)集和Reduce任務(wù)集。且只有該工件的Map任務(wù)集中任務(wù)加工完成后才能進行Reduce任務(wù)的加工。第一階段為m1臺平行機，第二階