数学建模---第九章-排序问题

第九章排序问题组合优化理论CombinatorialOptimizationTheory第九章排序问题§4旅行商问题§1单机排序问题§2平行机排序问题§3车间作业排序问题一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同.如何按排加工顺序才能以最短的时间加工完所有的零件.机械加工Example1第九章排序问题这是一个流水线排序问题.第九章排序问题在计算机多道程序操作系统中，并发执行多个进程，任何时刻CPU只能执行一个进程，进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或进程的平均周转时间最短？进程调度事先不知道每个进程的到达时间和执行时间——在线排序事先知道随机到达时间和执行时间的分布、数学期望、方差，目标是极小化平均周转时间的数学期望——随机排序Example2第九章排序问题机场调度在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞，登机门的种类和大小是不同的，而班机的机型和大小也是不同的.飞机按时刻表降落和起飞，当飞机占有登机门时,旅客上下飞机，飞机要接受加油、维护和装卸行李等服务.由于天气和机场的原因，飞机不能起飞，登机时间推迟.调度人员如何制订一个登机门的分配方案，使机场的利用率最高或晚点起飞的飞机最少.登机门——机器，飞机——零件，机场的规定——约束条件Example3第九章排序问题由于效率的度量方法的不同、引进不同的约束条件和机器的数量、类型等，使之得到不少的排序模型，也使排序问题有了更多的应用.用一台或一台以上的机器加工两个或两个以上的零件（任务）时，确定加工顺序使效率最高。——排序（Scheduling）问题由于应用范围逐渐扩大，新的问题不断出现，因而从事这一领域研究的人与日俱增，其内容也越来越丰富，应用也越来越广泛.第九章排序问题确定性排序随机性排序在线排序（On-lineScheduling）半在线排序(Semi-On-lineScheduling)离线排序（Off-lineScheduling）(DeterministicScheduling)所有数据在进行决策前都是已知的（StochasticScheduling）有的数据在进行决策前是未知的，是随机变量,但它们的分布是已知的常见的目标函数（效率的度量方法）用C=(C1，C2，…，Cn)表示任务的完工时间，极小化的目标函数总是完工时间Cj的函数.（1）时间表长时间表长（schedulelength，makespan）定义为maxmaxjjCC它等于最后一个被加工完任务的完工时间，小的时间表长意味着处理机有高的利用率.第九章排序问题第九章排序问题（2）平均加权流时间和加权总完工时间平均加权流时间（meanweightedflowtime）是11nnjjjjjFwFw任务的到达时间jjjFCr其中是任务Tj的流（周转）时间，它等于任务在系统中等待时间和加工时间的和.对平均加权流时间进行变形，可得极小化F相当于极小化加权总完工时间（totalweightedcompletiontime）1njjjCwC(如果wj=1j=1,2,…,n即为总完工时间)第九章排序问题式中的第一项的分母和第二项都是常数，所以111111nnjjjjjnnnnjjjjjjjjjjFwFwwCwwrw第九章排序问题（3）最大延误最大延误（maximumlateness）定义为maxmaxjjLL任务的截止期限（4）加权总误工加权总误工（totalweightedtardiness）是1njjjDwD其中Lj=Cj–dj是任务Tj的延误时间.其中Dj=max{Cj–dj，0}是任务Tj的误工时间.第九章排序问题（5）加权误工任务数加权误工任务数（weightednumberoftardytasks）是1njjjUwU10jjjjjjCdUTCd其中是对任务误工的单位惩罚第九章排序问题排序问题的三要素：机器（处理机）、作业（任务）、目标函数用三元组描述一个排序模型α：机器的数量和类型；β：作业的约束条件；γ：优化的目标函数.基本假设：（1）任务或作业和处理机都是有限的；（2）在任一时刻，任何处理机只能加工一个任务或一道工序;（3）极小化单一目标函数.第九章排序问题Definition1对于一个可行排序，如果有准备好被加工的任务或工序，不准有空闲的处理机，称这种可行排序为无耽搁排序（nondelayschedule）；否则称为耽搁排序（delayschedule）。无耽搁排序相当于有工作可做就不能闲着.对于大多数排序问题，包括所有的可中断排序，最优排序是无耽搁排序，然而也有一些不可中断排序问题的最优排序是耽搁排序.第九章排序问题排序问题1jjjrwC1：表示一台机器rj:表示任务有不同的到达时间n=2，t=(10，5)，r=(0，1)，w=(1，5)该问题有两个可行排序，用GanttCharts表示：01015AB01616BAnondelayschedule:delayschedule:Z1=10*1+15*5=85Z2=6*5+16*1=46Example4第九章排序问题阿克米自行车的装配问题工序紧前工序加工时间工序紧前工序加工时间A——8FD2BA7GF2CA，E7HE，G8D——2IE，G8ED3JB，C15这是一个排序问题.max2PprecC由两名熟练工人进行装配，要求装完时间最早.02578915162331P1P2ABCEFGHIJDExample5第九章排序问题如果每道工序的加工时间减少1，最优时间表会小于31吗？是26吗？013457132027ABJDCEFGHIP1P2最优耽搁排序工序紧前工序加工时间工序紧前工序加工时间A——7FD1BA6GF1CA，E6HE，G7D——1IE，G7ED2JB，C14第九章排序问题ABCDEFGHIJ0134571213182032P1P2最优无耽搁排序工序紧前工序加工时间工序紧前工序加工时间A——7FD1BA6GF1CA，E6HE，G7D——1IE，G7ED2JB，C14第九章排序问题如果加工时间不变而增加一个装配工人，最优时间表会小于31吗？最优耽搁排序02456814152230P1P2P3ADFGECHBIJ工序紧前工序加工时间工序紧前工序加工时间A——8FD2BA7GF2CA，E7HE，G8D——2IE，G8ED3JB，C15第九章排序问题最优无耽搁排序02456814152136P1P2P3ADEFGHIBCJGoback工序紧前工序加工时间工序紧前工序加工时间A——8FD2BA7GF2CA，E7HE，G8D——2IE，G8ED3JB，C15§1单机排序问题第九章排序问题单机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之一.首先单机排序问题比较容易求出解决方法，这些方法对于研究较复杂的排序问题具有指导作用，可为处理复杂排序问题提供近似算法；其次，单机排序问题大量存在于现实生活中，具有广泛的实际背景，许多实际问题都可以归结为单机排序问题.§1单机排序问题设一个机修车间有n台不同的机床要进行大修,它们的维修时间已知为t1,t2,…,tn,而机床Ai在车间逗留的过程中每单位时间的损失费为wi(i=1,…,n)1jjwC一、问题如何排序？maxC1问题试求一种排序，使得n台机床在修理完毕时，总的损失为最小.A1A2A3A4如何排序？猜Example6第九章排序问题设n台机床维修的排序为(k1,k2,…,kn)则机床1212:(,,...,)(,,...,)1~nnnHkkkkkk令为的一种排序的维修完毕的时间为skAn台机床按此排序维修完时，总的损失费为1iinkkiwC1siskkiCt本题要寻找一种排序（r1,r2,…,rn）满足1211min(,,...,)iiiinnrrkkniiwCwCkkkHSolution:§1单机排序问题设有两排序11(,,,)mmnkkkk……11(,,,)mmnkkkk……（1）（2）分析排序（1）与（2）的优劣总损失费仅在km,km+1处有区别按（1）排序1mmkkAA和的损失费mkA1mkA2mkA111111mmmmmmmmmmkkkkkkkkkkwCwtwCwtwt按（2）排序1mmkkAA和的损失费mkA1mkA2mkA111111mmmmmmmmmmkkkkkkkkkkwCwtwCwtwt1mkA1mkA第九章排序问题1111mmmmmmmmkkkkkkkkttwtwtww当即时，排序（2）优于排序（1）.Theorem11212...nnrrrrrrttt1jjwC满足下列条件的排序（r1,r2,…,rn）为问题的最优排序.§1单机排序问题如:考虑排序问题1jjwC其中n=5,t=(12，4，7，11，6)，w=(4，2，5，5，6)35124123453,2,1.4,2.2,1ttttt由66513217528440435jjwC53241()AAAAA，，，，此时得最优排序为第九章排序问题在Ex.6中，如果考虑各待维修的机床在机修车间平均逗留时间（或总逗留时间）最短，1)jjCCn（或如何排序？这只是Ex.6中wj=1/n和wj=1的特例12...nrrrttt为最优排序.或所以，满足下列条件的排序（r1,r2,…,rn）§1单机排序问题以下讨论的排序问题都与工期有关，即每个任务均有一个工期。工期dj表示对任务Tj限定的完工时间.如果不按期完工，应受到一定的惩罚.max1L二、问题任务没有准备时间的最大延误的排序问题比较简单，只需将任务按最早工期优先（EarliestDueDatefirst，简记EDD）规则，就可以得到最优排序.按照这一规则，任务按dj不减的顺序进行排序.maxmaxjjLCd第九章排序问题Theorem2max1Lprove1maxL由EDD规则可以求得最优排序143256(,,,,,)TTTTTT2maxL最大延误为Goon对于问题EDD规则可以得到最优排序.Example7考虑排序问题，其中n=6,t=(3,1,4,1,3,2)，d=(2,10,6,4,11,12)§1单机排序问题Theorem2的证明Goback只需证明任何不满足EDD规则的排序，均可转化为满足EDD规则而目标函数不增。设某一排序s违反了EDD规则，则在此排序中，至少有两个相邻任务jkjkjkTTTTdd、，排在之前，而pdkdjpdkdjTjTjTkTkjjjjkjkkTpLptdLpttd设在时间时开始加工，则，'''.jkjjkjkkkTTsLpttdLptd对调的位置，其余任务位置不变，得一排序在这排序中，'''maxmax,jkkjkkddLLLLLL因为，所以从而第九章排序问题在许多情况下，延误时间的长短并不重要。只要有延误发生，造成的影响是一样的.例如用航天飞机发射太空站，每个太空站都要完成特定的太空观测任务,误期发射的太空站将失去作用.此时，目标应使误期发射的太空站数目最少.1jU三、问题误工任务数问题Example8设有n个工件T1,T2,…,Tn要在一台机器上加工，加工时间分别为t1,t2,…,tn，要求的交货日期分别为d1,d2,…,dn.试求一种加工排序，使得误期交货的工件最少.算法:（1）把任务按EDD规则排序；（2）计算各任务的完工时间，如果当前排序已无延误任务，则转（5），否则转（3）；（3）找到第一个延误任务，不妨设为第k个任务；（4）在前k个任务中选取并删除加工时间最长的任务，得到一个部分排序，转（2）；（5）将删除的任务以任何顺序排在所得的部分排序之后，得到最优排序.1jUprov