本书主要介绍若干平行批处理机生产模型的解决方案, 即设计有效的算法从而得到较好的生产计划。平行批处理机问题的特点是每一台加工机器可以同时加工多个任务, 目标是设计合理的生产安排使得效率更高。同时在生产过程中加工任务允许中断重启。这意味着当新任务到达时可以中断正在加工的任务, 并和新任务重新开始一起加工。与不允许加工任务中断相比, 允许中断重启得到的生产安排往往更加高效。本书介绍了多个允许中断重启的平行批处理机生产模型的应用背景及高效生产计划。

1 绪论

1.1 排序论概述

1.2 算法和计算复杂*

1.3 排序的相关知识及进展

******2 允许有限重启的多台平行批处理机排序问题

******2.1 问题介绍 2.2 算法A（α）及相应排序的*质

******2.3 问题的下界

2.4 在线算法

3 允许有限重启的单台平行批处理机排序问题

3.1 问题介绍 3.2 批容量为2时问题的下界

3.3 批容量为2时的在线算法及竞争比分析

3.4 批容量大于2时问题的下界

3.5 批容量大于2时的在线算法及竞争比分析

4 允许重启的单台平行批处理机排序问题

******4.1 问题介绍

4.2 批容量为3时问题的下界

******4.3 批容量为3时的在线算法及竞争比分析

4.4 批容量大于3时问题的下界

4.5 批容量大于3时的在线算法及竞争比分析

******4.6 允许k-有限重启（k≥2）时的问题

5 带有重启和运输的平行批处理机排序问题

5.1 问题介绍

5.2 批容量为2时问题的下界

******5.3 批容量为2时的在线算法及竞争比分析

5.4 批容量大于2时问题的下界

5.5 批容量大于2时的在线算法及竞争比分析

参考文献