前言

scheduling是指为加工若干个工件(job)或者完成若干项任务(task)，而对包括机器(machine)或者处理机(processor)在内的人、财、物等资源，按时间进行分配和安排。在数学和管理科学中把scheduling译成排序，在计算机科学和工业工程中译成调度。但是，用排序或调度作为scheduling的中文译名都只是描述了scheduling的一个侧面。scheduling既有分配(allocation)的含义，即把被加工的对象“工件”分配给提供加工的对象“机器”以便进行加工；又有排序的内涵，包括安排被加工对象“工件”的次序和安排提供加工对象“机器”的次序；还有调度的含义，即把“机器”和“工件”按时间进行调度。 从最优化的角度来讲，“工件”何时就绪，何时安装，何时开始加工，何时中断加工，何时更换“工件”，何时再继续加工原“工件”，直到何时结束此“工件”的加工；“机器”何时就绪，何时进行加工，何时空闲(idle)，何时更换“机器”，等等。这些都是按时间进行最优的分配、排序和调度。因此，把scheduling译成“排序与调度”是比较合适的。这也就是本丛书名《排序与调度丛书》的由来。此外，排序和调度默认的含义是“机器排序”(machine scheduling)。除机器排序之外，还有项目排序(project scheduling)和数据排序(data sorting)；前者包括关键路线法和计划评审技术，后者又称为整序，是一些数据按照某种要求安排先后次序的问题。

从英语的词义和词性上来分析，sequence(次序)的动名词sequencing是“安排次序”；schedule(时间表)的动名词scheduling是“安排时间表”。sequencing是一种特殊的 scheduling，是只要确定“工件”的次序就完全确定加工的时间表(schedule)问题，并不涉及“机器”的因素。在不至于混淆和不会产生歧义的情况下，可以把sequencing和scheduling都称为排序，把scheduling学科（包括scheduling的理论、方法和应用）称为排序论。但这只是通俗的表述，千万不要混淆sequencing和scheduling的含义。

排序论的开创者之一贝克尔（Baker）曾指出：“排序领域内许多早期的工作是在制造业推动下发展起来的，所以在描述排序问题时会很自然地使用制造业的术语。虽然排序问题在许多非制造业的领域内已取得相当有意义的成果，但是制造业的术语仍然经常在使用。因而，往往把资源称为机器，把任务称为工件。有时工件可能是由几个先后次序约束相互联系着的基本任务所组成。这种基本任务被称为工序。例如，对门诊患者到医疗诊所看病的排序问题也描述为‘工件’在‘机器’上‘加工’的过程。”(Introduction to sequencing and scheduling. New York: John Wiley & Sons, 1974)排序论中的“机器”和“工件”已经不是机器制造业中的“车床”和“车床加工的螺丝”，已经从“车床”和“螺丝”等具体事物中抽象出来，是抽象的概念。排序论中的“工件”可以是任务、非圆齿轮、计算机终端、患者、降落的飞机等，“机器”可以是完成任务所需要的人财物资源、数控机床、计算机的中央处理器、医生、机场跑道等。例如，计算机科学中并行计算机的出现，促进排序论中对并行机排序的深入研究；反过来，排序论中的并行机可以应用到计算机科学的并行计算中去，并行机排序的成果在一定程度上推动并行计算和并行计算机的发展。

第二次世界大战期间运筹学(operational research)兴起，首次把运作(operations)作为研究(research)的对象。其间，研究运作的时间安排促成排序概念的建立和研究的开展。在20世纪中叶运筹学奠基时期，排序论的先驱工作已经在离散优化领域占有重要地位。此后，排序论始终保持蓬勃发展的势态。普遍认为1954年约翰逊（Johnson）发表的论文(Optimal two- and three-stage production schedules with setup times included. NRL, 1954,1:61-68)是经典排序的第一篇。这篇论文问世以来的60多年内全世界已经发表排序论文献4000余篇（见本书的附录B排序与调度文献）。国际上著名排序论专家波茨（Potts）等把前50年中每10年的排序论研究概括为一个主题，这5个研究主题是组合分析、分支定界、计算复杂性和分类、近似算法、现代排序。最近20年排序论与博弈论和行为科学交叉，排序博弈、供应链排序和手术排程等领域都有较大的发展。

20世纪60年代越民义就注意到排序问题的重要性和在理论上的难度。1963年他编写国内第一本排序论讲义。70年代初他和韩继业研究同顺序流水作业排序问题，开创了中国研究排序论的先河。在他们两位的倡导和带动下国内排序论的理论研究和应用研究有了较大的发展。1990年全国第一次排序论学术交流会在上海召开，会议期间成立了中国运筹学会排序分会（专业委员会）。30多年来排序分会开展学术交流、举办研讨班；推广国际上采用的三参数表示，推进排序论研究的正规化；编辑和修订“英汉排序与调度词汇”，促进排序论术语统一，以利于国内外学术交流。

编辑“英汉排序与调度词汇”, 是排序分会多年以来一直在提倡和推进的工作。科学用词, 不但需要对中文和英文两种文字的扎实基础, 更需要对于其在排序与调度的学术内涵和外延上的准确理解, 还要考虑使用的习惯和方便, 同时需要不断地改进和修改。经过排序分会多次讨论和反复修改, 列出英文用词相应不止一种的中文用词, 经过比较, 确定合适的中文译名; 排序论术语逐步统一, 是学科成熟的标志, 也是学术交流的需要。近年来“英汉排序与调度词汇”还作为《排序与调度丛书》各册的附录A与丛书一起出版。因此，在“英汉排序与调度词汇”的基础上编写一本《排序与调度辞典》就尤为重要。正是在这样的背景下，结合丛书每册书后的索引，我们编写这册《排序与调度辞典》，水到渠成，《排序与调度丛书》完美收官。

本辞典是解释排序与调度条目的工具书，收录条目638条，涉及运筹、管理和计算机等多门学科。每个条目列出执笔人和校阅人，以增强责任感，文责自负。本书的附录B是“排序与调度文献”，收录已经公开发表的国内外4279条排序与调度文献（扫二维码可获得）。只要书籍和期刊有正式的书号和刊号，我们都收录。

在此书出版后我们仍然会继续编辑排序与调度条目和文献。如果要增加条目和文献，请按地址gctang@sspu.edu.cn给我们发E-mail，我们收到后会给予答复，并提供最新版本的电子文件。

作者

2022年5月