基于TOC的作业计划方法研究

基于TOC的作业计划方法研究周红安田锡天贾晓亮耿俊浩（西北工业大学CAPP与制造工程软件研究所西安市710072）摘要：为解决车间生产不均衡以及作业计划工作繁杂的问题，研究了基于约束理论(TOC)的作业计划方法。该方法先找出生产系统瓶颈资源，然后根据基于启发式规则的调度算法生成瓶颈工序作业计划，再对瓶颈工序上下游工序按拉动式和推动式生产生成非瓶颈工序作业计划。文章首先论述了该方法的处理过程，然后详细分析了生产系统瓶颈识别技术以及基于启发式规则的瓶颈工序排序算法，最后通过实例验证了该方法的有效性。关键词：约束理论；作业计划；启发式规则ResearchonJobShopSchedulingBasedonTOCAbstract：Inordertobalancetheworkshopproductionandsimplifythejobshopscheduling,hasstudiedamethodofJobshopschedulingbasedonTOC.Themethodidentifythebottleneckoftheproductionsystemfirst；thengeneratetheoperationalplansofthebottleneckprocessbasedonheuristicrules；finally,theupstreamanddownstreamprocessesofthebottleneckareimplementedonthepullandpush-typeproduction.Thisarticlediscusstheprocessofthemethodfirst；thenanalysisthebottleneckidentificationtechnologyoftheproductionsystemsandheuristicrules-basedsortingalgorithmofthebottleneckprocesses；Finally，demonstratetheeffectivenessofthemethodthroughanexample.Keyword：TheoryofConstraints；ShopJobScheduling；Heuristicrules1引言生产车间作为制造型企业的核心部门，车间生产能力决定了企业的实际生产能力，而车间生产管理水平是决定车间生产能力的关键因素之一。作业计划作为车间生产管理的核心，合理的车间作业计划对提高企业生产能力起着重要的作用。近年来，以制造资源计划(ManufacturingResourcesPlanning，MRPⅡ)为核心的企业资源计划系统在我国企业中得到了较好的推广和应用。但MRPII存在三方面的不足：(1)能力约束考虑不足，往往造成生产计划无法完成、物料需求不切实际等情况；(2)不识别生产资源中的瓶颈，而瓶颈才真正控制了系统的有效产出；(3)生产计划与控制相分离，MRPII制定计划时不考虑控制，而通过事后反馈进行生产控制，相对于生产实际存在着无法避免的滞后[1]。因此MRPII不适合于车间级的作业计划管理。针对上述问题，本文结合约束理论(TheoryOfConstraints，TOC)[2]，提出了基于TOC的作业计划方法，并对该方法中瓶颈识别技术和关键工序作业排序等关键问题进行了深入研究。2基于TOC的作业计划过程TOC擅长于能力管理和现场控制，专注于资源安排，通过瓶颈识别、瓶颈调度，并使其余环节与瓶颈生产同步，保证物流平衡，寻求需求和能力的最佳结合，使系统产销率最大[3]。TOC编制计划的思想是：考虑计划期内的系统资源约束，先用有限能力排产法安排瓶颈资源作业计划，再以瓶颈资源作业计划为基准，把瓶颈工序之前、之间、之后的工序分别按拉动、工艺顺序、推动的方式排定，并进行一定优化，使非瓶颈的作业计划与瓶颈资源上的工序同步。TOC生产管理技术编制作业计划如图1所示：车铣瓶颈缓冲钻孔(瓶颈工序)清洗出货缓冲完成绳子绳子绳子派工单生产计划实际生产数量生产指令N产指令Y产指令图1TOC作业计划方法通过以上分析，可将基于TOC的作业计划划分为四个主要过程：能力需求计划与平衡、瓶颈资源识别、关键工序作业计划、非关键工序作业计划，如图2所示。首先，将生产需求转换成相应的能力需求，估算可用能力并确定采取措施，以协调生产能力与生产负荷的差距，避免因作业计划能力需求考虑不足而造成的生产计划无法按期完成；其次，找出生产系统中限制工作流整体水平的资源，即瓶颈资源，构造出车间的瓶颈资源网络和非瓶颈资源网络，流经瓶颈资源的工序称为瓶颈工序或关键工序，否则称之为非瓶颈工序或非关键工序；然后，编制关键工序作业计划，瓶颈资源通常任务多、时间紧，如何科学合理的安排瓶颈工序作业计划从而最大程度发挥瓶颈资源产能是关键问题；最后，以关键工序为基准，对关键工序上下游工序按拉动式和推动式生产进行作业计划，在作业计划时充分考虑到了工件在加工过程中各工序之间的先后关系，避免了生产控制相对于计划的滞后。图2基于TOC的作业计划过程能力需求计划与平衡是保证生产计划合理可行的依据，目前关于能力需求计划与平衡的理论和技术已很成熟。瓶颈资源产出决定了系统的产出，识别出系统瓶颈并最大程度利用瓶颈资源才能使整个生产系统产能最大化[4]。非关键工序作业计划的编制是以关键工序作业计划为基准。因此，瓶颈资源的识别和关键工序作业计划是基于TOC的作业计划方法研究的关键。本文将重点阐述工作中心瓶颈识别技术以及关键工序作业计划方法。3工作中心瓶颈识别基于TOC的车间作业计划编制的关键问题之一为制造系统瓶颈识别，只有识别了系统瓶颈工作中心，找到生产系统薄弱环节，才能进一步优化系统的物流，实现“鼓”、“缓冲器”和“绳子”的功能[5]。解决瓶颈识别问题的核心是根据瓶颈识别算法计算出各工作中心的负荷率，在此基础上通过工作中心间的约束关系，确定瓶颈工作中心的位置。车间从MRPⅡ系统得到零部件任务计划之后，由零部件的加工工艺信息、工时定额信息和加能力需求计划与平衡瓶颈资源识别关键工序作业计划非关键工序作业计划车间零部件作业计划工数量信息就可以得到相关工作中心在计划期内的负荷，并在考虑原计划的基础上就能确定本计划期内相关工作中心的可用能力，这样根据负荷与可用能力的比率确定工作中心的负荷率。计划期内工作中心负荷率的计算公式如下：TTLniik1式中：kL——工作中心k的负荷率；iT——作业i在工作中心k上的加工时间，含设备调整时间；n——工作中心k上总的作业数；T——工作中心k在给定时间内的可用能力；在一个计划期内可能存在着多个负荷率比较大即负荷紧张的工作中心，通过以上对资源负荷的计算我们将负荷率（实际负荷/额定能力）大于一定值(比如90%)的工作中心定义为约束工作中心。约束工作中心并不一定就是制造系统瓶颈工作中心，而要根据约束工作中心的关系才能确定制约系统产出的瓶颈工作中心。如图3所示，a、b中约束工作中心1和2之间存在着关联，以负荷率较大的约束工作中心为制造系统的瓶颈工作中心，c中约束工作中心之间没有关联，相互独立，则约束工作中心1和2都为制造系统的瓶颈工作中心。约束工作中心1约束工作中心2a.约束工作中心1约束工作中心2b.装配中心约束工作中心1约束工作中心2c.市场图3约束工作中心的几种关系4基于启发式规则的瓶颈工序排序识别出瓶颈工作中心后，处在瓶颈工作中心上加工的工序即为瓶颈工序，瓶颈工序是限制整个生产系统产出的薄弱环节，在瓶颈工序上损失或浪费多少时间，整个生产系统就会损失或浪费多少时间。因此，应将瓶颈工序作为整个生产系统控制的重点，尽最大的努力，使瓶颈工作中心满负荷工作。如何进行作业排序，许多生产管理研究者进行了大量的研究工作。目前，对于大规模的排序问题，按启发式规则的排序算法是最有效的[6]。4.1排序规则的确定目前调度规则很多，随着追求的目标不同，其规则也不同[7－9]。笔者采用的调度规则如下：1．剩余能力量最大的瓶颈工作中心先安排；2．当瓶颈工作中心正在加工的负荷量相同时，交货期早的工件优先安排；3．当瓶颈工作中心正在加工的负荷量、工件交货期均相同时，优先安排剩余加工时间最长的工件；4．当瓶颈工作中心正在加工的负荷量、工件交货期、工件剩余加工时间均相同时，优先安排剩余工序数最多的工件；5．当瓶颈工作中心正在加工的负荷量、工件交货期、工件剩余加工时间和工件剩余工序数均相同时，优先安排瓶颈工序加工时间最长的工件。4.2瓶颈工序启发式排序算法根据启发式排序规则，瓶颈工序的启发式排序算法如下：STEP1：确定D（初始D=0）时刻在瓶颈设备kw类机器前等待加工的工件数wkn；STEP2：确定D时刻在瓶颈设备kw类机器上可安排的机器数wkm；STEP3：当wkn＞wkm时，转向步骤4。否则全部等待加工工件均可以在wkm台机器上安排。按照以下方法：·首先求出wkm台机器在D时刻前已经安排的负荷量，并按照从小到大的顺序排列；·其次，将等待加工的wkn个工件，按交货期从小到大排列；交货期相同的工件，按工件剩余加工时间从大到小排列；剩余加工时间相同的工件，按工件剩余工序数从多到少排列；剩余工序数相同的工件，按将要安排的瓶颈工序的加工时间从大到小的次序排列；·按照已安排好的工件、机器排序，依次将工件的瓶颈工序安排在相应的机器上。然后转向5；STEP4：此时，wkn＞wkm，将有wkn-wkm个工件在D时刻无法安排。首先安排wkm个工件，选择工件并对它进行排序的方法参照步骤3中的方法。其次安排剩余的wkn-wkm个工件，如wkn-wkm依旧大于wkm，则继续优先安排前wkm个工件，直到剩余未安排的工件个数小于或等于wkm个工件，然后转3中各子步骤；STEP5：直到所有工件安排完，结束。5算例本文以某车间生产某种型号产品的一条生产线为例，该生产线每七天为一个计划期，每个计划期生产30套该型号部件。当生产任务逼近或超出车间生产能力时，产品的出产率就会受到瓶颈设备的限制，因此生产计划的重点应放在瓶颈设备上。经过瓶颈识别算法确定该生产线上的关键设备的种类，已知关键设备台数以及关键零件A、B、C、D在每种设备上的加工时间如表1：表1零件在各关键设备上的加工时间表零件2×1M2×2M1×3M2×4M4×5M工时工时工时工时工时A2.51.51.5134B41312.51125.51C0.751D6.54采用上述算法制定的关键设备的计划期内的作业计划如表2：表2关键设备作业计划表计划零件1M2M3M4M5M12121212341A52B3336822CD112A63B43371033CD223A63B43371033CD224A613B4337233CD225A6633B33333CD1226A11233B333C1313D2227A1233B332C1717D221工时97101.569.569.51226664105.59886.580通过分析可以看出:(1)各关键设备负荷均衡表3列出了各设备每日的能力需求，从中可以看出各设备每天的能力需求围绕在计划期平均水平小幅度波动，并且同种类的设备负荷基本持平；(2)各工件加工连续性好各设备都是在完成了某一工件的加工任务后再加工其他工件，减少了设备调整时间，从而使设备更多的时间处于工作状态，最大程度发挥了设备的生产效能；(3)关键设备利用率高从表3可以看出各关键设备基本满负荷作业，闲置率相当低，瓶颈资源产能得到了很好的发挥，从而可以提高整个生产系统的产能。因此，该方法能够较好的解决车间生产作业计划中存在的实际问题。表3设备日负荷表（单位：小时）日期1M2M3M4M5M1212121234113141010141010121210.510.5216159917.510916.516.51313316159917.510916.516.51313416159917.59916.516.51313512159917.59916.510.5131361215.510.7510