第十一章制造业作业计划与控制学时数：2教学目的：了解和掌握作业计划和排序问题的基本概念，流水作业排序问题、单件作业计划问题、生产作业控制的思想和方法。

教学重点和难点：流水作业排序问题、单件作业计划问题、生产作业控制的思想和方法。

主要教学内容及要求：（1）了解和掌握作业计划和排序问题的基本概念；（2）了解和掌握流水作业排序问题、单件作业计划问题、生产作业控制的思想和方法。

第一节作业计划和排序问题的基本概念编制作业计划要解决的问题⏹编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。

⏹由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。

有关的名词术语⏹编制作业计划或日程安排(Scheduling)⏹排序(Sequencing)⏹派工(Dispatching)⏹控制(Controlling)⏹赶工(Expediting)⏹“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动⏹“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。

一句话，表示“服务者”⏹“零件”代表“服务对象”。

零件可以是单个零件，也可以是一批相同的零件⏹“加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束⏹“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题第二节流水作业排序问题流水车间(Flow shop):工件的加工路线都一致，典型的如流水线1、最长流程时间的计算工件代号i 1 4 6 3 5 2P i1 4 5 3 4 8 6P i23 9 1 3 7 5P i37 6 8 2 5 9P i45 6 3 9 2 44 9 12 16 24 307 18 19 22 31 3614 24 32 34 39 4819 30 35 44 46 522、 两台机器排序问题的最优算法约翰森法则⏹ 如果Min(a i , b j ) < Min (a j , b i ),则工件i 应该排在工件j 之前。

约翰森算法⏹ （1）从加工时间矩阵中找出最短加工时间；⏹ （2）若最短加工时间出现在机器M 1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M 2 上，则对应工件应该尽可能往后排。

然后从加工时间矩阵中划去已排序工件的加工时间。

若最短加工时间有多个，则任挑一个。

（3）若所有工件都已排序，停止。

否则，转步骤（1）。

将工件2排在第1位2将工件3排在第6位23将工件5排在第2位253将工件6排在第3位 2 563将工件4排在第5位 2 5643将工件1排在第4位 256143最优加工顺序为S=(2,5,6,1,4,3), F max =28I 1 2 3 4 5 6Ai 5 1 8 5 3 4Bi 7 2 2 4 7 4Johnson 算法的改进1. 将所有a i ≤ b i 的工件按a i 值不减的顺序排成一个序列A ；2. 将a i ＞b i 的工件按b i 值不增的顺序排成一个序列B ；3. 将A 放到B 之前，就构成了一个最优加工顺序。

3、多台机器排序问题的启发式算法关键工件法⏹ 1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C ； ⏹ 2. 对于余下的工件，若p i1≤p im 则按p i1不减的顺序排成一个序列S a ,若p i1>p im 则按p im 不增的顺序排成一个序列S b; ⏹ 3. 顺序（S a ,C,S b ）即为所求顺序。

工件i 1 2 3 4P i1 2 1 6 3P i24 8 2 9P i3 5 4 8 211 13 16 14CS a (2,1)S b (4)所求顺序：（2,1,3,4）4、 相同零件不同移动方 式下加工周期的计算当n 个零件相同，则无排序问题。

但不同移动方式下的加工周期不同 三种典型的移动方式⏹ 顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工 ⏹ 平行移动方式：单个零件加工完成后，立即移动到下道工序加工 ⏹ 平行顺序移动方式：两者混合顺序移动方式加工周期时间1234顺序移动方式设零件批量为n （件），工序数目为m ，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T （分钟），零件在i 道工序的单件工时为 （分钟/件），i=1.2…n. 则该批零件的加工周期为：i t121...m imi T nt nt nt n t ==++=∑平行移动方式工序1234零件平行移动的加工周期 平行顺序移动方式特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。

如图所示：工序1234平行顺序移动加工周期计算第三节 单件作业计划问题1、 问题的描述T 平12111(1)m mi i nt t n t ==+-∑平111(1)m m i ii i T t n t -==+-∑∑平顺=nD=1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2T=2 4 13 4 5加工描述矩阵D和加工时间矩阵T对应2、两种作业计划的构成符号说明⏹每安排一道工序称为一“步”⏹{St}:t步之前已排序工序构成的部分作业计划；⏹{Ot}:t步可排序工序的集合；⏹Tk为{Ot}中工序Ok的最早可能开始时间；⏹T’k为{Ot}中工序Ok的最早可能完成时间。

能动作业计划的构成⏹（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）；否则，停止。

能动作业计划的构成t {Ot} Tk T`k T* M* Oj1 1,1,12,1,3 0232 M1 1,1,12 1,2,32,1,3 263 3 M3 2,1,33 1,2,32,2,1 33777 M3M11,2,34 1,3,2 2,2,17 3 8 7 7 M1 2,2,1 5 1,3,2 2,3,27 7 8 12 8M21,3,26 2,3,2 81313 M2 2,3,2能动作业计划的甘特图2,3,21,1,1 2,2,11,3,22,1,3 1,2,33 77 8 132 3 7时间机器M 1M 2M 3无延迟作业计划的构成⏹ （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）；否则，停止。

无延迟作业计划的构成t{O t }T kT`kT*M*O j11,1,12,1,3002300M 1M 31,1,121,2,32,1,320630M 32,1,331,2,32,2,1337733M 3M 11,2,341,3,22,2,173873M 12,2,151,3,22,3,27781277M 2M 22,3,261,3,2121312M 21,3,2无延迟作业计划的甘特图2,3,21,1,1 2,2,12,1,3 1,2,33 77 12 132 3 7时间机器M 1M 2M 31,3,23、 求解一般n/m/G/F max 问题的启发式方法（1）优先调度法则⏹ 构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 ⏹ 计算量小⏹ 已经提出100多种优先调度法则 优先调度法则⏹ FCFS （first come, first served ）选择最早进入可排序集合的工序 ⏹ SPT( shortest processing time ）选择加工时间最短的工序 ⏹ EDD （earliest due date ）选择完工期限最紧的工序 ⏹ SCR(smallest critical ratio)选择临界比最小的工件⏹MWKR(most work remaining)选择余下加工时间最长的工件⏹LWKR(least work remaining)选择余下加工时间最短的工件⏹MOPNR(most operations remaining)选择余下工序数最多的工件⏹RANDOM 随机挑选一个工件⏹Rush（2）随机抽样法⏹从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。

（3）概率调度法⏹将优先调度法则与随机抽样法结合⏹对不同工件将优先调度法则分配不同的挑选概率，效果较好第四节生产作业控制实行生产作业控制的原因生产环境的变化计划的失误执行的原因：执行过程中，有可能会出现操作人员执行不力、效率不高和工作态度等现象，造成计划完不成执行因素的影响生产作业控制的程序制定生产作业监控体系监控实际生产过程评估偏差情况采取纠偏措施生产作业控制的功能为每个车间的工单指派优先级维护车间在制品数量将车间工单信息传送到相应办公室提供实际产出数据来为能力控制服务根据车间工单对机位的要求，为在制品库存管理提供数量信息测量人员和设备的效率、利用率和产量。

生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：⏹调度单⏹日报、月报⏹例外报告、异常报告⏹输入/输出（Input/output control，I/O）报告漏斗模型模型介绍德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。

漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。

当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。

注：曲线图的垂直段表示某天到达或完成的一个或多个工件之间所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。

如果运输时间不变，输入曲线与上道工序的输出曲线相对应。

控制规则在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：⏹若希望保持在制品库存量，可暂时增加或减少输入。