第8章 排序问题优秀PPT.ppt

第8章 排序问题现在学习的是第1页，共27页8.1排序的基本概念排序的基本概念排序与编制作业计划排序与编制作业计划编制作业计划实质上是要将资源分配给不同的任务，按照既定编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。的优化目标，确定各种资源利用的时间问题。工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。讲课。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。在编制作业计划过程中在编制作业计划过程中,有一个问题需要管理人员注意，即投入生产过程有一个问题需要管理人员注意，即投入生产过程的作业顺序的安排。的作业顺序的安排。编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。主要工作之一就是要确定出最佳的作业顺序。现在学习的是第2页，共27页确定出最佳的作业顺序看似容易，只要列出所有的顺序，确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。不可能的。例如，考虑例如，考虑32项任务（工件），有项任务（工件），有32！2.6 1035种方案种方案,假假定计算机每秒钟可以检查定计算机每秒钟可以检查1billion个顺序个顺序,全部检验完毕需要全部检验完毕需要8.4 1015个世纪个世纪.如果只有如果只有16个工件个工件,同样按每秒钟可以检查同样按每秒钟可以检查1billion个顺序计算个顺序计算,也需要也需要2/3年年.以上问题还没有考虑其他的约束条件以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问所以，很有必要去寻找一些有效算法，解决管理中的实际问题。题。现在学习的是第3页，共27页排序问题的分类排序问题的分类根据机器数的多少根据机器数的多少单台机器的排序问题单台机器的排序问题多台机器的排序问题多台机器的排序问题根据加工路线的特征根据加工路线的特征单件车间排序单件车间排序(JobShop)流水型排序流水型排序(FlowShop)根据工件到达系统的情况根据工件到达系统的情况静态排序静态排序动态排序动态排序根据参数的性质根据参数的性质确定型排序确定型排序随机型排序随机型排序根据要实现的目标根据要实现的目标单目标排序单目标排序多目标排序多目标排序现在学习的是第4页，共27页排序问题的一般假设排序问题的一般假设为便于分析研究，建立数学模型，除非特别说明，本课程对排序问题有如为便于分析研究，建立数学模型，除非特别说明，本课程对排序问题有如下假设：下假设：一个工件不能同时在几台机器上加工一个工件不能同时在几台机器上加工工件在加工过程中采取平行移动方式，即上一道工序完工后，立工件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工即送下道工序加工不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件不得中途停止插入其它工件每道工序只在一台机器上完成每道工序只在一台机器上完成工件数、机器数和加工时间已知，加工时间与加工顺序无工件数、机器数和加工时间已知，加工时间与加工顺序无关关每台机器同时只能加工一个工件每台机器同时只能加工一个工件现在学习的是第5页，共27页排序常用的符号排序常用的符号Ji-工件工件i，i=1,2,.n Mj-机器机器j，j=1,2,.m di-工件工件i的交货期的交货期 Pij-工件工件i在机器在机器j上加工时间上加工时间,系统内有系统内有Pi=jPij Wij-工件工件i在机器在机器j的等待时间的等待时间,系统内有系统内有Wi=jWij Ci-工件工件i的完成时间的完成时间,在工件都已到达的情况下在工件都已到达的情况下,Ci=Pi+Wi Fi-工件工件i的流程时间的流程时间，在工件都已到达的情况下在工件都已到达的情况下,Fi=Pi+Wi Li-工件工件i的延误时间的延误时间,Li=Ci-di.Li0 延延误误 Ti-工件工件i的延期量的延期量,Ti=max0,Li Ei-工件工件i提前完成的时间提前完成的时间现在学习的是第6页，共27页排序问题的表示方法排序问题的表示方法排序问题常用四个符号来描述排序问题常用四个符号来描述:n/m/A/B其中其中,n-工件数；工件数；m-机器数；机器数；A-车间类型车间类型,F=流水型排序流水型排序P=排列排序排列排序G=一般类型一般类型,即单件型排序即单件型排序B-目标函数目标函数现在学习的是第7页，共27页8.2流水作业计划问题流水作业计划问题流水线是流水车间流水线是流水车间(Flowshop)典型的代表，每个零件的典型的代表，每个零件的加工路线都一致。加工路线都一致。只要加工路线一致：只要加工路线一致：M1,M2,M3，.,Mm,不要求每个零不要求每个零件都经过每台机器加工，如果某些工件不经过某些机器加工，件都经过每台机器加工，如果某些工件不经过某些机器加工，则设相应的加工时间为零即可。则设相应的加工时间为零即可。一般来说，对于流水车间的排序问题，工件在不同的机一般来说，对于流水车间的排序问题，工件在不同的机器上的加工顺序不尽相同。器上的加工顺序不尽相同。排列排序问题：所有工件在各机器上的加工顺序都是相同的。排列排序问题：所有工件在各机器上的加工顺序都是相同的。最长流程时间最长流程时间Fmax又称作加工周期又称作加工周期现在学习的是第8页，共27页最长流程时间最长流程时间Fmax又称作加工周期又称作加工周期设设n个工件的加工顺序为个工件的加工顺序为S=(s1,s2,sn)，Cj(si)为工件为工件si在机在机器器Mj上的完工时间，上的完工时间，psij表示工件在表示工件在Mj上的加工时间，则可按上的加工时间，则可按下式计算下式计算Cj(si)C1(si)C1(si-1)+psi1Cj(si)maxCj-1(si),Cj(si-1)+psijFmax=Cm(sn)这是个递推公式，从这是个递推公式，从j=1,i=1开始，最后可以得到开始，最后可以得到Fmax现在学习的是第9页，共27页加工周期为46iPi1Pi2Pi3Pi4表表8-2顺序顺序S下的加工时间矩阵下的加工时间矩阵【例【例8-1】6/4/p/Fmax问题，当按顺序问题，当按顺序S(6,1,5,2,4,3)加工时，求加工时，求Fmax。i123456Pi1423142Pi2456745Pi3587555Pi4424331表表8-1加工时间矩阵加工时间矩阵625511445454453225824175333674261012131671213111520273317223035422125323846现在学习的是第10页，共27页n/2/F/Fmax问题的含义问题的含义n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器机器1到达系统工件到达系统工件的集合的集合离开系统离开系统J1J2J3Jn机器机器2图图8-1n/2/F/Fmax系统系统现在学习的是第11页，共27页n/2/F/Fmax问题的目标问题的目标 n/2/F/Fmax问题的目标是使最大完成时间（总加工周期）问题的目标是使最大完成时间（总加工周期）Fmax最短。最短。Fmax的含义见如下的甘特图的含义见如下的甘特图(GanttChart)。多台机器排序的目标一般也是使最大完成时间（总加工周期）多台机器排序的目标一般也是使最大完成时间（总加工周期）Fmax最短。最短。Fmax 时间时间 机器机器AB在机器在机器A上的作业时间上的作业时间总加工周期总加工周期图图8-2n/2/F/Fmax问题问题现在学习的是第12页，共27页n/2/F/Fmax问题的算法问题的算法一个优化算法就是著名的约翰逊法(Johnsons Law)。其具体求解过程分为4个步骤：(1)列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。现在学习的是第13页，共27页【例【例8-2】某一班组有】某一班组有A、B两台设备，要完成两台设备，要完成5个工件的加工任个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。期最短的作业顺序。表表8-3工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号J1J2J3J4J5设备设备A36715设备设备B28643加工周期为加工周期为30现在学习的是第14页，共27页解解：由由约约翰翰逊逊法法可可知知，表表中中最最小小加加工工时时间间值值是是1个个时时间间单单位位，它它又又是是出出现现在在设备设备1上，根据约翰逊法的规则，应将对应的工件上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得：排在第一位，即得：J4-*-*-*-*去去掉掉J4，在在剩剩余余的的工工件件中中再再找找最最小小值值，不不难难看看出出，最最小小值值是是2个个时时间间单单位位，它它是是出现在设备出现在设备2上的，所以应将对应的工件上的，所以应将对应的工件J1排在最后一位，即：排在最后一位，即：J4-*-*-*-J1再去掉再去掉J1，在剩余的，在剩余的J2、J3、J5中重复上述步骤，求解过程为：中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1经经计计算算，初初始始作作业业顺顺序序的的总总加加工工周周期期是是30，用用约约翰翰逊逊法法排排出出的的作作业业顺顺序序总总加加工工周周期期是是26，显然后者的结果优于前者。，显然后者的结果优于前者。现在学习的是第15页，共27页问题算法的扩展问题算法的扩展(ExtensiontoThreeMachines)一般情况下，当机器数为一般情况下，当机器数为3台以上时，就很难找到最优解了。台以上时，就很难找到最优解了。但是，对于但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以个工件由三台机器流水作业时，在满足某些条件后可以采用采用JohnsonsLaw解决问题。解决问题。设：设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题：下条件，则可以转化为两台机器的排序问题：minAi=maxBiorminCi=maxBi定义：定义：Ai=Ai+Bi,Bi=Bi+Ci【例【例8-3】考虑以下问题：】考虑以下问题：5个工件由个工件由3台机器加工台机器加工,作业时间见下表。作业时间见下表。求求:总加工周期最短的作业顺序。总加工周期最短的作业顺序。现在学习的是第16页，共27页12345机器机器A49865机器机器B56234机器机器C810671153 解解:检查上表检查上表,发现发现:minAi=4maxBi=6minCi=6因此因此,满足以上条件满足以上条件,建立两台机器的作业时间表建立两台机器的作业时间表:表表8-4加工时间矩阵加工时间矩阵现在学习的是第17页，共27页应用应用Johnson法则，得出：法则，得出：总加工周期为：总加工周期为：12345机器机器A9151099机器机器B13168101514523机器机器A46598机器机器B53462机器机器C871110651表表8-5两台机器的加工时间矩阵两台机器的加工时间矩阵表表8-6三台机器的加工时间矩阵三台机器的加工时间矩阵现在学习的是第18页，共27页一般一般n/m/P/Fmax问题近优解的启发式算法问题近优解的启发式算法一般采用启发式算法一般采用启发式算法(Heuristics)解决这类问题。解决这类问题。关键工件法关键工件法步骤步骤1计算计算,找出其中最大者，定义为关键工件找出其中最大者，定义为关键工件JC。步骤步骤2除除JC外，将满足外，将满足ti1tim的工件，按的工件，按tim值的大小，从大到小排值的大小，从大到小排在在JC的后面。的后面。步骤步骤4除除JC外，将满足外，将满足ti1=tim的工件，排在的工件，排在JC的前面或者后面。的前面或者后面。步骤步骤5如有多个方案，可再加比较，从中选优。如有多个方案，可再加比较，从中选优。现在学习的是第19页，共27页【例【例8-4】关键工件法举例】关键工件法举例J1J2J3J4J5J6机器机器1ti15541210机器机器2ti25553610机器机器3ti3833474机器机器4ti4282156机器机器5ti55212810252315112840找出关键工件：工作负荷最大的找出关键工件：工作负荷最大的40，对应的是工件，对应的是工件6，所以，所以JC=J6确定排在关键工件前面的工件：满足步骤确定排在关键工件前面的工件：满足步骤2条件的有条件的有J4,J5,所以有所以有J4J5J6确定排在关键工件后面的工件：满足步骤确定排在关键工件后面的工件：满足步骤3条件的有条件的有J2,J3,所以有所以有J6J2J3满足步骤满足步骤4条件的有条件的有J1,所以有所以有J6J1，或者或者J1J6最后有：最后有：J4J5J6J1J2J3，或者或者J4J5J1J6J2J3现在学习的是第20页，共27页8.3单件作业排序问题单件作业排序问题加工描述矩阵和加工时间矩阵现在学习的是第21页，共27页无延迟作业计划的构成我们称每安排一道工序称作一我们称每安排一道工序称作一“步步”，设，设Stt步之前已排序工序构成的部分作业计划；步之前已排序工序构成的部分作业计划；Ot第第t步可以排序的工序的集合；步可以排序的工序的集合；TkOt中工序中工序Ok的最早可能开工时间；的最早可能开工时间；TkOt中工序中工序Ok的最早可能完工时间。的最早可能完工时间。现在学习的是第22页，共27页无延迟作业计划的构成步骤:设设t1，S1为空集，为空集，O1为各工件第一道工序的为各工件第一道工序的集合。集合。求求T*minTk，并求出，并求出T*出现的机器出现的机器M*。如果。如果M*有多台，则任选一台。有多台，则任选一台。从从Ot中挑出满足以下两个条件的工序中挑出满足以下两个条件的工序Oj：需要机器：需要机器M*加工，且加工，且TjT*。将确定的工序将确定的工序Oj放入放入St，从，从Ot中消去中消去Oj，并将，并将Oj的紧后工序放入的紧后工序放入Ot，使，使tt1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，停止。；否则，停止。现在学习的是第23页，共27页tOtTkTkT*M*Oj11,1,102011,1,12,1,3030321,2,3262,1,32,1,3030331,2,337331,2,32,2,1373141,3,2782,2,12,2,1373151,3,278722,3,22,3,27127261,3,212131221,3,2例【例【8-5】表表8-72/3/G/Fmax的无延迟作业计划的无延迟作业计划现在学习的是第24页，共27页图图8-3无延迟作业计划无延迟作业计划现在学习的是第25页，共27页优先派工法则在在介介绍绍无无延延迟迟作作业业计计划划的的构构成成步步骤骤时时，其其中中第第步步的的两两个个条条件件一一般般都都有有多多个个工工序序可可以以满满足足。按按什什么么样样的的准准则则来来选选择择可可安安排排的的工工序序，对对作作业业计计划划的的优优劣劣有有很很大大影影响响。为为了了得得到到所所希希望望的的作作业业计计划划，人人们们提提出出了了很很多多优优先先调调度度法法则则，按按优优先先调调度度法法则则挑挑选选工工序序比比随随意意挑挑选选一一道道工工序序的的方方法法更更能能符符合合计计划划编编制制者者的的要要求求，同同时时又又不不必必列列出出所所有有可可能能的作业计划，从而计算量小。的作业计划，从而计算量小。迄迄今今，人人们们已已提提出出了了100多多个个优优先先调调度度法法则则，其其中中主主要要的的有有下下8个：个：SPT(ShortestProcessingTime)法法则则优优先先选选择择加加工工时时间间最最短的工序。短的工序。FCFS(FirstComeFirstServed)法法则则优优先先选选择择最最早早进进入可排工序集合的工件。入可排工序集合的工件。现在学习的是第26页，共27页优先派工法则(续)EDD(EarliestDueDate)法则优先选择完工期限紧的工件。法则优先选择完工期限紧的工件。MWKR(MostWorkRemaining)法法则则优优先先选选择择余余下下加加工工时时间间最最长的工件。长的工件。LWKR(LeastWorkRemaining)法法则则优优先先选选择择余余下下加加工工时时间间最短的工件。最短的工件。MOPNR(MostOperationsRemaining)法法则则优优先先选选择择余余下下工工序序数数最多的工件。最多的工件。SCR(SmallestCriticalRatio)法法则则优优先先选选择择临临界界比比最最小小的的工工件。临界比为工件允许停留时间与工件余下加工时间之比。件。临界比为工件允许停留时间与工件余下加工时间之比。RANDOM法则随机地挑一个工件法则随机地挑一个工件现在学习的是第27页，共27页