运营管理第11章制造业作业计划与控制

流水作业排序问题单件作业排序问题重点内容排序问题的基本概念流水作业排序问题单件作业排序问题生产作业控制第11章制造业作业计划与控制生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化，是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。生产作业计划的内容作业计划与控制的关系作业计划：给生产活动制定详细时间表生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。第一节排序问题的基本概念一、名词术语生产管理“（编制）作业计划”（Scheduling）“排序”（Sequencing）“派工”（Dispatching）“控制”（Controlling）“赶工”（Expediting）排序工件在机器上的加工顺序（编制）作业计划工件的加工顺序加工工件的开始时间加工工件的完成时间作业计划的主要问题是确定各台机器上工件的加工顺序通常情况下都是按最早可能开（完）工时间来编排作业计划的当工件的加工顺序确定之后，作业计划也就确定了派工赶工属于“调度”范围“编制作业计划”加工制造发生之前的活动“调度”是在加工制造发生之后的活动，是发现实生产进度已经偏离预定计划而采取的调配资源的行动调度的依据是作业计划描述排序问题的术语“机器”“工件”“工序”“加工时间”n个工件经过m台机器加工“加工路线”工件加工的工艺过程决定一般用M1，M2，…来表示“加工顺序”每台机器加工n个工件的先后顺序排序问题的复杂性确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪。如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。二、假设条件与符号说明假设条件l.一个工件不能同时在几台不同的机器上加工2.工件在加工过程中采取平行移动方式3.不允许中断4.每道工序只在一台机器上完成5.工件数、机器数和加工时间已知，加工时间与加工顺序无关6.每台机器同时只能加工一个工件符号Ji——工件i，i=1，2，…，nMj——机器j，j=1，2，…，mPij——Ji在Mj上的加工时间，Ji的总加工时间为Pi=∑pijri——Ji的到达时间，指Ji从外部进入车间，可以开始加工的最早时间di——Ji的完工期限Ci——Ji的完工时间，Ci＝ri+∑(wij+pij)=ri+Wi+PiCmax——最长完工时间，Cmax=max｛Ci｝符号Fi——Ji的流程时间，即工件在车间的实际停留时间，Fi＝Ci-ri=Wi+PiFmax——最长流程时间，Fmax=max｛Fi｝Li——工件的延迟时间Wij——Ji在Mj上加工之前的等待时间Wi——Ji在加工过程中总的等待时间ai——Ji的允许停留时间符号Li=Ci-di=ri+Pi+Wi-di=(Pi+Wi)-(di-ri)=Fi-ai当Li＞0（正延迟），说明Ji的实际完工时间超过了完工期限当Li＜0（负延迟），说明Ji提前完工当Li=0（零延迟），Ji按期完工Lmax——最长延迟时间，Lmax=max｛Li｝三、排序问题的分类和表示法分类方法机器工件目标函数机器单台机器的排序问题多台机器的排序问题工件加工路线单件作业（Job-Shop）排序问题流水作业（Flow-shop）排序问题单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。流水车间排序问题的基本特征：•每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。•不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。静态的排序问题动态的排序问题单目标排序问题多目标排序问题确定型排序问题随机型排序问题Conway表示方法4参数表示法n／m／A／Bn工件数m机器数A车间类型F代表流水作业排序问题P表示流水作业排列排序问题G表示一般单件作业排序问题m＝1A空白B目标函数第二节流水作业排序问题基本特征工件的加工路线都一致工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致流水作业排列排序问题“同顺序”排序问题所有工件在各台机器上的加工顺序都相同排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解对于仅有2台和3台机器的特殊情况，排列排序问题下的最优解一定是相应流水作业排序问题的最优解一、最长流程时间Fmax的计算n／m／P／Fmax目标函数——最长流程时间最短最长流程时间——加工周期从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间Fmax等于排在末位的工件在车间的停留时间，等于一批工件的最长完工时间Cmax设n个工件的加工顺序为S=（S1，S2，…，Sn）Si排第i位加工的工件的代号表示工件Si在机器Mk上的完工时间iSkCkips表示工件Si在Mk上的加工时间k=1，2，…，mi=1，2，…，niSkC按以下公式计算1111ipsCCiSiSkikkkpsCCCkiSiSiS1,max1(11.1)k=1,2,…,m;i=1,2,…,n当ri=0，i=1,2,…,n时Fmax=nSmC例11.1有一个6／4／P／Fmax问题，其加工时间如表11－1所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。i123456pi1423142pi2456745pi3587555pi4424331表11-l加工时间矩阵i615243pi12246410212113316pi257411415520727633pi3512517522830535742pi4113421325232338446表11－2顺序S下的加工时间矩阵二、n/2/F/Fmax问题的最优算法n项任务在两台机器的排序问题SchedulingnJobsonTwoMachinesn个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器2两台机器排序问题的目标•两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。Fmax的含义见如下的甘特图(GanttChart)。•多台机器排序的目标一般也是使最大完成时间（总加工周期）Fmax最短。Fmax时间机器AB在机器A上的作业时间总加工周期•1954年Johnson提出•用ai表示Ji在M1上的加工时间，用bi表示Ji在M2上的加工时间。每个工件都按M1M2的路线加工。Johnson指出，若min(ai,bj)min(aj,bi),则Ji应排在Jj之前。•按上关系式可以确定每两个工件的相对位置，从而可以得到n个工件的完整的顺序•Johnson算法：–从加工时间矩阵中找出最短的加工时间–若它出现在M1上，则其对应的工件应尽可能往前排；若它出现在M2上，则其对应的工件应尽可能往后排–划去已排序工件并重复上述步骤直至排完例11.2求表11-3所示的6/2/F/Fmax问题的最优解i123456ai518534bi722474表11-3加工时间矩阵将工件2排第1位2将工件3排第6位23将工件5排第2位253将工件6排第3位2563将工件4排第5位25643将工件1排第4位256143最优加工顺序为S=（2，5，6，l，4，3）最优顺序下的Fmax=28Johnson法则2①将所有ai≤bi的工件按ai值不减的顺序排成一个序列A②将所有ai＞bi的工件按bi值不增的顺序排成一个序列B③将A放到B之前，就构成了最优加工顺序i123456ai518534bi722474i256143ai134558bi274742序列A为（2，5，6，1）序列B为（4，3）最优顺序为（2，5，6，l；4，3）应用Johnson法则求得的最优顺序中任意去掉一些工件时，余下的工件仍构成最优顺序Johnson法则只是一个充分条件，不是必要条件不符合这个法则的加工顺序，也可能是最优顺序两台机器排序问题算法的扩展(ExtensiontoThreeMachines)一般情况下当机器数为3台以上时，就很难找到最优解了但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以采用Johnson’sLaw解决问题。设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题：minAi=maxBiorminCi=maxBi定义：A’i=Ai+Bi,B’i=Bi+Ci例:考虑以下问题.5个工件由3台机器加工,作业时间见下表.求:总加工周期最短的作业顺序。12345机器A44913821627532机器B59619223330436机器C81710296357421153解:检查上表,发现:minAi=4maxBi=6minCi=6因此,满足以上条件,建立两台机器的作业时间表:12345机器A’9151099机器B’13168101514523机器A44610515924832机器B59313419630234机器C81772411351045651应用Johnson法则，得出：１－４－５－２－３总加工周期为：三、n/m/P/Fmax问题的启发式算法对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法对于一般的流水车间排列排序问题分支定界法启发式算法求一般n／m／P／Fmax问题近优解（Nearoptimalsolution）的启发式算法（一）Palmer法按斜度指标排列工件的启发式算法工件斜度指标mkikipmk121k=1,2,…,nm为机器数；pik为工件i在Mk上的加工时间按照各工件不增的顺序排列工件，可得出令人满意的顺序i(11.4)例11.3有一个4／3／F／Fmax问题，其加工时间如表11－5所示，用Palmer法求解i1234pi11263pi28429pi34582表11—5加工时间矩阵解：对于本例，式（11－4）变成mkikipmk121k=1,2,3=-pk1+pk3i1234=-p11+p13=-1+4=3=-p21+p23=-2+5=3=-p31+p33=-6+8=2=-p41+p43=-3+2=-1i按不增的顺序排列工件，得到加工顺序（l,2,3,4）和（2,l,3,4）这两个顺序都是最优顺序Fmax＝28（二）关键工件法步骤（1）计算每个工件的总加工时间Pi=∑pij，找出加工时间最长的工件C（j=m），将其作为关键工件。（2）对于余下的工件，若pi1≤pim，则按pi1不减的顺序排成一个序列Sa；若pi1＞pim，则按pim不增的顺序排列成一个序列Sb。（3）顺序（Sa，C，Sb）即为所求顺序。i1234pi11263pi28429pi34582pi13111614表11-6用关键工件法求解总加工时间最长的为3号工件（三）CDS法把Johnson算法用于一般的n／m／P／Fmax问题，得到（m-1）个加工顺序，取其中优者。具体做法lkikp1mlmkikp1按和合并组成新的“机器”l=1,2,…,m-1合并(m-1)次，得到(m-1)个n/2/F/Fmax问题用Johnson算法求（m-1）次加工顺序，取其中最好的结果加工顺序A加工