预防性维护下的混合型平行机调度问题研究

发布时间：2017-12-06 18:38

  本文关键词：预防性维护下的混合型平行机调度问题研究

  更多相关文章： 调度 维护 数学规划模型 启发式算法 最坏情况分析 数值实验

【摘要】：传统的调度研究假设机器可以一直被使用,直到加工完所有需要加工的工件.然而,在现实生产活动中,往往需要对机器进行预防性的维护.常见的维护类型有:单次维护、周期维护和工具更换维护.本文研究了预防性维护下一类混合型平行机调度问题:有n个工件需要加工,有两台平行机可供使用,其中一台需要工具更换维护,另一台需要周期维护,目标是确定每次工具更换维护的开始时刻和每个工件所对应的机器及其开始加工时刻使得这n个工件的时间表长(即最后完工的工件的完工时刻)最小.本文的主要工作如下.(1)分析了该问题的计算复杂性和不可逼近性.证明了该问题是强NP-难的并且不存在最坏情况界小于2的多项式时间算法除非P=NP.(2)为求解中小规模的调度实例,基于“把维护看作工件”、“机器拼接”和“工件与加工位置一一对应”的思想给出了两个数学规划模型,基于“装箱问题”的思想给出了另外两个数学规划模型,并编程实现了上述四个模型.(3)为求解大规模的调度实例,基于“工件完成时间优先分配机制”,“机器完成时间优先分配机制”,经典的“LPT规则”和“LS规则”设计了四个启发式算法.通过对上述四个算法所生成的调度方案的研究,提出了对上述算法得到的调度方案进行“后优化”想法并以此为基础设计了四个新的算法.注意到存在实例表明没有一个算法占绝对优势,于是把上述八个算法的输出结果中最好的一个做为最终输出,这样就得到了第九个启发式算法.(4)从理论上对上述九个算法进行了最坏情况分析.证明了当最后一个非空维护间隔中至少有两个工件时,上述九个算法的最坏情况界均为2.(5)通过数值实验对上述九个算法进行了平均误差分析和最大误差分析.为了避免使用数学规划模型求解大规模的调度实例,根据机器的特点设计了“逐次半毫升水量转移算法”来求最优时间表长的一个下界,根据工件加工的特点得到了最优时间表长的另外一个下界.取这两个下界中较大者做为数值实验中的比较对象,通过编程实现了上述九个算法和下界,给出了工件规模为20,200和2000下各36组参数(每组参数各取100个实例)对应的平均误差和最大误差.结果表明,基于“机器完成时间优先分配机制”和“LPT规则”的算法误差较小.(6)假定维护时长是其上一次维护间隔中的负载(即所加工的工件的加工时长之和)的非负增函数,得到了该平行机调度问题的一个扩展版本,给出了四个数学规划模型.
【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O224

【相似文献】

中国期刊全文数据库 前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年

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

1 刘珊珊;一些单机和平行机排序情形的研究[D];华东理工大学;2015年

2 陈友军;有运送协调性的最小化最大运送完成时间平行机排序[D];郑州大学;2016年

3 何杰;预防性维护下的混合型平行机调度问题研究[D];湖南大学;2016年

4 李松松;现代排序理论中的三类重要问题：博弈排序，分批可拒绝排序和在线排序[D];曲阜师范大学;2016年

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

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

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

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

1 赵云;带等级平行机调度和MapReduce调度问题的算法研究[D];浙江理工大学;2016年

2 张家宝;考虑维护和可中断工件的混合型平行机调度问题研究[D];东华理工大学;2016年

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

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

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

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

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

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

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

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

，

本文编号：1259598