考虑延误的平行机可拒绝排序

发布时间：2017-09-10 03:53

  本文关键词：考虑延误的平行机可拒绝排序

  更多相关文章： 可拒绝排序 平行机 到达时间 最大延误 动态规划

【摘要】：平行机排序问题是多处理机排序问题的一种情况,在理论及其应用过程中都有着重要的意义.从理论上来看,平行机排序问题是单机排序问题的推广;而从应用角度来看,它的研究与我们的生活息息相关,有着广泛的应用背景.本文我们主要研究工件可拒绝约束下的平行机排序问题.第一章主要介绍一些排序问题的背景、近年来的研究现状以及相关的一些基础知识.然后简单介绍了一下本文的主要研究成果.第二章主要研究同速机可拒绝的排序问题,主要分了三个模型：(1)工件不同时到达、可拒绝的同速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大完工时间.通过动态规划算法可在O(mn(rmax+P)m)时间内得到最优值,其中m是机器台数;n是工件个数;rmax表示工件的最大到达时间;pj是工件Jj的加工时间,P=∑j=1Pjn表示所有工件的加工时间之和.此外,我们还给出了这一排序问题的一个FPTAS算法;(2)工件可拒绝的同速机排序问题.目标为极小化接受工件的最大延误与拒绝工件的惩罚费用之和.通过动态规划可在O(mnPm∑j=1nWi)时间内得到最优值,其中wj,(j=1,2,…,n)表示工件Ji的惩罚费用;(3)工件可拒绝的同速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大延误.通过动态规划算法可在O(mnUPm)时间内得到最优值.第三章主要研究恒速机可拒绝的排序问题,主要分了四个模型：(1)工件不同时到达、可拒绝的恒速机排序问题.目标为极小化接受工件的最大完工时间与拒绝工件的惩罚费用之和.通过动态规划算法可在O(mn(rmax +P/bm)m)时间内得到最优值,其中bi,(i=1,2,…,m)表示机器M,的加工速度;(2)工件不同时到达、可拒绝的恒速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大完工时间.通过动态规划算法可在O(mn(rmax+P/bm)m)时间内得到最优值;(3)工件可拒绝的恒速机排序问题.目标为极小化接受工件的最大延误与拒绝工件的惩罚费用之和.通过动态规划算法可在O(mn(P/bm)m∑i=1nWi)时间内得到最优值;(4)工件可拒绝的恒速机排序问题.在拒绝工件的惩罚费用之和不超过一给定上界U的约束下,目标为极小化接受工件的最大延误.通过动态规划算法可在O(mnU(P/bm)m)时间内得到最优值.
【关键词】：可拒绝排序 平行机 到达时间 最大延误 动态规划
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要3-5
• Abstract5-8
• 第1章 绪论8-14
• §1.1 排序问题8
• §1.2 平行机排序和可拒绝排序8-9
• §1.3 预备知识9-11
• §1.4 符号说明11
• §1.5 研究现状11-13
• §1.6 本文的主要工作13-14
• 第2章 考虑延误的同速机可拒绝排序14-22
• §2.1 问题描述14
• §2.2 P_m|rej,r_j,∑_(j∈R)w_j≤U|C_(max)14-17
• §2.3 P_m|rej|L_(max)+∑_(j∈R)w_j17-20
• §2.4 P_m|rej,∑_(j∈R)w_j≤U|L_(max)20-21
• §2.5 总结21-22
• 第3章 考虑延误的恒速机可拒绝排序22-29
• §3.1 问题描述22
• §3.2 Q_m|rej,r_j|C_(max)+∑_(j∈R)w_j22-24
• §3.3 Q_m|rej,r_j,∑_(j∈R)w_j≤U|C_(max)24-26
• §3.4 Q_m|rej|L_(max)+∑_(j∈R)w_j26-27
• §3.5 Q_m|rej,∑_(j∈R)w_j≤U|L_(max)27-28
• §3.6 总结28-29
• 参考文献29-32
• 在读期间发表的学术论文及研究成果32-33
• 致谢33

【相似文献】

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

1 张智聪;郑力;翁小华;;基于增强学习的平行机调度研究[J];计算机集成制造系统;2007年01期

2 陈荣军;唐国春;;平行机的供应链排序[J];系统科学与数学;2010年02期

3 陈荣军;张峰;唐国春;;平行机及自由作业的排序与转包[J];系统工程学报;2011年05期

4 陈荣军;唐国春;;平行机的排序与转包(英文)[J];数学季刊;2012年04期

5 蒋大奎;李波;;平行机作业环境下的订单分配与排序[J];管理学报;2013年06期

6 王成尧,汪定伟;有模机配合约束的平行机台调度方法[J];东北大学学报;1999年04期

7 曾欢欢,胡建华;可换速平行机工件带起止值的抢先进度表[J];数学理论与应用;1999年02期

8 蒋大奎;李波;曹立思;;考虑转包的平行机供应链排序[J];控制与决策;2014年05期

9 陈仕平,张国川;两台平行机的实时到达在线排序[J];应用数学学报;2000年01期

10 周伟刚;高成修;黄凯;;加工时间可控和简单线性增长的平行机排序[J];应用数学学报;2010年04期

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

1 闻振卫;;一类平行机上的任务指派问题及其动态规划算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

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

1 程贞敏;平行机调度问题研究的若干结果[D];北京师范大学;2008年

2 蔡圣义;同类平行机在线半在线排序参数界的若干研究[D];浙江大学;2010年

3 何龙敏;一类平行机和批处理机组成的二阶段柔性流水作业问题[D];上海大学;2006年

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

1 洪文益;与平行机排序相关的几个组合问题研究[D];清华大学;2013年

2 李松松;在平行机博弈排序中的近似强纳什均衡问题[D];曲阜师范大学;2013年

3 王君丽;有加工权限平行机在线问题研究[D];浙江大学;2012年

4 财玉华;具有非交叉维修时间的平行机在线排序[D];郑州大学;2007年

5 莫祯贞;改进粒子群算法在模糊环境下平行机批调度问题中的应用研究[D];中国科学技术大学;2010年

6 林琳;具有同时性约束的平行机排序问题[D];郑州大学;2006年

7 徐武来;具有完工期和工装数量约束的平行机调度方法[D];广东工业大学;2012年

8 何晓琼;一致平行机上在线排序[D];湖南师范大学;2009年

9 袁俊岭;链组约束下的平行机在线排序[D];郑州大学;2008年

10 崔婉良;平行机上工件具有链组约束及可预测的在线排序[D];郑州大学;2013年

，

本文编号：824590