本书是编者在广泛收集国内外相关文献和资料的基础上，结合自己的研究成果编写而成，旨在为相关专业的高年级大学生、研究生和科研工作者提供系统、深入的排序与调度理论和算法方面的基础知识.

排序与调度问题的目标是按时间合理地安排稀缺资源，最有效地完成给定的任务。排序与调度问题有着广泛、深刻的应用背景，在制造业和服务业中均起着重要作用，是各类组织提高运营效率、降低成本乃至取得竞争优势的重要手段和有力工具。

虽然排序与调度论的重要性并不亚于排队论和库存论，但它却是运筹学的一个年轻分支。排序与调度数学模型的出现和分析几乎比电话系统的排队分析(Erlang，1909)和库存论中的经济批量模型(Harris，1913)晚了四五十年。1954年Johnson发表在Naval Research Logistics上的论文讨论了两台机器上的流水作业问题，建立了问题的数学模型并给出了模型的求解算法。1956年Jackson把该模型扩展到异序作业情形，Smith研究了多个单机排序问题的模型和求解算法。这些研究工作揭开了排序与调度问题研究的序幕，从此，排序与调度问题的研究得到飞速发展和广泛应用，取得了重大的经济效益和社会效益。自20世纪70年代以来，我国也有不少学者研究了排序与调度问题。其中，越民义、韩继业、唐国春、林诒勋和陈荣秋等学者在此领域做出了突出贡献。目前，我国从事排序与调度问题研究的人员数量增长迅速，但除了学术刊物上的论文和若干介绍文章之外，排序与调度方面的教材和专著还不够多。随着排序与调度问题研究的飞速发展，新问题、新模型和新方法不断涌现，同时，对排序与调度问题有兴趣的研究人员也越来越多，因此亟须全面、系统地介绍排序与调度的理论、模型和算法的书籍。

本书的编写主要取材于Pinedo(2016)、Baz·ewicz等(2001)、Parker(1995)、Baker和Trietsch(2009)等的教材和专著及学术刊物上的相关文献，并结合了编者的教学和研究实践。全书共分8章： 第1章介绍排序与调度问题的定义、功能和作用，并给出制造和服务业中若干排序与调度问题的实例； 第2章讨论排序与调度问题的表示及分类，以及分析和求解排序与调度问题的一般方法； 第3~8章介绍单台机器排序与调度问题及其高阶模型、多台平行机排序与调度问题、流水作业、异序作业和自由作业排序与调度问题。

本书在每章最后有一个小结与讨论，内容主要是本章小结及重要参考文献，并对相关问题的研究历史作简要的介绍。章后附有大量的参考文献，在提供排序与调度问题基础知识的同时，也有利于初学者了解排序与调度问题的历史和发展，以激发学习和研究的兴趣。

本书的编写得益于唐国春先生的极力推动，并得到了“排序与调度丛书”编辑委员会各位同仁的鼎力支持，清华大学出版社汪操编辑在本书的出版过程中提供了有力的支持和帮助。没有他们的支持与帮助，很难想象编者可以完成本书的编写。编者在本书的写作过程中与Pinedo教授有多次交流，受益匪浅，他的名著Scheduling： Theory, Algorithms and Systems是本书写作的主要参考书。越民义、韩继业和唐国春三位先生在百忙中拨冗审阅了本书，李德彪博士帮助整理了参考文献。在此，编者对上述各位表示衷心的感谢！

本书的写作得到国家自然科学基金(项目号：71125003和71421002)的资助，特此鸣谢。

由于编者学术水平以及写作时间的限制，书中一定存在不少缺点和不当之处，敬请读者和同仁批评指正，以便在再版时修订。

万国华上海交通大学2018年12月

第1章引论

1．1排序与调度： 定义、功能和作用

1．1．1排序与调度问题的定义

1．1．2排序与调度问题在制造/服务业中的地位与功能

1．2排序与调度： 典型问题举例

1．2．1工厂的产品装配问题

1．2．2集装箱码头吊车调度问题

1．2．3医院护士排班问题

1．2．4计算机系统中的进程调度问题

1．3小结与讨论

参考文献

第2章排序与调度问题： 定义、分类和求解

2．1排序与调度问题： 定义和记号

2．2排序与调度问题： 解的定义及类型

2．3排序与调度问题： 计算复杂性层次

2．4排序与调度问题的分析和求解

2．5小结与讨论

参考文献

第3章单机排序与调度： 基本模型

3．1(加权)总完工时间问题

3．1．1问题1‖∑wjCj

3．1．2问题1|rj|∑wjCj

3．1．3问题1|d～j|∑wjCj

3．2最大延迟问题和最大延误问题

3．3总延误问题

3．4（加权）总延误问题

3．5(加权)延误工件总数问题

3．6小结与讨论

参考文献

第4章单机排序与调度： 高阶模型

4．1工件存在约束关系的问题

4．1．1工件之间约束关系的有向图

4．1．2(加权)总完工时间问题

4．1．3问题1|prec|hmax

4．1．4问题1|prec|∑gj(Cj)

4．2非正则目标函数问题

4．2．1问题1|dj=d|∑(Ej+Tj)

4．2．2问题1‖∑(w1jEj+w2jTj)

4．3存在设置时间的问题

4．3．1问题1|sjk|Cmax

4．3．2问题1|fmls，sgh|∑wjCj

4．3．3问题1|fmls，sgh|Lmax

4．3．4问题1|fmls，sgh|∑Uj

4．4小结与讨论

参考文献

第5章平行机排序与调度

5．1时间表长度问题

5．1．1问题Pm‖Cmax及问题Pm|prec|Cmax

5．1．2问题Pm|prmp|Cmax

5．1．3问题Pm|prec|Cmax

5．1．4问题Pm|prmp，prec|Cmax

5．1．5问题P∞|prec|Cmax

5．2（加权）总完工时间问题

5．2．1问题Pm‖∑Cj

5．2．2问题Pm|prec|∑Cj

5．3目标函数与交货期相关的问题

5．4小结与讨论

参考文献

第6章流水作业排序与调度

6．1流水作业： 无限缓冲区

6．2流水作业： 有限缓冲区

6．3柔性流水作业

6．4小结与讨论

参考文献

第7章异序作业排序与调度

7．1异序作业排序与调度问题

7．2问题的析取图表示

7．3分支定界法

7.4移动瓶颈法

7．5小结与讨论

参考文献

第8章自由作业排序与调度

8.1时间表长度问题

8.1.1不可中断情形： 问题Om‖Cmax

8.1.2可中断情形： 问题Om|prmp|Cmax

8.2最大延迟问题

8.2.1不可中断情形： 问题Om‖Lmax

8.2.2可中断情形： 问题Om|prmp|Lmax

8.3其他自由作业问题

8．4小结与讨论

参考文献

索引

附录A英汉排序与调度词汇

本书是排序与调度领域的入门书，《排序与调度丛书》为“十三五”国家重点图书规划项目，2017年国家出版基金资助

万国华，上海交通大学特聘教授、博士生导师，安泰经济与管理学院副院长。在香港科技大学取得博士学位，并在香港科技大学、澳门大学和美国纽约大学从事科研和教学工作，2011年获“国家杰出青年科学基金”。主持完成10余项国家及省部级研究项目，出版英文学术著作一部，研究成果发表于Operations Research等国际权威学术刊物。现任Production and Operations Management的高级编辑，中国管理科学与工程学会常务理事和上海市运筹学会副理事长。