单机分批排序的两个新模型

论文摘要

排序论作为运筹学的一个分支，有坚实的应用背景和深刻的理论意义。分批排序是一种比较新的排序模型，其中如何使交货时间区间内加权完工工件个数最大、如何使分批排序的加工成本最小这两个问题都具有很重要的现实意义，本文就这两个问题题模型做了以下一些工作：1．在现代生产管理中，因为工件提前完工和延误完工都会增加费用，所以如何合理安排工件，使所加工的工件准时交货极为重要。当每个工件都有一个交货时间区间时，前人已经证明“交货时间区间内加权完工工件个数最大”这一排序问题是NP困难的。本文第二章讨论了只有一台批处理机时，在交货期区间内使加权完工工件数最大的分批排序问题，在Dj2-Dj1＜pj的情况下，首次给出了一个求这一问题的最优解的伪多项式时间算法。2．第三章研究了工件不允许拖期的单机分批调度问题，目标函数是使加工总成本最小。它不仅考虑了工件提前完工有提前惩罚成本，还考虑了批加工成本费用。对于这个问题，在交货期满足（?）{di+1-di}≥P的情况下，本论文首次给出了一种多项式时间的最优算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 排序问题
• §1.1.1 应用背景
• §1.1.2 排序问题的定义
• §1.2 排序问题的分类
• §1.3 排序问题的求解
• §1.3.1 计算复杂性
• §1.3.2 基本方法和技巧
• §1.4 本文主要结果及创新点
• 第二章 交货时间区间内加权完工工件个数最大的分批排序算法
• §2.1 问题背景及描述
• §2.2 算法
• §2.2.1 引理
• §2.2.2 问题的转化
• §2.2.3 区间排序问题的动态规划算法
• §2.3 小结
• 第三章 JIT方式下的单机分批调度问题的一种算法
• §3.1 问题描述及研究概况
• §3.2 数学模型
• §3.3 算法
• §3.4 应用实例
• §3.5 小结
• 参考文献
• 附录一 硕士生期间发表或完成的论文
• 附录二 致谢