搜索
第十一章制造业作业计划与控制•引言•通过MRP确定各车间的零部件投入出产计划，从而将全厂性的产品出产计划变成了各车间生产作业计划，将车间的生产任务变成各个班组、各个工作地和各个工人的任务。只有将计划安排到工作地和工人，任务才算真正落到实处。将任务安排到工作地，牵涉到任务分配和作业排序问题，这正是本章要讨论的。•11.1作业计划问题的基本概念•11.2流水作业排序问题•11.3单件作业的排序问题•11.4生产作业控制11收入、费用和利润要求掌握：1.最长流程时间的计算2.约翰逊算法3.一般流水作业排序问题的3种启发式算法4.相同零件的3种移动方式下机器加工周期的计算方法学习目的与要求重点最长流程时间的计算约翰逊算法相同零件的3种移动方式下机器加工周期的计算方法难点一般流水作业排序问题的启发式算法教学重点与难点生产任务的最终落实•MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。•各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务。•将任务安排到工作地，牵涉到作业计划。编制作业计划要解决的问题•由于每台机器都可能被分配了多项任务，就带来了零件在机器上加工的顺序问题。•编制作业计划要解决先加工哪个工件、后加工哪个工件的加工顺序问题•确定机器加工每个工件的开始时间和完成时间•例如;医院要安排病人手术，为此要安排手术室，配备手术器械、手术医师和护士。第一节排序问题的基本概念•一、名词术语•排序：确定工件在机器上的加工顺序。•作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划。•派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。•赶工：实际进度已落后于计划进度时采取的行动。•“机器”，可以是工厂里的各种机床，也可以是维修工人，表示“服务者”•“零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件•“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题二、假设条件和符号说明•假设条件：•1.一个工件不能同时在几台不同的机器上加工。•2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。•3.不允许中断。一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其他工件。•4.每道工序只在一台机器上完成。•5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。•6.每台机器同时只能加工一个工件有关符号•Ji：工件i，i=1，2，…，n•Mj：机器j，j=1，2，…，n•pij为Ji在Mj上的加工时间•ri为Ji的到达时间，指Ji从外部进入车间，可以加工的最早时间•di为Ji的完工期限•Ci为Ji的完工时间•Cmax为最长完工时间•Fi为Ji的流程时间，即工件在车间的实际停留时间•Fmax为最长流程时间•Li为工件的延迟时间•Lmax为最长延迟时间三、排序问题的分类•根据机器数的多少–单台机器的排序问题–多台机器的排序问题•对于多台机器排序问题，根据加工路线的特征，分成–单件作业排序(Job-Shop)问题–流水作业排序(Flow-Shop)问题•工件的加工路线不同，是单件作业排序问题的基本特征；•所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。•根据工件到达系统的情况–静态排序–动态排序•根据参数的性质–确定型排序–随机型排序4参数法•n/m/A/B•其中，n为工件数•m为机器数•A车间类型。在A的位置若标以标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般单件作业排序问题。当m=1，则A处为空白。•B为目标函数，通常是使其值最小•例如：n/3/P/Cmax四、作业排序方案的评价标准•1.工作流程时间•从工件可以开始加工至完工的时间，包括在各个机器之间的移动时间、等待时间、加工时间以及由于机器故障、部件无法得到等问题引起的延误时间等。•2.加工周期•完成一组工作所需的全部时间。它是从第一个工件在第一台机器上开始加工时算起，到最后一个工件在最后一台机器上完工时为止所经过的时间。•3.在制品库存（WIP）•在制品是对介于原材料和成品之间的生产过程中的产品的称谓。一个工件正从一个工作地移向另一个，由于一些原因被拖延加工，正在被加工或放置于零件库中，都可以看作在制品库存。•4.利用率•用一台机器或一个工人的有效生产时间占总工作时间的百分比来表示。五、优先调度规则•调度方法：•所谓调度方法，就是运用若干预先规定的优先顺序规则，顺次决定下一个应被加工的工件的排序方法。•一个工作地可选择的下一个工件会有很多种，因此，按什么样的准则来选择，对排序方案的优劣有很大影响。常用的优先顺序规则：•FCFS规则优先选择最早进入可排序集合的工件。•EDD规则优先选择完工期限最紧的工作。•SPT规则优先选择加工时间最短的工件。•SCR规则优先选择临界比最小的工件。临界比为工作允许停留时间和工件余下加工时间之比。•MWKR规则优先选择余下加工时间最长的工件。•LWKR规则优先选择余下加工时间最短的工件。•MOPNR规则优先选择余下工序数最多的工件。•RANDOM规则随机地挑选下一个工件。一般作业排序的目标满足顾客或下一道工序的交货期要求流程时间最短准备时间最短或成本最小化在制品库存最低机器设备或劳动力利用最大化•[例]一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间。下表显示了周一上午的情况，顾客的取货时间用从周一上午开始，还有多少工作小时来计算。发动机机壳所需标准加工时间（包括机器调整）预计顾客取货时间（从现在开始算起的所需工作时间）机壳1810机壳2612机壳31520机壳4318机壳51222机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳40333181815机壳2369912123机壳198171710177机壳51712292922297机壳329154444204424总数1021201838平均数20.43.67.6平均在制品库存=102/44=2.32个平均总库存=120/44=2.73个SPT规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。流程时间=等待时间+加工时间平均在制品库存=各工件流程时间之和÷加工周期平均总库存=各工件实际取货时间之和÷加工周期机壳加工次序开始工作加工时间结束工作流程时间预计顾客取货时间顾客实际取货时间提前小时数拖延小时数机壳1088810102机壳286141412142机壳4143171718181机壳317153232203212机壳532124444224422总数115118336平均数23.00.67.2平均在制品库存=115/44=2.61个平均总库存=118/44=2.68个EDD规则排序结果顾客实际取货时间基于以下假设：顾客不会在预定取货时间之前来取货；如果有拖延发生，他们将在加工结束时马上取走。比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，在制品库存更少。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平。优先调度法则•按SPT法则可使工件的平均流程时间最短，从而减少在制品量。•FCFS法则来自排队论，它对工件较公平。•EDD法则可使工件延误时间最小。•MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。第二节流水作业排序问题•流水作业排序问题的基本特征是每个工件的加工路线都一致。•加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。•对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。•排列排序问题：所有工件在各台机器上的加工顺序都相同的情况。一、最长流程时间Fmax的计算•n/m/P/Fmax问题，n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。•最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。•例有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序S=（6，1，5，2，4，3）加工时，求Fmax。i1234564231424567455875554243311iP2iP3iP4iPipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846二、两台机器排序问题•两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤：•（1）列出每个作业在两台机器上的加工时间。•（2）选择最短的加工时间，如果有两个相同的值，则任选一个。•（3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。•（4）对于剩余的作业重复第二步和第三步，直到整个排序完成。【例】求如表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474.5将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143【例题】•有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间：•（1）根据Johnson算法安排工作顺序；•（2）计算加工周期。任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5任务操作1所需时间（小时）操作2所需时间（小时）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2iCBDEA操作1操作2116.26.132635.95.35.120.35.55.20.90.3115.17.132.1【例题】根据Johnson算法求以下8/2/F/Fmax问题的最优解。任务aibiA96B72C103D81EFGH21545874•1.将所有ai≤bi的工件按ai值不减的顺序排成一个序列A；•2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；•3.将A放到B之前，就构成了一个最优加工顺序。改进算法工件号123456ai518534bi722474工件最优顺序：25614313455827474214813182631115222628aibi最优顺序下的加工周期为28练习•某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。•（1）安排生产顺序，使得在最短时间内完成生产。•（2）机器1共需工作多长时间？•（3）机器2应该在机器1开始工作后多长时间开始运转？任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.10任务在机器1上加工所需时间（小时）在机器2上加工所需时间（小时）A3.22.10B2.51.25C1.73.00D2.109.