分批排序问题和资源约束排序问题

摘要

排序问题是一类重要的组合最优化问题。本文讨论了分批排序、流水成组排序和资源约束排序问题。文章分三部分：带到达时间的分批排序的数学模型；带滞留时间的流水作业成组排序问题的多项式算法；三个资源约束排序的最优算法。　　第二章给出了问题1|B，rj|Cmax的0-1整数规划模型；利用统计软件SAS中的LP过程编程对这一模型进行数值求解实验，得到了按此数学模型计算机能求得最优解的该问题的规模.　　第三章讨论了带滞留时间的两台同顺序成组流水作业排序问题F2|Sij，GT|Cmax，分析证明了此问题存在的多项式算法。　　第四章讨论了两个单机排序的资源分配问题1|rj，pj=bj-ajuj，Cmax≤^C|∑uj和1|rj，prec，pj=bj-ajuj，Cmax≤^C|∑uj，以及离散资源约束排序问题P2|res…，pj=a，2a，|Cmax(加工时间相等的任务不能在两台机器上同时加工)。分析证明了这些问题存在多项式算法。

目录

文摘

英文文摘

苏州大学学位论文独创性声明及使用授权声明

第一章序言

1.1背景

1.2符号

1.3论文的主要内容

第二章带到达时间的分批排序问题的模型

2.1引言

2.2排序问题1 ｜B，rj｜ Cmax的数学模型

2.3数学模型的数值求解实验

2.4数学模型的改进及数值求解实验

第三章带滞留时间的流水作业成组排序问题

3.1引言

3.2问题的最优排序方法

第四章资源约束排序

4.1引言

4.2两台同速机的最小完工时间离散资源约束排序问题

4.3带到达时间的单机排序中的资源分配问题

第五章总结

附录：SAS程序

参考文献

致谢