【摘要】：本文主要研究Lp范數(shù)下的半在線排序問題。問題描述如下,給定m臺(tái)同型機(jī),以及n個(gè)工件,我們需要將每個(gè)工件安排在這些機(jī)器中的一臺(tái)或者若干臺(tái)上進(jìn)行加工,每一時(shí)刻每臺(tái)機(jī)器上只能加工一個(gè)工件,每一工件在同一時(shí)刻在其需要的數(shù)量的機(jī)器上加工,每個(gè)工件加工時(shí)間不一定相同,工件需要的機(jī)器數(shù)量也可能不同,工件是按照列表順序達(dá)到的,只有當(dāng)前一個(gè)工件安排之后,后一個(gè)工件才到來(lái),工件的具體信息只有當(dāng)其到達(dá)之后才知曉。每個(gè)工件安排以后就必須加工完,不允許中斷。我們的目標(biāo)是將工件安排在這些機(jī)器上,使得處理機(jī)的完工時(shí)間向量(負(fù)載)的Lp范數(shù)最小。論文結(jié)構(gòu)如下,第一、二章介紹了排序問題的背景知識(shí)。第三章和第四章討論三臺(tái)同型機(jī)的半在線排序問題,此處討論的問題中每個(gè)工件只需要一臺(tái)機(jī)器加工即可,目標(biāo)是極小化機(jī)器負(fù)載的Lp范數(shù),在第三章,針對(duì)總加工時(shí)間已知的情形,我們?cè)O(shè)計(jì)了競(jìng)爭(zhēng)比至多為max{3/2,(?)}的半在線算法。在第四章針對(duì)的是最大加工時(shí)間已知情形,我們?cè)O(shè)計(jì)了競(jìng)爭(zhēng)比至多為max{(?),(?)}的在線算法。在第五章,我們研究了 Lp范數(shù)下m臺(tái)同型機(jī)并行工件半在線排序問題的算法,此處工件是并行工件,即每個(gè)工件加工需要的機(jī)器數(shù)可以不止一臺(tái),對(duì)已知最大加工時(shí)間的情形,我們給出了競(jìng)爭(zhēng)比至多為40/3的算法,進(jìn)一步分析表明該算法的競(jìng)爭(zhēng)比至少為6。最后對(duì)論文進(jìn)行了總結(jié),分析了所得結(jié)果的不足之處以及進(jìn)一步研究的方向和思路。
【圖文】：

圖３－２情況一的排序表逡逑
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O223

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 郭玲;趙傳立;;帶有公共交貨期窗口和加工時(shí)間可控的單機(jī)排序問題[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年06期

2 李巖;田海龍;;總完工時(shí)間最短的恒速機(jī)排序[J];吉林化工學(xué)院學(xué)報(bào);2009年03期

3 胡覺亮;劉晨;;帶服務(wù)等級(jí)約束的單位長(zhǎng)度工件排序問題[J];浙江理工大學(xué)學(xué)報(bào);2008年01期

4 張果桃;趙金雁;白中英;;基于LT-backfilling算法的集群作業(yè)調(diào)度系統(tǒng)[J];計(jì)算機(jī)工程;2007年21期

5 林凌;;l_p范數(shù)下兩臺(tái)同型機(jī)半在線問題的最優(yōu)算法[J];浙江大學(xué)學(xué)報(bào)(理學(xué)版);2007年02期

6 蔡圣義;;預(yù)先知道總加工時(shí)間的一類特殊的三臺(tái)平行同類機(jī)在線排序[J];溫州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年05期

7 朱熙;楊啟帆;;可中斷半在線排序問題[J];浙江大學(xué)學(xué)報(bào)(理學(xué)版);2006年01期

8 蔡圣義;兩臺(tái)機(jī)在線均衡調(diào)度算法的改進(jìn)[J];溫州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年02期

9 何勇,楊啟帆,談之奕;平行機(jī)半在線排序問題研究(Ⅱ)[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);2003年02期

10 何勇,楊啟帆,談之奕;平行機(jī)半在線排序問題研究(Ⅰ)[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);2003年01期

，

本文編號(hào)：2518518