极小化总完工时间的带服务等级平行机在线排序问题

发布时间：2017-12-16 19:33

  本文关键词：极小化总完工时间的带服务等级平行机在线排序问题

  更多相关文章： 排序 服务等级 竞争比 下界 总完工时间 在线算法

【摘要】：排序(scheduling)问题是运筹学领域中一个非常活跃的分支,它广泛应用于计算机科学、管理科学和工程技术等众多领域。本文主要研究带服务等级约束的同型机在线排序问题,目标是极小化总完工时间全文共分为四个章节。第一章简要介绍排序的基本理论及带服务等级约束排序问题的相关知识。第二章主要研究带两个服务等级约束的m台平行机排序问题,所有工件的加工时间均为单位时间且服务等级为1或2,服务等级为1的工件只能在服务等级为1的机器上加工,服务等级为2的工件可以在m台机器中任意一台上加工。目标是极小化总完工时间。本章主要考虑以下两种情形:对机器台数为台,其中第1台机器服务等级为1,后台机器服务等级为2的情形给出了竞争比为的在线算法,且该结果好于已有结果;对前台机器服务等级为1,后台机器服务等级为2的情形给出了问题的下界第三章主要研究带服务等级约束的3台平行机排序问题,目标是极小化总完工时间。本章主要考虑以下两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法。第四章总结全文内容并提出可进一步研究的方向。
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】

中国期刊全文数据库 前10条

1 李曙光,李国君,赵浩;无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案(英文)[J];运筹学学报;2004年04期

2 王玉青;孙世杰;;单机最小化加权总完工时间的产品加工问题(英文)[J];Journal of Shanghai University(English Edition);2007年02期

3 李岩;田海龙;;总完工时间最短的恒速机排序[J];吉林化工学院学报;2009年03期

4 曹国梅;石忠和;;加工时间相同的分族分批排序加权总完工时间问题[J];安阳工学院学报;2009年04期

5 李曙光;李国君;赵洪銮;;极小化完工时间和的有界批调度问题(英文)[J];应用数学;2006年02期

6 李曙光;杨振光;亓兴勤;;极小化最大完工时间的单机分批加工问题(英文)[J];运筹学学报;2006年01期

7 王珍;曹志刚;张玉忠;;极小化最大完工时间及拒绝费用的单机可拒绝分批排序[J];曲阜师范大学学报(自然科学版);2007年02期

8 金霁;顾燕红;唐国春;;最大完工时间排序的两人合作博弈[J];上海第二工业大学学报;2011年01期

9 郭晓;冯密罗;慕运动;;时间错位限制下最小化总完工时间的继列分批重新排序[J];郑州大学学报(理学版);2012年01期

10 刘园园;许小艳;郝峗;慕运动;;时间期望错位限制下完工时间和的随机重新排序[J];河南科学;2012年07期

中国重要会议论文全文数据库 前2条

1 张树霞;曹志刚;张玉忠;;极小化最大完工时间的离散可控排序(英文)[A];中国运筹学会第八届学术交流会论文集[C];2006年

2 陈克兵;高成修;;可变加工时间的单机排序(英文)[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

中国博士学位论文全文数据库 前7条

1 赵晓丽;多代理生产调度问题的理论研究[D];东北大学;2015年

2 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

3 李曙光;批调度与网络问题的组合算法[D];山东大学;2007年

4 马冉;最小化加权完工时间和的在线排序研究[D];郑州大学;2015年

5 何程;多目标分批排序及其相关课题[D];郑州大学;2009年

6 张国辉;柔性作业车间调度方法研究[D];华中科技大学;2009年

7 郑俊丽;船舶分段制造车间的模块空间调度模型及算法[D];上海交通大学;2011年

中国硕士学位论文全文数据库 前10条

1 孔祥玉;作业时空受限的生产与运输调度问题研究[D];沈阳大学;2015年

2 柴幸;最小化最大加权完工时间的平行分批在线排序问题[D];郑州大学;2015年

3 邱言玲;工件加工中的排序博弈方法[D];西安电子科技大学;2014年

4 朱晓灿;基于Hadoop的试验检测计划总完工时间极小化研究[D];西安电子科技大学;2015年

5 林琳;基于分枝定界的动态流水车间最大完工时间问题研究[D];东北大学;2015年

6 王玉艳;极小化总完工时间的带服务等级平行机在线排序问题[D];浙江理工大学;2017年

7 卫志刚;可自由离线批处理机最小化加权完工时间和排序[D];郑州大学;2011年

8 尹婷;钢铁生产中连续批调度的策略研究[D];武汉科技大学;2011年

9 夏劲伟;GPU中针对任务完工时间最小化问题的研究[D];东北大学;2012年

10 曹志刚;分批排序、可拒绝排序及离散可控排序中的若干问题[D];曲阜师范大学;2006年

，

本文编号：1297221