生产第十一章-制造业作业计划与控制.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十一章 制造业作业计划与控制,引言,通过,MRP,确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。,1,11.1,作业计划问题的基本概念,11.2,流水作业排序问题,11.3,单件作业的排序问题,11.4,生产作业控制,2,11,收入、费用和利润,要求掌握：,最长流程时间的计算,2.,约翰逊算法,3.,一般流水作业排序问题的,3,种启发式算法,4.,相同零件的,3,种移动方式下机器加工周期的计算方法,学习目的与要求,3,重点,最长流程时间的计算,约翰逊算法,相同零件的,3,种移动方式下机器加工周期的计算方法,难点,一般流水作业排序问题的启发式算法,教学重点与难点,4,生产任务的最终落实,MRP,确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。,各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。,将任务安排到工作地，牵涉到作业计划。,5,编制作业计划要解决的问题,由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。,编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题,确定机器加工每个工件的开始时间和完成时间,例如,;,医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。,6,第一节 排序问题的基本概念,一、名词术语,排序：确定工件在机器上的加工顺序。,作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。,派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。,赶工：实际进度已落后于计划进度时采取的行动。,7,“,机器,”,，可以是工厂里的各种机床，也可以是维修工人，表示,“,服务者,”,“,零件,”,代表,“,服务对象,”,。零件可以是单个零件，也可以是一批相同的零件,“,加工顺序,”,则表示每台机器加工,n,个零件的先后顺序，是排序和编制作业计划要解决的问题,8,二、假设条件和符号说明,假设条件：,1.,一个工件不能同时在几台不同的机器上加工。,2.,工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。,3.,不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。,4.,每道工序只在一台机器上完成。,5.,工件数、机器数和加工时间已知，加工时间与加工顺序无关。,6.,每台机器同时只能加工一个工件,9,有关符号,J,i,：工件,i,，,i=1,，,2,，,，,n,M,j,：机器,j,，,j=1,，,2,，,，,n,p,ij,为,J,i,在,M,j,上的加工时间,r,i,为,J,i,的到达时间，指,J,i,从外部进入车间，可以加工的最早时间,d,i,为,J,i,的完工期限,C,i,为,J,i,的完工时间,C,max,为最长完工时间,F,i,为,J,i,的流程时间，即工件在车间的实际停留时间,F,max,为最长流程时间,L,i,为工件的延迟时间,L,max,为最长延迟时间,10,三、排序问题的分类,根据机器数的多少,单台机器的排序问题,多台机器的排序问题,对于多台机器排序问题，根据加工路线的特征，分成,单件作业排序,(Job-Shop),问题,流水作业排序,(Flow-Shop),问题,工件的加工路线不同，是单件作业排序问题的基本特征；,所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。,11,根据工件到达系统的情况,静态排序,动态排序,根据参数的性质,确定型排序,随机型排序,12,4,参数法,n/m/A/B,其中，,n,为工件数,m,为机器数,A,车间类型。在,A,的位置若标以标以,“,P,”,，则表示,流水作业排列排序,问题；若标以,“,G,”,，则表示一般单件作业排序问题。当,m=1,，则,A,处为空白。,B,为目标函数，通常是使其值最小,例如：,n/3/P/C,max,13,四、作业排序方案的评价标准,1.,工作流程时间,从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。,2.,加工周期,完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。,14,3.,在制品库存（,WIP,）,在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。,4.,利用率,用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。,15,五、优先调度规则,调度方法：,所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。,一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。,16,常用的优先顺序规则：,FCFS,规则,优先选择最早进入可排序集合的工件。,EDD,规则 优先选择完工期限最紧的工作。,SPT,规则 优先选择加工时间最短的工件。,SCR,规则,优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。,MWKR,规则,优先选择余下加工时间最长的工件。,LWKR,规则,优先选择余下加工时间最短的工件。,MOPNR,规则,优先选择余下工序数最多的工件。,RANDOM,规则,随机地挑选下一个工件。,17,一般作业排序的目标,满足顾客或下一道工序的交货期要求,流程时间最短,准备时间最短或成本最小化,在制品库存最低,机器设备或劳动力利用最大化,18,例,一个加工车间负责加工发动机机壳，现在共有,5,个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。,发动机机壳,所需标准加工时间,（包括机器调整）,预计顾客取货时间,（从现在开始算起的所需工作时间）,机壳,1,8,10,机壳,2,6,12,机壳,3,15,20,机壳,4,3,18,机壳,5,12,22,19,机壳加工次序,开始,工作,加工,时间,结束,工作,流程,时间,预计顾客,取货时间,顾客实际取货时间,提前,小时数,拖延,小时数,机壳,4,0,3,3,3,18,18,15,机壳,2,3,6,9,9,12,12,3,机壳,1,9,8,17,17,10,17,7,机壳,5,17,12,29,29,22,29,7,机壳,3,29,15,44,44,20,44,24,总数,102,120,18,38,平均数,20.4,3.6,7.6,平均在制品库存,=102/44=2.32,个 平均总库存,=120/44=2.73,个,SPT,规则排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,流程时间,=,等待时间,+,加工时间,平均在制品库存,=,各工件流程时间之和,加工周期,平均总库存,=,各工件实际取货时间之和,加工周期,20,机壳加工次序,开始,工作,加工,时间,结束,工作,流程,时间,预计顾客,取货时间,顾客实际取货时间,提前,小时数,拖延,小时数,机壳,1,0,8,8,8,10,10,2,机壳,2,8,6,14,14,12,14,2,机壳,4,14,3,17,17,18,18,1,机壳,3,17,15,32,32,20,32,12,机壳,5,32,12,44,44,22,44,22,总数,115,118,3,36,平均数,23.0,0.6,7.2,平均在制品库存,=115/44=2.61,个 平均总库存,=118/44=2.68,个,EDD,规则排序结果,顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。,比较,SPT,规则和,EDD,规则的排序结果，用,SPT,规则排序，其平均流程时间更短，在制品库存更少。用,EDD,规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。,21,优先调度法则,按,SPT,法则可使工件的平均流程时间最短，从而减少在制品量。,FCFS,法则来自排队论，它对工件较公平。,EDD,法则可使工件延误时间最小。,MWKR,法则使不同工作量的工件的完工时间尽量接近。,LWKR,法则，使工作量小的工件尽快完成。,22,第二节 流水作业排序问题,流水作业排序问题的基本特征是每个工件的加工路线都一致。,加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。,对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。,排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。,23,一、最长流程时间,Fmax,的计算,n/m/P/F,max,问题，,n,个零件要按相同的加工路线经过,m,台机器加工，目标是使这批零件的最长流程时间最短。,最长流程时间,又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。,24,例 有一个,6/4/P/Fmax,问题，其加工时间如下表所示。当按顺序,S=,（,6,，,1,，,5,，,2,，,4,，,3,）加工时，求,Fmax,。,i,1,2,3,4,5,6,4,2,3,1,4,2,4,5,6,7,4,5,5,8,7,5,5,5,4,2,4,3,3,1,25,i,p,i1,p,i2,p,i3,p,i4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,30,35,42,13,21,25,32,38,46,26,二、两台机器排序问题,两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于,1954,年提出了一个有效算法，那就是著名的,Johnson,算法,。约翰逊算法包括以下几个步骤：,（,1,）列出每个作业在两台机器上的加工时间。,（,2,）选择最短的加工时间，如果有两个相同的值，则任选一个。,（,3,）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。,（,4,）对于剩余的作业重复第二步和第三步，直到整个排序完成。,27,【,例,】,求如表所示的,6/2/F/Fmax,问题的最优解。,i,1,2,3,4,5,6,a,i,5,1,8,5,3,4,b,i,7,2,2,4,7,4.5,将零件,2,排第,1,位,2,将零件,3,排第,6,位,2 3,将零件,5,排第,2,位,2 5 3,将零件,6,排第,3,位,2 5 6 3,将零件,4,排第,5,位,2 5 6 4 3,将零件,1,排第,4,位,2 5 6 1 4 3,28,【,例 题,】,有,5,件任务都需要两步操作（先,1,后,2,）来完成，下表给出了相应的时间：,（,1,）根据,Johnson,算法安排工作顺序；,（,2,）计算加工周期。,任务,操作,1,所需时间（小时）,操作,2,所需时间（小时）,A,3.0,1.2,B,2.0,2.5,C,1.0,1.6,D,3.0,3.0,E,3.5,1.5,29,任务,操作,1,所需时间（小时）,操作,2,所需时间（小时）,A,3.0,1.2,B,2.0,2.5,C,1.0,1.6,D,3.0,3.0,E,3.5,1.5,A,3.0,E,3.5,D,3,B,2,C,1,1.0,3.0,6.0,9.5,12.5,0,操作,1,A,1.2,E,1.5,D,3.0,B,2.5,C,1.6,2.6,5.5,9.0,11,13.7,操作,2,30,A,3.0,E,3.5,D,3,B,2,C,1,1.0,3.0,6.0,9.5,12.5,0,操作,1,A,1.2,E,1.5,D,3.0,B,2.5,C,1.6,2.6,5.5,9.0,11,13.7,操作,2,i,C,B,D,E,A,操作,1,操作,2,31,【,例 题,】,根据,Johnson,算法求以下,8/2/F/F,max,问题的最优解。,任务,a,i,b,i,A,9,6,B,7,2,C,10,3,D,8,1,E,F,G,H,2,1,5,4,5,8,7,4,32,1.,将所有,a,i,b,i,的工件按,a,i,值不减的顺序排成一个序列,A,；,2.,将,a,i,b,i,的工件按,b,i,值不增的顺序排成一个序列,B,；,3.,将,A,放到,B,之前，就构成了一个最优加工顺序。,改进算法,33,工件号,1 2 3 4 5 6,a,i,5 1 8 5 3 4,b,i,7 2 2 4 7 4,工件最优顺序：,2 5 6 1 4 3,1 3 4 5 5 8,2 7 4 7 4 2,4,8,13,18,26,3 11 15 22 26 28,a,i,b,i,最优顺序下的加工周期为,28,34,练 习,某公司要生产,4,种产品，需要两台机器,1,和,2,。其中，有,3,种产品需要先在机器,1,上加工。下表给出了两台机器上加工各产品所需的时间。,（,1,）安排生产顺序，使得在最短时间内完成生产。,（,2,）机器,1,共需工作多长时间？,（,3,）机器,2,应该在机器,1,开始工作后多长时间开始运转？,任务,在机器,1,上加工所需时间（小时）,在机器,2,上加工所需时间（小时）,A,3.2,2.10,B,2.5,1.25,C,1.7,3.00,D,2.1,0,35,任务,在机器,1,上加工所需时间（小时）,在机器,2,上加工所需时间（小时）,A,3.2,2.10,B,2.5,1.25,C,1.7,3.00,D,2.1,0,9.5,B,1.25,A,2.10,C,3.00,D,2.1,B,2.5,A,3.2,C,1.7,1.7,4.9,7.4,4.7,6.8,8.65,机器,1,机器,2,36,三、一般,n/m/P/Fmax,问题的启发式算法,启发式算法是一个基于直观或经验构造的算法，在可接受的花费,(,时间、占用空间等,),下给出待解决组合优化问题的可行解。,启发式方法因其易于实现、计算复杂度低等原因，目前应用得最为广泛。,37,（一）,Palmer,法,1965,年，,D,S,Palmer,提出按,斜度指标,排列工件的启发式算法，称之为,Palmer,法。,工件的斜度指标可按下式计算：,k=l,，,2,，,，,m,式中，,m,为机器数；,p,ik,为工件,i,在,M,k,上的加工时间。,按照各工件,i,不增,的顺序排列工件，可得出令人满意的顺序。,38,39,例 有一个,4/3/F/Fmax,问题，其加工时间如下表所示，试用帕尔默法求最优顺序。,i,1,2,3,4,P,i1,1,2,6,3,P,i2,8,4,2,9,P,i3,4,5,8,2,解：对于本例，,i,=,P,i1,P,i3,于是，,1,=,P,11,P,13,=,1,4=3,2,=,P,21,P,23,=,2,5=3,3,=,P,31,P,33,=,6,8=2,4,=,P,41,P,43,=,3,2=,1,按,i,不增的顺序排列工件，得到加工顺序,(1,，,2,，,3,，,4),和,(2,，,1,，,3,，,4),，恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下，,F max=28,。,40,（二）关键零件法,步骤如下：,（,1,）计算每个零件的总加工时间，找出加工时间最长的零件,C,，将其作为关键零件。,（,2,）对于余下的零件，若,p,i1,p,im,，则按,p,i1,不减,的顺序排成一个序列,S,a,；若,p,i1,p,im,，则按,p,im,不增,的顺序排成一个序列,S,b,。,（,3,）顺序（,S,a,，,C,，,S,b,）即为所求顺序。,41,i,1,2,3,4,p,i1,1,2,6,3,p,i2,8,4,2,9,p,i3,4,5,8,2,p,i,13,11,16,14,例 有一个4/3/F/Fmax问题，其加工时间如下表所示，试用关键零件法求最优顺序。,解：总加工时间最长的为3号零件，p,i1,p,i3,的零件为1和2，按p,i1,不减的顺序排成S,a,=（1，2）；p,i1,p,i3,的零件为4号零件，S,b,=（4）,这样得到的加工顺序为（1，2，3，4）。,42,例 题,用关键工件法求解下表的最优排序。,解：总加工时间最长的为,2,号零件，,p,i1,p,i4,的零件为,1,和,3,，按,p,i1,不减的顺序排成,s,a,=,（,1,，,4,）；,p,i1,p,i4,的零件为,4,号零件，,s,b,=,（,3,），这样得到的顺序为（,1,，,4,，,2,，,3,）。,i,1,2,3,4,p,i1,1,9,5,4,p,i2,5,7,6,3,p,i3,4,6,3,5,p,i4,6,2,3,7,i,1,2,3,4,p,i1,1,9,5,4,p,i2,5,7,6,3,p,i3,4,6,3,5,p,i4,6,2,3,7,p,i,16,24,17,19,43,（三）,CDS,法,康坎贝尔,-,杜德克,-,史密斯三人提出了一个启发式算法，简称,CDS,法。,具体做法是，对加工时间,用,Johnson,算法求（,m-1,）次加工顺序，取其中最好的结果。,44,m=2,时，,l=1,加工时间分别为,p,i1,和,p,i2,；,m=3,时，,l=1,2,加工时间分别为,：,（,1,）,l=1,，,p,i1,和,p,i3,（,2,）,l=2,p,i1,+p,i2,和,p,i2,+p,i3,m=4,时，,l=1,，,2,，,3,，加工时间分别为：,（,1,）,l=1,p,i1,和,p,i4,（,2,）,l=2,，,p,i1,+p,i2,和,p,i3,+p,i4,（,3,）,l=3,，,p,i1,+p,i2,+p,i3,和,p,i2,+p,i3,+p,i4,45,l,A,加工时间,B,加工时间,1,t,1,t,m,2,t,1,+t,2,t,m-1,+t,m,3,t,1,+t,2,+t,3,t,m-2,+t,m-1,+t,m,m-1,t,1,+t,2,+,+t,m-1,t,2,+,+t,m-,1,+t,m,46,i,1,2,3,4,P,i1,1,2,6,3,P,i2,8,4,2,9,P,i3,4,5,8,2,i,1,2,3,4,l,=1,p,i1,1,2,6,3,p,i3,4,5,8,2,l,=2,p,i1,+p,i2,9,6,8,12,p,i2,+p,i3,12,9,10,11,47,i,1,2,3,4,l,=1,p,i1,1,2,6,3,p,i3,4,5,8,2,l,=2,p,i1,+p,i2,9,6,8,12,p,i2,+p,i3,12,9,10,11,当,l=1,时，按（,Johnson,）算法得到加工顺序（,1,，,2,，,3,，,4,）；,当,l=2,时，得到加工顺序（,2,，,3,，,1,，,4,）。,对于（,2,，,3,，,1,，,4,），相应的,Fmax=29,。,所以，取顺序（,1,，,2,，,3,，,4,）。,48,用,Palmer,法、关键工件法和,CDS,法求以下,4/4/P/F,max,问题的最优解，并比较三种方法的结果。,i,1,2,3,4,p,i1,1,9,5,4,p,i2,5,7,6,3,p,i3,4,6,3,5,p,i4,6,2,3,7,49,四、相同零件、不同移动方式下加工周期的计算,排序问题针对的是不同零件，如果,n,个零件相同，则没有排序问题。但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。,三种典型的移动方式,顺序移动方式,(,串行工程,),平行移动方式（平行工程）,平行顺序移动方式,50,（一）顺序移动方式,加工周期,时间,工序,1,2,3,4,顺序移动方式,一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。,51,设零件批量为,n,（件），工序数目为,m,，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为,T,（分钟），零件在,i,道工序的单件工时为,t,i,（分钟,/,件），,i=1.2,n,。,则该批零件的加工周期为：,已知,n=4,，,t1=10,分钟，,t2=5,分钟，,t3=15,分钟，,t4=10,分钟，则,T,顺,=4,（,10+5+15+10,）,=160,分钟,52,（二）平行移动方式,工序,1,2,3,4,时间,加工周期,每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。,53,零件平行移动的加工周期 为：,已知,n=4,，,t1=10,分钟，,t2=5,分钟，,t3=15,分钟，,t4=10,分钟，则,T,平,=,（,10+5+15+10,）,+,（,4-1,）,15=85,分钟,54,（三）平行顺序移动方式,既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。,时间,工序,1,2,3,4,加工 周期,（,1,）当,t,i,t,i+1,时，零件按平行移动方式转移；,（,2,）当,t,i,t,i+1,时，以,i,工序最后一个零件的完工时间为基准，往前推移（,n-1,）,t,i+1,作为零件在（,i+1,）工序的开始时间。,55,具体做法,（,1,）当,t,i,t,i+1,时，零件按平行移动方式转移；,（,2,）当,t,i,t,i+1,时，以,i,工序最后一个零件的完工时间为基准，往前推移（,n-1,）,t,i+1,作为零件在（,i+1,）工序的开始时间。,56,平行顺序移动加工周期计算,已知,n=4,，,t,1,=10,分钟，,t,2,=5,分钟，,t,3,=15,分钟，,t,4,=10,分钟，则,T,平顺,=4,（,10+5+15+10,）,-,（,4-1,）,（,5+5+10,）,=100,分钟,57,例,已知,n=4,，,t,1,=10,分钟，,t,2,=5,分钟，,t,3,=15,分钟，,t,4,=10,分钟。求三种移动方式下的加工周期。,解：,T,顺,=4,（,10+5+15+10,）,=160,分钟,T,平,=,（,10+5+15+10,）,+,（,4-1,）,15=85,分钟,T,平顺,=4,（,10+5+15+10,）,-,（,4-1,）,（,5+5+10,）,=100,分钟,58,比较项目,平行移动,平行顺序移动,顺序移动,生产周期,短,中,长,运输次数,多,中,少,设备利用,差,好,好,组织管理,中,复杂,简单,零件三种移动方式的比较,59,已知,m=5,n=4,t,1,=10,t,2,=4,t,3,=8,t,4,=12,t,5,=6,分别求在顺序移动、平行移动和平行顺序移动方式下，这批零件的加工周期。,60,第三节 单件作业排序问题,11.3.1,指派问题,11.3.2,单件作业排序问题的描述,11.3.3,两种作业计划的构成,11.3.4,求解一般,n/m/G/Fmax,问题的启发式方法,61,1,、指派问题的形式表述,给定了一系列所要完成的任务（,tasks,）以及一系列完成任务的被指派者（,assignees,），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务,2,、指派问题的假设,被指派者的数量和任务的数量是,相同的,每一个被指派者只完成,一项任务,每一项任务只能由,一,个被指派者,来完成,每个被指派者和每项任务的组合有一个相关成本,目标是要确定怎样进行指派才能使得总成本最小,11.3.1,指派问题,62,设,n,个人被分配去做,n,件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第,i,个人去做第,j,件工作的的效率为,C,ij,(,i,=1.2,n,;,j,=1.2,n,),并假设,C,ij,0,。问应如何分配才能使总效率（时间或费用）最高？,3,、指派问题模型,（,The Model for Assignment Problem,）,63,典型问题,例,1,：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。,64,问：如何分配，能使所需的总时间最少？,甲 乙 丙 丁,工作,人,译英文,译日文,译德文,译俄文,2 10 9 7,15 4 14 8,13 14 16 11,4 15 13 9,65,建立模型,设,x,ij,=,1,0,若第,i,项工作交与第,j,个人完成,若第,i,项工作不交与第,j,个人完成,译英文：,x,11,+x,12,+x,13,+x,14,=1,译日文：,x,21,+x,22,+x,23,+x,24,=1,译德文：,x,31,+x,32,+x,33,+x,34,=1,译俄文：,x,41,+x,42,+x,43,+x,44,=1,甲：,x,11,+x,21,+x,31,+x,41,=1,乙：,x,12,+x,22,+x,32,+x,42,=1,丙：,x,13,+x,23,+x,33,+x,43,=1,丁：,x,14,+x,24,+x,34,+x,44,=1,x,ij,=0,或,1 (i=1,2,3,4;j=1,2,3,4),甲 乙 丙 丁,工作,人,译英文,译日文,译德文,译俄文,2 10 9 7,15 4 14 8,13 14 16 11,4 15 13 9,66,4,、指派问题的匈牙利解法,67,2,4,9,7,第,1,步：变换指派问题的系数矩阵（,c,ij,），使各行各列中都出现,0,元素,(1),从（,c,ij,）的每行元素都减去该行的最小元素；,(2),再从所得新系数矩阵无零元素的列中减去该列的最小元素。,4,2,68,在变化后的效率矩阵中找尽可能多的独立,0,元素，若能找出,n,个独立,0,元素，就以这,n,个独立,0,元素对应解矩阵,(,x,ij,),中的元素为,1,，其余为,0,，这就得到最优解。,第,2,步：进行试指派，即确定独立零元素,（,1,）从有唯一的零元素的行或列开始确定独立零元素，并用 表示，并划掉其所在行或列的其他零。直到尽可能多的零元素都被圈出和划掉为止。,0,（,2,）若,独立零元素,的数目,m,等于矩阵的阶数,n,，那么这指派问题的最优解已得到。若,m,n,则转入下一步。,69,70,例,2,有甲、乙、丙、丁四个工人，要分别派他们完成四项不同的任务，分别记作,A,、,B,、,C,、,D,。他们完成各项任务所需时间如下表所示，问如何分派任务，可使总时间最少？,任务,人员,A,B,C,D,甲,6,7,11,2,乙,4,5,9,8,丙,3,1,10,4,丁,5,9,8,2,71,第,1,步，变换系数矩阵：,-,5,第,2,步，确定独立零元素,找到,3,个独立零元素，但,m=3 n=4,求解过程如下,第,3,步，作最少的直线覆盖所有零元素：,(1),对没有独立零元素的行打号；,(2),对已打号的行中所有含划掉零元素的列打号；,(3),再对打有号的列中含独立零元素的行打号；,72,(4),重复,(2),，,(3),直到得不出新的打号的行、列为止；,(5),对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有零元素的最少直线数,73,第,4,步：在没有被直线覆盖的所有元素中找出最小元素，然后将所在行,（或列）,都减去这最小元素；,在出现负数的列,（或行）,都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第,2,步。,74,-,5,75,11.3.2,问题的描述,加工描述矩阵,D,为,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,对于一般单件作业排序问题，每个工件都有其独特的加工路线，工件没有一定的流向。,要描述一道工序，需要用三个参数：,3,个参数：,i,，,j,和,k,。,i,表示工件代号，,j,表示工序号，,k,表示完成工序,i,的第,j,道工序的机器代号。,（,i,，,j,，,k,）表示工件,i,的第,j,道工序在机器,k,上进行。,76,11.3.3,两种作业计划的构成,各工序都按最早可能完工时间安排的作业计划称为能动作业计划。,各工序都按最早可能开始时间安排的作业计划称为无延迟作业计划。,无延迟作业计划是没有任何延迟出现的能动作业计划。,77,符号说明,每安排一道工序称为一,“,步,”,S,t,:t,步之前已排序工序构成的部分作业计划；,O,t,:t,步可排序工序的集合；,T,k,为,O,t,中工序,O,k,的最早可能开始时间；,T,k,为,O,t,中工序,O,k,的最早可能完成时间。,78,（一）能动作业计划的构成步骤,（,1,）设,t=1,S,1,为空集，,O,1,为各工件第一道工序的集合。,（,2,）求,T,*,=minT,k,并求出,T,*,所出现的机器,M,*,。,如果,M,*,有多台，则任选一台。,（,3,）从,O,t,中选出满足以下两个条件的工序,O,j,：需要,M,*,加工，且,T,j,T,*,。,（,4,）将选定的工序,O,j,放入,S,t,从,O,t,中消去,O,j,并将,O,j,的紧后工序放入,O,t,，使,t=t+1.,（,5,）若还有未安排的工序，转步骤（,2,）；否则，停止。,79,例 有一个,2/3/G/Fmax,问题，其加工描述矩阵,D,和加工时间矩阵,T,分别为：,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,1 2,3,2,T=,2 4 1,3 4 5,试构成一个能动作业计划。,80,能动作业计划的构成,2,3,2,M,2,13,13,8,2,3,2,6,1,3,2,M,2,8,8,12,7,7,1,3,2,2,3,2,5,2,2,1,M,1,7,8,7,7,3,1,3,2,2,2,1,4,1,2,3,M,3,7,7,7,3,3,1,2,3,2,2,1,3,2,1,3,M,3,3,6,3,2,0,1,2,3,2,1,3,2,1,1,1,M,1,2,2,3,0,0,1,1,1,2,1,3,1,O,j,M*,T*,T,k,T,k,O,t,t,81,能动作业计划的甘特图,2,3,2,1,1,1 2,2,1,1,3,2,2,1,3 1,2,3,3 7,7 8 13,2 3 7,0,时间,机器,M,1,M,2,M,3,82,（二）无延迟作业计划构成步骤,（,1,）设,t=1,S,1,为空集，,O,1,为各工件第一道工序的集合。,（,2,）求,T,*,=min,T,k,并求出,T,*,所出现的机器,M,*,。,如果,M,*,有多台，则任选一台。,（,3,）从,O,t,中选出满足以下两个条件的工序,Oj,：需要,M,*,加工，且,T,j,=,T,*,。,（,4,）将选定的工序,O,j,放入,S,t,从,O,t,中消去,O,j,并将,O,j,的紧后工序放入,O,t,，使,t=t+1,。,（,5,）若还有未安排的工序，转步骤（,2,）；否则，停止。,83,无延迟作业计划的构成,1,3,2,M,2,12,13,12,1,3,2,6,2,3,2,M,2,M,2,7,7,8,12,7,7,1,3,2,2,3,2,5,2,2,1,M,1,3,8,7,7,3,1,3,2,2,2,1,4,1,2,3,M,3,M,1,3,3,7,7,3,3,1,2,3,2,2,1,3,2,1,3,M,3,0,6,3,2,0,1,2,3,2,1,3,2,1,1,1,M,1,M,3,0,0,2,3,0,0,1,1,1,2,1,3,1,O,j,M*,T*,T,k,T,k,O,t,t,84,无延迟作业计划的甘特图,2,3,2,1,1,1 2,2,1,2,1,3 1,2,3,3 7,7 12 13,2 3 7,0,时间,机器,M,1,M,2,M,3,1,3,2,85,能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。,一般能动作业计划和无延迟作业计划都有多个。,一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,86,练 习,1.,南希汽车座椅罩和喷漆工厂正在竞标一份为爱得旧车交易所提供全部客户服务的合同。取得合同的主要要求是快速交货。爱得说，如果南希厂可以在,24,小时内将爱得收到的,5,辆车全部整修并且重新喷漆，合同就归该厂。下面是这,5,辆车在整修和喷漆车间各自需要的时间。假定车子在重新喷漆前要经过重新整修的步骤，南希厂可以满足时间要求并且得到合同吗？,汽车,整修时间（小时）,重新喷漆时间（小时）,A,6,3,B,0,4,C,5,2,D,8,6,E,2,1,87,2.,有一个,2/3/G/Fmax,问题，其加工描述矩阵,D,和加工时间矩阵,T,分别为：,试构成一个能动作业计划和无延迟作业计划。,D=,1,1,1 1,2,3 1,3,2,2,1,3 2,2,2 2,3,1,T=,3 5 2,2 4 3,88,4,，,1,，,2,M2,0,6,0,4,，,1,，,2,0,4,0,3,，,1,，,1,11,8,2,，,2,，,1,12,5,1,，,2,，,2,3,0,6,0,4,，,1,，,2,0,4,0,3,，,1,，,1,11,8,2,，,2,，,1,1,，,1,，,1,M1,0,5,0,1,，,1,，,1,2,0,6,0,4,，,1,，,2,0,4,0,3,，,1,，,1,2,，,1,，,3,M3,0,8,0,2,，,1,，,3,0,5,0,1,，,1,，,1,1,O,j,M*,T*,T,k,Tk,Ot,t,89,16,9,4,，,3,，,1,13,9,3,，,2,，,4,12,9,2,，,2,，,1,1,，,2,，,2,M2,6,13,6,1,，,2,，,2,6,4,，,2,，,4,M4,6,8,6,4,，,2,，,4,13,9,3,，,2,，,4,12,9,2,，,2,，,1,6,13,6,1,，,2,，,2,5,8,6,4,，,2,，,4,3,，,1,，,1,M1,5,9,5,3,，,1,，,1,11,8,2,，,2,，,1,13,6,1,，,2,，,2,4,O,j,M*,T*,T,k,Tk,Ot,t,90,4,，,3,，,1,M1,12,19,12,4,，,3,，,1,18,13,3,，,3,，,3,17,13,2,，,3,，,4,19,13,1,，,3,，,3,9,19,12,4,，,3,，,1,3,，,2,，,4,M4,9,13,9,3,，,2,，,4,16,12,2,，,3,，,4,19,13,1,，,3,，,3,8,9,16,9,4,，,3,，,1,9,13,9,3,，,2,，,4,2,，,2,，,1,M1,9,12,9,2,，,2,，,1,19,13,1,，,3,，,3,7,O,j,M*,T*,T,k,Tk,Ot,t,91,22,19,4,，,4,，,3,18,19,18,3,，,4,，,2,18,27,18,2,，,4,，,3,1,，,3,，,3,M3,18,24,18,1,，,3,，,3,12,22,19,4,，,4,，,3,3,，,3,，,3,M3,13,18,13,3,，,3,，,3,26,17,2,，,4,，,3,13,19,13,1,，,3,，,3,11,22,19,4,，,4,，,3,13,18,13,3,，,3,，,3,2,，,3,，,4,M4,13,17,