几类分批排序和在线排序问题的复杂性

摘要

排序问题是一类重要的组合优化问题,它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域,而其中的分批排序以及在线排序问题,因其明显的实际意义,更是吸引了国内外许多学者.该文主要研究这两类排序问题.论文共分四章.第一章(绪言)主要介绍了排序的产生背景、发展及其一些符号等相关的基本知识.第二章讨论的是带惩罚费用的单位工时的工件在平行机上的在线排序.该章是由工件在一台机器上的在线情况([6]),推广到在任意台同型平行机上.文中针对m台同型平行机,设计一在线算法G1,并给出了此算法的竞赛比为1/2(2+√3)≈1.86602.第三章主要研究了复制法在分批排序中的应用.揭示了分批排序与经典排序之间的联系.第四章讨论的是几个极小化加权总完工时间的分批排序问题.对于这几个问题,在一般情况下的NP-完备性都是已知的([17][18]),但对于工时恒等这一特殊情况,还未见有人讨论.

目录

文摘

英文文摘

第一章序言

§1.1排序

§1.2计算复杂性

§1.3 P类和NP类

§1.4近似算法

§1.5分批排序和在线排序

第二章带有惩罚费用的平行机在线排序

摘要

§2.1引言

§2.2预备知识

§2.3算法及其分析

§2.4主要定理

§2.5结论

第三章复制法及其在分批排序问题中的应用

摘要

§3.1引言

§3.2符号和定义

§3.3主要结果

§3.4结论

第四章极小化加权总完工时间的分批排序问题

摘要

§4.1引言

§4.2工件在单批处理机上的情形

§4.3工件在同型平行批处理机上的情形

§4.4结论

参考文献

在校期间的研究成果及发表的学术论文

致谢