数学建模---第九章-排序问题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）定义为）定义为m axm ax jjCC 它等于最后一个被加工完任务的完工时间，小的它等于最后一个被加工完任务的完工时间，小的时间表长意味着处理机有高的利用率时间表长意味着处理机有高的利用率.第九章第九章 排序问题排序问题在整堂课的教学中，刘教师总是让学

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

10、间（total weighted completion time）1njjjCw C(如果如果 wj=1 j=1,2,n 即即 为总完工时间为总完工时间)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题式中的第一项的分母和第二项都是常数，所以式中的第一项的分母和第二项都是常数，所以111111 nnjjjjjnnnnjjjjjjjjjjFw Fww Cww rw在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题（3）最

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

12、务数（weighted number of tardy tasks）是是1njjjUw U10jjjjjjCdUTCd其中是对任务误工的单位惩罚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题排序问题的三要素：排序问题的三要素：机器（处理机）、作业（任务）、目标函数机器（处理机）、作业（任务）、目标函数用三元组用三元组描述一个排序模型描述一个排序模型 ：机器的数量和类型；：机器的数量和类型；：作业的约束条件；：作业的约束条件；：优化的目标函数：优化的目标函数.基本假设基本假设：（1）任务或作业和处理机都是

13、有限的；）任务或作业和处理机都是有限的；（2）在任一时刻，任何处理机只能加工一个任务或一）在任一时刻，任何处理机只能加工一个任务或一 道工序道工序;（3）极小化单一目标函数）极小化单一目标函数.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Definition 1 对于一个可行排序，如果有准备好被加对于一个可行排序，如果有准备好被加工的任务或工序，不准有空闲的处理机，称这种可行排工的任务或工序，不准有空闲的处理机，称这种可行排序为无耽搁排序（序为无耽搁排序（nondelay schedule）；否则称为

14、耽搁排）；否则称为耽搁排序（序（delay schedule）。）。无耽搁排序相当于有工作可做就不能闲着无耽搁排序相当于有工作可做就不能闲着.对于对于大多数排序问题，包括所有的可中断排序，最优排序大多数排序问题，包括所有的可中断排序，最优排序是无耽搁排序，然而也有一些不可中断排序问题的最是无耽搁排序，然而也有一些不可中断排序问题的最优排序是耽搁排序优排序是耽搁排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题排序问题排序问题 1jjjrw C1：表示一台机器表示一台机器rj:表示任务有不表示任务有不

15、同的到达时间同的到达时间n=2，t=(10，5)，r=(0，1)，w=(1，5)该问题有两个可行排序，用该问题有两个可行排序，用 Gantt Charts 表示：表示：0 10 15AB0 1 6 16BAnondelay schedule:delay schedule:Z1=10*1+15*5=85Z2=6*5+16*1=46Example 4在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题阿克米自行车的装配问题阿克米自行车的装配问题工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加

16、工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15这是一个这是一个 排序问题排序问题.max2Pprec C由两名熟练工人进行装配，要求装完时间最早由两名熟练工人进行装配，要求装完时间最早.0 2 5 7 8 9 1516 23 31P1P2ABCEFGHIJDExample 5在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 如果每道工序的加工时间减少如果每道工序的加工时间减少1，最优时间表会，最优时间表会小于小于 31 吗？是吗？是 26 吗？吗？0 1 3 4

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

18、6HE，G7D1IE，G7ED2JB，C14在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 如果加工时间不变而增加一个装配工人，最优时如果加工时间不变而增加一个装配工人，最优时间表会小于间表会小于31 吗？吗？最优耽搁排序最优耽搁排序0 2 4 5 6 8 14 15 22 30P1P2P3ADF GECHBIJ工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15在整堂课的教学中，刘教师总是让学生带

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

20、同时也是最重要的排序问题之一是最重要的排序问题之一.首先单机排序问题比较容首先单机排序问题比较容易求出解决方法，这些方法对于研究较复杂的排序问易求出解决方法，这些方法对于研究较复杂的排序问题具有指导作用，可为处理复杂排序问题提供近似算题具有指导作用，可为处理复杂排序问题提供近似算法；其次，单机排序问题大量存在于现实生活中，具法；其次，单机排序问题大量存在于现实生活中，具有广泛的实际背景，许多实际问题都可以归结为单机有广泛的实际背景，许多实际问题都可以归结为单机排序问题排序问题.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单

21、机排序问题单机排序问题 设一个机修车间有设一个机修车间有 n台不同的机床要进行台不同的机床要进行大修大修,它们的维修时间已知为它们的维修时间已知为 t1,t2,tn,而机床而机床 Ai 在在车间逗留的过程中每单位时间的损失费为车间逗留的过程中每单位时间的损失费为 wi(i=1,n)1jjwC一、问题如何排序？max C1问题试求一种排序，使得试求一种排序，使得 n台机床在修理完毕时，总的损失台机床在修理完毕时，总的损失为最小为最小.A1A2A3A4如何排序？猜Example 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九

22、章 排序问题排序问题设设 n台机床维修的排序为台机床维修的排序为(k1,k2,kn)则机床则机床 1212:(,.,)(,.,)1nnnHk kkk kk令为的一种排序的维修完毕的时间为的维修完毕的时间为skAn 台机床按此排序维修完时，总的损失费为台机床按此排序维修完时，总的损失费为 1iinkkiw C1siskkiCt本题要寻找一种排序本题要寻找一种排序（r1,r2,rn）满足）满足1211min(,.,)iiiinnrrkkniiw Cw Ck kkHSolution:在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单

23、机排序问题单机排序问题设有两排序设有两排序11(,)mmnkkkk11(,)mmnkkkk（1）（2）分析排序（分析排序（1）与（）与（2）的优劣）的优劣总损失费仅在总损失费仅在km,km+1处有区别处有区别按（按（1）排序）排序1mmkkAA和的损失费mkA1mkA2mkA111111mmmmmmmmmmkkkkkkkkkkw Cw twCwtwt按（按（2）排序）排序1mmkkAA和的损失费mkA1mkA2mkA111111mmmmmmmmmmkkkkkkkkkkwCwtw Cw tw t1mkA1mkA在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深

24、，所提出的问题也很明确第九章第九章 排序问题排序问题1111mmmmmmmmkkkkkkkkttwtw tww当即时，排序（排序（2）优于排序（）优于排序（1）.Theorem 11212.nnrrrrrrtttwww1jjw C满足下列条件的排序满足下列条件的排序（r1,r2,rn）为问题为问题 的最优排序的最优排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题如如:考虑排序问题考虑排序问题1jjwC 其中其中 n=5,t=(12，4，7，11，6)，w=(4，2，5，5，6)3512412345

25、3,2,1.4,2.2,1tttttwwwww由由6 65 132 17 5 284 40435jjw C 53241 ()AAAAA，此时此时得最优排序为得最优排序为在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 在在 Ex.6 中，如果考虑各待维修的机床在机修车中，如果考虑各待维修的机床在机修车间平均逗留时间（或总逗留时间）最短，间平均逗留时间（或总逗留时间）最短，1)jjCCn（或如何排序？如何排序？这只是这只是 Ex.6 中中 wj=1/n 和和 wj=1 的特例的特例12.nrrrttt为最优

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

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

28、问题 EDD 规则可以得到规则可以得到最优排序最优排序.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 规则，则规则，则在此排序中，

29、至少有两个相邻任务在此排序中，至少有两个相邻任务 jkjkjkTTTTdd、，排在之前，而p dk djp dk djTjTjTkTk jjjjkjkkTpLptdLpttd设在时间时开始加工，则，.jkjjkjkkkT TsLpttdLptd对调的位置，其余任务位置不变，得一排序在这排序中，maxmax ,jkkjkkddLL LLLL因为，所以从而在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 在许多情况下，延误时间的长短并不重要。只要有在许多情况下，延误时间的长短并不重要。只要有延误发生，造成的影

30、响是一样的延误发生，造成的影响是一样的.例如用航天飞机发射例如用航天飞机发射太空站，每个太空站都要完成特定的太空观测任务太空站，每个太空站都要完成特定的太空观测任务,误误期发射的太空站将失去作用期发射的太空站将失去作用.此时，目标应使误期发射此时，目标应使误期发射的太空站数目最少的太空站数目最少.1jU三、问题 误工任误工任务数问题务数问题Example 8 设有设有 n 个工件个工件 T1,T2,Tn 要在一台机要在一台机器上加工，加工时间分别为器上加工，加工时间分别为 t1,t2,tn，要求的交货，要求的交货日期分别为日期分别为 d1,d2,dn.试求一种加工排序，使得试求一种加工排序，使

31、得误期交货的工件最少误期交货的工件最少.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确算法算法:（1）把任务按）把任务按 EDD 规则排序规则排序；（2）计算各任务的完工时间，如果当前排序已无延）计算各任务的完工时间，如果当前排序已无延 误任务，则转（误任务，则转（5），否则转（），否则转（3）；（3）找到第一个延误任务，不妨设为第）找到第一个延误任务，不妨设为第 k 个任务个任务；（4）在前）在前 k 个任务中选取并删除加工时间最长的任个任务中选取并删除加工时间最长的任 务，得到一个部分排序，转（务，得到一个部分排序，转（2）；（

32、5）将删除的任务以任何顺序排在所得的部分排序）将删除的任务以任何顺序排在所得的部分排序 之后，得到最优排序之后，得到最优排序.1jUproveGo on1 1 单机排序问题单机排序问题Theorem 3对于问题对于问题 ,上述算法给出最优排序上述算法给出最优排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题12 .ndddTheorem 3 的证明的证明 假定假定 ，令，令 Fk 表示前表示前 k 个任务构成的个任务构成的集合集合 T1,T2,Tn 的子集，满足下述两个条件：的子集，满足下述两个条件：集

33、合集合 Fn 与最优排序相对应与最优排序相对应.下面用数学归纳法下面用数学归纳法证明算法产生的排序就是证明算法产生的排序就是 Fn.1、在任务集、在任务集 T1,T2,Tk 的所有子集中，的所有子集中，Fk 具有最具有最 多按期完工的任务，按期完工的任务数记为多按期完工的任务，按期完工的任务数记为 Nk;2、在、在 T1,T2,Tk 的所有含有的所有含有 Nk 个按期完工任务个按期完工任务 的子集中，的子集中，Fk 中的任务所用的总加工时间最少中的任务所用的总加工时间最少.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排

34、序问题单机排序问题分两种情况讨论分两种情况讨论：当当 k=1 时，显然满足；时，显然满足；假设对前假设对前 k 个任务算法产生的排序是个任务算法产生的排序是 Fk，Fk 满足上述两个条件；满足上述两个条件；对前对前 k+1 个任务，由个任务，由 Fk 出发，按算法要求可产出发，按算法要求可产生满足上述两个条件的生满足上述两个条件的 Fk+1,Case 1 将任务将任务 Tk+1 加入加入 Fk 后，后，Tk+1 按期完工按期完工.此时，此时，Nk+1=Nk+1 ,Fk+1=Fk Tk+1，显然上述，显然上述两个条件满足；两个条件满足；在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设

35、置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Case 2 将将Tk+1 加入加入 Fk 后，任务后，任务Tk+1 没有按期完工没有按期完工.由由 Nk 是任务集是任务集 T1,T2,Tk 的子集中按期完工任的子集中按期完工任务数最大的一个，以及务数最大的一个，以及 Fk 是含有是含有 Nk 个任务的子集中个任务的子集中加工总时间最少的一个，可知加工总时间最少的一个，可知 Nk+1=Nk.将将 Tk+1 加入加入 Fk 中没有增加按期完工的任务数，但应从任务集中没有增加按期完工的任务数，但应从任务集 Fk Tk+1 中删除加工时间最大的一个任务，因此中删除加工时

36、间最大的一个任务，因此 Fk+1 满足上述两个条件满足上述两个条件.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题1jU i12345678TriT5T4T8T3T2T6T7T1tri416368710Cri45111420283545dri6891120252835 按按EDD规则，重新排序得右表规则，重新排序得右表.此时，任务此时，任务T8 延误，而在前三延误，而在前三项任务中，项任务中，T8 的加工时间最长的加工时间最长,所以将所以将T8 放至最放至最后，得一新表后，得一新表.Example 9

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

38、后，得一新表.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题 i12345678TriT5T4T3T2T7T1T8T6tri413671068Cri4581421313745dri6811202835925 目前，前六项任务中已没有延误任务，所以此时目前，前六项任务中已没有延误任务，所以此时为最优排序为最优排序.有两个任务有两个任务T8、T6 延误延误.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题 jD 设设

39、 Dj 表示任务表示任务 Tj 的误工时间，使整个误工的误工时间，使整个误工最小的排序是十分重要的最小的排序是十分重要的.因为单纯讨论使误工任务因为单纯讨论使误工任务数最少可能会使有些任务的等待时间变得很长数最少可能会使有些任务的等待时间变得很长.如果将目标函数换成如果将目标函数换成 ，研究它的极小化，则，研究它的极小化，则不会产生上述现象，这也很有应用背景不会产生上述现象，这也很有应用背景.jD 自然会想到能否按自然会想到能否按 EDD 规则排序，即按规则排序，即按 dj 不减不减的顺序进行排序的顺序进行排序.能得到最优排序吗？能得到最优排序吗？在整堂课的教学中，刘教师总是让学生带着问题来学

40、习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1 单机排序问题单机排序问题12 .nrrrddd1iirrddirTirTirTirT1irT1irT1irT1irT 设排序设排序（r1,r2,rn）(1)满足满足与排序与排序（r1,ri+1,ri,rn）(2)进行比较：进行比较：若若 Tri,Tri+1 在（在（1）中不误期，则在（）中不误期，则在（2）中）中Tri+1 不误期不误期,而在而在 Tri 前插入前插入 tri+1单位时间单位时间,就有误期的可能；就有误期的可能；若若 Tri 在（在（1）中不误期，而）中不误期，而 Tri+1 在（在（1）中误期）中误期 l

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

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

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

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

45、互称为对偶问题题，常互称为对偶问题.把箱子与处理机对应，物品把箱子与处理机对应，物品与任务对应，则装箱问题是箱长给定，目标是箱子数与任务对应，则装箱问题是箱长给定，目标是箱子数最少最少.该问题是箱子数给定，而使箱子长度最短该问题是箱子数给定，而使箱子长度最短.max 2.PCNPhard问题 01 (1,1)ijxinjm1niitm1()max optii nfIt(1)考察它的连续松弛问题考察它的连续松弛问题则松弛问题的最优值则松弛问题的最优值(2)对原问题的任一实例对原问题的任一实例 I，一定有，一定有Theorem 4在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一

46、定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题11 max ,max .niii niCLtmt 二、近似算法二、近似算法1、LS 算法算法 （List Scheduling）LS算法是由算法是由Graham于于1966年首先提出，他在研年首先提出，他在研究究LS算法的近似程度时，第一次提出了近似算法的最算法的近似程度时，第一次提出了近似算法的最坏情况进行分析的办法坏情况进行分析的办法.从此讨论近似算法的绝对或渐从此讨论近似算法的绝对或渐进性能比，就广泛地应用于组合优化的研究中进性能比，就广泛地应用于组合优化的研究中.max PmCTheorem 5问题问题 最优值的一

47、个下界为最优值的一个下界为在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题 LS算法的思想是按任务给定的顺序，将每一个工算法的思想是按任务给定的顺序，将每一个工件分给最早空闲的机器（也即使该工件最早完工的机件分给最早空闲的机器（也即使该工件最早完工的机器）加工，在安排当前任务的加工时，不要求知道下一器）加工，在安排当前任务的加工时，不要求知道下一个工件的信息，所以特别适用于在线排序问题个工件的信息，所以特别适用于在线排序问题.01 min jjj mLL 0 1,kjx000 0 ,1,2,.,1k

48、jjjkxjjjmLLtkkLS 算法算法step 1 设设 Lj=0 j=1 m k=1step 2若若 令令若若 k=n+1 时，停止；否则时，停止；否则 重复重复 step 2.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题1 2LSRmprovemax PmC0 1 2 4 7 8 9 14 14LSfP1 P2 P31J2J3J4J5J6J7JSolution:Example 10考虑排序问题考虑排序问题 ，其中，其中 m=3，n=7，t=(1,4,2,8,6,3,7).你有想法吗？你有想法吗

49、？Theorem 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题2、LPT 算法算法 （Largest Processing Time）LPT 算法思想是先将任务按其加工时间从大到小的算法思想是先将任务按其加工时间从大到小的顺序排列，然后用顺序排列，然后用LS算法排序。这也是算法排序。这也是Graham 给出的给出的,它要求任务的信息全部已知后才开始加工。它要求任务的信息全部已知后才开始加工。见前例见前例 t=(1,4,2,8,6,3,7)41 33LPTRm按加工时间重新排列按加工时间重新排列

50、 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 P32J3J5J6J7JP14J1J 11LPToptff一定是最优值吗？理由：1、2、反例Go backJ=(J4,J7,J5,J2,J6,J3,J1)t=(8,7,6,4,3,2,1)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机

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

52、LSLSoptoptfIfIfIfI，而且*()()()()LSLSoptoptfIfIfIfI111 .niistm 由于由于 I 为最小反例，所以为最小反例，所以 fLS(I)等于最后一个任等于最后一个任务务 Jn 的完工时间的完工时间.因为若不然，设因为若不然，设 Jk 的完工时间等于的完工时间等于 fLS(I)，考虑新的任务集考虑新的任务集 J1,J2,Jk,则对由此任务得则对由此任务得到的新实例到的新实例 I*有有因此因此 有有说明说明 I*是一个更小的反例是一个更小的反例.由由 s 为开始加工为开始加工 Jn 时刻，则时刻，则 fLS(I)=s+tn.由由 LS 规则规则Jn 是分

53、给最早空闲的机器加工，是分给最早空闲的机器加工，在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2 平行机排序问题平行机排序问题11()()noptnoptiifItfItm及111111(1)()()()()()nnininLSniioptoptoptoptttttfIstmmmfIfIfIfI11 1(1)2 mm 1 2.LSRm由由 Th 5 知知 因此因此这与这与 I 是反例矛盾，此矛盾说明是反例矛盾，此矛盾说明（2）考虑任务集）考虑任务集 J1，J2，J m2 m+1，其加工时，其加工时间分别为：间分别为：t1=t2=

54、t m2-m=1,t m2-m+1=m,在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题()1 2.()LSoptfIfIm1 2.LSRmGo back需分给需分给 m 台机器加工，易证台机器加工，易证 fLS(I)=2m 1,fopt(I)=m.故故因此因此 有有 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确车间作业排序问题是多处理机中多类型机排序问题车间作业排序问题是多处理机中多类型机排序问题m个处理机具个处理机具有不同的功能有不同的功

55、能12,.,nJJ JJ处理机集处理机集12,.,mPP PP(0).ijt车间作业排序问题：车间作业排序问题：1、同顺序、同顺序(流水流水)作业排序问题作业排序问题3 3、自由、自由(开放开放)作业排序问题作业排序问题2、异顺序作业排序问题、异顺序作业排序问题设有作业集设有作业集每个作业每个作业 Jj 有有 m 道工序：道工序：T1j，T2j，Tmj，工序工序 Tij 的加工时间为的加工时间为 tij各作业分别在处理机各作业分别在处理机 P1，P2,Pm 上完成各道工序上完成各道工序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确

56、第九章第九章 排序问题排序问题Note:在流水作业排序问题中，各作业均依次在处理在流水作业排序问题中，各作业均依次在处理机机 P1,P2,Pm 上完成各道工序上完成各道工序.但对于同一台处理但对于同一台处理机机,各作业在其上的加工顺序可能不同各作业在其上的加工顺序可能不同.排列排序（排列排序（permutation schedule）各作业在全部处理机上的加工顺序相同的排序各作业在全部处理机上的加工顺序相同的排序4 m 排列排序共有排列排序共有所有排序共有排序数所有排序共有排序数!n(!)mn对于对于 的情况，同顺序作业排序问题的最优排序的情况，同顺序作业排序问题的最优排序未必是排列排序未必是

57、排列排序.即排列排序中可能不含有最优排序即排列排序中可能不含有最优排序.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3 3 车间作业排序问题车间作业排序问题14414114t m m 个处理机个处理机，流水作业流水作业排列排序共有两个，排序时间表长均为排列排序共有两个，排序时间表长均为max14C0 1 5 6 7 11 12P1P2P3P41J2J1J1J1J2J2J2Jmax12 ()Copt最优排序不是排列排序，也不是无耽搁排序最优排序不是排列排序，也不是无耽搁排序max Fm CExample 11 考虑排序问题考虑排序问

58、题 其中其中 m=4,n=2.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题Theorem 8 对于流水作业排序问题，至少存在一个对于流水作业排序问题，至少存在一个 最优排序，在此最优排序中，其最前面两台处理最优排序，在此最优排序中，其最前面两台处理P1,P2 上各作业的加工顺序相同上各作业的加工顺序相同.Theorem 9 对于流水作业排序问题，至少存在一个对于流水作业排序问题，至少存在一个 最优排序，在此最优排序中，其最后两台处理最优排序，在此最优排序中，其最后两台处理Pm-1,Pm 上各作业的加工

59、顺序相同上各作业的加工顺序相同.P1P1P2P2iJjJiJiJiJjJjJjJ一定有在第一台处理机上无耽搁的最优排序一定有在第一台处理机上无耽搁的最优排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3 3 车间作业排序问题车间作业排序问题max 2(P)FC问题 Shortest ProcessingTime first Longest ProcessingTime first1212J1,J2 jjjjjjJttJttTheorem 10对于排序问题对于排序问题 ，Johnson 算法算法产生最优排序产生最优排序.Johnso

60、n 算法算法 (SPT-LPT)(1)把作业按工序加工时间分成两个子集：把作业按工序加工时间分成两个子集：对于满足对于满足 t1j=t2j 的作业可分在任一集中；的作业可分在任一集中；(2)先将集先将集 J1 中的作业按中的作业按 t1j 不减排列不减排列(SPT 规则规则)，再将集再将集 J2 中的作业按中的作业按 t2j 不增排列不增排列(LPT 规则规则).在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题443062514303t14523J1,J2,.J JJJJ 0 2 5 6 1112 42

61、4647P1P25J1J4J3J2J2J5J1J4J3JExample 12考虑排序考虑排序 其中其中 n=5max2 FCSolution:由由 Johnson 算法可得算法可得：J1 中的作业按中的作业按 t1j 不减排列：不减排列：J5,J1,J4;J2 中的作业按中的作业按 t2j 不增排列：不增排列：J3,J2,所以最优排列为所以最优排列为 J5,J1,J4,J3,J2,时间表长为时间表长为 Cmax=47.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3 3 车间作业排序问题车间作业排序问题85009210 10260t

62、11113131422122222433233:8 1:5 9 :2JxxxxJxxxxJxx Example 13考虑排序考虑排序 其中其中 n=3max4 FCSolution:建立整数规划模型建立整数规划模型.设设 xij 为作业为作业 Ji 在处理机在处理机 Pj 上开始加工的上开始加工的时间，第一组约束为每一作业在处理机上加工顺序：时间，第一组约束为每一作业在处理机上加工顺序：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题2111 5xx 1121121111 8 5(1)xxMyxxMy22

63、32232222133333313314244241449 2(1)1 10(1)2 6(1)xxMyxxMyxxMyxxMyxxMyxxMy 第二组约束为一族选择性的约束条件，以保证每第二组约束为一族选择性的约束条件，以保证每一处理机同一时间只能处理一个作业：一处理机同一时间只能处理一个作业：8500921010260t如对如对 P1有有：1121 8xx或或引进引进 0-1 变量变量 y1,上述选择性约束条件为：上述选择性约束条件为：类似类似 y2,y3,y4 为为 0-1 变量，对处理机变量，对处理机 P2,P3.P4 有有在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具

64、有一定的梯度，由浅入深，所提出的问题也很明确3 3 车间作业排序问题车间作业排序问题max142433max 2,6,10Cxxx142433 2,6,10CxCxCxmin fC2421 621xx 则Go back第三组约束条件为三个作业的完工时间第三组约束条件为三个作业的完工时间8500921010260t将它化为线性约束将它化为线性约束目标函数为目标函数为 若在原问题上再要求作业若在原问题上再要求作业 J2 在各处理机上的加在各处理机上的加工和等待时间总和不超过工和等待时间总和不超过 21.在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的

65、问题也很明确第九章第九章 排序问题排序问题（Traveling Salesman Problem）TSP:有一位旅行售货员，欲到城市有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知：进行商品销售，已知：的距离为的距离为 wij.(,.(,).).他从其中某个城市出发，需访问每一个他从其中某个城市出发，需访问每一个城市一次且仅一次（在欧氏距离下）而回到出发的城城市一次且仅一次（在欧氏距离下）而回到出发的城市市.问应如何计划他的旅行路线，使他所走路线的总问应如何计划他的旅行路线，使他所走路线的总长度最短？长度最短？ijvvij,1i jn一、旅行商问题的描述一、旅行商问题的描述在

66、整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确4 4 旅行商问题旅行商问题minijijijd x设：设：TSP 问题的数学模型问题的数学模型1.11(1)nijjstxin111(2)nijixjn,1221,2,(3)iji j sxssnsn 1iji Sj Sx或10,1ijxi jnij 表示回路通过表示回路通过 第第 i 个城市到第个城市到第 j 个城市的边个城市的边否则否则在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第九章第九章 排序问题排序问题二、分枝定界法二、分枝定界法1、最小生成树算法解、最小生成树算法解 TSP网络中构成网络中构成 Hamilton 回路的条件回路的条件：a、回路与各个顶点之间有且仅有两条边关联；、回路与各个顶点之间有且仅有两条边关联；b、回路是连通的、回路是连通的.仅以连通作为问题的松弛条件。显然，在赋权网仅以连通作为问题的松弛条件。显然，在赋权网络中，总权数最小的连通子图为最小生成络中，总权数最小的连通子图为最小生成树树.