运营管理(11-14)

1生产与运作管理-1-Production&OperationManagementTheSchoolofEconomicsandBusinessAdministrationHeilongjiangUniversity纲要第三篇生产运作系统的运行（2）第十一章制造业作业计划与控制第十二章服务业的运作计划第十三章供应链管理第十四章项目计划管理-2-SchedulingandControllingforManufacturing11.1作业计划问题的基本概念11.2流水作业排序问题11.3单件作业排序问题11.4生产作业控制第11章制造业作业计划与控制-3-11.4生产作业控制必要性†作业排序是安排作业的活动、资源使用或配置设施的时间表†排序不当的车间：„作业等待时间占总生产周期的95%„→造成一个较长的工作流周期-4-„→加上库存时间和其他时间，就是使现金流周期较长†排序得当的车间：„节约75%的排队时间„→使现金流周期缩减同样数量的时间11.1作业计划问题的基本概念†工作中心：生产经营中的一个区域，在这个区域中，组织生产资源来完成工作„可以是一台机器、一组机器或完成某一类型工作的一个区域„可以按工艺专业化的一般作业车间组织，或者按产品流程、装配线、成组技术单元（GT-cell）结构进行组织-5-程、装配线、成组技术单元（GT-cell）结构进行组织编制作业计划要解决的问题†编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。†由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。-6-工的顺序问题。2有关的名词术语†编制作业计划或日程安排(Scheduling)：确定工件在机器上的加工顺序，以及及其加工每个工件的开始时间和完成时间†排序(Sequencing)：确定工件在机器上的加工顺序†派工(Dispatching)：按作业计划的要求，将具体生产任务安排到具体的机床上加工，属于“调度”范围†赶工(Expediting)：是在实际进度已落后于计划进度是采取-7-†赶工(Expediting)：是在实际进度已落后于计划进度是采取的行动，属于“调度”范围†控制(Controlling)†“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动有关的名词术语（续）†机器：表示“服务者”„可以是工厂里的各种机床，也可以是维修工人„可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元†零件：代表“服务对象”零件可以是单个零件，也可以是一批相同的零件-8-„零件可以是单个零件，也可以是一批相同的零件†加工路线：是零件加工的工艺过程决定的，它是零件加工在技术上的约束†加工顺序：表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题排序问题的分类†按机器的种类和数量分类„单台机器的排序问题„多台机器的排序问题，按工件的加工路线又可分为：{单件作业（job-shop）排序问题：加工路线不同{流水作业（flow-shop）排序问题：加工路线完全相同-9-†按照工件到达车间的情况不同„静态的排序问题：排序前工件全部到达„动态的排序问题：工件陆续到达，随时安排加工顺序排序问题的分类（续）†按目标函数的性质不同„单目标排序问题和多目标排序问题„平均流程时间最短、误期完工工件数量最少……†按参数的性质„确定型排序问题：加工时间和其他有关参数是已知、确-10-„确定型排序问题：加工时间和其他有关参数是已知、确定的量„随机型排序问题：加工时间和其他有关参数是随机变量排序问题的表示法†康威（Conway）模型，四个参数：„n/m/A/B„n：工件数„m：机器数„A：车间类型-11-A：车间类型{F：流水作业排序问题{P：流水作业排序问题{G：一般单件作业排序问题{m=1，则A处为空白„B：目标函数，通常使其值最小{如：最长完工时间最短典型的作业排序和控制功能†分配订单、设备和人员到各工作中心或其他规定的地方，即短期能力计划†决定订单顺序，即建立订单优先级†对已排序作业开始安排生产，即调度†车间作业控制（生产作业控制），包括：-12-†车间作业控制（生产作业控制），包括：„在作业进行过程中，检查其状态和控制作业的速度„加快为期已晚的和关键的作业3工作中心作业排序的目标†满足交货日期†极小化提前期†极小化准备时间或成本†极小化在制品库存极大化设备或劳动力的利用-13-†极大化设备或劳动力的利用作业排序的十个优先规则†FCFS（先到先服务）：按订单送到的先后顺序进行加工。†SOT（最短作业时间）：所需加工时间最短的作业首先进行，然后是加工时间第二最短的，如此等等。这个规则等同于SPT（最短加工时间）规则。†交货期——最早交货期最早加工。将交货期最早的作业放在第一个进行。DDate——当指的是全部作业交货期时，用DDate表示；OPNDD——当指的是下一个作业交货期时，用-14-DDate表示；OPNDD——当指的是下一个作业交货期时，用OPNDD表示。†开始日期——交货期减去正常的提前期（最早开始的作业第一个进行）。†STR（剩余松弛时间）——STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的任务最先进行。作业排序的十个优先规则（续）†STR/OP（每个作业剩余的松弛时间）：STR/OP最短的任务最先进行。STR/OP的计算方法如下：„STR/OP=（交货期前所剩的时间-剩余的加工时间）/剩余的作业数†CR（关键比率）：关键比率是用交货日期减去当前日期的差值除以剩余的工作日数。关键比率最小的任务先行。†QR（排队比率）：排队比率是用计划中剩余的松弛时间除以-15-QR（排队比率）：排队比率是用计划中剩余的松弛时间除以计划中剩余的排队时间，排队比率最小的任务先执行。†LCS（后到先服务）：该规则经常作为缺省规则使用。因为后来的工单放在先来的上面，操作员通常是先加工上面的工单。†随机次序或随兴所致：主管或操作工通常随意选择一件他们喜欢的进行加工。11.2流水作业排序问题†流水车间(Flowshop):工件的加工路线都一致，典型的如流水线„加工路线一致：指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工„问题1：最长流程时间的计算„问题2：两台机器排序问题的最优算法-16-„问题2：两台机器排序问题的最优算法„问题3：多台机器排序问题的启发式算法„问题4：相同零件不同移动方式下加工周期的计算WorkCenter#1WorkCenter#2Output一、最长流程时间的计算†例：6/4/p/Fmax问题„加工时间矩阵如下表{行：不同工件在某台机器上的加工时间{列：某工件在不同机器上的加工时间„当顺序S=（6，1，5，2，4，3）加工时，求Fmax-17-i123456Pi1423142Pi2456745Pi3587555Pi4424331算法†第1行„第1列：把加工时间作为完工时间标在加工时间的右上角„第2列到第n列：从左到右依次将前一列右上角的数字加上计算列的加工时间，将结果填在计算列加工时间的右上角-18-†第2行到第m行„第1列：把上一行右上角的数字和本行的加工时间相加，将结果填在本行加工时间的右上角„第2列到第n列：从本行前一列右上角和本列上一行的右上角数字中取大者，再和本列加工时间相加，将结果填在本列加工时间的右上角†最后一行的最后一列右上角数字，即为Fmax4例（续）†顺序S下的加工时间矩阵„表示形式：加工时间完工时间i615243Pi12246410212113316P57411415520727633-19-†Fmax=46Pi257411415520727633Pi3512517522830535742Pi4113421325232338446二、n/2/F/Fmax问题的最优算法†约翰森（Johnson）法则„ai表示Ji在M1上的加工时间，bi表示Ji在M2上的加工时间，加工路线：M1→M2„如果Min(ai,bj)Min(aj,bi),则工件i应该排在工件j之前；若为等号，则i排在j前、后皆可。†约翰森算法-20-†约翰森算法①从加工时间矩阵中找出最短加工时间；②若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。③若所有工件都已排序，停止。否则，转步骤①。例：6/2/F/Fmax问题将工件2排在第1位2将工件3排在第6位23I123456Ai518534Bi722474-21-将工件5排在第2位253将工件6排在第3位2563将工件4排在第5位25643将工件1排在第4位256143最优加工顺序为S=(2,5,6,1,4,3),Fmax=28Johnson算法的改进1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。-22-举例工件号123456ai518534bi722474-23-工件最优顺序：25614313455827474214813182631115222628aibi最优顺序下的加工周期为28三、一般n/m/P/Fmax问题的启发式算法†Palmer法†关键工件法†CDS法-24-5Palmer法†1965年，Palmer提出按斜度指标排列工件的启发式算法，即Palmer法。†工件的斜度指标可按下式计算：()nkpmkikmkiL,2,1,211=⎥⎦⎤⎢⎣⎡+−=∑λ-25-„m为机器数„pik为工件i在Mk上的加工时间†排列原则：按照各工件λi不增的顺序排列工件，可得出令人满意的顺序k1⎥⎦⎢⎣=Palmer法——例†4/3/F/Fmax问题†时间加工矩阵如下：i1234Pi11263-26-Pi11263Pi28429Pi34582Palmer法——例：计算过程†计算λiλ=3，λ=3，λ=2，λ=-1()3,2,1,21331=⎥⎦⎤⎢⎣⎡+−=∑=kpkikkiλ31iiipp+−=λ-27-†λ1=3，λ2=3，λ3=2，λ4=-1†按λi不增的顺序排列工件，得到加工顺序（1，2，3，4）和（2，1，3，4），恰好这两个顺序都是最优顺序。如不是这样，则从中挑选较优者。在最优顺序下，Fmax=28关键工件法1.计算每个工件的总加工时间Pi=∑pij，将加工时间最长的工件C作为关键工件；2.对于余下的工件，若pi1≤pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排成一个序列Sb;3.顺序（S,C,S）即为所求顺序。-28-3.顺序（Sa,C,Sb）即为所求顺序。关键工件法——例†计算Pi，i=1，2，3，4i1234Pi11263Pi28429P4582-29-†总加工时间最长的为3号工件；pi1≤pi3的工件为1和2，按pi1不减的顺序排成Sa=（1，2）；pi1＞pi3的工件为4，Sb=（4），这样得到的加工顺序为（1，2，3，4），对本例为最优顺序。Pi34582Pi13111614CDS法†Campbell-Dudek-Smith三人提出了一个启发式算法，即CDS法：把Johnson算法用于一般的n/m/P/Fmax问题，得到（m-1）个加工顺序，取其中优者。„对加工时间121lm−=∑∑mpplL和-30-„用Johnson算法求（m-1）个加工顺序，取其中优者（Fmax最小）。1,,2,1l,1m1=∑∑−+==mpplkikkik和6CDS法——例†（l=1,2），则i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011-31-„当l=1时，按Johnson算法得到加工顺序（1，2，3，4），Fmax=28„当l=2时，按Johnson算法得到加工顺序（2，3