[科普中国]-排序问题

排序的基本概念

排序问题已被广泛应用于生产管理、计算机系统、运输调度等领域。排序问题是一类重要的组合优化问题。一般来说，凡是有多个不同的任务要完成，就有作业排序与作业计划问题。几批不同的工件要加工，几个程序等待要运行，几个问题要处理等，都有作业排序。这些问题的共同特征是要将不同的工作任务安排一个执行的顺序和时间．使得目标最优化。所以．作业排序实质上是要解决如何按时间的先后，将有限的资源分配给不同的工作任务，使预定的目标最优化的问题。

需要说明的是，在生产运作管理中常用到编制作业计划、排序、调度、派工、控制、赶工等名词。一般来说，作业排序只确定工件在机器上的加工顺序，而编制作业计划不仅确定工件的加工顺序，而且还包括确定每个工件的开始时间和完成时间，这样才能指导工人的生产活动。由于当各台机器上工件的加工顺序确定后，就可以按最早可能开始时间安排所有工件的计划，这样初始可行的作业计划就可以编制好，因而编制作业计划的问题之一就是作业排序问题。派工是按作业计划的要求，将具体的牛产任务安排到具体的机器上并交给相应的操作工人负责；控制是监控实际生产过程．并使其和计划保证一致的过程；调度是在加工制造发生之后，发现实际进度已经偏离计划而采取的调配资源的行动，调度属于控制的范围；而赶工是在实际进度已经落后于计划进度时采取的追赶进度的行动，赶工属于调度的范围。如火车时刻表是事先确定的一种作业计划，各列火车都按该计划来执行；在实际执行过程需要监控所有火车运行情况，根据这些运行信息相应采取措施以确保计划的完成，这种监控采取的预防和实际措施的过程就是控制；其中实际运行情况偏离了计划所采取的措施就是调度；如果火车发生晚点，采取加快运行速度来赶上计划时间就是赶工2。

排序问题的描述最初的排序研究与应用主要是针对加工制造企业，一般使用机器、工件、加工路线、工序和加工时间来描述一个排序作业的任务。即假定有n个工件要按一定的加工路线经过m台机器加工，其中加工路线是由工件加工的工艺过程决定的，是工件加工在技术上的约束，是工件所需要的加工工序的顺序。而排序就是确定这n个工件在m台机器上加工的先后顺序。随着排序在其他各行各业的应用，原有的“机器”、“工件”、“工序”和“加工时间”的意义已经发生了变化，如“机器”的意义已经扩展到“服务者”，“工件”则泛指“服务对象”，“工序”则指“服务活动”，“加工时间”则是“服务时间”。如计算机网络的服务器（机器）同时接到多个电邮请求（工件），处理后发到请求的用户信箱；多艘轮船（工件）同时要停靠码头（机器）；维修工人（机器）维修多个机器设备（工件）等2。

机器只有一台机器的排序问题称为单机排序问题，否则称为多机排序问题。

在多机问题中机器分为两大类：通用平行(parallel)机和专用串联(dedicated)机，如果所有机器的功能相同，称为同类机或平行机，即一个工件需要在多台平行机的一个机器上加工一次；而串联机则是机器具有不同的功能，工件需要在不同的机器上加工。

平行机又可分成3类：具有相同速度的同速(identical)机、具有不同加工速度但此速度不依赖于工件的恒速( uniform)机和随加工的工件不同加速度也不同的变速(unrelated)机。

串联机也可分为3类：第一个工件以特定的相同机器顺序加工的流水作业(flow shop)、工件依次在机器上加工的次序可以任意的开放作业(open shop)和每一工件以各自特定的机器次序进行加工的单件作业(job shop)。

还有一类更复杂的情况，就是柔性流水作业(flexible flow shop)，它是流水作业和平行机的推广。在柔性流水作业中，有多类机器，每个工件有多道工序，每道工序需要在每类机器中的一台机器上加工，且每个工件的加工顺序相同。机器的分类情况见图12。

工件和工序对不允许中断加工的情况来说，一个工件（ ）在一台机器( )上连续加工的过程称为工序****(operation)。按工件到达车间的不同，可以将排序分为静态和动态两种。当进行排序时所有工件都已经到达，可以一次对它们进行排序，这是静态排序问题；若工件是陆续到达的，要随时对它们进行排序，这是动态排序问题。

排序中的约束条件，主要指的是工件的性质以及它们在加工过程中的要求和限制。

1)加工时间

一个工件的加工时间： ；n个工件的加工时间则用矩阵来表示：

式中： ——工件 在机器i 上所需要的加工时间。

2)到达时间(arrival time)或就绪时间(ready time)

到达时间或就绪时间 是工件已经准备好可以马上被加工的时间。若所有工件的就绪时间相同，则取 。

3)工件工期(due date)或截止期限(deadline)

工期dj表示对工件限定的完工时间。若不按期完工，就会受到一定的惩罚。绝对不允许延误的工期称为截止期限。

4)工件权重(weight)

工件权重是相对于其他工件而言工件的重要性程度2。

目标函数用表示工件的完工时间。一般来说，要使完工时间的函数达到极小化。在排序问题中，目标函数主要有以下几种。

1)最大完工时间或时间表长(schedule length，make-span)

时间表长可定义为：，即为最后一个被加工完的工件的完工时间。

2)加权流程时间(weighted flow time)和加权完工时间

一个工件的流程时间是指工件从到达系统开始一直到加工完为止的时间，包括在系统中的等待时间和加工时间：。

系统的平均加权流程时间：。

将上述平均流程时间转换一下：由于第二项是常数，第一项的分母也是常数，因此极小化平均加权流程时间相当于极小化总加权完工时间(total weighted completion time)：

3)最大延误时间(maximum lateness)

工件的延误时间定义为最大延误时间。

4)加权总误工(total weighted tardiness)

一个工件当其完工时间大于其完工期限时称为误工：

加权总误工：

5)加权误工工件数(weighted number of tardy jobs)

用0/1来表示某工件是否误工：

加权误工件数：

总之，在排序中，工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源；排序是安排一个时间表，以在一定约束条件下对工件和机器按时间进行分配和安排次序，使某一或一些目标达到最优2。

排序问题的分类与表示方法排序问题的类别有多种划分方法，如前面按机器、按工件有不同的划分方法，另外根据参数的性质还可以划分为确定型与随机型排序，即加工时间和其他有关参数是已经知道的、确定的量，就称为确定型排序；而加工时间和相关参数是随机型的量则称为随机型排序。由机器、工件、加工参数和目标函数的不同特征及其他方面的差别，构成了多种不同的排序问题。这里采用国际上使用的三参数表示方法来描述排序问题，即。

域表示机器的数量、类型和环境：，其中，各符号分别代表单机、同速机、恒速机、自由作业、流水作业、单件作业和柔性流水作业；，分别表示机器的数目不确定和有m台机器。

域表示工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等，它可以同时包含多项，可能的主项有：（工件有不同的到达时间）、（工件顺序加工的设备调整时间）、prmp（允许中断）等。

域表示要优化的目标函数：（时间表长）、（加权总完工时间）、（最大延误时间）、（加权总误工）、（加权误工件数）等。

如表示单机排序问题，目标函数是总延误时间最小；表示有m台同速机的排序问题，目标函数是极小化时间表长；而表示一个由m台机器组成的流水作业排序问题，每个作业的所有工序的加工时间都相等，目标是加权总完工时间最小；表示两台机器单件作业排序问题，每个工件在每台机器上至多加工一次，其目标函数是时间表长最小2。

排序问题的求解可行排序与最优排序排序问题是一类组合优化问题，由于在实际生产中，排序问题中的机器、工序、资源都是有限的，绝大部分排序问题是从有限个可行解中找出一个最优解，使目标函数达到极小。

三种计划车间作业计划可能存在着很多可行的作业计划安排方法，其中各工序都按最早可能加工或完工时间安排的作业计划称为半能动计划( semi-active schedule)；若半能动计划中任何一台机器的每段空闲时间都不足以加工一道加工工序的，称为能动作业计划(active schedule)；若在能动计划中，没有任何延迟(delay)现象出现，则称为无延迟作业计划(non-delay schedule)，这里的无延迟是指如果有准备好的被加工的T序，不准许有空闲的机器出现，该计划相当于不允许强迫机器空闲。

对于大多数排序问题，包括所有可中断排序问题，最优排序是无延迟排序，但也有一些不可中断的排序问题是延迟排序2。