第1章
排序论概述

1.1　排序问题

20世纪50年代提出了排序问题（Johnson，1954），通过几十年的发展，解决排序问题的理论（排序理论）逐步形成并得到了巨大的发展（Potts，2009），成为运筹学中一个独立发展的研究领域，其理论日趋完善（万国华，2019）。排序理论所研究的对象从最初的制造业扩展到各类非制造业，其应用领域越来越广泛，从而归纳出许多有别于经典排序的新型排序模型（唐国春等，2003），所得到的丰富理论和有效方法可以用于处理与解决广泛的实际问题。由于排序理论的应用领域广泛，使其所研究的问题及其类型呈现出多样性，并且复杂程度更高，从而进一步推动了排序理论的发展，近几十年排序理论成为运筹学中研究最为广泛的领域之一。

排序理论的许多早期研究工作是由制造业领域所提出的问题推动的，特别是生产作业调度，因此，我们现在研究排序理论都是将需要完成的工作、任务、被服务的对象统称为“工件”，将完成工作、任务、服务所需要的资源统称为“机器”，把完成工作、任务、服务的过程看成“工件”被安排在“机器”上加工。

设有n个工件J＝｛1，2，…，n｝，若是单台机器排序问题，则工件j（j＝1，2，…，n）有一确定的加工时间pj＞，若是多台机器排序问题，则设有m台机器M＝｛M1，M2，…，Mm｝，若工件j被安排在机器Mi（i＝1，2，…，m）上加工，则其加工时间为pi j。对于经典排序模型，其基本假设为一台机器在任何时刻最多加工一个工件，一个工件在任何时刻至多在一台机器上被加工。工件j有一权wj表示工件的重要性。工件j有一交货期dj，当工件j在交货期dj之前完成加工，我们称工件j按时完工，当工件j在交货期dj之后完成加工，也就是工件加工发生误工，有一个惩罚。工件j有一就绪时间rj，表示工件j在时刻rj之后才能被安排加工，对于多台机器问题，工件j在不同的机器上可以有不同的就绪时间，即工件j被安排在机器Mi上加工，其就绪时间为ri j，表示工件j在时刻ri j之后才能在机器Mi上开始加工。在本书中我们假定工件的相关参数都是非负整数。

工件加工限制条件包括工件之间有前后约束关系表示工件j只有在工件k完工之后才能开始加工。工件加工可分为不可中断与可中断，工件加工不可中断表示一个工件一旦安排在某台机器上开始加工，则必须在这台机器上连续加工完成，工件加工可中断表示一个工件被安排在某台机器上加工以后，在没有完成加工之前任何时候都可以停止加工，该台机器可以安排加工其他工件，而被停止加工的工件可以在以后的任何时刻在任何一台空闲机器上恢复加工。

用Cj表示工件j的完工时间，Lj＝Cj－dj称为工件j的延迟，Tj＝max｛0，Cj－dj｝称为工件j的延误，Uj＝0或1称为工件j的误工数，即当Cj≤dj时，Uj＝0，即工件j加工没有误工，其误工数为0，当Cj＞dj时，Uj＝1，即工件j加工发生误工，其误工数为1。

所谓排序就是将若干个需要加工的工件安排到机器上，分配并确定每个工件加工的时间段，使被考虑的目标函数值最优。在经典排序中，目标函数自变量一般是工件的完工时间。对于最小化问题，目标函数是工件完工时间的非降函数，即所谓的正则性，也称为目标函数是正则的。正则性保证了机器在加工工件过程中没有人为设置的空闲时间。

排序理论几十年的发展，应用领域从最初的制造业渗透到社会经济的各个方面，突破了经典排序模型的特征，新的排序模型不断涌现（唐国春等，2003），包括可控排序、工件可拒绝排序、同时加工排序（批加工排序）、成组分批排序、准时排序与窗时排序、资源受限排序、在线排序、随机排序等。与此同时，求解各类排序问题的算法也得到了发展，证明一个排序问题存在多项式时间算法，并给出相应的多项式时间算法是排序理论中最重要的部分。20世纪70年代计算复杂性理论的发现，则对于NP困难问题（NP-hard problem）设计有效算法至关重要，也是排序理论得以在社会经济各领域广泛应用的关键。早期与设计一般组合优化问题的算法一样，排序问题也是用纯组合的方法设计算法，以及应用分支定界算法、动态规划算法等，也可以将排序问题转化成（混合）整数线性规划以及应用列生成技术进行求解。随着排序问题的应用，其问题规模越来越大，快速有效求解性能比好的近似解更具有现实理论意义和实际应用价值。在这一发展趋势的推动下，提出了各种启发式搜索方法，伴随着计算机技术的发展，促进了各种智能算法的研究，与此同时，数学规划松弛方法得到了大发展。