《《第6章排序问题》-精选课件（公开PPT）》由会员分享，可在线阅读，更多相关《《第6章排序问题》-精选课件（公开PPT）（87页珍藏版）》请在金锄头文库上搜索。
1、第六章 排序问题,6.1 单机排序问题 6.2 平行机排序问题 6.3 车间作业排序问题 6.4 旅行商问题,第六章 排序问题,一个机械加工车间要加工一批机器零件，每一个 零件都具有相同的工序，即按相同的顺序在几个不同 的机床上加工，但每个零件在每个机床上的加工时间 可能不同。如何按排加工顺序才能以最短的时间加工 完所有的零件。这是一个流水线排序问题。,机械加工,Example 1,第六章 排序问题,在计算机多道程序操作系统中，并发执行多个进程， 任何时刻CPU只能执行一个进程，进程的到达时间是不同 的，怎样调度这些进程才能使CPU的利用率最高或进程的 平均周转时间最短？,进程调度,事先不知道
2、每个进程的到达时间和执行时间在线 排序,事先知道随机到达时间和执行时间的分布、数学期 望、方差，目标是极小化平均周转时间的数学期望 随机排序,Example 2,第六章 排序问题,机场调度,在一个飞机场，有几十个登机门，每天有几百架飞机 降落和起飞，登机门的种类和大小是不同的，而班机的机 型和大小也是不同的。,飞机按时刻表降落和起飞，当飞机占有登机门时，旅 客上下飞机，飞机要接受加油、维护和装卸行李等服务。 由于天气和机场的原因，飞机不能起飞，登机时间推迟。,调度人员如何制订一个登机门的分配方案，使机场的 利用率最高或晚点起飞的飞机最少。,登机门机器， 飞机零件， 机场的规定约束条件,Exam
3、ple 3,第六章 排序问题,由于效率的度量方法的不同、引进不同的约束条 件和机器的数量、类型等，使之得到不少的排序模型， 也使排序问题有了更多的应用。,用一台或一台以上的机器加工两个或两个以上的 零件（任务）时，确定加工顺序使效率最高。, 排序（Scheduling）问题,由于应用范围逐渐扩大，新的问题不断出现，因而从事这 一领域研究的人与日俱增，其内容也越来越丰富，应用也越来 越广泛。,第六章 排序问题,确定性排序,随机性排序,在线排序 （On-line Scheduling ）,半在线排序 (Semi- On-line Scheduling ),离线排序 （Off-line Schedu
4、ling ）,(Deterministic Scheduling),所有数据在进行决策前都是已知的,（Stochastic Scheduling）,有的数据在进行决策前是未知的，是随机变量，但它们 的分布是已知的,第六章 排序问题,目标函数（效率的度量方法）,用 表示任务的完 工时间，极小化的目标函数总是完工时间 Cj 的函数,（1） 时间表长,时间表长（schedule length，makespan）定义为,它等于最后一个被加工完任务的完工时间，小的 时间表长意味着处理机有高的利用率,第六章 排序问题,（2） 平均加权流时间和加权总完工时间,平均加权流时间（mean weighted fl
5、ow time）是,任务的到达时间,是任务Tj 的流（周转）时间，,它等于任务在系统中等待时间和加工时间的和。,对平均加权流时间进行变形，可得极小化 F 相当于极 小化加权总完工时间（total weighted completion time ）,( 为总完工 时间),第六章 排序问题,式中的第一项的分母和第二项都是常数，所以,第六章 排序问题,（3） 最大延误,最大延误（maximum lateness）定义为,任务的截止期限,（4） 加权总误工,加权总误工（total weighted tardiness）是,第六章 排序问题,（5） 加权误工任务数,加权误工任务数（weighted n
6、umber of tardy tasks）是,第六章 排序问题,排序问题的三要素：,机器（处理机）、作业（任务）、目标函数,用三元组,描述一个排序模型,：机器的数量和类型；：作业的约束条件； ：优化的目标函数.,基本假设：,（1）任务或作业和处理机都是有限的；,（2）在任一时刻，任何处理机只能加工一个任务或一道工序;,（3）极小化单一目标函数.,第六章 排序问题,Definition 1,对于一个可行排序，如果有准备好被加 工的任务或工序，不准有空闲的处理机，称这种可行排 序为无耽搁排序（nondelay schedule）；否则称为耽搁排 序（delay schedule）。,无耽搁排序相当
7、于有工作可做就不能闲着。对于大 多数排序问题，包括所有的可中断排序，最优排序是无 耽搁排序，然而也有一些不可中断排序问题的最优排序 是耽搁排序。,第六章 排序问题,排序问题,1：表示一台机器 rj: 表示任务有不 同的到达时间,n = 2，t = (10，5)，r = (0，1)，w = (1，5),该问题有两个可行排序，用 Gantt Charts 表示：,0 10 15,A,B,0 1 6 16,B,A,nondelay schedule:,delay schedule:,Z1 = 10*1+15*5 = 85,Z2 = 6*5 + 16*1 = 46,Example 4,第六章 排序问题
8、,阿克米自行车的装配问题,这是一个,由两名熟练工人进行装配，要求装完时间最早。,排序问题。,0 2 5 7 8 9 1516 23 31,P1,P2,A,B,C,E,F,G,H,I,J,D,Example 5,第六章 排序问题,如果每道工序的加工时间减少1，最优时间表会小 于31吗？是26吗？,0 1 3 4 5 7 13 20 27,A,B,J,D,C,E,F,G,H,I,P1,P2,最优耽搁排序,第六章 排序问题,A,B,C,D,E,F,G,H,I,J,0 1 3 4 5 7 1213 18 20 32,P1,P2,最优无耽搁排序,第六章 排序问题,如果加工时间不变而增加一个装配工人，最优
9、时 间表会小于31吗？,最优耽搁排序,0 2 4 5 6 8 12 1415 22 30,P1,P2,P3,A,D,F,G,E,C,H,B,I,J,第六章 排序问题,最优无耽搁排序,0 2 4 5 6 8 1415 21 36,P1,P2,P3,A,D,E,F,G,H,I,B,C,J,返回,6.1 单机排序问题,单机排序问题是最简单的一类排序问题，同时也 是最重要的排序问题之一。首先单机排序问题比较容 易求出解决方法，这些方法对于研究较复杂的排序问 题具有指导作用，可为处理复杂排序问题提供近似算 法；其次，单机排序问题大量存在于现实生活中，具 有广泛的实际背景，许多实际问题都可以归结为单机 排
10、序问题。,6.1 单机排序问题,设一个机修车间有 n台不同的机床要进行 大修，它们的维修时间已知为 而机床,如何排序？,在车间逗留的过程中每单位时间的损失费为,试求一种排序，使得 n台机床在修理完毕时，总的损失 为最小。,A1,A2,A3,A4,如何排序？ 猜,Example 6,6.1 单机排序问题,解：,设 n台机床维修的排序为,则机床 的维修完毕的时间为,n 台机床按此排序维修完时，总的损失费为,本题要寻找一种排序,满足,6.1 单机排序问题,设有两排序,（1）,（2）,分析排序（1）与（2）的优劣,总损失费仅在km,km+1处有区别,按（1）排序,按（2）排序,6.1 单机排序问题,排
11、序（2）优于排序（1）。,Theorem 1,6.1 单机排序问题,如: 考虑排序问题,其中 n = 5, t = (12，4，7，11，6)， w = (4，2，5，5，6),由,6.1 单机排序问题,在 Ex. 6 中，如果考虑各待维修的机床在机修车间 平均逗留时间（或总逗留时间）最短，,如何排序？,这只是 Ex. 6 中 wj =1/n 和 wj = 1 的特例,为最优排序。,6.1 单机排序问题,以下讨论的排序问题都与工期有关，即每个任务 均有一个工期。工期 dj表示对任务 Tj限定的完工时间。 如果不按期完工，应受到一定的惩罚。,任务没有准备时间的最大延误的排序问题比较简 单，只需将
12、任务按最早工期优先（Earliest Due Date first，简记 EDD）规则，就可以得到最优排序。按照 这一规则，任务按 dj 不减的顺序进行排序。,6.1 单机排序问题,Theorem 2,prove,由EDD规则可以求得最优排序,Go on,6.1 单机排序问题,Theorem 2 的证明,返回,只需证明任何不满足EDD规则的排序，均可转化为满足EDD规则而目标函数不增。,设某一排序 s 违反了 EDD 规则，则 在此排序中，至少有两个相邻任务,p dk dj,p dk dj,Tj,Tj,Tk,Tk,6.1 单机排序问题,在许多情况下，延误时间的长短并不重要。只要有 延误发生，造
13、成的影响是一样的。例如用航天飞机发射 太空站，每个太空站都要完成特定的太空观测任务，误 期发射的太空站将失去作用。此时，目标应使误期发射 的太空站数目最少。,误工任务数问题,Example 7,6.1 单机排序问题,算法:,（1）把任务按 EDD 规则排序；,（2）计算各任务的完工时间，如果当前排序已无延 误任务，则转（5），否则转（3）；,（3）找到第一个延误任务，不妨设为第 k 个任务；,（4）在前 k 个任务中选取并删除加工时间最长的任 务，得到一个部分排序，转（2）；,（5）将删除的任务以任何顺序排在所得的部分排序 之后，得到最优排序。,prove,Go on,6.1 单机排序问题,6
14、.1 单机排序问题,分两种情况讨论：,6.1 单机排序问题,6.1 单机排序问题,按EDD规则，重 新排序得右表。,此时，任务T8 延 误，而在前三项任 务中， T8 的加工 时间最长，所以将 T8 放至最后，得一 新表。,6.1 单机排序问题,此时，任务T7 延误，而在前六项任务中， T6 的加 工时间最长，所以将T6 放至最后，得一新表。,6.1 单机排序问题,目前，前六项任务中已没有延误任务，所以此时 为最优排序。,有两个任务T8 、 T6延误。,6.1 单机排序问题,6.1 单机排序问题,6.1 单机排序问题,返回,6.2 平行机排序问题,平行机排序问题（Parallel Machin
15、e Scheduling） 是多处理机排序问题的一种情况。所谓平行机是指参 与完成任务的的处理机具有完全相同的作用，即任务 在任一处理机上处理都可以。PMS 是排序中研究较早，很有代表性的一个问题，在理论上它是单机排序问题的推广，在应用上则具有更广泛的实际背景。,任务集,无关（任务间是独立的）,相关（任务有紧前要求）,处理机,同速机,恒速机,变速机,6.2 平行机排序问题,可中断如何？,6.2 平行机排序问题,该问题与装箱问题是密切相关的，有相同的判定问 题，常互称为对偶问题。把箱子与处理机对应，物品 与任务对应，则装箱问题是箱长给定，目标是箱子数 最少。该问题是箱子数给定，而使箱子长度最短。,6.2 平行机排序问题,二、近似算法,1、LS 算法 （List Scheduling）,LS算法是由Graham于1966年首先提出，他在研究 LS算法的近似程度时，第一次提出了近似算法的最坏情 况进行分析的办法.从此讨论近似算法的绝对或渐进性 能比，就广泛地应用于组合优化的研究中。,6.2 平行
