第四章-排序论

第4章排序问题,4.1绪论4.1.1引例排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇宙飞船的飞行计划都要用到排序的理论和方法。例4.1.1机械加工一个机械加工车间要加工一批机器零件，每一个零件都有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同。如何安排加工顺序才能以最短的时间完成所有的零件。这是一个流水线排序问题。,例4.1.2进程调度在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或者进程的平均周转时间最短？这也是一个排序问题。例4.1.3机场的调度机场的调度人员需要制定一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序问题。,4.1.2排序问题的定义排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或资源，最优的完成一批给定的任务或作业。在执行任务的过程中需要满足某些限制条件，如任务的到达时间、加工顺序等。最优指的是使目标函数达到最小，目标函数通常是对加工时间长短、处理机效率的描述。,处理机只有一个处理机的排序问题为单机排序问题，否则为多机排序问题。处理机的各种类型和环境描述如下：,单处理机,同类机（平行机）,同速机,恒速机,变速机,多类机（车间作业）,同顺序作业,异顺序作业,自由顺序作业,柔性流水作业,任务和作业排序中的约束条件主要指的是任务或作业的性质及在加工过程中要求和限制。（1）加工时间向量其中表示任务在处理机上所需要的时间。（2）到达时间到达时间或准备时间是任务已经准备好被加工的时间。（3）工期和截止期限工期是对任务限定的完工时间。（4）优先因子优先因子是一个权，表示任务相对于其他任务的重要程度。,任务被加工的一个重要约束是可中断或不可中断。若排序中每一个任务在加工时都可暂停加工，加工该任务的处理机可加工其他任务，以后也可在任意时刻任意处理机重新加工，这叫做可中断排序，否则为不可中断排序。目标函数目标函数主要有以下几种：（1）时间表长：最后一个被加工完任务的完工时间，越小处理机利用率越高。（2）平均加工流时间和加权总完工时间平均加工流时间：加权总完工时间：,（3）最大延误（4）加权总误工（totalweightedtardiness）（5）加权误工任务数,4.1.3排序问题的分类,确定性排序和随机排序。确定性排序：所有数据在进行决策之前都是已知的。随机排序：在决策之前有些数据是随机的，但他们的分布是已知的。这两类排序我们假设：（1）任务或作业和处理机是有限的。（2）在任一时刻任何处理机只能加工一个工件。（3）极小化单一目标函数。处理机、任务、目标函数三要素构成了排序问题。因此，可以用三元组来表示排序问题。,域表示处理机的数量、环境和类型，它可以为：1：单处理机：m个同速机：m个恒速机：m个变速机：m个处理机，流水作业,域表示任务或作业的性质、加工要求、限制，资源的种类、数量和对加工的影响等约束条件。域表示要优化的目标函数。例4.1.4表示一个单机、可中断的排序问题，任务有不同的到达时间，极小化的目标函数是加权总完工时间。例4.1.5表示一个任务集无关、不可中断、极小化的排序表长的同速机排序问题。,4.1.4排序问题的求解,可行排序与最优排序绝大多数排序问题是从有限个可行解中找出一个最优解，使目标函数达到最小，在排序中可行解称为可行排序，最优解称为最优排序。例4.1.8给定排序问题，其中n=4,是一个可行排序，对应的总加工时间为31。最优的排序为，最优加工时间为21。,例4.1.9给定的排序，其中n=5,，作业集的任一个排序都是可行排序，而最优排序是,无耽搁排序定义4.1.1对于一个可行排序，若有准备好被加工的任务，不准许有空闲处理机，称这种排序为无耽搁排序，否则为耽搁排序。对于所有的可中断排序，最优排序是无耽搁排序，然而，也有一些不可中断排序问题的最优排序是耽搁排序。例4.1.11排序问题，其中n=2，,该问题有两个可行排序，但是它的最优排序是耽搁排序，目标函数值是46。,排序问题的算法和复杂性求解排序问题的基本思路：应用和借鉴求解其他组合最优化问题的方法，充分利用排序问题本身的特殊性质，以确定满足约束条件的最优排序。对具有多项式算法的排序问题，要尽可能找出空间复杂性和时间复杂性好的算法。求解这类问题的两种方法：一是分枝定界法、动态规划法等巧妙的穷举法求出精确最优排序；二是求出近似算法，各种局部搜索法和启发式算法都是很有效的。,4.2单机排序问题,4.2.1加权总完工时间问题单机排序问题的一个重要目标函数是加权平均流时间。由于极小化加权平均流时间等价于极小化加权总完工时间，因此下面仅以加权总完工时间为目标函数讨论。首先讨论问题定理4.2.1对于问题（4.2.1），WSPT规则得到的是最优排序,例4.2.1考虑排序问题，其中n=5,，由WSPT规则，可得最优排序为,加权总完工时间为435。,4.2.2问题,当任务有优先约束时，问题比较复杂。对于一般优先约束，问题是NP-难的。下面考虑最简单的优先约束，即以平行链的形式出现的优先约束时的情形。这类问题可以描述为此类问题满足优先约束条件排序所具有的性质为基础可以构造出多项式算法。定理4.2.2如果则由任务组成的链再由任务组成的链前加工。,对于多个链，且不可中断，则可以按照得到最优排序。下面考虑链可中断的情况，即加工某一个链时可以不必全部加工完所有任务，就可以加工其他链的任务，然后回来再加工前面链中剩余的任务（自然要保持原来的优先顺序）。下面的问题是如何排序能使总完工时间最小。在上述假设下，需定义一个链的因子如下：对于链令满足上式左端值称为链的因子，记为称为决定的任务。,定理4.2.3如果是决策链的因子任务，则存在一个最优排序，在该排序中，任务连续加工而不被其它链的任务打断。算法4.2.1（1）在当前未加工链中，选择因子最大的链。（2）连续加工已选定的链，直到加工完决定该链因子的任务。（3）若加工完全部任务，则停止；否则转1。,例4.2.2考虑排序问题，其中n=7，由算法4.2.1得最优的排序为，加权总完工时间为1967。,4.2.3问题,任务具有相同的准备时间，总完工时间问题可以用SPT规则求解。对于任务具有不同的准备时间的情况，总完工时间问题是NP-难的。求解总完工时间问题的常用方法是启发式算法。算法4.2.2ECT（最早完工时间优先）算法（1）设处理机当前可加工任务时间为t,对于尚未排序的任务，定义任务的最早开始加工时间和完工时间如下：（2）在尚未排序任务中选取完工时间最小者加工（若有多个，则选取最早开始加工时间最小者）。（3）若已排完全部任务，则停止；否则转1。,算法4.2.3EST（最早开始时间优先）算法（1）设处理机当前可加工任务时间为t,对于尚未排序的任务，定义任务的最早开始加工时间和完工时间如下：（2）在尚未排序任务中选取最早开始加工时间最小者加工（若有多个，则选取完工时间最小者）。（3）若以排完全部任务，则停止；否则转1。,例4.2.3考虑排序问题，其中n=5，分别求其ECT、EST排序和相应的总完工时间。ECT排序为，总完工时间为379。EST排序为，总完工时间330。,4.2.4最大延误问题任务没有准备时间的最大延误的排序问题比较简单，只需将任务按最早工期优先（简称EDD）规则，就可以得到最优排序。按照这一规则，任务按不减的顺序进行排序。定理4.2.4对于问题，EDD规则可以得到最优排序。,证明：下面证明任何不满足EDD规则的排序，均可转化为满足EDD规则的排序而目标函数不增。假设某最优排序违反了EDD规则，则在此排序中，至少有两个相邻的任务，前者排在后者之前，而。设在时间t时开始加工，则将做如下变动：对调任务的位置，保持其余任务位置不变，从而得到另一个排序,在此排序中，的开始加工时间是t，紧随其后，因此，因为，所以，因此，这说明任何不满足EDD规则的排序均可转化为满足其规则的排序而目标函数不增。定理证毕。,例4.2.4考虑排序问题，其中n=6，由EDD规则可以求得最优排序为,最大延误为2。,4.2.5问题对于任务具有不同准备时间，任务准许中断的排序问题下面的算法是最优多项式算法。算法4.2.4（1）在当前到达的任务中，选取工期最小者加工，若有多个，任选其一。（2）每当加工完某任务或又有任务到达，则转（1），重新确定当前加工任务，直到加工完全部任务。,4.2.6问题任务具有不同准备时间、任务加工不允许中断的排序问题相当复杂，且最优排序未必是无耽搁排序，在一个新任务到达之前，让处理机空闲也许是有益的。定理4.2.5问题是强NP-难的。,4.2.7问题如果任务具有单位加工时间(即)，那么问题有如下的多项式最优算法。算法4.2.5（1）在当前到达的任务中，选取工期最小者加工，若有多个，任选其一。（2）每当加工完任务，则转1，重新确定当前加工任务，直到加工完全部任务。一个需要注意的事实，若任务的加工时间相同，即，而p不能整除所有，则算法4.2.5未必产生最优排序。,例4.2.7考虑排序问题，其中n=2,由算法4.2.5产生的排序是，而最优排序是,4.2.5问题对于任务具有优先约束的情况。我们讨论更广泛的问题显然最后一个任务在时间完成，它与各任务的加工顺序无关。以下用,算法4.2.6（1）置，是按照优先约束可以排在后面的任务的集合。（2）记，求将加入中，从中删除将排在最后一位，修正,使之表示当前可排在后面的任务集合。（3）如果，停止，否则转步骤（2），直到所有任务都排完。定理4.2.6对于问题，算法4.2.6给出的排序是最优排序。,例4.2.8考虑排序问题，n=3,任务间没有优先约束，用算法4.2.6求其最优排序。由于任务间没有优先约束，故三个任务均可排在后面，即(1)先确定排在最后一位的任务。从而由任务排在最后一位。（2）确定排在第二位的座位，此时，由，知可取1或者2，即任务均可排在第二位，从而最优排序为,4.2.6误工任务数问题该排序问题有下面的有效算法。算法4.2.7（1）把任务按照EDD规则排序。（2）计算各任务的完工时间，若果当前排序已无延误任务，则转(5)，否则转(3).（3）找到第一个延误任务，例如第k个任务。（4）在前k个任务中选取并删除加工时间最长的任务，得到一个部分排序，转(2).（5）将删除的任务以任何排序排在所得的部分排序之后，得到最优排序。,例4.2.10考虑排序问题,n=5，初始顺序恰好满足EDD规则，依次求出每个任务的完工时间所以，第一个延误任务是，从前三个任务中找出加工时间最长的一个是，从中删除，然后再求剩余任务中的完工时间。于是从任务中找出加工时间最长的一个，即，从中删除继续求剩余任务的完工时间。,因此得到最优排序中部分加工顺序为，因此最优排序为,总务工数为2。,成组加工问题,成组加工问题不仅包括确定各任务之间的加工顺序，而且包括确定同组中每个任务之间的加工顺序，使目标函数最优。模型可描述为：,用三参数表示法，成组加工问题可记为其中是任务的准备时间向量，处理机的调整时间向量为。第组的调整时间记为，GT指同组任务顺序加工，g为某个给定的目标函数。,4.2.7问题,本节讨论目标函数是时间表长的成组排序问题算法4.2.10（1）把各组中的任务按准备时间不减排列。设第i组中任务的排列顺序为（2）对第i组中，计算（3）将各组按不减排列。,4.2.8问题,成组排序问题中另一个常见的目标函数是总完工时间。下面来讨论这一问题算法4.2.11（1）把各组任务按SPT规则排列。设第i组中的排列顺序为（2）对第i组，计算（3）将各组按不减排列。定理4.2.8对于问题，算法2.11给出的排序是最优排序。,例4.2.14考虑问题，其中n=8，先确定组内加工顺序再确定各组间排序所以组间排序为，总加工时间为177。,4.3平行机排序问题,平行机排序是多处理机排序问题的一种情况，在理论上，平行机排序是单机排序问题的推广；在应用上，平行机排序问题则有更广泛的实际背景。在平行机排序问题中，通常假设有n个任务m台处理机。处理机类型分为同速机、恒速机、变速机。,4.3.1不可中断时间表长问题,问题同速机不可中断时间表长排序问题是NP-难问题，即使是对两台处理机也是如此。算法4.3.1LPT算法（1）把任务按加工时间不增排列，即（2）当t=0时，取前m个任务依次排在m个处理机上，此后每当有处理机加工完某任务，取表中最前面的任务排在该处理机上，直到全部排完。对于LPT算法，我们有如下结论：,定理4.3.1,例4.3.1考虑排序问题LPT排序和最优排序对应的时间表长分别为11和9。,例4.3.2考虑排序问题,4.3.2可中断时间表长问题,问题对于排序问题下面的引理给出其时间表长的一个下界。引理4.3.1算法4.3.2（1）计算（2）把n个任务任意排在一个处理机加工，其时间表长等于n个任务加工时间之和，且不超过mC。,（3）把上述单机排序时间表分成m部分，第一部分为0,C,第二部分为C,2C,第三部分为2C,3C等。（4）把第一部分的排序作为处理机的排序，第二部分作为处理机的排序，.显然上诉排序是可行的，且时间表长达到下界，即，因此是最优排序。,4.3.3总完工时间问题,对于总完工时间问题利用SPT规则可以得到最优排序。算法4.3.3（1）将全部任务按加工时间不减列表。（2）在表中取前面m个任务任意分配给m个处理机。（3）重复2,直到全部任务排完。,定理4.3.2.SPT算法对问题产生最优排序。例4.3.4考虑排序问题，其中m=3,n=8,p=(1,1,2,3,5,6,6,8)利用SPT规则得到的是最优排序，总完工时间为46.,对于处理机是恒速机的情况，问题也存在多项式算法。算法4.3.4（1）在中选取n个较小的数按不减顺序排列；（2）任务按加工时间不增排列；（3）经过（1）,（2）两步后，（1）中的数与任务形成1-1对应，若任务对应数则任务排在处理机的倒数第k个位置。,4.4同顺序作业问题,4.4.1问题描述同顺序作业排序问题也叫流水作业问题，可以表述为其中g是完工时间的不减函数，是一类常见的车间作业排序问题，也是一类重要的车间作业排序问题。在同顺序作业中，各作业依次在处理机上完成各道工序。但是对于同一台机