第4讲 制造业作业计划与控制

1生产运作管理Production&OperationsManagement青岛理工大学（临沂）冯海侠2016年5月2第4章制造业作业计划与控制SchedulingandControllingforManufacturing4.1作业计划问题的基本概念4.2流水车间作业计划问题4.3单件车间作业计划问题4.4生产作业控制34.1作业计划问题的基本概念4.1.1生产作业计划概述4.1.2有关的名词术语4.1.3假设条件与符号说明4.1.4排序问题的分类和表示法44.1.1生产作业计划概述生产作业计划是企业年度生产计划和MRP输出的具体执行计划。它根据年度生产计划的要求对每个生产单位（车间、工段、班组），在每个具体的时期（月、旬、周、日、轮班、小时等）内的生产任务作出详细的安排并规定实现的方法，从而保证企业按数量、品种、质量、交货期的要求全面完成生产计划。5生产作业计划的内容生产作业计划的主要任务是将主生产计划或MRP中零部件的投入出产计划细化，他是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。6生产作业计划工作由作业计划编制与作业计划控制两部分组成。作业计划编制：包括制定期量标准、开展生产运作能力核算与平衡、编制各种形式的生产作业计划等。作业计划控制包括生产运作调度、生产运作作业统计与分析等内容。7生产作业计划的作用保证主生产计划规定的生产运作任务的完成。保证企业获取更好的经济效益。84.1.2有关的名词术语排序：就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。派工：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人。赶工：是在实际进度已经落后于计划进度时采取的行动。调度：是作业计划编制以后，实行生产控制的一切行动。94.1.2有关的名词术语（续）“机器”，表示“服务者”.可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题104.1.3假设条件与符号说明假设条件①一个零件不能同时在几台不同的机器上加工。②零件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。③不允许中断。当一个零件一旦开始加工，必须一直进行到完工，不得中途停止插入其它零件。④每道工序只在一台机器上完成。⑤零件数、机器数和加工时间已知。⑥每台机器同时只能加工一个零件。114.1.3假设条件与符号说明（续）Ji─零件i，i＝1,2,…,n。Mj─机器j，j＝1,2,…,m。pij一Ji在Mj上的加工时间，Ji的总加工时间为Pi＝∑pijri一Ji的到达时间，指Ji从外部进入车间，可以开始加工的最早时间。di一Ji的完工期限。Ci一Ji的完工时间,Ci＝ri＋∑(wij+pij)=ri+Wi+Pi.Cmax─最长完工时间,Cmax＝max{Ci}.12Fi一Ji的流程时间，即零件在车间的实际停留时间,Fi＝Ci-ri＝Wi+Pi.Fmax─最长流程时间，Fmax＝max{Fi}.Li─零件的延迟时间Li=Ci-di当Li＞0(正延迟)，说明Ji的实际完工时间超过了完工期限；当Li＜0(负延迟)，说明Ji提前完工；当Li＝0(零延迟)，Ji按期完工。Lmax─最长延迟时间，Lmax＝max{Li}.4.1.3假设条件与符号说明（续）134.1.4排序问题的分类和表示法按机器单机排序问题和多机排序问题多机：单件作业排序与流水作业排序按工件到达情况静态和动态按目标函数单目标排序问题和多目标排序问题14按参数的性质确定型排序问题（加工时间和其他有关参数是已知的确定量）随机型排序问题（加工时间和有关参数为随机变量）四参数表示法（康韦（Conway））：n/m/A/B其中，n为零件数，m为机器数，A为车间类型，若标以F，则代表流水作业排序问题，若标以P，则代表流水作业排列排序问题，若标以G，则表示一般单件作业排序问题。B为目标函数，通常是使其值最小。例如：n/3/P/Cmax表示n个零件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间Cmax最短。154.2流水作业排序问题流水车间(Flowshop):工件的加工路线都一致，典型的如流水线4.2.1加工周期的计算4.2.2两台机器排序问题的最优算法4.2.3一般n/m/p/Fmax排序问题的启发式算法4.2.4相同零件、不同移动方式下加工周期WorkCenter#1WorkCenter#2Output16n个不同的零件要按相同的加工路线经过m台机器加工，目标是使这批零件的加工周期最短----n/m/P/Fmax加工周期又称为最长流程时间，它是从第一个零件在第一台机器开始加工时起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。假设所有零件的到达时间都为零（ri=0,i=1,2,…,n)，则Fmax等于排在末位加工的零件在车间的停留时间，也等于一批零件的最长完工时间Cmax4.2.1加工周期的计算17设n个零件的加工顺序为S=（S1，S2，…,Sn），其中Si为排第i位加工的零件的代号。以CkSi表示零件Si在机器Mk上的完工时间，PSik表示零件Si在Mk上的加工时间，k=1,2,…,m;i=1,2,…,n,则CkSi可按以下公式计算C1Si=C1Si-1+PSi1CkSi=maxC(k-1)Si,CkSi-1+PSikk=2,3,…,m;i=1,2,…,nCmSn,即为最长流程时间Fmax184.2.1加工周期的计算工件代号i123456Pi1464583Pi2353971Pi3792658Pi4549623有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（1,4,6,3,5,2）加工时，求Fmax194.2.1加工周期的计算工件代号i146352Pi1453486Pi2391375Pi3768259Pi456392449121624307181922313614243234394819303544465220对于n个零件经过两台机器加工，要使加工周期最短的流水作业排序问题，即n/2/F/Fmax问题，约翰逊于1954年提出了一个最优算法，即著名的Johnson算法。为叙述方便，以ai表示零件Ji在机器M1上的加工时间，以bi表示零件Ji在机器M2上的加工时间，每个零件都按M1M2的路线加工。4.2.2两台机器排序问题的最优算法214.2.2两台机器排序问题的最优算法约翰逊法则如果Min(ai,bj)Min(aj,bi),则工件i应该排在工件j之前。如果为等号，则零件i即可安排在零件j之前，又可安排在零件j之后。约翰逊算法（Johnson算法）（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。224.2.2两台机器排序问题的最优算法（续）然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤（1）。23将工件2排在第1位2将工件3排在第6位23将工件5排在第2位253将工件6排在第3位2563将工件4排在第5位25643将工件1排在第4位256143最优加工顺序为S=(2,5,6,1,4,3),Fmax=28I123456ai518534bi7224744.2.2两台机器排序问题的最优算法（续）244.2.2两台机器排序问题的最优算法（续）Johnson算法的改进1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。254.2.2两台机器排序问题的最优算法（续）举例工件号123456ai518534bi722474工件最优顺序：25614313455827474214813182631115222628aibi最优顺序下的加工周期为2826应用Johnson算法求得的最优顺序中任意去掉一些零件时，余下零件构成的顺序仍为最优顺序。Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。最优顺序不一定是唯一的。例如顺序（2,5,6,4,1,3）说明：274.2.3多台机器排序问题的启发式算法关键工件法1.计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；2.对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa,若pi1pim则按pim不增的顺序排成一个序列Sb;3.顺序（Sa,C,Sb）即为所求顺序。284.2.3多台机器排序问题的启发式算法（续）举例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求顺序：（2,1,3,4）29Palmer（帕尔默）法1965年，帕尔默（D.S.Palmer)对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标，然后将各工件按其斜度指标不增进行排序。零件的斜度指标可按下式计算：1(),1,2,....21ikmmikPknkl+=-=å=式中，m为机器数，Pik为零件i在机器Mk上的加工时间。按照各零件不增的顺序排列零件，可得出令人满意的加工顺序。il30例3：有一个4/3/F/Fmax问题，其加工时间如下表所示，试用Palmer法求解。工件i1234Pi11263Pi28429Pi3458231CDS法坎贝尔（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一个启发式算法，简称CDS法。他们把Johnson算法用于一般的n/m/F/Fmax问题，得到（m-1）个加工顺序，取其中的优者。具体的做法是：对加工时间,,1,2,...,1;11iklmpikplmkkml根据Johnson算法可以求得一个排序，共可得到m-1个排序，从中选优。=-邋==+-注：当取不同值，对每一组值，看成是分别在两个机器上的加工时间。l324.3单件车间作业计划问题4.3.1任务分配问题4.3.2排序问题的描述4.3.3两种作业计划的构成4.3.4求解一般n/m/G/Fmax问题的启发式方法334.3.1任务分配问题把n项任务分给n台机器加工，有n!方案匈牙利算法(1)从加工时间(费用)矩阵每一行所有元素减去该行最小的元素，使每行至少出现一个零元素。(2)从实施第(1)步得到的矩阵中的每一列所有元素减去该列最小的元素，使每列至少出现一个零元素。(3)从实施第(2)步得到的矩阵中，划出能覆盖尽可能多的零元素的直线，如果线条数等于矩阵的行数，则已找到最优矩阵，转第(6)步；否则，转第(4)步。(4)从矩阵中未被线条穿过的元素中减去这些元素中的最小数，并将这个最小数加到直线交叉的元素上，其余元素不变。(5)重复步骤(3)和步骤(4)，直到获得最优矩阵。（6）从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素。零元素对应的就是最优分配方案。例4-3-1有如下任务分配问题:34求解过程如下表所示：3536e零件1由机器M3加工，零件2由机器M2加工，零件3由机器M4加工，零件4由机器M1加工，可使总加工时间最少。3738对于一般单件作业排序问题，要描述一道工序，要用三个参数：i,j,和k。i表示工件的代号，j表示工序，k表示完成工件i的第