第十章-作业计划与控制

第十章作业计划与控制丁秋雷大连理工大学经济系0501班姜珊2通过MRP确定了各车间零部件的投入出产计划，将全厂性的生产计划变成了各车间的生产任务。各车间要完成既定的生产任务，还必须将零部件投入出产计划转变为车间生产作业计划，即：将车间的生产任务变成各个工段、班组、工作地的任务。将任务安排到工作地，就涉及到任务分配和作业排序等问题。1.1作业计划的必要性[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊3一个排序的例子[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊4（a）装配顺序为A→B→C→D，总装配时间为48小时（b）装配顺序为C→B→D→A，总装配时间为45小时（c）装配顺序为D→C→A→B，总装配时间为51小时大连理工大学经济系0501班姜珊5排序给出零部件在一台或一组设备上加工的先后顺序，实质上是要解决如何按时间的先后，将有限的资源分配给不同的工作任务使预定的目标最优化的问题。编制作业计划不仅要解决先加工哪个工件、后加工哪个工件的加工顺序问题，还包括确定机器加工每个工件的开始时间和完成时间。编制作业计划与排序的概念和目的都是不同的。但是，在工件的加工顺序确定以后，作业计划也就确定了，因此往往将“排序”和“编制作业计划”等同。1.2排序与编制作业计划的差别[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊6确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！种方案，假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间更无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。1.3排序的难度[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊7根据排序规则对每一个到达的订单安排作业顺序工作地工件排队等待加工来自上游工作地的订单加工完毕的订单流向下一工作地单件车间制定作业计划示意图大连理工大学经济系0501班姜珊8作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划，是加工制造发生之前的活动。排序：确定零件在机器上的加工顺序。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。调度：是作业计划编制后实施生产控制所采取的行动。2.1名词术语[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊9一个零件不能同时在几台不同的机器上加工，每台机器同时只能加工一个零件；零件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工；不允许中断，零件一旦开始加工，必须一直进行到完工，不得中途停止并插入其它零件；每道工序只在一台机器上完成；零件数、机器数和加工时间已知。2.2假设条件[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊102.3排序的分类排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质按参数确定型排序问题随机型排序问题单目标的排序问题多目标的排序问题[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊11按机器的种类和数量不同，分为单台机器的排序问题和多台机器的排序问题对于多台机器排序，根据加工路线的特征，分成：单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题2.3排序的分类工件的加工路线不同，是单件作业排序问题的基本特征；所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊12排序问题常用四个符号来描述:n/m/A/B其中：n—工件数m—机器数A—车间类型B—目标函数，通常使其值最小，如B=Fmax，是使最长流程时间最短。例如：4/2/P/Fmax表示4个工件在2台机器上流水作业时以最长流程时间最短为目标的排序。2.4排序问题的一般表示方法[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊132.5生产调度问题优化的主要目标1基于经济的调度目标：生产费用最小，利润最大，库存费用最少等2最大能力指标：包括最大生产率、最短的生产周期等3客户满意度指标：包括最短的延迟，最小提前或者拖后惩罚，平均延迟时间小等目标之间往往相互冲突，即某个目标性能的改善可能导致另一个或者另几个目标性能的降低大连理工大学经济系0501班姜珊14n个工件全部经由一台机器处理3.1定义J1J2Jn机器到达系统工件的集合离开系统（机器）[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊15平均流程最短最大延期量最小3.2常见单台机器排序问题的目标函数定义:为n个零件经由一台机器的平流程时间，流程时间=等待时间+加工时间目标函数：定义:为最大延迟量。目标函数：[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊16根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priorityrules)有：SPT---ShortestProcessTime,EDD---EarliestDueDate等,分别用于解决不同的问题。按什么样的准则来选择，对排序方案的优劣有很大影响。3.2常见单台机器排序问题的目标函数[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊17SPT（Shortestprocessingtime）法则优先选择加工时间最短的工序使工件的平均流程时间最短，从而减少在制品量EDD（Earliestduedate）法则优先选择交货期最早的工件可使工件的平均延期时间最小FCFS（Firstcomefirstserved）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平CR（CriticalRatio）法则CR是用交货日期减去当前日期的差值除以剩余的工作日数。关键比率最小的任务先执行。保证工件的延期数量最小3.3常用的优先顺序规则[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊18MWKR（Mostworkremaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近LWKR（Leastworkremaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成STR（SlackTimeRemaining）法则：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的任务最先进行。使任何任务（订单）最大延期最小RANDOM法则：随机地挑一个工件3.3常用的优先顺序规则[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊19例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间，采用SPT法则和EDD法则，求工件的加工顺序。大连理工大学经济系0501班姜珊20大连理工大学经济系0501班姜珊21EDD规则（优先选择完工期限最紧的工作）排序结果比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，减少在制品量，但平均延迟较大。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平，但平均流程时间较长。大连理工大学经济系0501班姜珊22流水车间(Flowshop)：工件的加工路线都一致。在流水线上制造不同的零件，即流水作业的排序问题。上面说的加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。本节主要考虑：（1）最长流程时间的计算（2）两台机器排序问题的最优算法4.1前言[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊23n/m/P/Fmax问题，其中n为工件数，m为机器数，P表示流水作业的排序问题，Fmax为目标函数。n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。假设：所有工件的到达时间都为零4.2最长流程时间的计算[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊24例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。序号为3的工件在序号为2的机器上的加工时间为6[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊25例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。按顺序S=(6,1,5,2,4,3)列出加工时间矩阵。615243Pi1244213Pi2544576Pi3555857Pi41432342712134+max{7,6}=11111520273317223035422125323846610121316[关键内容]:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划大连理工大学经济系0501班姜珊26约翰森算法（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工