本文選題：在線排序 + 服務(wù)等級��； 參考：《高校應(yīng)用數(shù)學(xué)學(xué)報A輯》2017年02期

【摘要】：研究了帶服務(wù)等級約束的三臺平行機在線排序問題.每臺機器和每個工件的服務(wù)等級為1或者2,工件只能在等級不高于它的機器上加工,即等級為1的工件只能在等級為1的機器上加工,等級為2的工件可在所有機器上加工.每個工件的加工時間為一個單位,目標(biāo)是極小化所有工件的總完工時間.考慮兩種情形:當(dāng)一臺機器等級為1,兩臺機器等級為2時,給出了競爭比為17/14的最優(yōu)在線算法;當(dāng)兩臺機器等級為1,一臺機器等級為2時,給出了競爭比為43/36的最優(yōu)在線算法.
[Abstract]:In this paper, the online scheduling problem of three parallel machines with service level constraints is studied. Each machine and each workpiece has a service rating of 1 or 2, and the workpiece can only be processed on a machine not above it, that is, the workpiece of grade 1 can only be machined on a machine of grade 1, and the workpiece of class 2 can be processed on all machines. The processing time of each workpiece is one unit and the goal is to minimize the total completion time of all workpieces. Two cases are considered: when one machine has a class of 1 and two machines with a level of 2, an optimal online algorithm with a competition ratio of 17 / 14 is given, and an optimal online algorithm with a competition ratio of 43 / 36 is given when the two machines have a class of 1 and one machine has a level of 2.
【作者單位】： 浙江樹人大學(xué)基礎(chǔ)部;浙江工商大學(xué)管理工程與電子商務(wù)學(xué)院;浙江理工大學(xué)理學(xué)院;
【基金】：國家自然科學(xué)基金(11571013)
【分類號】：O223

【相似文獻(xiàn)】

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

1 李波,石冰心;一種松弛的尺寸可變裝箱問題及其在線算法[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2005年02期

2 李榮珩,鄧漢元;單臺機訂單排序的在線與半在線算法[J];湖南師范大學(xué)自然科學(xué)學(xué)報;2001年01期

3 陳礴;A Review of On-Line Machine Scheduling:Algorithms and Competitiveness[J];數(shù)學(xué)理論與應(yīng)用;1999年03期

4 柏慶國;王忠志;張玉忠;;工件有尺寸的單機批調(diào)度問題的在線算法[J];山東大學(xué)學(xué)報(理學(xué)版);2009年12期

5 張國川;k－Bounded　Space　On－line裝箱中AFB_k算法的界[J];應(yīng)用數(shù)學(xué)學(xué)報;1996年03期

6 蔡圣義;三臺平行同型機的一個半在線排序算法[J];溫州師范學(xué)院學(xué)報(自然科學(xué)版);2002年03期

7 原晉江;農(nóng)慶琴;;平行批排序最小化最大完工時間在線算法的一個注記(英文)[J];鄭州大學(xué)學(xué)報(理學(xué)版);2006年03期

8 唐慶晨;劉永;;時間一致時極小化工件的配送時間的單機在線算法[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);2008年03期

9 張國川;帶參在線箱覆蓋問題(英文)[J];運籌學(xué)學(xué)報;1999年02期

10 蔡圣義;;帶機器準(zhǔn)備時間的機器覆蓋問題的在線、半在線算法[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯;2007年03期

相關(guān)會議論文 前2條

1 柏慶國;張玉忠;;有尺寸的單機在線分批排序[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

2 石永強;張國川;;工件尺寸不同的單臺批處理機加工在線問題[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

相關(guān)博士學(xué)位論文 前2條

1 李文杰;具有交貨期或友好釋放時間的在線排序研究[D];鄭州大學(xué);2014年

2 農(nóng)慶琴;在線排序與路由安排[D];鄭州大學(xué);2006年

相關(guān)碩士學(xué)位論文 前3條

1 吳用;平行機覆蓋問題的半在線算法研究[D];浙江大學(xué);2006年

2 高潔;批容量有界的單機分批列表在線排序[D];鄭州大學(xué);2011年

3 馬平娟;兩類單機批容量有界的分批在線排序[D];鄭州大學(xué);2012年

，

本文編號：1980940