论文题目: 工件加工时间可变的现代排序问题
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 王吉波
导师: 夏尊铨
关键词: 排序,单机,流水作业,线性加工时间,有跟森林,串并有向图,最坏情况界,最优算法,恶化工件,可控加工时间,学习效应
文献来源: 大连理工大学
发表年度: 2005
论文摘要: 排序问题是一类重要的组合优化问题。在经典排序问题中,通常假设工件的加工时间为常数。但在许多实际问题中,工件的加工时间可能与其开工时间、所用资源或所排位置有着某种联系,由此产生一些现代排序问题.这些现代排序问题比经典排序问题更为复杂,绝大多数都是NP-难问题.对这些NP-难问题,讨论它的近似算法,并给出算法的最坏情况界很有必要;考虑实际应用的需要,研究现代排序问题存在多项式算法的情况也很有必要,这些问题的多项式算法一方面可以对某些问题给出求解方法,另一方面还可以为解决其它问题提供近似算法。本文研究工件加工时间可变的现代排序问题,主要在如下几个方面做了一些工作: 1.工件加工时间是开工时间的增加函数的排序问题。 (a)最大完工时间单机排序问题。对于一般模型中工件具有有跟森林约束和有串并有向图约束的极小化最大完工时间单机问题分别给出了最优算法。 (b)加权完工时间和单机排序问题.对增长率与基本加工时间相关且工件具有有跟森林约束和有串并有向图约束的的单机问题进行研究,分别给出了最优算法。 (C)流水作业排序问题.对机器间满足优势关系的不等待或无空闲问题进行研究,目标函数分别为最大完工时间、加权完工时间和与最大延误,对它们分别给出了最优算法。 2.工件加工时间是开工时间的减少函数的排序问题。 (a)单机排序问题。研究递减率与基本加工时间相关的单机问题,对最大完工时间问题、加权完工时间和问题、工件具有平行链约束的加权完工时间和问题、最大费用问题与最大延误问题分别给出了最优算法。 (b)流水作业排序问题。对两台机器极小化最大完工时间问题,证明了利用John-son规则可以求得最优排序。对工件各工序基本加工时间均相等的流水作业问题进行了研究,并对某些情况给出了明确结论。 3.加工时间可控的单机可控排序问题。 首先,研究加工时间一般可控的排序问题,目标函数分别为极小化完工时间和、完工时间偏差和与压缩费用的线性组合,等待时间和、等待时间偏差和与压缩费用的线性组合。提前时间、延误时间、工期与压缩费用的线性组合。所有这些问题都可转化为指派问题,从而多项式时间可解。其次,研究加工时间离散可控的排序问题,对几类多目标问题进行了转化。4.具有学习效应的排序问题. 对单机问题,研究了几类多目标问题,它们都可转化为指派问题,从而多项式时 间可解.对流水作业问题,用反例说明在工件引入学习效应后经典的Johllson规则 对两台机器最大完工时间问题不是多项式最优算法,从而用,Jo hnson规则作为它的 近似算法,分析了它的最坏情况界.对m台机器最大完工时间与完工时间和情况, 分别给出了近似算法并分析了它们的最坏情况界.同时对某些特殊情况给出了多项 式算法.关键词:排序,单机,流水作业,线性加工时间,有跟森林,串并有向图,最坏情况界,最优算法,恶化工件,可控加工时间,学习效应
论文目录:
中文摘要
Abstract
1 绪论
1．1 概述
1．2 经典排序问题与现代排序问题
1．3 研究概况
1．4 本文研究内容与主要结果
2 工件加工时间是开工时间的增加函数的排序问题
2．1 引言
2．2 增长率与基本加工时间无关的单机排序问题
2．3 增长率与基本加工时间相关的单机排序问题
2．4 增长率与基本加工时间相关的流水作业问题
3 工件加工时间是开工时间的减少函数的排序问题
3．1 引言
3．2 递减率与基本加工时间相关的单机问题
3．3 递减率与基本加工时间相关的流水作业问题
3．4 小结
4 加工时间可控的单机可控排序问题
4．1 引言
4．2 具有总绝对差的可控排序问题
4．3 具有多个共同工期的可控排序问题
4．4 离散可控单机排序问题
4．5 小结
5 具有学习效应的排序问题
5．1 引言
5．2 单机问题
5．3 流水作业问题
5．4 小结
6 结论与展望
参考文献
索引
发表论文情况
论文创新点摘要
致谢
发布时间: 2005-05-13
参考文献
- [1].不确定情形下若干排序问题的研究[D]. 沈佳煜.南京理工大学2017
- [2].新型排序问题的计算复杂性研究[D]. 高园.郑州大学2018
- [3].依赖于资源分配的排序问题研究[D]. 殷娜.上海大学2015
- [4].若干排序问题研究[D]. 李好好.浙江大学2014
- [5].平行机半在线排序问题[D]. 罗润梓.上海大学2005
- [6].当代工业中的若干排序问题研究[D]. 季敏.浙江大学2006
- [7].通讯网络中排序问题的若干在线和高性能算法[D]. 叶德仕.浙江大学2005
- [8].关于分批排序问题的研究[D]. 李文华.郑州大学2006
- [9].窗时排序问题中的最优化算法研究[D]. 赵洪銮.山东大学2007
- [10].带尺寸、可拒绝的分批排序[D]. 张咸昭.曲阜师范大学2007
相关论文
- [1].若干组合优化问题的近似算法设计与分析[D]. 陈仕平.浙江大学2002
- [2].与Due Date相关的排序问题研究[D]. 沈灏.浙江大学2002
- [3].平行机半在线排序问题[D]. 罗润梓.上海大学2005
- [4].若干批处理机排序与装箱问题的算法研究[D]. 石永强.浙江大学2005
- [5].关于分批排序问题的研究[D]. 李文华.郑州大学2006
- [6].延误与离散可控排序[D]. 张树霞.华东师范大学2007
- [7].窗时排序问题中的最优化算法研究[D]. 赵洪銮.山东大学2007
- [8].关于重新排序问题的研究[D]. 慕运动.郑州大学2007
标签：排序论文; 单机论文; 流水作业论文; 线性加工时间论文; 有跟森林论文; 串并有向图论文; 最坏情况界论文; 最优算法论文; 恶化工件论文; 可控加工时间论文; 学习效应论文;