数学建模---第九章-排序问题ppt课件.ppt

《数学建模---第九章-排序问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模---第九章-排序问题ppt课件.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第九章第九章 排序问题排序问题组合优化理论组合优化理论 Combinatorial Optimization Theory在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题4 旅行商问题旅行商问题 1 单机排序问题单机排序问题 2 平行机排序问题平行机排序问题 3 车间作业排序问题车间作业排序问题 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 一个机械加工车间要加工一批机器零件，每一个一个机械加工车间要加工一批机器零件，每一个零件都具有相同的

2、工序，即按相同的顺序在几个不同零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间的机床上加工，但每个零件在每个机床上的加工时间可能不同可能不同.如何按排加工顺序才能以最短的时间加如何按排加工顺序才能以最短的时间加工工完所有的零件完所有的零件.机械加工机械加工Example 1第九章第九章 排序问题排序问题这是一个流水线排序问题这是一个流水线排序问题.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 在计算机多道程序操作系统中，并发执行多个进在计算机多道程序操作系统

3、中，并发执行多个进程，任何时刻程，任何时刻CPU只能执行一个进程，进程的到达时只能执行一个进程，进程的到达时间是不同的，怎样调度这些进程才能使间是不同的，怎样调度这些进程才能使CPU的利用率的利用率最高或进程的平均周转时间最短？最高或进程的平均周转时间最短？进程调度进程调度 事先不知道每个进程的到达时间和执行时间事先不知道每个进程的到达时间和执行时间在线排序在线排序 事先知道随机到达时间和执行时间的分布、数学事先知道随机到达时间和执行时间的分布、数学期望、方差，目标是极小化平均周转时间的数学期期望、方差，目标是极小化平均周转时间的数学期望望随机排序随机排序Example 2在整堂课的教学中，刘

4、教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题机场调度机场调度 在一个飞机场，有几十个登机门，每天有几百架在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞，登机门的种类和大小是不同的，而飞机降落和起飞，登机门的种类和大小是不同的，而班机的机型和大小也是不同的班机的机型和大小也是不同的.飞机按时刻表降落和起飞，当飞机占有登机门时飞机按时刻表降落和起飞，当飞机占有登机门时,旅客上下飞机，飞机要接受加油、维护和装卸行李等旅客上下飞机，飞机要接受加油、维护和装卸行李等服务服务.由于天气和机场的原因，飞机不能起飞，登机由于天

5、气和机场的原因，飞机不能起飞，登机时间推迟时间推迟.调度人员如何制订一个登机门的分配方案，使机调度人员如何制订一个登机门的分配方案，使机场的利用率最高或晚点起飞的飞机最少场的利用率最高或晚点起飞的飞机最少.登机门登机门机器，机器，飞机飞机零件，零件，机场的规定机场的规定约束条件约束条件Example 3在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 由于效率的度量方法的不同、引进不同的约束条由于效率的度量方法的不同、引进不同的约束条件和机器的数量、类型等，使之得到不少的排序模件和机器的数量、类型等，使之

6、得到不少的排序模型，也使排序问题有了更多的应用型，也使排序问题有了更多的应用.用一台或一台以上的机器加工两个或两个以上的用一台或一台以上的机器加工两个或两个以上的零件（任务）时，确定加工顺序使效率最高零件（任务）时，确定加工顺序使效率最高。排序（排序（Scheduling）问题）问题 由于应用范围逐渐扩大，新的问题不断出现，因由于应用范围逐渐扩大，新的问题不断出现，因而从事这一领域研究的人与日俱增，其内容也越来越而从事这一领域研究的人与日俱增，其内容也越来越丰富，应用也越来越广泛丰富，应用也越来越广泛.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提

7、出的问题也很明确第九章第九章 排序问题排序问题确定性排序确定性排序随机性排序随机性排序在线排序在线排序 （On-line Scheduling）半在线排序半在线排序 (Semi-On-line Scheduling)离线排序离线排序 （Off-line Scheduling）(Deterministic Scheduling)所有数据在进行决策前都是已知的所有数据在进行决策前都是已知的（Stochastic Scheduling）有的数据在进行决策前是未知的，是随机变量有的数据在进行决策前是未知的，是随机变量,但它们的分布是已知的但它们的分布是已知的在整堂课的教学中，刘教师总是让学生带着问题来

8、学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确常见的目标函数（效率的度量方法）常见的目标函数（效率的度量方法）用用 C=(C1，C2，Cn)表示任务的完工时间，表示任务的完工时间，极小化极小化的目标函数总是完工时间的目标函数总是完工时间 Cj 的函数的函数.（1）时间表长时间表长 时间表长（时间表长（schedule length，makespan）定义为）定义为 它等于最后一个被加工完任务的完工时间，小的它等于最后一个被加工完任务的完工时间，小的时间表长意味着处理机有高的利用率时间表长意味着处理机有高的利用率.第九章第九章 排序问题排序问题在整堂课的教学中，刘教师总是让学生

9、带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题（2）平均加权流时间和加权总完工时间平均加权流时间和加权总完工时间平均加权流时间（平均加权流时间（mean weighted flow time）是）是任务的到任务的到达时间达时间其中其中 是任务是任务Tj 的流（周转）时间，的流（周转）时间，它等于任务在系统中等待时间和加工时间的它等于任务在系统中等待时间和加工时间的和和.对平均加权流时间进行变形，可得极小化对平均加权流时间进行变形，可得极小化 F 相当于相当于极小化加权总完工时间极小化加权总完工时间（total weighted comp

10、letion time）(如果如果 wj=1 j=1,2,n 即即 为为总完工时间总完工时间)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题式中的第一项的分母和第二项都是常数，式中的第一项的分母和第二项都是常数，所以所以在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题（3）最大延误最大延误最大延误（最大延误（maximum lateness）定义为）定义为任务的截任务的截止期限止期限（4）加权总误工加权总误工加权总

11、误工（加权总误工（total weighted tardiness）是）是其中其中 Lj=Cj dj 是任务是任务 Tj 的延误时间的延误时间.其中其中 Dj=max Cj dj，0 是任务是任务 Tj 的误工时间的误工时间.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题（5）加权误工任务数加权误工任务数加权误工任务数加权误工任务数（weighted number of tardy tasks）是是在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明

12、确第九章第九章 排序问题排序问题排序问题的三要素：排序问题的三要素：机器（处理机）、作业（任务）、目标函数机器（处理机）、作业（任务）、目标函数用三元组用三元组描述一个排序模型描述一个排序模型 ：机器的数量和类型；：机器的数量和类型；：作业的约束条件；：作业的约束条件；：优化的目标函数：优化的目标函数.基本假设基本假设：（1）任务或作业和处理机都是有限的；）任务或作业和处理机都是有限的；（2）在任一时刻，任何处理机只能加工一个任务或一）在任一时刻，任何处理机只能加工一个任务或一 道工序道工序;（3）极小化单一目标函数）极小化单一目标函数.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题

13、的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Definition 1 对于一个可行排序，如果有准备好被加对于一个可行排序，如果有准备好被加工的任务或工序，不准有空闲的处理机，称这种可行排工的任务或工序，不准有空闲的处理机，称这种可行排序为无耽搁排序（序为无耽搁排序（nondelay schedule）；否则称为耽搁排）；否则称为耽搁排序（序（delay schedule）。）。无耽搁排序相当于有工作可做就不能闲着无耽搁排序相当于有工作可做就不能闲着.对于对于大多数排序问题，包括所有的可中断排序，最优排序大多数排序问题，包括所有的可中断排序，最优排序是无耽搁

14、排序，然而也有一些不可中断排序问题的最是无耽搁排序，然而也有一些不可中断排序问题的最优排序是耽搁排序优排序是耽搁排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题排序问题排序问题 1：表示一台机器表示一台机器rj:表示任务有不表示任务有不 同的到达时间同的到达时间n=2，t=(10，5)，r=(0，1)，w=(1，5)该问题有两个可行排序，用该问题有两个可行排序，用 Gantt Charts 表示：表示：0 10 15AB0 1 6 16BAnondelay schedule:delay schedu

15、le:Z1=10*1+15*5=85Z2=6*5+16*1=46Example 4在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题阿克米自行车的装配问题阿克米自行车的装配问题工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15这是一个这是一个 排序问排序问题题.由两名熟练工人进行装配，要求装完时间最早由两名熟练工人进行装配，要求装完时间最早.0 2 5 7 8 9 1516 23 31P1P2ABCE

16、FGHIJDExample 5在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 如果每道工序的加工时间减少如果每道工序的加工时间减少1，最优时间表会，最优时间表会小于小于 31 吗？是吗？是 26 吗？吗？0 1 3 4 5 7 13 20 27ABJDCEFGHIP1P2最优耽搁排序最优耽搁排序工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A7FD1BA6GF1CA，E6HE，G7D1IE，G7ED2JB，C14在整堂课的教学中，刘教师总是让学生带着问题来学习，而问

17、题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题ABCD E F GHIJ 0 1 3 4 5 7 1213 18 20 32P1P2最优无耽搁排序最优无耽搁排序工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A7FD1BA6GF1CA，E6HE，G7D1IE，G7ED2JB，C14在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 如果加工时间不变而增加一个装配工人，最优时如果加工时间不变而增加一个装配工人，最优时间表会小于间表会小于

18、31 吗？吗？最优耽搁排序最优耽搁排序0 2 4 5 6 8 14 15 22 30P1P2P3ADF GECHBIJ工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题最优无耽搁排序最优无耽搁排序 0 2 4 5 6 8 1415 21 36 P1P2P3ADEFGHIBCJGo back工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前

19、工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 单机排序问题单机排序问题第九章第九章 排序问题排序问题 单机排序问题是最简单的一类排序问题，同时也单机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之一是最重要的排序问题之一.首先单机排序问题比较容首先单机排序问题比较容易求出解决方法，这些方法对于研究较复杂的排序问易求出解决方法，这些方法对于研究较复杂的排序问题具有指导作用，可为处理复杂排序问题提供近似算题具有指导作用，可为处理复

20、杂排序问题提供近似算法；其次，单机排序问题大量存在于现实生活中，具法；其次，单机排序问题大量存在于现实生活中，具有广泛的实际背景，许多实际问题都可以归结为单机有广泛的实际背景，许多实际问题都可以归结为单机排序问题排序问题.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 设一个机修车间有设一个机修车间有 n台不同的机床要进行台不同的机床要进行大修大修,它们的维修时间已知为它们的维修时间已知为 t1,t2,tn,而机床而机床 Ai 在在车间逗留的过程中每单位时间的损失费为车间逗留的过程中每单位时间的损失费

21、为 wi(i=1,n)如何排序？试求一种排序，使得试求一种排序，使得 n台机床在修理完毕时，总的损失台机床在修理完毕时，总的损失为最小为最小.A1A2A3A4如何排序？猜Example 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题设设 n台机床维修的排序为台机床维修的排序为(k1,k2,kn)则机床则机床 的维修完毕的时间为的维修完毕的时间为n 台机床按此排序维修完时，总的损失费为台机床按此排序维修完时，总的损失费为 本题要寻找一种排序本题要寻找一种排序（r1,r2,rn）满足）满足Solution

22、:在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题设有两排序设有两排序（1）（2）分析排序（分析排序（1）与（）与（2）的优劣）的优劣总损失费仅在总损失费仅在km,km+1处有区别处有区别按（按（1）排序）排序按（按（2）排序）排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题排序（排序（2）优于排序（）优于排序（1）.Theorem 1满足下列条件的排序满足下列条件的排序（r1,r2,rn）为问题为问题 的最优

23、排序的最优排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题如如:考虑排序问题考虑排序问题 其中其中 n=5,t=(12，4，7，11，6)，w=(4，2，5，5，6)由由此时此时得最优排序为得最优排序为在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 在在 Ex.6 中，如果考虑各待维修的机床在机修车中，如果考虑各待维修的机床在机修车间平均逗留时间（或总逗留时间）最短，间平均逗留时间（或总逗留时间）最短，如何

24、排序？如何排序？这只是这只是 Ex.6 中中 wj=1/n 和和 wj=1 的特例的特例为最优排序为最优排序.或或所以，满足下列条件的排序（所以，满足下列条件的排序（r1,r2,rn）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 以下讨论的排序问题都与工期有关，即每个任务以下讨论的排序问题都与工期有关，即每个任务均有一个工期。工期均有一个工期。工期 dj表示对任务表示对任务 Tj限定的完工时间限定的完工时间.如果不按期完工，应受到一定的惩罚如果不按期完工，应受到一定的惩罚.任务没有准备时间的最大延误

25、的排序问题比较简任务没有准备时间的最大延误的排序问题比较简单，只需将任务按最早工期优先（单，只需将任务按最早工期优先（Earliest Due Date first，简记，简记 EDD）规则，就可以得到最优排序）规则，就可以得到最优排序.按照按照这一规则，任务按这一规则，任务按 dj 不减的顺序进行排序不减的顺序进行排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Theorem 2prove由由EDD规则可以求得最优排序规则可以求得最优排序Go on 对于问题对于问题 EDD 规则可以得到规则可以得

26、到最优排序最优排序.Example 7 考虑排序问题考虑排序问题 ，其中，其中 n=6 ,t=(3,1,4,1,3,2)，d=(2,10,6,4,11,12)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 Theorem 2 的证明的证明Go back 只需证明任何不只需证明任何不满足满足EDD规则的排规则的排序，均可转化为满序，均可转化为满足足EDD规则而目标规则而目标函数不增。函数不增。设某一排序设某一排序 s 违反了违反了 EDD 规则，则规则，则在此排序中，至少有两个相邻任务在此排序中，至少有

27、两个相邻任务p dk djp dk djTjTjTkTk在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 在许多情况下，延误时间的长短并不重要。只要有在许多情况下，延误时间的长短并不重要。只要有延误发生，造成的影响是一样的延误发生，造成的影响是一样的.例如用航天飞机发射例如用航天飞机发射太空站，每个太空站都要完成特定的太空观测任务太空站，每个太空站都要完成特定的太空观测任务,误误期发射的太空站将失去作用期发射的太空站将失去作用.此时，目标应使误期发射此时，目标应使误期发射的太空站数目最少的太空站数目最少.

28、误工任误工任务数问题务数问题Example 8 设有设有 n 个工件个工件 T1,T2,Tn 要在一台要在一台机机器上加工，加工时间分别为器上加工，加工时间分别为 t1,t2,tn，要求的交货，要求的交货日期分别为日期分别为 d1,d2,dn.试求一种加工排序，使得试求一种加工排序，使得误期交货的工件最少误期交货的工件最少.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确算法算法:（1）把任务按）把任务按 EDD 规则排序规则排序；（2）计算各任务的完工时间，如果当前排序已无延）计算各任务的完工时间，如果当前排序已无延 误任务，则转（

29、误任务，则转（5），否则转（），否则转（3）；（3）找到第一个延误任务，不妨设为第）找到第一个延误任务，不妨设为第 k 个任务个任务；（4）在前）在前 k 个任务中选取并删除加工时间最长的任个任务中选取并删除加工时间最长的任 务，得到一个部分排序，转（务，得到一个部分排序，转（2）；（5）将删除的任务以任何顺序排在所得的部分排序）将删除的任务以任何顺序排在所得的部分排序 之后，得到最优排序之后，得到最优排序.proveGo on1 1 单机排序问题单机排序问题Theorem 3对于问题对于问题 ,上述算法给出最优排序上述算法给出最优排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的

30、设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Theorem 3 的证明的证明 假定假定 ，令，令 Fk 表示前表示前 k 个任务构成的个任务构成的集合集合 T1,T2,Tn 的子集，满足下述两个条件：的子集，满足下述两个条件：集合集合 Fn 与最优排序相对应与最优排序相对应.下面用数学归纳法下面用数学归纳法证明算法产生的排序就是证明算法产生的排序就是 Fn.1、在任务集、在任务集 T1,T2,Tk 的所有子集中，的所有子集中，Fk 具有最具有最 多按期完工的任务，按期完工的任务数记为多按期完工的任务，按期完工的任务数记为 Nk;2、在、在 T1,T2,Tk

31、的所有含有的所有含有 Nk 个按期完工任务个按期完工任务 的子集中，的子集中，Fk 中的任务所用的总加工时间最少中的任务所用的总加工时间最少.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题分两种情况讨论分两种情况讨论：当当 k=1 时，显然满足；时，显然满足；假设对前假设对前 k 个任务算法产生的排序是个任务算法产生的排序是 Fk，Fk 满足上述两个条件；满足上述两个条件；对前对前 k+1 个任务，由个任务，由 Fk 出发，按算法要求可产出发，按算法要求可产生满足上述两个条件的生满足上述两个条件的 F

32、k+1,Case 1 将任务将任务 Tk+1 加入加入 Fk 后，后，Tk+1 按期完工按期完工.此时，此时，Nk+1=Nk+1 ,Fk+1=Fk Tk+1，显然上述，显然上述两个条件满足；两个条件满足；在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Case 2 将将Tk+1 加入加入 Fk 后，任务后，任务Tk+1 没有按期完工没有按期完工.由由 Nk 是任务集是任务集 T1,T2,Tk 的子集中按期完工的子集中按期完工任任务数最大的一个，以及务数最大的一个，以及 Fk 是含有是含有 Nk 个任务的子

33、集中个任务的子集中加工总时间最少的一个，可知加工总时间最少的一个，可知 Nk+1=Nk.将将 Tk+1 加入加入 Fk 中没有增加按期完工的任务数，但应从任务集中没有增加按期完工的任务数，但应从任务集 Fk Tk+1 中删除加工时间最大的一个任务，因此中删除加工时间最大的一个任务，因此 Fk+1 满足上述两个条件满足上述两个条件.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 i12345678TriT5T4T8T3T2T6T7T1tri416368710Cri45111420283545dri689

34、1120252835 按按EDD规则，重新排序得右表规则，重新排序得右表.此时，任务此时，任务T8 延误，而在前三延误，而在前三项任务中，项任务中，T8 的加工时间最长的加工时间最长,所以将所以将T8 放至最放至最后，得一新表后，得一新表.Example 9 考虑排序问题考虑排序问题 ，其中，其中 n=8t=(10,6,3,1,4,8,7,6),d=(35,20,11,8,6,25,28,9)Solution:在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 i12345678TriT5T4T3T2T6T

35、7T1T8tri413687106Cri4581422293945dri6811202528359 此时，任务此时，任务 T7 延误，而在前六项任务中，延误，而在前六项任务中，T6 的的加工时间最长，所以将加工时间最长，所以将 T6 放至最后，得一新表放至最后，得一新表.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 i12345678TriT5T4T3T2T7T1T8T6tri413671068Cri4581421313745dri6811202835925 目前，前六项任务中已没有延误任务，所以此

36、时目前，前六项任务中已没有延误任务，所以此时为最优排序为最优排序.有两个任务有两个任务T8、T6 延误延误.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 设设 Dj 表示任务表示任务 Tj 的误工时间，使整个误工的误工时间，使整个误工最小的排序是十分重要的最小的排序是十分重要的.因为单纯讨论使误工任务因为单纯讨论使误工任务数最少可能会使有些任务的等待时间变得很长数最少可能会使有些任务的等待时间变得很长.如果将目标函数换成如果将目标函数换成 ，研究它的极小化，则，研究它的极小化，则不会产生上述现象，这也

37、很有应用背景不会产生上述现象，这也很有应用背景.自然会想到能否按自然会想到能否按 EDD 规则排序，即按规则排序，即按 dj 不减不减的顺序进行排序的顺序进行排序.能得到最优排序吗？能得到最优排序吗？在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 设排序设排序（r1,r2,rn）(1)满足满足与排序与排序（r1,ri+1,ri,rn）(2)进行比较：进行比较：若若 Tri,Tri+1 在（在（1）中不误期，则在（）中不误期，则在（2）中）中Tri+1 不误期不误期,而在而在 Tri 前插入前插入 tr

38、i+1单位时间单位时间,就有误期的可能；就有误期的可能；若若 Tri 在（在（1）中不误期，而）中不误期，而 Tri+1 在（在（1）中误期）中误期 l 单位时间，则由于单位时间，则由于 ，任务，任务 Tri 在（在（2）的误期）的误期在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Go back 若若 Tri 在在(1)中有误期中有误期 l 单位时间，而单位时间，而Tri+1 在在(1)中中没没有误期，则在有误期，则在(2)中中 Tri+1 仍没有误期，而在仍没有误期，而在 Tri 前插入前插入 tri

39、+1 单位时间，任务单位时间，任务 Tri 在在(2)中的误期中的误期 若若 Tri、Tri+1 在在(1)中都有误期中都有误期 l、s 单位时间，则单位时间，则在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 平行机排序问题（平行机排序问题（Parallel Machine Scheduling）是多处理机排序问题的一种情况是多处理机排序问题的一种情况.所谓平行机是指参所谓平行机是指参与完成任务的的处理机具有完全相同的作用，即任务与完成任务的的处理机具有完全相同的作用，即任务在任一处理机上处理都可以在任一处理机上处理都可以.PMS

40、是排序中研究较是排序中研究较早，很有代表性的一个问题，在理论上它是单机排序早，很有代表性的一个问题，在理论上它是单机排序问题的推广，在应用上则具有更广泛的实际背景问题的推广，在应用上则具有更广泛的实际背景.任务集任务集无关（任务间是独立的）无关（任务间是独立的）相关（任务有紧前要求）相关（任务有紧前要求）处理机处理机同速机同速机恒速机恒速机变速机变速机2 平行机排序问题平行机排序问题在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题可中断如何可中断如何？同速机不可中断地处理无关任务集的时间表长问题同速机不可

41、中断地处理无关任务集的时间表长问题.设有设有 m 台完全相同的处理机台完全相同的处理机 Pj(j=1 m),n个相互个相互独独立的任务立的任务 Ji(i=1 n),Ji 的加工时间为的加工时间为 ti(i=1 n)任务任务 Ji 在处理机在处理机 Pj 上加工上加工否则否则则问题则问题可用可用 IP 描述如下描述如下：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题 该问题与装箱问题是密切相关的，有相同的判定问该问题与装箱问题是密切相关的，有相同的判定问题，常互称为对偶问题题，常互称为对偶问题.把箱

42、子与处理机对应，物品把箱子与处理机对应，物品与任务对应，则装箱问题是箱长给定，目标是箱子数与任务对应，则装箱问题是箱长给定，目标是箱子数最少最少.该问题是箱子数给定，而使箱子长度最短该问题是箱子数给定，而使箱子长度最短.(1)考察它的连续松弛问题考察它的连续松弛问题则松弛问题的最优值则松弛问题的最优值(2)对原问题的任一实例对原问题的任一实例 I，一定有，一定有Theorem 4在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题二、近似算法二、近似算法1、LS 算法算法 （List Scheduling）L

43、S算法是由算法是由Graham于于1966年首先提出，他在研年首先提出，他在研究究LS算法的近似程度时，第一次提出了近似算法的最算法的近似程度时，第一次提出了近似算法的最坏情况进行分析的办法坏情况进行分析的办法.从此讨论近似算法的绝对或渐从此讨论近似算法的绝对或渐进性能比，就广泛地应用于组合优化的研究中进性能比，就广泛地应用于组合优化的研究中.Theorem 5问题问题 最优值的一个下界为最优值的一个下界为在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题 LS算法的思想是按任务给定的顺序，将每一个工

44、算法的思想是按任务给定的顺序，将每一个工件分给最早空闲的机器（也即使该工件最早完工的机件分给最早空闲的机器（也即使该工件最早完工的机器）加工，在安排当前任务的加工时，不要求知道下一器）加工，在安排当前任务的加工时，不要求知道下一个工件的信息，所以特别适用于在线排序问题个工件的信息，所以特别适用于在线排序问题.LS 算法算法step 1 设设 Lj=0 j=1 m k=1step 2若若 令令若若 k=n+1 时，停止；否则时，停止；否则 重复重复 step 2.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序

45、问题prove0 1 2 4 7 8 9 14P1 P2 P3Solution:Example 10考虑排序问题考虑排序问题 ，其中，其中 m=3，n=7，t=(1,4,2,8,6,3,7).你有想法吗？你有想法吗？Theorem 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题2、LPT 算法算法 （Largest Processing Time）LPT 算法思想是先将任务按其加工时间从大到小的算法思想是先将任务按其加工时间从大到小的顺序排列，然后用顺序排列，然后用LS算法排序。这也是算法排序。

46、这也是Graham 给出的给出的,它要求任务的信息全部已知后才开始加工。它要求任务的信息全部已知后才开始加工。见前例见前例 t=(1,4,2,8,6,3,7)按加工时间重新排列按加工时间重新排列 J=(J4,J7,J5,J2,J6,J3,J1)t=(8,7,6,4,3,2,1)Theorem 7在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 0 6 7 8 10 11 P2 P3P1一定是最优值吗？理由：1、2、反例Go backJ=(J4,J7,J5,J2,J6,J3,J1)t=(8,7,6,4,3,

47、2,1)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题Theorem 6 的证明的证明Proof:分两步分两步(1)证明对任意的实例证明对任意的实例 I,(2)说明该界不可改进说明该界不可改进.（1）用反证法证明用反证法证明 假设该结论不成立，则存在一反例假设该结论不成立，则存在一反例 I 使使考虑反例中任务数最少的一个（称为最小反例）考虑反例中任务数最少的一个（称为最小反例）.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章

48、 排序问题排序问题 由于由于 I 为最小反例，所以为最小反例，所以 fLS(I)等于最后一个任等于最后一个任务务 Jn 的完工时间的完工时间.因为若不然，设因为若不然，设 Jk 的完工时间等于的完工时间等于 fLS(I)，考虑新的任务集考虑新的任务集 J1,J2,Jk,则对由此任务得则对由此任务得到的新实例到的新实例 I*有有因此因此 有有说明说明 I*是一个更小的反例是一个更小的反例.由由 s 为开始加工为开始加工 Jn 时刻，则时刻，则 fLS(I)=s+tn.由由 LS 规则规则Jn 是分给最早空闲的机器加工，是分给最早空闲的机器加工，在整堂课的教学中，刘教师总是让学生带着问题来学习，而

49、问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题由由 Th 5 知知 因此因此这与这与 I 是反例矛盾，此矛盾说明是反例矛盾，此矛盾说明（2）考虑任务集）考虑任务集 J1，J2，J m2 m+1，其加工，其加工时时间分别为：间分别为：t1=t2=t m2-m=1,t m2-m+1=m,在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Go back需分给需分给 m 台机器加工，易证台机器加工，易证 fLS(I)=2m 1,fopt(I)=m.故故因此因此 有有 在

50、整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确车间作业排序问题是多处理机中多类型机排序问题车间作业排序问题是多处理机中多类型机排序问题m个处理机具个处理机具有不同的功能有不同的功能处理机集处理机集车间作业排序问题：车间作业排序问题：1、同顺序、同顺序(流水流水)作业排序问题作业排序问题3 3、自由、自由(开放开放)作业排序问题作业排序问题2、异顺序作业排序问题、异顺序作业排序问题3 车间作业排序问题车间作业排序问题设有作业集设有作业集每个作业每个作业 Jj 有有 m 道工序：道工序：T1j，T2j，Tmj，工序工序 Tij 的加工时间