生产与运作管理chapt制造业作业计划

第11章制造业作业计划与控制SchedulingandControllingforManufacturing11.1作业计划问题的基本概念11.2流水作业排序问题11.3单件作业的排序问题11.4生产作业控制

第一页，共四十一页。1华中科大管理学院陈荣秋马士华11.1作业计划问题的基本概念编制作业计划要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。第二页，共四十一页。2华中科大管理学院陈荣秋马士华11.1作业计划问题的基本概念（续）有关的名词术语编制作业计划或日程安排(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)赶工(Expediting)“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动第三页，共四十一页。3华中科大管理学院陈荣秋马士华11.1作业计划问题的基本概念（续）“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题第四页，共四十一页。4华中科大管理学院陈荣秋马士华11.2流水作业排序问题流水车间(Flowshop):工件的加工路线都一致，典型的如流水线11.2.1最长流程时间的计算11.2.2两台机器排序问题的最优算法11.2.3多台机器排序问题的启发式算法Work

Center#1WorkCenter#2Output第五页，共四十一页。5华中科大管理学院陈荣秋马士华11.2.1最长流程时间的计算工件代号i146352Pi1453486Pi2391375Pi3768259Pi4563924491216243071819223136142432343948193035444652第六页，共四十一页。6华中科大管理学院陈荣秋马士华11.2.2两台机器排序问题的最优算法约翰森法则如果Min(ai,bj)<Min(aj,bi),则工件i应该排在工件j之前。约翰森算法（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1

上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。第七页，共四十一页。7华中科大管理学院陈荣秋马士华11.2.2两台机器排序问题的最优算法（续）然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤（1）。第八页，共四十一页。8华中科大管理学院陈荣秋马士华将工件2排在第1位

2将工件3排在第6位

2

3将工件5排在第2位

2

5

3将工件6排在第3位

2

5

6

3将工件4排在第5位

2

5

6

4

3将工件1排在第4位

2

5

6

1

4

3最优加工顺序为S=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi72247411.2.2两台机器排序问题的最优算法（续）第九页，共四十一页。9华中科大管理学院陈荣秋马士华11.2.2两台机器排序问题的最优算法（续）Johnson算法的改进1.将所有ai≤

bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。第十页，共四十一页。10华中科大管理学院陈荣秋马士华11.2.2两台机器排序问题的最优算法（续）举例工件号123456ai518534bi722474工件最优顺序：256143

1345582747424

8

13

18

2631115222628aibi最优顺序下的加工周期为28第十一页，共四十一页。11华中科大管理学院陈荣秋马士华11.2.3多台机器排序问题的启发式算法关键工件法1.计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；2.对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa

,若pi1>pim则按pim不增的顺序排成一个序列Sb;3.顺序（Sa,C,Sb）即为所求顺序。第十二页，共四十一页。12华中科大管理学院陈荣秋马士华11.2.3多台机器排序问题的启发式算法（续）举例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求顺序：（2,1,3,4）第十三页，共四十一页。13华中科大管理学院陈荣秋马士华11.2.4相同零件不同移动方式下加工周期的计算当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合第十四页，共四十一页。14华中科大管理学院陈荣秋马士华顺序移动方式

加工周期时间工序1234顺序移动方式第十五页，共四十一页。15华中科大管理学院陈荣秋马士华

设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为（分钟/件），i=1.2…n.则该批零件的加工周期为：

顺序移动方式（续）第十六页，共四十一页。16华中科大管理学院陈荣秋马士华平行移动方式工序1234时间加工周期第十七页，共四十一页。17华中科大管理学院陈荣秋马士华平行移动方式（续）零件平行移动的加工周期为：

第十八页，共四十一页。18华中科大管理学院陈荣秋马士华平行顺序移动方式特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：时间工序1234加工周期第十九页，共四十一页。19华中科大管理学院陈荣秋马士华平行顺序移动方式（续）平行顺序移动加工周期计算

第二十页，共四十一页。20华中科大管理学院陈荣秋马士华11.3单件作业排序问题11.3.1问题的描述11.3.2两种作业计划的构成11.3.3求解一般n/m/G/Fmax问题的启发式方法第二十一页，共四十一页。21华中科大管理学院陈荣秋马士华11.3.1问题的描述D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345加工描述矩阵D和加工时间矩阵T对应第二十二页，共四十一页。22华中科大管理学院陈荣秋马士华11.3.2两种作业计划的构成符号说明每安排一道工序称为一“步”{St}:t步之前已排序工序构成的部分作业计划；{Ot}:t步可排序工序的集合；Tk为{Ot}中工序Ok的最早可能开始时间；T’k为{Ot}中工序Ok的最早可能完成时间。第二十三页，共四十一页。23华中科大管理学院陈荣秋马士华11.3.2两种作业计划的构成能动作业计划的构成（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。（2）求T*=min{T’k},并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj<T*。（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot}，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。第二十四页，共四十一页。24华中科大管理学院陈荣秋马士华能动作业计划的构成t{Ot}TkT`kT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,2第二十五页，共四十一页。25华中科大管理学院陈荣秋马士华能动作业计划的甘特图2,3,21,1,12,2,11,3,22,1,31,2,33778132370时间机器M1M2M3第二十六页，共四十一页。26华中科大管理学院陈荣秋马士华11.3.2两种作业计划的构成（续）无延迟作业计划的构成（1）设t=1,{S1}为空集，{O1}为各工件第一道工序的集合。（2）求T*=min{Tk},并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从{Ot}中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T*。（4）将选定的工序Oj放入{St},从{Ot}中消去Oj,并将Oj的紧后工序放入{Ot}，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。第二十七页，共四十一页。27华中科大管理学院陈荣秋马士华无延迟作业计划的构成t{Ot}TkT`kT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,3,27781277M2M22,3,261,3,2121312M21,3,2第二十八页，共四十一页。28华中科大管理学院陈荣秋马士华无延迟作业计划的甘特图2,3,21,1,12,2,12,1,31,2,337712132370时间机器M1M2M31,3,2第二十九页，共四十一页。29华中科大管理学院陈荣秋马士华11.3.3三类启发式算法（1）优先调度法则构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划计算量小已经提出100多种优先调度法则第三十页，共四十一页。30华中科大管理学院陈荣秋马士华优先调度法则FCFS（firstcome,firstserved）选择最早进入可排序集合的工序SPT(shortestprocessingtime）选择加工时间最短的工序EDD（earliestduedate）选择完工期限最紧的工序SCR(smallestcriticalratio)选择临界比最小的工件MWKR(mostworkremaining)选择余下加工时间最长的工件LWKR(leastworkremaining)选择余下加工时间最短的工件MOPNR(mostoperationsremaining)选择余下工序数最多的工件RANDOM随机挑选一个工件RushTopPriority第三十一页，共四十一页。31华中科大管理学院陈荣秋马士华11.3.3三类启发式算法（续）（2）随机抽样法从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。（3）概率调度法将优先调度法则与随机抽样法结合对不同工件将优先调度法则分配不同的挑选概率，效果较好第三十二页，共四十一页。32华中科大管理学院陈荣秋马士华11.4生产作业控制实行生产作业控制的原因生产环境的变化计划的失误执行的原因：执行过程中，有可能会出现操作人员执行不力、效率不高和工作态度等现象，造成计划完不成执行因素的影响第三十三页，共四十一页。33华中科大管理学院陈荣秋马士华11.4生产作业控制（续）生产作业控制的程序制定生产作业监控体系监控实际生产过程评估偏差情况采取纠偏措施第三十四页，共四十一页。34华中科大管理学院陈荣秋马士华11.4生产作业控制（续）生产作业控制的功能为每个车间的工单指派优先级维护车间在制品数量将车间工单信息传送到相应办公室提供实际产出数据来为能力控制服务根据车间工单对机位的要求，为在制品库存管理提供数量信息测量人员和设备的效率、利用率和产量。第三十五页，共四十一页。35华中科大管理学院陈荣秋马士华第三十六页，共四十一页。36华中科大管理学院陈荣秋马士华11.4生产作业控制（续）生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：调度单日报、月报例外报告、异常报告输入/输出（Input/outputcontrol，I/O）报告第三十七页，共四十一页。37华中科大管理学院陈荣秋马士华11.4生产作业控制（续）漏斗模型模型介绍德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型