误工最小化流水调度精确及启发式算法研究

发布时间：2020-05-05 02:02

【摘要】：研究了流水机环境下最小化总误工损失的调度问题。流水机调度指的是n个工件需要m台机器加工,每个工件需要m道工序,每道工序需要不同的机器;n个工件在m台机器上的加工顺序相同。工件的误工损失是与交付期有关的一种惩罚量,其数值正比于工件滞后于其交付期加工的部分。针对该问题不同模型,分别设计了分枝定界算法求解其小规模运算实例,以及遗传算法求解大规模实例。对于两台流水机模型,重新分析了2006年发表的分枝定界算法,利用反例法指出其下界设计中的错误;然后给出了新的计算下界方法,给出一个新的分枝定界算法。该算法利用遗传算法获得初始解,并利用上下界剪枝规则、节点间的支配规则去掉无效节点,缩小搜索规模。对于多台流水机模型,扩展了上述的遗传算法。根据问题特性,定义了染色体的编码方式、交叉和变异规则,以及算法终止条件。对于多台流水机模型,问题规模稍微增大,精确算法很难在满意的时间内找到最优解,甚至不可能找到最优解;因此,本文用遗传算法求所研究问题的近似解,并与其它的启发式算法的实验结果做比较,证明了遗传算法相比于其它启发式算法能更好的改善问题的初始解。实验数据表明,上述两个算法在处理小规模实例和中大规模实例过程中性能表现良好。带下界规则的分枝定界算法能有效地去除搜索树中的无效分枝,支配规则可以有效的去除无效节点,显著地提高了分支定界算法的搜索效率。遗传算法能够快速求解大规模算例,且性能远优于那些简单的启发式规则,能够为求解大规模问题算例时提供较好初始解。
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 桂洪照;;几种具有代表性的启发式算法研究[J];电子制作;2016年02期

2 王芳,施国洪;商贸服务业选址决策研究——一种基于阿德兰启发式算法的选址方法[J];江苏商论;2004年07期

3 陶光远;周佩德;王强;;最优运输径路选择的启发式算法[J];南京工学院学报;1987年06期

4 许杰锋;;客车调度问题(BSP)的数学模型及一种新的启发式算法[J];上海交通大学学报;1988年06期

5 邢琳;;一种启发式识别被积函数算法的设计与实现[J];中南矿冶学院学报;1988年01期

6 郭耀煌,范莉莉;货运汽车调度的一种启发式算法[J];系统工程;1989年01期

7 杨英杰;;单体型装配问题的启发式算法研究[J];数字技术与应用;2017年01期

8 陈燕;谢琪琦;刘咏;崔耀东;;圆形件下料顺序分组启发式算法的设计与实现[J];图学学报;2017年01期

9 潘立军;符卓;;求解带硬时间窗车辆路径问题的时差插入启发式算法[J];计算机应用;2012年11期

10 高尚,陈钢;可靠性优化的一种新的启发式算法[J];工程设计学报;2004年03期

相关会议论文 前10条

1 冯德鸿;唐加福;郭琦;李辉;;订货批量问题改进的相关策略启发式算法与仿真分析[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

2 罗守成;唐国春;;二维集装箱问题的一个启发式算法[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

3 刘嘉敏;马广煜;黄有群;;基于组合的三维集装箱装入启发式算法的研究[A];全国第13届计算机辅助设计与图形学（CAD/CG）学术会议论文集[C];2004年

4 戴娜;肖杰;邸瑞华;;异构计算环境下任务调度模型的启发式算法研究[A];2006年全国开放式分布与并行计算机学术会议论文集（三）[C];2006年

5 许争争;;自有和租用车辆并存条件下基于协作的启发式算法研究[A];第十九届中国管理科学学术年会论文集[C];2017年

6 刘青松;孔云峰;党兰学;王震;;元启发式算法在校车路径规划中的应用[A];第七届全国地理学研究生学术年会论文摘要集[C];2012年

7 何正文;徐渝;;多模式项目支付进度问题的优化模型及启发式算法[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

8 黄忠圣;;高等启发式算法在桁架结构优化中的应用[A];北京力学会第21届学术年会暨北京振动工程学会第22届学术年会论文集[C];2015年

9 李兵;蒋慰孙;;改进的遗传算法及在一类组合优化问题中的应用[A];1995中国控制与决策学术年会论文集[C];1995年

10 张建勇;李军;;模糊需求VRP的一种Sweeping启发式算法[A];第九届中国管理科学学术年会论文集[C];2007年

相关重要报纸文章 前2条

1 羽中;启发式算法的大能量[N];国家电网报;2018年

2 褚会会;建立数学模型 启发式算法求解[N];东方烟草报;2016年

相关博士学位论文 前10条

1 闫志远;地理网络分析中的并行启发式算法研究[D];中国矿业大学(北京);2015年

2 古继兴;KOD多播技术与Steiner树启发式算法[D];上海交通大学;2007年

3 董兴业;启发式算法及其在同顺序流水作业问题中的应用[D];北京交通大学;2008年

4 马华伟;带时间窗车辆路径问题及其启发式算法研究[D];合肥工业大学;2008年

5 胡大伟;设施定位和车辆路线问题模型及其启发式算法研究[D];长安大学;2008年

6 石文;空中交通管理优化问题研究[D];天津大学;2014年

7 杨玉珍;基于元启发式算法的带生产约束作业车间调度问题若干研究[D];华东理工大学;2014年

8 邓冠龙;基于元启发式算法的调度问题若干研究[D];华东理工大学;2012年

9 郑君玺;一类混合生产线调度与数值仿真技术的研究[D];华南理工大学;2016年

10 李常敏;两层规划的逼近理论及算法研究[D];复旦大学;2010年

相关硕士学位论文 前10条

1 郑志祥;基于元启发式算法的进场决策支持研究[D];南京航空航天大学;2018年

2 王中玉;误工最小化流水调度精确及启发式算法研究[D];大连理工大学;2018年

3 郭竹峰;基于变量权重的约束满足问题启发式算法研究[D];吉林大学;2018年

4 苗晓燕;基于启发式算法边坡及支挡结构稳定性分析方法[D];湖南大学;2017年

5 霍超;求解多目标无约束二元二次规划问题的元启发式算法研究[D];电子科技大学;2018年

6 罗云凤;基于启发式智能搜索的货运列车节能优化研究[D];江西理工大学;2018年

7 江韵;《大数据元启发式算法》（第5章与第8章）翻译实践报告[D];青岛科技大学;2018年

8 边哲永;基于两种改进策略的亚启发式算法求解路径相关问题研究[D];天津大学;2016年

9 刘畅;基于混合启发式算法的单线公交车辆调度问题研究[D];北京交通大学;2016年

10 姜毅;扰动型超启发式算法的适应度地貌分析[D];大连理工大学;2013年

，

本文编号：2649345