排序问题是一类重要的组合最优化问题,是运筹学研究的一个非常活跃的分支,广泛地应用于管理科学、计算机科学、工程技术、制造业、运输业、分派销售和其他服务行业。它研究如何在有限的资源限制和约束下对于给定的一些“工件”或“活动”从时间上和顺序上进行合理的安排和分配,以使某目标(如生产效率、资源利用率和合格率等)达到或接近最优。
动态规划是运筹学的一个重要分支。动态规划方法是研究多阶段决策过程最优化的一种数学方法,通过把多阶段过程划分为一系列相互联系的单阶段过程,再逐个阶段求解,从而使整个过程达到目标最优。动态规划方法在工程技术、经济管理、工业生产和军事等方面都有着广泛的应用。动态规划方法没有统一的标准模型,没有统一的处理格式。它必须依据问题本身的特性,利用灵活的数学技巧来处理。在排序与调度领域中,存在大量NP难的多阶段决策问题,用动态规划方法求得精确最优解是非常有效的方法之一。
现有讨论排序问题的书籍中,绝大多数是从问题的模型角度进行分类研究,很少从解决问题的方法角度展开讨论。本书系统地介绍了排序理论和动态规划理论方面的研究成果,讨论动态规划方法在解决排序与调度问题中的应用。从众多用动态规划方法求解的排序问题中选取有代表性的部分问题,进行总结和分析。读者通过本书可以对动态规划在排序问题中的应用有全面的了解和认识。
本书共分7章。第1章介绍动态规划的基础知识;第2章介绍排序问题的基本理论;第3章讨论经典的单机排序问题的动态规划求解方法;第4章研究若干新型排序问题的动态规划解法,其中包括分批排序问题、成组加工排序问题、可控排序问题以及可拒绝排序问题;第5章讨论如何用动态规划方法解决供应链排序问题;第6章研究双代理排序问题的动态规划解法;第7章讨论利用动态规划算法设计完全多项式时间近似方案(FPTAS)的应用成果。其中第1章、第5章由沈阳师范大学柏孟卓撰写,第6章、第7章由重庆师范大学张新功撰写,第2章至第4章由柏孟卓、张新功共同撰写。
本书内容既包含了用动态规划方法求解排序问题的经典研究成果,也包含了作者多年来研究工作积累的成果。本书从最初的构想到最终的成稿,一直得到唐国春教授的大力推动与悉心指导。此外,我们还得到了清华大学出版社编辑的细心帮助。在此向唐国春教授和清华大学出版社表示深深的感谢!
本书可以作为运筹与管理、计算机和自动化等相关学科的教师和学生的参考书。由于作者时间有限,书中或会有不妥之处,恳请读者批评指正!