第10章作业排序与生产作业计划

2019/10/41第十章作业排序与生产作业计划第一节作业排序的基本概念第二节流水作业排序问题第三节单件作业排序问题第四节多台设备作业排序引言在确定了各车间的零部件投入、出产计划、将全厂的生产计划变成了各车间的生产任务后,各车间还应将零部件的投入、出产计划变成车间的作业计划，即将车间的生产任务变成各工段、班组、各工作地的生产任务。编制车间生产作业计划，应该解决工件加工顺序问题。这就是我们要讨论的作业排序问题。采用排序理论与方法，可以得出工件加工的最优或令人满意的顺序。第一节作业排序的基本概念一、编制生产作业计划与排序的关系编制生产作业计划与作业排序不同，排序只是确定工件在机器上的加工顺序，可以用一组工件的代号的排列来表示这组工件的加工顺序，而编制生产作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。所以，只有生产作业计划才能指导工人的生产活动。在编制生产作业计划时常常出现一个工件在某道工序加工完之后，加工它的下一道工序的机器还在加工前一个工件，这时该工件不得不等待一段时间才能开始在下一道工序的机器上加工。这种情况称为“工件等待”。当某台机器已加工完一个工件，而下一个工件尚未到达。这种情况称为“机器空闲”。第一节作业排序的基本概念由于编制生产作业计划的主要问题是确定各台机器上工件的加工顺序，并且一般都是按最早可能开工时间或最早可能完工时间来编制生产作业计划。所以，当工件的加工按一定的时间确定了加工顺序后，作业计划也就确定了。这就造成了人们通常不加区别的使用“排序”与“编制作业计划”两个术语。第一节作业排序的基本概念2019/10/45几个名词术语•排序——工件在机器上的加工顺序•派工——将生产任务安排到具体机床上加工—调度范围；•赶工——实际进度落后于计划进度时采取的行动—调度范围；•调度——发现实际进度落后于计划进度时而采取的调配资源的行动。•机器——服务者•工件——服务对象•加工路线——工件加工的工艺过程•工序——加工路线上的每一个具体工作地（机器）。1.一个工件不能同时在几台不同的机器上被加工。2.采取平行移动方式移送被加工的工件。3.不允许中断。当一个工件一旦开始加工,必须一直进行到完工,不得中途停止插入其它工件。4.工件在每道工序的加工只在一台机器上进行。5.工件数（或批量）、机器数已知，单件加工时间已知,完成加工的时间与加工顺序无关。6.每台机器同时只能加工一个工件。第一节作业排序的基本概念二、假设条件与符号说明为了便于采用数学模型来分析研究排序问题，做下列假设：2019/10/47第一节作业排序的基本概念符号说明Wi=∑mj=1Wij•Ji——第i工件，i=1,2,…,n；•Mj——第j台机器，j=1,2,…,m；(i,j,k)——Ji的第j道工序在Mk上进行；Pi=∑mj=1PijPij——Ji在Mj上的加工时间，Ji加工完的总加工时间；ri——Ji到达工序时间，即可以开始加工的最早时间；di——Ji的完工期限；ai——Ji在车间允许停留的时间（Ji进入车间到完工时刻之间的时间间隔：ai=di－ri）；Wij——Ji在第j道工序前的等待时间，Ji总的等待时间：Ci=ri+∑(Pij+Wij)=ri+Pi+WiLi=Ci－di=ri+Pi+Wi－di=(Pi+Wi)－(di－ri)=Fi－aiFi=Ci－ri=Pi+Wi;第一节作业排序的基本概念Ci——Ji的完工时间•Cmax——最长完工时间,Cmax=max{Ci},即一批工件中的最长完工时间;•Fi——Ji的流程时间,即工件在车间的实际停留时间,Fmax——最长流程时间,Fmax=max{Fi},即一批工件中的最长流程时间;Li——Ji工件的延迟时间，第一节作业排序的基本概念当Li0时为正延迟,即Ji的实际完工时间超过了完工期限;当Li0时为负延迟,即Ji提前完工;当Li=0时为零延迟,即Ji按期完工。Lmax——最长延迟时间,Lmax=max{Li}.即在一批工件中找出的最大延迟时间.三、排序问题的分类和表示法排序问题常见的分类方法有按机器、工件、目标函数的特征分类。1.按机器的种类和数量不同,可以分成单台机器的排序问题多台机器的排序问题对于多台机器的排序问题,按工件加工路线的特征,单件作业排序问题——加工路线不同流水作业排序问题——加工路线相同可以分成第一节作业排序的基本概念2.按工件到达车间的情况不同,可以分成静态的排序问题——排序时所有工件都已到达,可以一次对它们进行排序.动态的排序问题——排序时工件陆续到达,要随时安排它们的加工顺序3.按目标函数的性质不同,也可划分不同的排序问题单台机器的排序使平均流程时间最短使误期完工工件数最少……多台机器的排序：不同目标排序问题单目标排序问题：以往研究的对象多目标排序问题：很少有人研究第一节作业排序的基本概念4.另外，按参数的性质，可以划分为确定型排序问题——指加工时间和有关参数是已知确定的量随机型排序问题——加工时间和有关参数为随机变量这两种排序问题的解法本质上不同。现只讨论几种有代表性的排序问题。第一节作业排序的基本概念通常采用Conway等人提出的排序方法。这个方法主要涉及到4个参数，只用4个参数就可以表示大多数不同的排序问题。这4个参数通常表示为：n/m/A/B。n为工件数；m为机器数B为目标函数,通常是使其值最小A为车间类型，通常有以下几种情况，在A的位置：(1)若标以F,则代表流水作业排序问题(2)若标以“P”,则表示流水作业排列排序问题，也常被称为“同顺序”排序问题(3)若标以“G”,则表示一般单件作业排序问题。第一节作业排序的基本概念当m=1时，A处为空白。因为对于单台机器的排序问题来说，不存在所谓的加工路线问题，当然也就谈不到是流水作业排序问题还是单件作业的排序问题了。通过n/m/A/B这4个符号，就可以简捷的表述一般的排序问题了。例如，n/3/P/Cmax表示n个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间最短。第一节作业排序的基本概念2019/10/415第十章作业排序与生产作业计划回顾•排序问题常见的分类方法有按机器、工件、目标函数的特征分类。•排序问题由4个参数表示：n/m/A/B。•n为工件数；m为机器数•B为目标函数,通常是使其值最小•A为车间类型，通常有以下几种情况，在A的位置：(1)若标以“F”,则代表流水作业排序问题。(2)若标以“P”,则表示流水作业排列排序问题，也常被称为“同顺序”排序问题。(3)若标以“G”,则表示一般单件作业排序问题。•Cmax——最长完工时间；Fmax——最长流程时间；Lmax——最长延迟时间。Lmax=max{Li}.即在一批工件中找出的最大延迟时间。当Li0时为正延迟,即Ji的实际完工时间超过了完工期限;当Li0时为负延迟,即Ji提前完工;当Li=0时为零延迟,即Ji按期完工。例如：n/3/P/Cmax表示n个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间最短。流水作业排序问题的基本特征是每个工件的加工路线都一致。在流水生产线上制造不同的零件,遇到的就是流水作业排序问题。我们说加工路线一致,是指工件的流向一致,并不要求每个工件必须经过加工路线上每台机器加工。如果某些工件不经某些机器加工,则设相应的加工时间为零。一般说来,对于流水作业排序问题,工件在不同机器上的加工顺序不尽一致。但本节要讨论的是一种特殊情况,即所有工件在各台机器上的加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作同顺序排序问题。对于一般情形,排列排序问题的最优解不一定是相应的流水作业排序问题的最优解,但一般是比较好的解;对于仅有2台和3台机器的特殊情况,可以证明,排列排序问题下的最优解一定是相应流水作业排序问题的最优解。本节只讨论排列排序问题。但对于2台机器的排序问题,实际上不只是排列排序问题，因为两者的最优解及其解法是相同的。第二节流水作业排序问题一、最长流程时间Fmax的计算最长流程时间就是工件在车间实际停留的最长时间。本节所讨论的是n/m/ρ/Fmax问题,目标函数是使最长流程时间最短。最长流程时间又称作加工周期,它是从第一个工件在第一台机器开始加工时算起,到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(r=0，i=1,2,…,n),所以Fmax等于排在末位加工的工件在车间的停留时间,也等于一批工件的最长完工时间Cmax。第二节流水作业排序问题设n个工件的加工顺序为S=(S1,S2,…,Sn),其中Si为排第i位加工的工件的代号。以Ck(si)表示工件Si在机器Mk上的完工时间,Psik表示工件Si在Mk上的加工时间,k=1,2,…,m；i=1,2,…,n则Ck(si)可按以下公式计算:C1(si)=C1(si-1)+Psi1Ck(si)=max{Ck-1(si),Ck(si-1)}+Psik(11—1)第二节流水作业排序问题显然，当ri=0时，Fmax=Cm(sn)在知道了上述计算Fmax公式后，便可直接在工件加工的时间矩阵上从左向右计算完工时间。第二节流水作业排序问题例11.1有一个6/4/p/Fmax问题,其加工时间如下表所示。当按顺序S=(6,1,5,2,4,3)加工时,求Fmax表11-1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi44243312019/10/420i615243Pi1244213Pi2544576Pi3555857Pi4143234表11-2顺序S下的加工时间矩阵261012131671115202733121722303542132125323846Fmax=46Johnson算法:(1)从加工时间矩阵中找出最短的加工时间。(2)若最短的加工时间出现在M1上,则对应的工件尽可能往前排；若最短加工时间出现在M2上，则对应工件尽可能往后排。然后,从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个,则任挑一个往前排。(3)若所有工件都已排序,停止.否则,转步骤(1).第二节流水作业排序问题二、n/2/F/Fmax问题的最优算法第二节流水作业排序问题二、n/2/F/Fmax问题的最优算法例11.2求表1１-３所示的6/２/Ｆ/Fmax问题的最优解。i１２３４５６ai５１８５３４bi８２２４７４表11-3加工时间矩阵5614192226131517233034Fmax0(1,2,3,4,5,6)=342019/10/423i１２３４５６ai５１８５３４bi８２２４７４表11-4改进算法见教材303页Johnson改进算法：１.将所有ai≤bi的工件按ai值不减的顺序排成一个列Ａ；２.将所有ai＞bi的工件按bi值不增的顺序排成一个列Ｂ；３.将Ａ放到Ｂ之前，就构成了最优加工顺序．(1)(2)(3)(4)A=(2,5,6,1)(5)(6)B=(4,3)S=(2,5,6,1,4,3)i２５６１４３ai１３４５５８bi２７４８４２14813182631115232729Fmax*(2,5,6,1,4,3)=29当我们从应用Johnson法则求得的最优顺序中任意去掉一些工件时,余下的工件仍构成最优顺序。如对例11.2的最优顺序(2,5,6,1,4,3),若去掉一些工件,得到的顺序(5,6,1,4,3)、(2,6,4,3)、(2,6,1,4)等仍为余下工件的最优顺序。但是,工件的加工顺序不能颠倒,否则不一定是最优顺序。同时,我们还要指出,Johnson法则只是一个充分条件,不是必要条件。不符合这个法则的加工顺序,也可能是最优顺序。对例11.2顺序(2,5,6,4,1,3)不符合Johnson法则,但它也是一个最优顺序。第二节流水作业排序问题2019/10/425例11.2顺序(2,5,6,4,1,3)i２５６４１３ai１３４５５８bi２７４４８２31481318261115192729Fmax*(2,5,6,4,1,3)=29第二节流水作业排序问题三