机器有不可用时间段的可拒绝排序问题

发布时间：2017-09-02 05:35

  本文关键词：机器有不可用时间段的可拒绝排序问题

  更多相关文章： 排序 不可用时间段 配送 伪多项式 动态规划算法 拒绝

【摘要】：由于实际生产的需要,机器可能有些时间段不能工作,所以机器有不可用时间段的排序问题被广泛应用到各个领域.不仅如此,生产商开始对工件进行选择,他们尽量选择一些能给企业带来更大收益的工件进行生产,同时拒绝加工耗时长而又收益小的工件,或者将拒绝的工件外包给其他企业进行生产.当然,机器并不是一直可用的,比如工人有自己的上班时间,机器需要维修或者保养,那么在工人休息时间或者机器维修保养、更换零件的时间,是不允许加工工件的,而且根据具体需要,工件的加工时间可遵循恶化效应.作为供应链的一部分,制造商不仅需要加工工件,而且完工工件需要被尽快运输到客户,可以选择第三方物流企业帮助运输.总之,随着时代的发展和实际生产生活的需要,如何合理接受工件、安排接受工件的生产、组织工件运输、分批运输以提高客户的服务水平,同时极小化工件的配送时间,这一问题已得到更多关注.文章结构安排如下:第一章主要介绍了排序问题的基本知识、主要概念以及组合优化中的基本常识,而且简要介绍了机器有不可用时间段的排序问题、可拒绝排序问题以及供应链排序问题的基本概念,最后简单说明了一下该问题的研究现状以及本文的主要成果.第二章研究了两台机器,其中一台机器有一个固定不可用时间段的可拒绝排序问题,工件可以接受并在机器上加工或者拒绝加工,目标是极小化接受工件的最大时间表长与拒绝工件的拒绝费用之和,主要有以下两个模型:(1)工件加工不可恢复,通过动态规划算法最优地解决该问题;(2)工件加工可恢复,本节给出了伪多项式动态规划算法.第三章考虑了m台平行机,每台机器有一个固定不可用时间段的可拒绝排序问题,主要有以下两个模型:(1)机器加工不可恢复,生产商可以选择接受并加工工件,也可以选择拒绝或将工件外包,会产生一定的拒绝费用,目标是极小化接受工件的总完工时间以及拒绝工件的总拒绝费用之和,通过动态规划算法得到问题最优解;(2)机器加工不可恢复,对工件可以进行选择性加工,工件的加工时间是开工时间的简单线性函数,目标是极小化接受工件的总加权完工时间与拒绝工件的总拒绝费用之和.文中给出了一个伪多项式动态规划算法.第四章研究了单机生产的排序问题,机器上有一个固定不可用时间段,工件加工允许拒绝,完工工件需运输到同一个客户,本章主要考虑了以下三个模型:(1)单机生产,工件加工允许拒绝,不可用时间段之前未完工的工件,在之后可以继续加工,工件的加工时间是其基本加工时间和开工时间的线性函数,完工工件需要批运输到同一客户,运输车辆无限,车容量有限,目标是极小化最后一批工件配送到客户的时间、运输费用与拒绝工件的拒绝费用之和,本节给出了伪多项式动态规划算法及其复杂性;(2)单机生产,机器上有一个不可用时间段,在这个时间段之前未完工的工件,在其后可以继续加工,工件加工允许拒绝,完工工件需要批运输到同一个客户,运输车辆无限,车容量有限,目标是极小化接受工件的总配送时间、运输费用与拒绝工件总拒绝费用之和,通过动态规划算法得到该问题的最优解;(3)单机生产,机器上有一个不可用时间段,工件加工可恢复,允许拒绝,完工工件单个立即运输,车辆无限,车容量为1,每个工件有一个交货期,目标是极小化最大延误时间、运输费用与拒绝工件的拒绝费用之和.本节给出了伪多项式动态规划算法.
【关键词】：排序 不可用时间段 配送 伪多项式 动态规划算法 拒绝
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O223
【目录】：

• 摘要3-5
• Abstract5-8
• 第1章 绪论8-14
• §1.1 排序问题概述8-9
• §1.1.1 机器有不可用时间段的排序问题8-9
• §1.1.2 供应链排序问题9
• §1.1.3 可拒绝排序问题9
• §1.2 基本概念9-11
• §1.3 研究现状11-13
• §1.4 本文的主要工作13-14
• 第2章 机器有一个不可用时间段的两台平行机可拒绝排序问题14-19
• §2.1 引言14
• §2.2 问题描述14-15
• §2.3 P_2,h_(11)|nr-a,rej|C_(max)+∑_(J_i∈R)e_j15-17
• §2.4 P_2,h_(11)|nr-a,rej|C_(max)+∑_(J_i∈R)e_j17-18
• §2.5 总结18-19
• 第3章 每台机器有一个不可用时间段的m台平行机可拒绝排序问题19-26
• §3.1 引言19
• §3.2 问题描述19-20
• §3.3 P_m,h_(i1)|nr-a,rej|∑_(J_i∈A)C_j+∑_(J_i∈R)e_j20-22
• §3.4 P_m,h_(i1)|nr-a,rej,p_j=b_js_j|∑_(J_i∈A)ω_jC_j+∑_(J_i∈R)e_j22-25
• §3.5 总结25-26
• 第4章 机器有不可用时间段的可拒绝供应链排序问题26-36
• §4.1 引言26
• §4.2 问题描述26-28
• §4.3 1|rej,p_j=a_j+b_js_j,r-a|v(∞,z),direct|1|D_(max)+∑_(J_i∈R)e_j+GB28-31
• §4.4 1|rej,r-a|v(∞,z),direct|1|∑_(J_i∈A)D_j+∑_(J_i∈R)e_j+GB31-33
• §4.5 1|rej,r-a|v(∞,1),iid|1|L_(max)+∑_(J_i∈R)e_j+GB33-35
• §4.6 总结35-36
• 第5章 研究结论、建议及研究展望36-38
• §5.1 研究结论及建议36
• §5.2 研究展望36-38
• 参考文献38-41
• 在读期间发表的论文及研究成果41-42
• 致谢42

【相似文献】

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

1 马英;左春荣;杨善林;;带不可用时间段和恶化加工时间的单机调度[J];系统工程学报;2010年03期

2 马英;杨善林;储诚斌;;带不可用时间段的部分可续型单机最大完工时间调度[J];系统工程理论与实践;2009年04期

3 马英;左春荣;杨善林;;带不可用时间段的两台同类机加权完工时间和调度[J];中国科学技术大学学报;2009年06期

4 王海明;刘吉红;王庆磊;;带不可用时间段的不允许等待柔性流水排序问题[J];兰州大学学报(自然科学版);2007年01期

5 ;[J];;年期

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

1 范静;带不可用时间段的若干单机供应链排序问题的算法研究[D];华东理工大学;2015年

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

1 池晶晶;机器有不可用时间段的可拒绝排序问题[D];曲阜师范大学;2016年

，

本文编号：776713