若干网络排序问题的算法和复杂性研究
| 摘要 | 第1-6页 |
| Abstract | 第6-10页 |
| 第1章 绪论 | 第10-24页 |
| ·组合优化问题、算法和复杂性 | 第10-14页 |
| ·在线算法和竞争比 | 第14页 |
| ·网络排序问题 | 第14-18页 |
| ·问题背景 | 第14-16页 |
| ·数学描述 | 第16-18页 |
| ·文献综述 | 第18-21页 |
| ·单机VSP问题 | 第18-19页 |
| ·平行机VSP问题 | 第19-20页 |
| ·网络作业排序 | 第20页 |
| ·在线VRP问题 | 第20-21页 |
| ·论文概述 | 第21-22页 |
| ·文献注记 | 第22-24页 |
| 第2章 线形网络上的VRP问题 | 第24-40页 |
| ·引言 | 第24-25页 |
| ·一般正则目标问题 | 第25-33页 |
| ·单机一般正则求和目标 | 第25-26页 |
| ·单机加权延误工件数 | 第26-28页 |
| ·单机加权总延误 | 第28-30页 |
| ·工件有共同工期的单机加权延误工件数和加权总延误 | 第30-31页 |
| ·单机一般正则瓶颈目标 | 第31-32页 |
| ·平行机一般正则目标 | 第32-33页 |
| ·有准备时间约束的平行机极小化时间表长问题 | 第33-40页 |
| ·返回型 | 第33-37页 |
| ·不返回型 | 第37-40页 |
| 第3章 线形网络上的单机VSP问题 | 第40-52页 |
| ·引言 | 第40-41页 |
| ·符号说明 | 第41-42页 |
| ·算法描述 | 第42-43页 |
| ·返回型问题的性能比分析 | 第43-48页 |
| ·不返回型问题的性能比分析 | 第48-52页 |
| 第4章 在线不返回型TSP和QTSP | 第52-64页 |
| ·引言 | 第52-53页 |
| ·符号说明 | 第53页 |
| ·在线不返回型TSP的算法及分析 | 第53-54页 |
| ·在线QTSP的算法及分析 | 第54-57页 |
| ·QTSP的近似算法 | 第57-60页 |
| ·不返回型QTSP的近似算法 | 第60-64页 |
| 第5章 网络作业排序问题 | 第64-86页 |
| ·引言 | 第64-65页 |
| ·符号说明 | 第65页 |
| ·一般网络上的自由作业排序 | 第65-76页 |
| ·两台机器返回型问题 | 第65-70页 |
| ·两台机器不返回型问题 | 第70-73页 |
| ·m台机器情形 | 第73-76页 |
| ·树形网络上的两台机器流水作业排序 | 第76-86页 |
| ·NP困难性证明 | 第76-78页 |
| ·返回型问题的10/7-近似算法 | 第78-86页 |
| 第6章 结论 | 第86-88页 |
| 参考文献 | 第88-94页 |
| 致谢 | 第94-96页 |
| 在读期间完成的论文 | 第96-97页 |
| 卷内备考表 | 第97-98页 |
