前言

众所周知，运筹学是一门应用性非常强的交叉学科，涉及数学、管理科学和计算机科学等多个学科。它首先将一个复杂的问题抽象为数学模型，然后使用数学的理论和方法给出最优的解决方案，再借助计算机编程等手段，最后提供给管理人员使用并作出最终的科学决策。因此，我们可以看出，运筹学的本质是为了“优化”。当优化的目标函数只有一个时，称为单目标优化。比如，你从一个地方到另一个地方，你会关心走哪条路线的距离更短。这就是运筹学中最经典的最短路径问题。单目标优化相对来说比较简单，在相关文献中已经被广泛研究，给出最优解或者近似解都比较容易一些。例如，对上述最短路径问题， DIJKSTRA算法、 BELLMAN-FORD算法和 FLOYD算法等都是非常有效的。

当优化的目标函数有两个或两个以上时，称为多目标优化。在理想情形下，决策者当然希望多个目标都能同时达到最优。然而，在大多数情形，同时满足多个不同目标的最优解往往是不存在的。比如我们想买一辆汽车，价格、品牌、油耗、外观和安全性等都要考虑。俗话说“便宜无好货，好货不便宜”，这表明在大多数情形下不同目标函数之间是“冲突”的。因此，在求解一个多目标优化问题时，得到的解通常是一个或者一组均衡解。 

Scheduling，中文一般翻译成排序、调度或者排程。为了方便，本书统一称为排序。所谓排序，就是在满足一定的约束条件下对工件和机器按时间进行分配，找到一个可行解，使得一个给定的目标函数尽可能小（或者尽可能大）。对排序理论的研究最早起源于 20世纪 50年代。随着各种先进机器的发明及应用，生产能力大幅提高，工业生产也得到了迅速发展。工件（或者订单）数量急剧增加，工件的加工条件也各不相同，这使得找到一个可行解或者最优解变得非常困难。一个坏的解（排序）不仅会使生产成本剧增，甚至可能会导致结果不可行，即在规定的时间内无法加工完成所有的工件。大规模机器生产的出现，促使一些工业管理者和研究人员研究排序理论。因此，工业化大生产促进了排序理论研究的迅速发展 ;而反过来，排序理论的研究也进一步促进了工业生产的发展。机器制造业的迅速发展，使得产品数量和购买需求急剧增加，这也需要有更多的人员来运输、销售和维护这些产品。这些因素又促进了服务行业（包括运输、商业、金融、医疗、通信和计算机网络等）的快速发展。很快人们发现排序理论能够广泛应用在不同的服务行业中，这时用“机器”代表“服务提供者”，而用“工件”代表“顾客”或者“订单”。

1954年，JOHNSON在Naval Research Logistics发表了他的论文“ Optimal two-and three-stage production schedules with setup times ncluded”，大多数排序研究人员普遍认为这是第一篇研究生产排序问题的论文。自此之后，关于排序问题研究的论文层出不穷。然而，在 20世纪 80年代之前，人们主要研究一些经典的单目标排序问题。后来，人们发现在实际应用中往往要同时考虑多个目标函数。例如，在一个工厂中，为了降低生产费用，这需要使工件的最大完工时间 Cmax越小越好 ;为了降低储存费用，也要最小化工件的加权完工时间和艺wjCj ;同时为了提高顾客的满意程度，还必须最小化误工工件的数量艺 Uj。因此，仅考虑一个目标函数往往都是不平衡的，这促使人们越来越多地关注和研究多目标排序问题。因为多个目标函数之间往往有一定的“冲突”关系，所以如何在不同目标函数之间寻求平衡最为关键。

本书共包含 7章:其中，第 1章给大家介绍了排序问题的基本定义和概念，国内外当前研究的现状以及研究多目标排序的一些常见方法 ;第 2章介绍了一些经典的单机多目标排序结果 ;第 3章给出了单机批加工多目标排序的一些结果 ;第 4章介绍了多台机器多目标排序的一些结果 ;第 5章介绍了工件可拒绝排序的一些结果;第 6章和第 7章分别介绍了重新排序和多代理排序的一些结果。

本书的编写得益于唐国春教授的极力推动，并得到了“排序与调度丛书”编委会各位专家学者的支持和帮助。为了完成本书，我们还参考了唐国春教授等撰写的《现代排序论》、万国华教授撰写的《排序与调度的理论、模型和算法》以及 T’KINDTH与 BILLAUT所著的 Multicriteria Scheduling: Theory，Models and Algorithms。除此之外，我们还要感谢慕运动、马冉、刘其佳、耿志超、高园以及赵秋兰等几位老师对撰写本书所提供的帮助。最后，我们也要感谢国家自然科学基金（项目号 : 12271491、11971443、12261039和 11901168）以及河南省高等教育教学改革研究与实践项目-研究生教育（项目号 : 2019SJGLX051Y）的资助。

本书的主要目的是向读者介绍多目标排序的一些常见模型、研究方法和主要结果。因为编者水平有限，所以本书主要选取了编者比较熟悉的一些论文结果。这些结果大部分来自于郑州大学林诒勋教授和原晋江教授指导的博士论文。书中一定存在很多缺点和不足之处，敬请读者和各位专家学者批评指正。特别地，国内外很多同行的优秀成果没有被编入本书，敬请大家见谅。

录岭法 

2023年 7月