作业计划与控制.ppt
2019/8/19,1,Chapter11 作业计划与控制,§1 作业计划的基本概念 一、作业计划 是将主生产计划（MPS）细化为每周、每个工作日、甚至每小时的具体作业的安排。 编制作业计划实质上是将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。,2019/8/19,2,二、作业计划与控制的功能,1、确定订单执行的顺序。 2、作业调度或派工：将已排序的作业安排到具体的工作地。 4、生产作业控制： 监控订单执行过程，保证订单如期完成。 加快滞后订单或关键订单。 5、不断修订作业计划，以适应最新的订单状态变化。,2019/8/19,3,三、作业排序的目标,1、满足交货日期。 2、流程时间最短。 3、在制品（WIP）库存最小。 4、机器或人员空闲时间最小。,2019/8/19,4,四、作业排序问题的分类,1、两种基本的作业排序： 劳动力作业排序：确定人员何时工作。 生产作业排序：将不同工件安排到不同设备上，或安排不同的人做不同的工作。 在制造业中，生产作业排序是主要的 在服务业中，劳动力作业排序是主要的，因为服务的及时性是影响公司竞争力的主要因素。,2019/8/19,5,2、按机器的种类和数量不同，分为单台机器的排序和多台机器的排序。,多台机器排序问题，按工件加工路线的特征，可分为单件车间排序问题和流水车间排序问题。 3、按零件到达车间的情况不同，分为静态排序和动态排序。,2019/8/19,6,五、作业排序问题的4参数表示法:,n /m /A /B。 其中, n 零件数； m 机器数； A 作业类型；在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题。若标以“G”，则表示一般单件作业排序问题。当m1，则A处为空白 B目标函数，通常是使其值最小。,2019/8/19,7,§2 流水作业计划问题,流水车间作业计划问题基本上就是流水作业排序问题。而且一旦加工顺序确定，就可以重复进行，形成循环作业计划。 一、加工周期的计算 n个不同零件按相同的加工路线经过m台机器加工，目标是使这批零件的加工周期最短。 加工周期又称作最长流程时间Fmax,2019/8/19,8,例题,6/4/p/ Fmax问题，当按顺序S( 6,1,5,2,4,3)加工时，求Fmax.,2019/8/19,9,加工周期为46,因1317，取大的17加4,2019/8/19,10,二、n/2/F/Fmax问题的最优算法,Johnson算法： 从加工时间矩阵中找出最短的加工时间。 若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个 若所有零件都已排序，停止。否则，转步骤。,2019/8/19,11,求最优顺序,怎么计算出来的？,2019/8/19,12,利用横道图计算加工周期,1,2,3,0,2,20,10,30,时间,工序,a,b,7,零件2,零件5,零件6,零件1,零件4,零件3,4,4,5,7,5,4,2,8,28,2019/8/19,13,算法步骤的改进,把Johnson算法作些改变，改变后的算法按以下步骤进行： 将所有aibi的零件按ai值不减的顺序排成一个序列A。 将所有aibi的零件按bi值不增的顺序排成一个序列B。 将A放到B之前，就构成了最优加工顺序,2019/8/19,14,序列A为 (2， 5，6，1)，序列B为(4，3)，构成最优顺序为 (2，5，6，1， 4，3)，与Johnson算法结果一致。,2019/8/19,15,习题,现有5个零件，设要先车后铣，其加工工时如下表所示。问如何安排零件加工顺序，使加工周期最短，并计算出加工周期。（答案：39分钟）,2019/8/19,16,三、求一般n/m/P/ Fmax问题近优解的启发式算法,1、Palmer法 2、关键零件法 3、CDS法,2019/8/19,17,1、Palmer法,按零件的斜度指标排列零件的启发式算法 式中，m为机器数；pik为零件i在机器Mk上的加工时间。 按照各零件i不增的顺序排列零件。,2019/8/19,18,例题,有一个4/3/F/Fmax问题，其加工时间如表所示，试用Palmer法求解。 加工时间矩阵,2019/8/19,19,解,1=-P11+P13=-1+4=3,2=-P21+P23=-2+5=3,4=-P41+P43=-3+2=-1,3=-P31+P33=-6+8=2,按i不增的顺序排列零件，得到加工顺序（1，2，3，4）或（2，1，3，4） 最长流程时间Fmax=28,2019/8/19,20,2、关键零件法求近优解举例,余下的零件，若Pi1Pim，则按Pi1不减的顺序排成一个序列Sa；若Pi1Pim，则按Pi1不增的顺序排列成序列Sb，顺序（Sa，C，Sb）为所求顺序,找出加工时间最长的零件C本例为3号零件,2019/8/19,21,3、CDS法,Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(1)个加工顺序，取其中优者 具体做法是，对加工时间 和 用Johnson算法求（m-1）次加工顺序，取其中最好的结果。,2019/8/19,22,当1时，按Johnson算法得到加工顺序(1，2，3，4)； 当2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax29。所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。,2019/8/19,23,四、相同零件、不同移动方式下加工周期的计算,零件在加工过程中有三种移动方式： 顺序移动 平行移动 平行顺序移动,2019/8/19,24,1、顺序移动方式,例题,已知n=4，t1=10分钟，5分钟，15分钟，10分钟，则T顺=4×（10+5+15+10）=160分钟。,T顺,工序,时间,2019/8/19,25,2、平行移动方式,t1,t2,t3,t4,T平,M1,M2,M3,M4,工序,时间,2019/8/19,26,3、平行顺序移动方式,综合了以上两种方式的优点。 平行顺序移动方式要求每道工序连续加工，但又要求各道工序尽可能平行地加工。 具体做法是： 1、当titi+1时，零件按平行移动方式转移； 2、当titi+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）×ti+1作为零件在（i+1）工序的开始加工时间。,2019/8/19,27,t1,t2,t3,t4,T平,M1,M2,M3,M4,工序,时间,2019/8/19,28,§3 单件车间作业计划问题,一、任务分配问题 n个零件分配给n台机器加工，用匈牙利算法可找到最优分配方案。 例题,2019/8/19,29,匈牙利算法的步骤,1、行缩减,2、列缩减,2019/8/19,30,3、用最少的直线覆盖全部的0,如直线数等于矩阵的行数，则已找到最优矩阵；否则转入下一步。,2019/8/19,31,4、未覆盖的元素中减去其中的最小数，并将这一最小数加到直线交叉的元素上。其余数字不变,2019/8/19,32,5、分配任务,J1M3；J2M2；J3M4；J4M1,2019/8/19,33,二、n个作业单机床排序,8个优先调度规则： 1、SPT(Shortest Processing Time)法则 优先选择加工时间最短的工序。 例题,2019/8/19,34,SPT排序,总流程时间=1+3+6+10+16=36（天） 平均流程时间=36/5=7.2（天） 作业E和C可以满足交货日期，作业A只晚1天交货。 平均作业延迟（0+0+1+4+7）/5=2.4天,2019/8/19,35,2、FCFS(First Come First Served)法则,总流程时间=3+7+9+15+16=50（天） 平均流程时间=50/5=10（天） 作业A能及时完成。作业B、C、D、E都分别迟1、2、6和14天。 平均作业延迟（0+1+2+6+14）/5=4.6天,2019/8/19,36,3、EDD(Earliest Due Date)法则 优先选择完工期限紧的工件。,总流程时间=1+4+8+10+16=39（天） 平均流程时间=39/5=7.8（天） 作业B、C、D、都将延误。 平均作业延迟（0+0+2+3+7）/5=2.4天,2019/8/19,37,4、MWKR(Most Work Remaining)法则 优先选择余下加工时间最长的工件。,5、LWKR(Least Work Remaining)法则 优先选择余下加工时间最短的工件。 6、MOPNR(Most Operations Remaining)法则 优先选择余下工序数最多的工件。 7、SCR(Smallest Critical Ratio)法则 优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。 8、RANDOM法则 随机地挑一个工件,2019/8/19,38,§4 生产作业控制,一、实行生产作业控制的原因和条件 1、原因： 1）加工时间估计不准确 2）随机因素的影响 3）加工路线的多样性 4）企业环境的动态性 2、实施生产控制的三个条件： 1）要有一个标准 2）要取得实际生产进度与计划偏离的信息 3）要能采取纠正偏差的行动。,2019/8/19,39,二、生产作业控制工具,1、廿特图 有两种形式的廿特图：作业进度图和机器图,作业进度图,2019/8/19,40,机器图,2019/8/19,41,二、日常调度单,它告诉主管哪些工件要被加工，这些工件的优先级以及加工时间。,2019/8/19,42,三、各种状态和异常报告,1、预计延期报告 2、废品报告 3、返工报告 4、作业总结报告,2019/8/19,43,§5 服务业中的服务作业排序,一、服务作业排序与生产作业排序的区别 1、所提供产品的类型 由于服务过程有顾客的参与，作业排序对他们有直接影响，并因此成为服务的一部分。 2、排序内容 作业排序要定义服务交易的时间。 如商场营业时间；列车时刻表；公交车首末班车。,2019/8/19,44,3、过程控制,顾客直接与服务员的接触，会对服务人员提出各种要求和发出各种指示，使服务人员不能按预定的程序工作。 4、人员规模 在顾客化服务业中，服务的输出与劳动力的最佳规模之间的关系很难确定。,2019/8/19,45,两类服务作业排序,顾客化服务： 先到先服务方式 基于操作时间或服务人员的可利用性的预约式作业排序 标准化服务：如交通运输和零售业等，更多的与设备、工具相连。 在交通运输业中，时刻表不考虑个别顾客的要求。 对邮件分发、垃圾回收及清洁街道等服务的作业排序，是根据路径计划以及最大限度地有效利用工具设备的目的来进行的。,2019/8/19,46,服务业两种排序方式：,将顾客需求分配到服务能力的不同时间段内； 将服务人员安排到顾客需求的不能时间段内。 二、服务作业排序方法之一安排顾客需求 在这种方式下，服务能力保持一定，而顾客需求被适当安排，以提供准时服务和充分利用能力。,2019/8/19,47,二、服务作业排序方法之一 安排顾客需求,1、预约 优点在于及时的顾客服务和服务人员的高效率。 如医生、律师和汽车修理。 2、预订 类似于预约，但它通常被用于顾客接受服务时需占据或使用相关的服务设施的情况。 如预订宾馆房间、火车或飞机座位，买音乐会门票。 优点在于给予服务管理者一段提前期来计划设施的充分利用。,2019/8/19,48,3、排队等待,如餐馆、银行、零售店、理发店 规则是先到先服务。 特殊顾客有优先权。 如军人、残疾人、离休干部优先,2019/8/19,49,三、服务业作业排序方法之二 安排服务人员,当需要迅速响应顾客需求且需求总量大致可以预测时，可通过服务人员的适当安排来调整服务能力，以满足不同时段的服务负荷。 如营业员、护士、警察、公交司机的日常排班,2019/8/19,50,1、人员排序方案的要求,人员排序方案需要确定每个人一周内的工作日和休息日。 人员排序必须满足每天的不同需求。 还需根据需求的变化随时调整人员排序计划。,2019/8/19,51,邮局包裹服务部的人员排序计划 （其中×表示工作日，空白表示休息日）,2019/8/19,52,保证每人有两日连休的方法,2019/8/19,53,续表,
