生产与运作管理 第8章 制造业作业计划

中北大学经济与管理学院1生产与运作管理Production&OperationsManagement中北大学经济与管理学院EconomicsManagementSchool，NUC中北大学经济与管理学院2MRP确定了各车间的零部件投入出产计划各车间的生产任务各个班组、各个工作地的任务全厂性的生产计划有效的生产控制独立需求中北大学经济与管理学院3第8章制造业作业计划与控制SchedulingandControllingforManufacturing8.1排序问题的基本概念8.2流水作业排序问题8.3单件作业排序问题8.4生产作业控制重点：流水作业排序问题、单件作业排序问题、漏斗模型中北大学经济与管理学院48.1排序问题的基本概念1、编制作业计划要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。中北大学经济与管理学院58.1排序问题的基本概念（续）2、有关的名词术语排序(Sequencing)编制作业计划(Scheduling)派工(Dispatching)(将具体生产任务安排到具体的机床上加工)赶工(Expediting)“调度”是作业计划编制后实施生产控制所采取的一切行动。中北大学经济与管理学院6“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头。一句话，表示“服务者”。“工件”代表“服务对象”。工件可以是单个零件，也可以是一批相同的零件。“加工路线”是工件加工的工艺过程决定的，它是工件加工在技术上的约束。“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题。8.1排序问题的基本概念（续）中北大学经济与管理学院7（1）一个工件不能同时在几台不同的的机器上加工；（2）工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工；（3）不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件；（4）每道工序只在一台机器上完成；（5）工件数、机器数和加工时间已知，加工时间与加工顺序无关；（6）每台机器同时只能加工一个工件。3、假设条件与符号说明假设条件（6个）：有关符号的说明：为最长延迟时间。说明按期完工。提前完工，说明完工期限，的实际完工时间超过了说明为工件的延迟时间。为最长流程时间，车间的实际停留时间，的流程时间，即工件在为；为最长完工时间，时间。在加工过程中总的等待为其中，的完工时间，为的完工期限；为开始加工的最早时间；从外部进入车间，可以得到达时间，指为的总加工时间为上的加工时间，在为为机器，为工件}max{,0,0,0,};max{}max{;)(;;,,3,2,1,;,,3,2,1maxmaxmaxmaxmaxiiiiiiiiiiiiiiiiiiiiiiiiijijiiiiiiiiiijiijiijjiLLLJLJLdCLLFFFPwrCFJFCCCJwPwrpwrCJCJdJJrpPJMJpmjjMniiJ中北大学经济与管理学院94、排序问题分类和表示法(1)按机器的种类和数量：单台/多台。■多台机器排序问题：按工件加工路线特征（相同与否），分为单件（JOB-SHOP）作业排序和流水作业（FLOW-SHOP）排序问题。（2）按工件到达车间的情况不同：静态排序问题、动态排序问题（3）按目标函数的性质：单目标和多目标排序问题。（4）按参数性质：确定型/随机型排序问题排序问题的分类中北大学经济与管理学院10康威（conway)表示法：4参数表示法n/m/A/Bn：工件数m：机器数A：车间类型（F代表流水作业排序问题、P代表流水作业排列排序问题，G表示单件作业排序问题。当m=1时,A空白）B：目标函数（通常是使其值最小）排序问题的表示法如：n/3/p/Cmax。表示n个工件经3台机器加工的流水作业排列排序问题，目标函数是使最长完工时间Cmax最短。F：工件在不同机器上的加工顺序不尽一致；P：所有工件在各台机器上的加工顺序都相同。中北大学经济与管理学院118.2流水作业排序问题流水车间(Flowshop):工件的加工路线都一致，典型的如流水线。只讨论排列排序问题。8.2.1最长流程时间的计算8.2.2两台机器排序问题的最优算法8.2.3多台机器排序问题的启发式算法WorkCenter#1WorkCenter#2OutputWorkCenter#2中北大学经济与管理学院121、最长流程时间：又称为加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。◆由于假设所有工件的到达时间都为0（ri=0），所以Fmax等于一批工件的最长完工时间Cmax，或者等于排在末位加工的工件在车间的停留时间。本节讨论的是n/m/p/Fmax问题。8.2.1最长流程时间Fmax的计算中北大学经济与管理学院131111isisisPCCiksisikssikkPCCC},max{)1()1(设n个工件的加工顺序为S=(S1,S2,…Sn)，其中Si为排第i位加工的工件代号。以Cksi表示工件Si在机器Mk上的完工时间，Psik表示工件Si在Mk上的加工时间，k=1,2,…,m;i=1,2,…,n,则有：8.2.1最长流程时间Fmax的计算msniCFirmax,2,1,0时，当中北大学经济与管理学院148.2.1最长流程时间的计算Fmax工件代号i123456Pi1464583Pi2353971Pi3792658Pi4549623例题：有一个6/4/p/Fmax问题，其加工时间矩阵如下表所示，当按照顺序S=(1，4，6，3，5，2)加工时，求Fmax。工件代号i146352Pi1453486Pi2391375Pi3768259Pi4563924142432343948193035444652例题：有一个6/4/p/Fmax问题，其加工时间矩阵如下表所示，当按照顺序S=(1，4，6，3，5，2)加工时，求Fmax。491216243071819223136Fmax=Cmax=521111isisisPCCiksisikssikkPCCC},max{)1()1(中北大学经济与管理学院16练习：有一个6/4/p/Fmax问题，其加工时间矩阵如下表所示。当按照顺序（6，1，5，2，4，3）加工时，求Fmax。工件代号i123456Pi1423142Pi2456745Pi3587555Pi4424331Fmax=46中北大学经济与管理学院178.2.2两台机器排序问题的最优算法——n/2/F/Fmax问题1、约翰森法则：我们以ai表示Ji在M1上的加工时间，以bi表示在M2上的加工时间。每个工件都按M1M2的路线加工。如果Min(ai,bj)Min(aj,bi),则工件Ji应排在工件Jj之前。2、约翰森算法：（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。中北大学经济与管理学院188.2.2两台机器排序问题的最优算法（续）（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤（1）。将工件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=28i123456ai518534bi7224748.2.2两台机器排序问题的最优算法（续）例题：求一个6/2/F/Fmax问题的最优解，并求出最优顺序下的Fmax。中北大学经济与管理学院208.2.2两台机器排序问题的最优算法——Johnson算法的改进：基本步骤：1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。中北大学经济与管理学院218.2.2两台机器排序问题的最优算法举例工件号123456ai518534bi722474工件最优顺序：25614314813182631115222628134558274742aibi最优顺序下的加工周期为28请求出最优顺序下的加工周期？A:(2,5,6,1)B:(4,3)中北大学经济与管理学院22作业：P322练习题1中北大学经济与管理学院238.2.3一般n/m/p/Fmax问题的启发式算法一、关键工件法1.计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；2.对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa，若pi1pim则按pim不增的顺序排成一个序列Sb;3.顺序（Sa,C,Sb）即为所求顺序。中北大学经济与管理学院248.2.3多台机器排序问题的启发式算法举例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求顺序：（2,1,3,4）中北大学经济与管理学院25课堂练习P322第2题8.2.3多台机器排序问题的启发式算法中北大学经济与管理学院268.2.4相同零件、不同移动方式下加工周期的计算当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合中北大学经济与管理学院27顺序移动方式加工周期时间工序M1M2M3M4顺序移动方式1t2t3t4t中北大学经济与管理学院28设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为（分钟/件），i=1.2…n.则该批零件的加工周期为：it121...mimiTntntntnt顺序移动方式（续）中北大学经济与管理学院29例题：已知n=4,分钟101t分钟52t分钟153t分钟104t则：分钟）（顺16010155104T121...mimiTntntntnt顺序移动方式（续）中北大学经济与管理学院30为最长的单件工序时间:LtLmiitntT)1(1平工序1234时间加工周期1t2t3t4t平行移动方式4t平行移动方式：单个零件加工完成后，立即移动到下道工序加工中北大学经济与管理学院31平行移动方式（续）零件平行移动的加工周期为：T平LmiitntT)1(1平为最长的单件工序时间:Lt8515141015510)1(1）（）（平LmiitntT例题：已知n=4,分钟101t分钟52t分钟153t分钟104t中北大学经济与管理学院32平行顺序移动方式特点：既保持一批零件顺序加工，又尽可能使相邻工序加工时间平行进行。如图所示：时间工序1234加工周期具体做法：（1）当ti＜ti+1时零件按平行移动方式转移；（2）当ti＞ti+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）×ti+1作为零件在（i+1）工序的开始加工时间。中北大学经济与管理学院33时间工序1234加工周期1111),min()1(mjjjmiittntnT平顺具体做法：（1）当ti＜ti+