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

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

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

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