第四章 排序论

第4章排序问题4.1绪论4.1.1引例排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇宙飞船的飞行计划都要用到排序的理论和方法。例4.1.1机械加工一个机械加工车间要加工一批机器零件，每一个零件都有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同。如何安排加工顺序才能以最短的时间完成所有的零件。这是一个流水线排序问题。例4.1.2进程调度在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或者进程的平均周转时间最短？这也是一个排序问题。例4.1.3机场的调度机场的调度人员需要制定一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序问题。4.1.2排序问题的定义排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或资源，最优的完成一批给定的任务或作业。在执行任务的过程中需要满足某些限制条件，如任务的到达时间、加工顺序等。最优指的是使目标函数达到最小，目标函数通常是对加工时间长短、处理机效率的描述。处理机只有一个处理机的排序问题为单机排序问题，否则为多机排序问题。处理机的各种类型和环境描述如下：单处理机同类机（平行机）同速机恒速机变速机多类机（车间作业）同顺序作业异顺序作业自由顺序作业柔性流水作业任务和作业排序中的约束条件主要指的是任务或作业的性质及在加工过程中要求和限制。（1）加工时间向量其中表示任务在处理机上所需要的时间。（2）到达时间到达时间或准备时间是任务已经准备好被加工的时间。（3）工期和截止期限工期是对任务限定的完工时间。（4）优先因子优先因子是一个权，表示任务相对于其他任务的重要程度。),...,,(21mjjjjppppijpjTiPjrjTjdjTjw任务被加工的一个重要约束是可中断或不可中断。若排序中每一个任务在加工时都可暂停加工，加工该任务的处理机可加工其他任务，以后也可在任意时刻任意处理机重新加工，这叫做可中断排序，否则为不可中断排序。目标函数目标函数主要有以下几种：（1）时间表长：最后一个被加工完任务的完工时间，越小处理机利用率越高。（2）平均加工流时间和加权总完工时间平均加工流时间：加权总完工时间：}max{maxjCC11/,nnjjjjjjjjFwFwFCr其中njjjCwC1（3）最大延误（4）加权总误工（totalweightedtardiness）（5）加权误工任务数maxmax{},jLLlateness)jjjjLCdT其中是任务的延误时间(.1,max{,0}max{,0}njjjjjjjTwTTCdL其中是任务的误工时间。njjjUwU11,0,jjjjjjCdUTCd其中=是任务误工的单位惩罚.4.1.3排序问题的分类确定性排序和随机排序。确定性排序：所有数据在进行决策之前都是已知的。随机排序：在决策之前有些数据是随机的，但他们的分布是已知的。这两类排序我们假设：（1）任务或作业和处理机是有限的。（2）在任一时刻任何处理机只能加工一个工件。（3）极小化单一目标函数。处理机、任务、目标函数三要素构成了排序问题。因此，可以用三元组来表示排序问题。||域表示处理机的数量、环境和类型，它可以为：1：单处理机：m个同速机：m个恒速机：m个变速机：m个处理机，流水作业mpmQmRmF域表示任务或作业的性质、加工要求、限制，资源的种类、数量和对加工的影响等约束条件。域表示要优化的目标函数。例4.1.4表示一个单机、可中断的排序问题，任务有不同的到达时间，极小化的目标函数是加权总完工时间。例4.1.5表示一个任务集无关、不可中断、极小化的排序表长的同速机排序问题。1,jjjrprmpwCmaxCPm4.1.4排序问题的求解可行排序与最优排序绝大多数排序问题是从有限个可行解中找出一个最优解，使目标函数达到最小，在排序中可行解称为可行排序，最优解称为最优排序。例4.1.8给定排序问题，其中n=4,,,是一个可行排序，对应的总加工时间为31。最优的排序为，最优加工时间为21。jjCr1)1,5,2,3(p)0,0,1,0(r],,,[2431pppp],,,[3124pppp例4.1.9给定的排序，其中n=5,，作业集的任一个排序都是可行排序，而最优排序是max2CF441062514103p],,,,[23415JJJJJ无耽搁排序定义4.1.1对于一个可行排序，若有准备好被加工的任务，不准许有空闲处理机，称这种排序为无耽搁排序，否则为耽搁排序。对于所有的可中断排序，最优排序是无耽搁排序，然而，也有一些不可中断排序问题的最优排序是耽搁排序。例4.1.11排序问题，其中n=2，，,,该问题有两个可行排序，但是它的最优排序是耽搁排序，目标函数值是46。jjjCwr1)5,10(p)1,0(r)5,1(w排序问题的算法和复杂性求解排序问题的基本思路：应用和借鉴求解其他组合最优化问题的方法，充分利用排序问题本身的特殊性质，以确定满足约束条件的最优排序。对具有多项式算法的排序问题，要尽可能找出空间复杂性和时间复杂性好的算法。求解这类问题的两种方法：一是分枝定界法、动态规划法等巧妙的穷举法求出精确最优排序；二是求出近似算法，各种局部搜索法和启发式算法都是很有效的。4.2单机排序问题4.2.1加权总完工时间问题单机排序问题的一个重要目标函数是加权平均流时间。由于极小化加权平均流时间等价于极小化加权总完工时间，因此下面仅以加权总完工时间为目标函数讨论。首先讨论问题定理4.2.1对于问题（4.2.1），WSPT规则得到的是最优排序,1(4.2.1)jjwCjjpw即把工件按照非减的顺序排列。例4.2.1考虑排序问题，其中n=5,，由WSPT规则，可得最优排序为,加权总完工时间为435。jjCw1)6,11,7,4,12(p)6,5,5,2,4(w],,,,[14235TTTTT4.2.2问题jjCwchains1当任务有优先约束时，问题比较复杂。对于一般优先约束，问题是NP-难的。下面考虑最简单的优先约束，即以平行链的形式出现的优先约束时的情形。这类问题可以描述为此类问题满足优先约束条件排序所具有的性质为基础可以构造出多项式算法。定理4.2.2如果则由任务组成的链再由任务组成的链前加工。1(4.2.2)jjchainswCnkjjnkjjkjjkjjpwpw1111kTTT,...,21nkTT,...,11211121211111121211212=[,,,,,,]()()'=[,,,,,,,](')()kknkjjkjjknkjnjjjkknkjjkkkkkTTTTTwCwpwppwpwpwpTTTTTTwCwpwpp证明：在顺序下加权总完工时间等于而在顺序下11111nnnjjjkjknkjjwpwppwp1111()-(')()('),jjjjknnkjjjjjjkjkjjjjjwCwCpwpwwCwC简单计算可得在假设条件下上式右端小于0，故定理证毕。对于多个链，且不可中断，则可以按照得到最优排序。下面考虑链可中断的情况，即加工某一个链时可以不必全部加工完所有任务，就可以加工其他链的任务，然后回来再加工前面链中剩余的任务（自然要保持原来的优先顺序）。下面的问题是如何排序能使总完工时间最小。在上述假设下，需定义一个链的因子如下：对于链令满足上式左端值称为链的因子，记为称为决定的任务。12...kTTT*lT*l**11111maxlljjjjlllkjjjjwwpp12...kTTT(1,2,,)k定理4.2.3如果是决策链的因子任务，则存在一个最优排序，在该排序中，任务连续加工而不被其它链的任务打断。算法4.2.1（1）在当前未加工链中，选择因子最大的链。（2）连续加工已选定的链，直到加工完决定该链因子的任务。（3）若加工完全部任务，则停止；否则转1。*lTkTTT,...,,21*,...,,21lTTT例4.2.2考虑排序问题，其中n=7，由算法4.2.1得最优的排序为，加权总完工时间为1967。jjCwchains1)10,8,4,5,6,6,3(p)18,17,8,8,12,18,6(w1234567,TTTTTTT1256374[,,,,,,]TTTTTTT4.2.3问题jjCr1任务具有相同的准备时间，总完工时间问题可以用SPT规则求解。对于任务具有不同的准备时间的情况，总完工时间问题是NP-难的。求解总完工时间问题的常用方法是启发式算法。算法4.2.2ECT（最早完工时间优先）算法（1）设处理机当前可加工任务时间为t,对于尚未排序的任务，定义任务的最早开始加工时间和完工时间如下：（2）在尚未排序任务中选取完工时间最小者加工（若有多个，则选取最早开始加工时间最小者）。（3）若已排完全部任务，则停止；否则转1。jjCr1jsjCjjjjjpsCtrs},,max{1||jC算法4.2.3EST（最早开始时间优先）算法（1）设处理机当前可加工任务时间为t,对于尚未排序的任务，定义任务的最早开始加工时间和完工时间如下：（2）在尚未排序任务中选取最早开始加工时间最小者加工（若有多个，则选取完工时间最小者）。（3）若以排完全部任务，则停止；否则转1。jsjCjjjjjpsCtrs},,max{例4.2.3考虑排序问题，其中n=5，，分别求其ECT、EST排序和相应的总完工时间。ECT排序为，总完工时间为379。EST排序为，总完工时间330。jjCr1(3,18,17,21,25)p(35,22,34,37,66)r],,,,[54231TTTTT],,,,[54312TTTTT4.2.4最大延误问题任务没有准备时间的最大延误的排序问题比较简单，只需将任务按最早工期优先（简称EDD）规则，就可以得到最优排序。按照这一规则，任务按不减的顺序进行排序。定理4.2.4对于问题，EDD规则可以得到最优排序。max1Lmax1Ljdmax1L证明：下面证明任何不满足EDD规则的排序，均可转化为满足EDD规则的排序而目标函数不增。假设某最优排序违反了EDD规则，则在此排序中，至少有两个相邻的任务，前者排在后者之前，而。设在时间t时开始加工，则将做如下变动：对调任务的位置，保持其余任务位置不变，从而得到另一个排序,在此排序中，的开始加工时间是t，紧随其后，因此，因为，所以，因此，这说明任何不满足EDD规则的排序均可转化为满足其规则的排序而目标函数不增。定理证毕。kjTT,kjddjTkkkjjjdptLdptL,kjTT,'kTjT'',jjkjkkkLtppdLTPdkjdd'',kkjkLLLL'maxmaxLL例4.2.4考虑排序问题，其中n=6，由EDD规则可以求得最优排序为,最大延误为2。max1L(3,1,4,1,3,2),(2,10,6,4,11,12)pd],,,,,[652341TTTTTT4.2.5问题对于任务具有不同准备时间，任务准许中断的排序问题下面的算法是最优多项式算法。算法4.2.4（1）在当前到达的任务中，选取工期最小者加工，若有多个，任选其一。（2）每当加工完某任务或又有任务到达，则转（1），重新确定当前加工任务，直到加工完全部任务。max,1Lprmprjmax1,jrpr