两种新型排序问题的近似算法——分批排序和柔性流水车间排序问题的研究

摘要

论文主要内容包括两部分.第一部分针对m台同型机,工件具有到达时间的情况,研究了分批排序问题P<,m>|r<,j>,B|ΣC<,j>.由于1|r,B|ΣC<,j>为NP-hard的,因而P<,m>|r<,j>,B|ΣC<,j>也是NP-hard的.给出了当机器台数m及批容量B均为常数情况下的PTAS算法.第二部分研究了具有可用时间限制的两道工序的柔性流水车间排序问题F<,2>(p),h<,11.1>|m<,1>,m<,2>=μ≥2|C<,max>,论文提出了几种近似算法,给出了算法的相应性能比,改进了一些已有的结果.

目录

文摘

英文文摘

第一章绪论

§1.1排序

§1.2计算复杂性

§1.3 P类，NP类和NP完备

§1.4近似算法

§1.5分批排序

第二章Pm|rj，B|∑Cj的一个PTAS算法

§2.1引言与符号

§2.2算法

§2.3结论

第三章F2(p)，h11.1|m1=1，m2=μ≥2|Cmax的近似算法及最坏情形分析

§3.1引言与符号

§3.2预序列算法及其最坏情形分析

参考文献

致谢