带两个服务等级的三台机最优在线算法

发布时间：2018-06-05 06:14

  本文选题：在线排序 + 服务等级　； 参考：《高校应用数学学报A辑》2017年02期

【摘要】：研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.
[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.
【作者单位】： 浙江树人大学基础部;浙江工商大学管理工程与电子商务学院;浙江理工大学理学院;
【基金】：国家自然科学基金(11571013)
【分类号】：O223

【相似文献】

相关期刊论文 前10条

1 李波,石冰心;一种松弛的尺寸可变装箱问题及其在线算法[J];华中科技大学学报(自然科学版);2005年02期

2 李荣珩,邓汉元;单台机订单排序的在线与半在线算法[J];湖南师范大学自然科学学报;2001年01期

3 陈礴;A Review of On-Line Machine Scheduling:Algorithms and Competitiveness[J];数学理论与应用;1999年03期

4 柏庆国;王忠志;张玉忠;;工件有尺寸的单机批调度问题的在线算法[J];山东大学学报(理学版);2009年12期

5 张国川;k－Bounded　Space　On－line装箱中AFB_k算法的界[J];应用数学学报;1996年03期

6 蔡圣义;三台平行同型机的一个半在线排序算法[J];温州师范学院学报(自然科学版);2002年03期

7 原晋江;农庆琴;;平行批排序最小化最大完工时间在线算法的一个注记(英文)[J];郑州大学学报(理学版);2006年03期

8 唐庆晨;刘永;;时间一致时极小化工件的配送时间的单机在线算法[J];曲阜师范大学学报(自然科学版);2008年03期

9 张国川;带参在线箱覆盖问题(英文)[J];运筹学学报;1999年02期

10 蔡圣义;;带机器准备时间的机器覆盖问题的在线、半在线算法[J];高校应用数学学报A辑;2007年03期

相关会议论文 前2条

1 柏庆国;张玉忠;;有尺寸的单机在线分批排序[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 石永强;张国川;;工件尺寸不同的单台批处理机加工在线问题[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

相关博士学位论文 前2条

1 李文杰;具有交货期或友好释放时间的在线排序研究[D];郑州大学;2014年

2 农庆琴;在线排序与路由安排[D];郑州大学;2006年

相关硕士学位论文 前3条

1 吴用;平行机覆盖问题的半在线算法研究[D];浙江大学;2006年

2 高洁;批容量有界的单机分批列表在线排序[D];郑州大学;2011年

3 马平娟;两类单机批容量有界的分批在线排序[D];郑州大学;2012年

，

本文编号：1980940