本文選題：在線排序 + 競(jìng)爭(zhēng)比��； 參考：《浙江理工大學(xué)》2016年碩士論文

【摘要】：排序是一類重要的組合優(yōu)化問題,它廣泛應(yīng)用于管理科學(xué)、計(jì)算機(jī)科學(xué)和工程技術(shù)等眾多領(lǐng)域。本文主要研究?jī)深惻判騿栴}：第一類是帶服務(wù)等級(jí)約束的兩臺(tái)同類機(jī)在線排序問題,目標(biāo)是極小化總完工時(shí)間(∑j=1n Cj)。第二類是MapReduce流水作業(yè)調(diào)度問題的算法研究,目標(biāo)是極小化最大完工時(shí)間(Cmax)。全文共分四章。第一章簡(jiǎn)要的介紹排序的基本理論以及MapReduce的相關(guān)知識(shí)。第二章主要研究帶兩個(gè)服務(wù)等級(jí)的兩臺(tái)同類機(jī)在線排序,目標(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),我們給出問題的常數(shù)下界至少為20(?)41+9≈1.299,并給出最優(yōu)常數(shù)界算法；情形二：第一臺(tái)機(jī)器速度為s(s≥1),第二臺(tái)速度為1,我們也同樣的給出問題的常數(shù)下界至少為(?)≈1.372和最優(yōu)常數(shù)界算法。最后,我們對(duì)問題的后續(xù)研究做出一些討論。第三章主要研究?jī)呻A段流水作業(yè)(flow shop)環(huán)境下的MapReduce調(diào)度問題,目標(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ī),第二階段為m2臺(tái)平行機(jī)。在Reduce任務(wù)均不可中斷的情況下,我們根據(jù)Map任務(wù)是否可任意分割分為兩種情況來研究。若Map任務(wù)不可中斷,我們給出最壞情況界為2-1/m的近似算法H1,其中m=max{m1,m2};若Map任務(wù)可以任意分割,我們主要討論p(Rj)=βp(Mj)(0β+∞)的特殊情況,給出近似算法H2并證明其最壞情況界不大于2-1/m2-(1-m2)1/1+βm1;最后,我們對(duì)問題的后續(xù)研究做出一些討論。第四章總結(jié)全文并提出相關(guān)問題進(jìn)一步的研究方向。
[Abstract]:Sequencing is an important combinatorial optimization problem, which is widely used in many fields such as management science, computer science and engineering technology. In this paper, we mainly study two kinds of scheduling problems: the first is the on-line scheduling problem of two similar machines with service level constraints, the goal of which is to minimize the total completion time (鈭，

本文編號(hào)：1973553