帶等級平行機調度和MapReduce調度問題的算法研究.pdf

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

2、同類機在線排序，目標是極小化總完工時間。加工的工件均是單位長度且具有服務等級。等級低的工件只能在第一臺機器上加工，等級高的工件可在兩臺機器中任意一臺加工。本章分兩種情形討論。情形一：第一臺機器速度為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調度問題，目標是極小化最大完工時間。MapReduce加工主要包括Map和Reduce兩階段。相應的，每個工件有Map和Reduce兩道加工工序，每道工序有一個任務集，記為Map任務集和Reduce任務集。且只有該工件的Map任務集中任務加工完成后才能進行Reduce任務的加工。第一階段為m1臺平行機，第二階