第十章-作业计划与控制课件

第十章作业计划与控制丁秋雷第十章作业计划与控制丁秋雷2

通过MRP确定了各车间零部件的投入出产计划，将全厂性的生产计划变成了各车间的生产任务。各车间要完成既定的生产任务，还必须将零部件投入出产计划转变为车间生产作业计划，即：将车间的生产任务变成各个工段、班组、工作地的任务。将任务安排到工作地，就涉及到任务分配和作业排序等问题。1.1作业计划的必要性[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划2通过MRP确定了各车间零部件的投入出产计划，将全厂性的生3

一个排序的例子

[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划3一个排序的例子

[关键内容]:4

（a）装配顺序为A→B→C→D，总装配时间为48小时（b）装配顺序为C→B→D→A，总装配时间为45小时（c）装配顺序为D→C→A→B，总装配时间为51小时4（a）装配顺序为A→B→C→D，总装配时间为48小时（b5

排序给出零部件在一台或一组设备上加工的先后顺序，实质上是要解决如何按时间的先后，将有限的资源分配给不同的工作任务使预定的目标最优化的问题。编制作业计划不仅要解决先加工哪个工件、后加工哪个工件的加工顺序问题，还包括确定机器加工每个工件的开始时间和完成时间。编制作业计划与排序的概念和目的都是不同的。但是，在工件的加工顺序确定以后，作业计划也就确定了，因此往往将“排序”和“编制作业计划”等同。1.2排序与编制作业计划的差别[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划5排序给出零部件在一台或一组设备上加工的先后顺序，实质上是6

确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！种方案，假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间更无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。1.3排序的难度[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划6确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再7

根据排序规则对每一个到达的订单安排作业顺序工作地工件排队等待加工来自上游工作地的订单加工完毕的订单流向下一工作地单件车间制定作业计划示意图7根据排序规则对每一个到达的订单安排作业顺序工作地工件排来8

作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划，是加工制造发生之前的活动。排序：确定零件在机器上的加工顺序。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。调度：是作业计划编制后实施生产控制所采取的行动。2.1名词术语[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划8作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工9

一个零件不能同时在几台不同的机器上加工，每台机器同时只能加工一个零件；零件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工；不允许中断，零件一旦开始加工，必须一直进行到完工，不得中途停止并插入其它零件；每道工序只在一台机器上完成；零件数、机器数和加工时间已知。2.2假设条件[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划9一个零件不能同时在几台不同的机器上加工，每台机器同时只能10

2.3排序的分类排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质按参数确定型排序问题随机型排序问题单目标的排序问题多目标的排序问题[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划102.3排序的分类排序问题分类按机器单台机器排序问题单11

按机器的种类和数量不同，分为单台机器的排序问题和多台机器的排序问题对于多台机器排序，根据加工路线的特征，分成：单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题2.3排序的分类工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划11按机器的种类和数量不同，分为单台机器的排序问题和多台机12

排序问题常用四个符号来描述:n/m/A/B其中：n—工件数m—机器数A—车间类型B—目标函数，通常使其值最小，如B=Fmax，是使最长流程时间最短。例如：4/2/P/Fmax表示4个工件在2台机器上流水作业时以最长流程时间最短为目标的排序。2.4排序问题的一般表示方法[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划12排序问题常用四个符号来描述:n/m/A/B2.413

2.5生产调度问题优化的主要目标

1基于经济的调度目标：生产费用最小，利润最大，库存费用最少等2最大能力指标：包括最大生产率、最短的生产周期等3客户满意度指标：包括最短的延迟，最小提前或者拖后惩罚，平均延迟时间小等目标之间往往相互冲突，即某个目标性能的改善可能导致另一个或者另几个目标性能的降低132.5生产调度问题优化的主要目标1基于经济的调度目14

n个工件全部经由一台机器处理3.1定义J1J2Jn机器到达系统工件的集合离开系统（机器）[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划14n个工件全部经由一台机器处理3.1定义J1机器到达系15

平均流程最短最大延期量最小

3.2常见单台机器排序问题的目标函数定义:为n个零件经由一台机器的平流程时间，流程时间=等待时间+加工时间目标函数：定义:为最大延迟量。目标函数：[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划15平均流程最短3.2常见单台机器排序问题的目标函数定义16

根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priorityrules)有：SPT---ShortestProcessTime,EDD---EarliestDueDate等,分别用于解决不同的问题。按什么样的准则来选择，对排序方案的优劣有很大影响。3.2常见单台机器排序问题的目标函数[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划16根据排序目标的不同，可以选择不同的排序规则，有时又称为17

SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序使工件的平均流程时间最短，从而减少在制品量EDD（Earliestduedate）法则优先选择交货期最早的工件可使工件的平均延期时间最小FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平CR（CriticalRatio）法则CR是用交货日期减去当前日期的差值除以剩余的工作日数。关键比率最小的任务先执行。保证工件的延期数量最小3.3常用的优先顺序规则[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划17SPT（Shortestprocessingtim18

MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成STR（SlackTimeRemaining）法则：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的任务最先进行。使任何任务（订单）最大延期最小RANDOM法则：随机地挑一个工件3.3常用的优先顺序规则[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划18MWKR（Mostworkremaining）法则19

例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间，采用SPT法则和EDD法则，求工件的加工顺序。19例：一个加工车间负责加工发动机机壳，现在共202021

EDD规则（优先选择完工期限最紧的工作）排序结果

比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，减少在制品量，但平均延迟较大。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平，但平均流程时间较长。21EDD规则（优先选择完工期限最紧的工作）排序结果22

流水车间(Flowshop)：工件的加工路线都一致。在流水线上制造不同的零件，即流水作业的排序问题。上面说的加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。本节主要考虑：（1）最长流程时间的计算（2）两台机器排序问题的最优算法4.1前言[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划22流水车间(Flowshop)：工件的加工路线都一致。23

n/m/P/Fmax问题，其中n为工件数，m为机器数，P表示流水作业的排序问题，Fmax为目标函数。n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。假设：所有工件的到达时间都为零4.2最长流程时间的计算

[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划23n/m/P/Fmax问题，其中n为工件数，m为机器数24

例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。序号为3的工件在序号为2的机器上的加工时间为6[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划24例：6/4/P/Fmax问题，加工时间如表所示。当按25

例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。按顺序S=(6,1,5,2,4,3)列出加工时间矩阵。

615243Pi1244213Pi2544576Pi3555857Pi41432342712134+max{7,6}=1111

15202733

1722303542

2125323846610121316[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划25例：6/4/P/Fmax问题，加工时间如表所示。当按26

约翰森算法（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤1。4.3两台机器排序问题的最优算法[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划26约翰森算法4.3两台机器排序问题的最优算法[关键内容27例：将工件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=28I123456Ai518534Bi722474[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划27例：将工件2排在第1位2I28

约翰森算法的改进（1）将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；（2）将ai＞bi的工件按bi值不增的顺序排成一个序列B；（3）将A放到B之前，就构成了一个最优加工顺序。4.3两台机器排序问题的最优算法[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划28约翰森算法的改进4.3两台机器排序问题的最优算法[关29例：工件号123456

ai518534

bi722474最优顺序256143

134558274742

4

8

13

18

2631115222628

ai

bi最优顺序下的加工周期为28[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序