两类资源受限的排序问题研究

发布时间：2021-12-31 08:31

　　为有效的生产,排序模型和算法被广泛地应用于制造领域。然而,资源的短缺导致生产效率和生产收益越来越低。本文研究两类资源受限的生产排序问题:问题一,考虑具有额外资源的平行机排序问题,即每个工件的加工不仅需要机器而且还需要一些额外的资源才能完成,且需要相同资源的两个工件不能在同一时刻加工,目标为极小化最大完工时间。问题二,我们考虑具有柔性维护周期的单机排序,此情形下,所有的工件必须在周期的时间窗口加工,目标为极小化误工工件数。全文共分为四章。第一章主要介绍一些排序问题和计算复杂性理论的基础知识。特别地,我们对资源受限排序问题进行了简单介绍。第二章讨论问题一。首先,根据决策变量的不同选择,给出了所考虑问题的四种不同的数学规划模型。其次,基于LPT算法设计了求解该问题的近似算法ILPT,并证明了该算法的最坏情况界为2-2m+1。最后,我们注意到文献中一个基于LPT的算法LLPT和ILPT算法在理论上有相同的界,并且我们通过数值实验评估了该算法的性能。第三章研究具有柔性维护周期的单机排序问题。首先证明了极小化误工工件数问题是不可近似的,即不存在具有常数界的近似算法。接着给出了求解一般问题的伪多项式... 

【文章来源】：杭州电子科技大学浙江省

【文章页数】：42 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
1 绪论
    1.1 排序问题
    1.2 算法与复杂性
    1.3 经典排序问题
    1.4 资源受限的排序问题
    1.5 论文概述
2 带有额外资源的平行机排序问题
    2.1 问题描述
    2.2 研究现状
    2.3 数学规划模型
    2.4 ILPT算法及其近似比分析
    2.5 LLPT算法与数值实验
    2.6 本章小结
3 具有柔性维护周期的单机排序问题
    3.1 问题描述及符号说明
    3.2 不可近似性证明
    3.3 动态规划算法与可解情形
    3.4 本章小结
4 结论
致谢
参考文献
附录


【参考文献】：
期刊论文
[1]2003年到2005年排序（调度）学科在中国的发展（I）[J]. 唐国春.  上海第二工业大学学报. 2006(03)
[2]排序问题的简短历史和国外发展动态[J]. 孙世杰.  运筹学杂志. 1991(01)
[3]排序问题的定义、分类和在国内的某些研究进展[J]. 唐国春.  运筹学杂志. 1990(02)

博士论文
[1]面向订单生产的供应链排序问题研究[D]. 王磊.暨南大学 2011

硕士论文
[1]两种排序问题的近似算法[D]. 谷会昆.浙江大学 2004



本文编号：3559943