车间作业计划调度四篇

2024-07-07

车间作业计划调度篇1

车间作业计划(Production Activity Control,PAC)是依据主生产计划(MPS)而编制的具体执行工作方案。它把车间的生产任务落实到每个人、每台设备上,是车间组织生产的依据,也是企业管理中最重要的部分[1]。PAC的实施贯穿于生产系统的各道工序,受很多因素的制约。随着生产规模的扩大和复杂程度的提高,PAC的实施与调度也出现了一些问题。本文应用车间作业调度方法,针对当前PAC与调度中存在的问题进行研究,为企业提供优化的生产作业排序和车间作业调度策略,从实践与理论方面提升PAC及其调度水平,以提高制造系统的运行效率,增强企业的市场竞争力。

1 PAC与车间调度的内涵与特点

PAC系统是一个高度复杂的系统,它有效综合了机械、信息、网络等资源。制定PAC是为了使生产设备、物料、人员和信息四者匹配,实现车间均衡、协调、持续生产。在PAC生产执行过程中,决策部门需要根据车间的生产能力及其他资源的使用等反馈情况不断地调整PAC,而调整计划贯穿于企业生产活动的全过程。因此,要最大限度地发挥生产系统的柔性潜力,满足市场需求。

1.1 PAC与车间调度的界定与内涵

PAC的编制包括确定操作顺序、分配资源和制定期量标准等。PAC与车间调度问题是一个典型的任务集,包括资源集、约束条件集、性能指标集。其中,资源集包括人员、设备、工具和材料等,而每台设备可以完成一种或多种作业,不同设备能完成的作业集可能相同也可能不同;约束条件集用以规定生产过程中需要的条件,如任务的优先级、每个作业要求完成的时间、资源的能力、生产工艺、质量标准等;性能指标集用以规定生产过程中需要优化的目标,如生产周期、在制品量、订单交货期、资源利用率和生产成本等。每一个任务都包含一组需要执行的作业序列(工序),而这些作业序列需要占用系统的机器、工具等资源,并且必须按照一定的工艺顺序执行。

调度的目标是为作业合理分配资源,为每一个加工对象合理安排具体的加工顺序、路径、时间、制造设备资源和操作等,使内部和外部约束条件被满足,其中内部约束主要为企业的资源约束、能力约束和生产过程中的技术约束等;外部约束主要为订单规定的时间要求和品质要求等,同时使大部分生产性能指标得到优化。在有限产能、库存容量及资源的约束下,通过优化配置生产资源来提高PAC的可实施性以及生产过程的可计划性、可控性[2,3]。而车间作业调度与控制则是实现生产高效率、高柔性和高可靠性的关键环节。

1.2 编制PAC的特点

在编制PAC过程中应考虑其如下特点:

(1)实用性。

以在制品加工进度为基础编制工序能力计划,使PAC紧跟生产现场,达到计划编制与生产节拍的和谐统一。PAC计划期短、计划内容具体、计划单位小等,可操作性强。

(2)合理性。

综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素,通过合理的排程方法,达到满足交付和有效利用资源的目的。

(3)计算机模拟与预见性。

采用“模拟和预测”的方式,帮助计划员提前预测未来计划的执行情况,而且通过模拟可以导出最优工序排序方案、瓶颈和薄弱环节,找准切入点,分析模拟输出结果,从中选择出较满意的PAC方案,该方法可提高管理质量及效率。

(4)平衡性。

以零组件交付需求为依据,不断地平衡和处理任务与生产能力、计划与实际的关系和矛盾,特别是设备负荷的平衡和生产现场问题的有效处理,将进一步强化生产现场组织、协调与控制。

2 PAC与车间调度存在的问题

PAC处理问题的广域性、动态性和多约束性使PAC的编制容易产生各种问题[4]。加之生产环境具有不可预测性、多变性、随机性、干扰性和经验性等问题的存在,PAC的编制成为企业生产管理中的一个难点,许多问题至今尚未得到很好的解决,例如数据处理、加工排序、库存、批量与加工瓶颈等问题,这些问题都影响到PAC的适应性和效率。当前PAC与车间调度存在的主要问题如下:

(1)生产实际情况与PAC冲突。

在客户要求订货批量愈来愈少、品种愈来愈多和交货期愈来愈短的情况下,生产线负荷和能力的调控越来越复杂,不但耗费大量人力,还经常出现生产异常情况,使生产和交货脱节。另外,由于PAC的制定多考虑按时交货,少考虑生产线能力的限制,经常造成实际生产偏离计划。实际生产环境中存在着大量的随机事件,一方面由于产品的品种多,工序复杂,产品的工艺过程经常变更;另一方面又常常会面对紧急订单、订单变更及订单取消等异常情况,又很难预测订单在什么时候到来。虽然产品订单是生产制造部门的任务标的,但由于产品订单签约日期、签约产品类型和数量具有不稳定性,如果将其直接作为生产制造部门的任务来源,则会造成生产制造部门生产的波动,破坏生产过程的均衡,一旦计划与实际的出入过大,将难以保证客户订单按时完成,影响企业的交货信用。企业要快速响应市场需求必须及时发现PAC同实际的偏离,并不断改进,同时也需要PAC能适应客户需求和客观环境的不断变化。但如果一味追随变化,朝令夕改,势必造成生产上的混乱。因此控制计划变动是保证计划可执行程度的重要内容。显然,期望通过不断地调整企业本身的生产资源去适应和匹配不可预测的、动态变化的订单任务是不现实和不可行的。事实上,需要进一步分析产生上述生产系统不平衡和频繁更改现象的原因,很多情况可能是没有系统合理考虑加工资源而造成的。由于企业内外部环境不确定因素的影响,虽然智能型生产系统在一定程度上能缓冲静态作业计划与动态调度间的矛盾,但依然无法从根本上解决计划与调度间的脱节问题。如果将车间内所有班组进行实时调度,由于在普通机床上零件的加工工序不能确保加工时间以及加工质量,加工执行情况必须依赖人工录入的信息,即使按照工艺规定的辅助工时和加工工时进行预先的安排,但普通机床实际的加工结果必须等待人机交互录入后才能进入计算机以及数据库管理系统,因此势必影响后续工序的安排和调度。

(2)不同生产条件下,PAC编程方式也不同。

PAC的编制者可以选择不同的优化目标,对不同的优化目标,又可以采用不同的排序方法,不同的排序规则编排同一作业计划时也将产生不同的排序结果;不同的目标影响调度的具体模式;在不同的制造资源、约束条件、生产规模、生产形式和管理方法下,车间调度问题的调度策略及其数学模型一般不同;不同企业因生产过程不同,其生产组织和管理也有所差异,计划员对现场掌控不同所得出的结果也将不同;即使同样的生产计划经验,同样的设备和人员,所安排的生产计划也略有差异;企业的生产类型和生产组织形式不同,采用的有关生产期限和生产数量的标准即期量标准也将不同;企业性质不同生产结果和方式也不尽相同;按照约束条件去安排,无论是拉式生产,还是推式或混合式生产,其生产方式不一样,计划的安排方式也不一样,不同的编制方式其结果往往差异很大;生产计划还与所处的环境有关系,如果企业周围有着良好的工业环境,距码头近,则计划的方式和生产方式也存在着差别;客户不同安排的结果又不一样;生熟手不同,产生的效率也不同。如果作业分配和排序安排不当,将出现人员或设备窝工,生产周期拉长,急件和缺件不断生产等复杂的问题,只按经验或随意安排作业,导致生产的全面被动乃至恶性循环。另外,PAC编制存在两大问题:第一,在当月PAC尚未执行完毕时,过早地编制下一个月的计划,结果造成当月生产实际完成量与计划量的偏差及用户和市场需求情况的变化,造成计划与生产脱节;第二,在当月PAC全部执行完毕时再编制下一个月的PAC,结果造成生产连续性缺乏必要数量的在制品储备和当月投料、当月加工、当月装配被动的局面。PAC的制订应与企业当前的生产状况相适应,投料过早或过多,各加工中心的在制品数量增加,等待时间延长,导致生产周期增加,系统稳定性变差;投料过少或过晚,系统利用率低,造成产出降低、订单延误。

(3)影响PAC因素的多样性而导致其变动。

影响PAC及其调度有各方面因素,识别这些影响和干扰具有一定的困难。车间制造环境的复杂性、生产加工任务和调度目标的多样性,系统加工任务的动态性,使得PAC和车间调度存在一定的复杂性和困难。由于大量不确定因素的存在,传统的PAC与控制模式存在作业计划与现场调度相脱节的问题,目前PAC的研究与制定大部分逐层进行,往往是上层计划的可行性到下层计划编制实现时才能验证。这样既加大了车间调度的难度,又使作业计划流于形式,生产控制目标难以实现。在PAC编制工作完成以后,付诸生产实施时,由于作业计划考虑的是静态情况,而实际生产过程是动态的,无论编制PAC时考虑多么周密,安排如何具体,也无法预见实际生产过程中的所有变化。PAC将随着市场、加工时间、加工路线等生产影响因素和约束条件的变化而变化,在实施过程中也不是一成不变。在生产中,由于生产能力的变化,前一周期任务的延期完成、废品的产生都可能影响PAC的完成。另外,停机、停工、准备时间的变化,可用原材料的减少等也都是影响PAC完成的因素。尽管制定PAC时已经充分考虑了现有的生产能力,但由于其在实施过程中受到各种因素的影响造成事实情况与计划要求不符或偏离,这种差异主要表现为生产进度和生产数量的不一致;多品种产品的总需求量及其比例的预测与实际情况的差异;特定品种的需求预测和实际情况的差异;订货计划和实际需求情况的差异;计划产量(计划时间)和实际产量(实际时间)的差异;库存量的变动和产品中断发生的差异,此外还有因设备故障和出勤情况变化而造成的工作效率变动。因此,PAC能否得到有效执行,不仅仅取决于该计划是否完善,还取决于对一些不可预见的突发事件的处理,如原材料供应变化、生产任务变化、工件加工质量达不到要求而被迫返工等。在制定PAC时,有可能面临着原料供应、产品需求量、产品价格等都是不确定的,无法提供计划所需材料(比如由于供方失约、原材料短缺等原因),不得不减少甚至停止生产。当出现下列情况时,PAC也要进行调整与修改:市场对产品的需求发生变化;经营方针、目标发生变化;企业微观经济效益、宏观经济效益发生变化和其他宏观控制条件变化;季节性变化;人、财、物等资源供应条件发生变化;专业化、协作者关系及其组织形式发生变化。

(4)外部动态性和内部相对静态的矛盾。

在实际车间调度中,不仅需要考虑管理人员、制造人员的技术水平,刀具、夹具、量具、检具、物料转序等因素,还需考虑产品的投产期、交货期、生产能力、加工顺序、制造设备和原材料的可用性、生产批量、加工工艺路径、成本限制等其他因素,以及生产作业调度和制造资源调度。尽管影响车间调度问题的因素很多,但有些约束条件必须满足,如交货期,生产能力等,而有些只需控制在一定的范围之内,即可把相互矛盾的目标做到相对平衡,如生产成本,这些约束在进行车间调度时可以作为确定性因素处理。实际车间调度问题的难度远超过经典车间调度中的排序问题,其中诸多因素影响调度决策,如市场、技术、人员、资金、经营管理、制造资源。企业生产的内部要素,即企业的生产资源和生产能力,相对来说是确定的、静态的。因此,外部动态性和内部相对静态性二者之间的不匹配和冲突干扰不可避免地成为单件订货型生产系统的固有特性,造成了生产系统的不平衡性,主要表现在两方面:某些时段订单多,任务量大,企业出现某些资源紧张,负荷率大甚至不堪重负,不得不通过频繁大量的加班或外协来完成生产任务;在另一些时段,生产负荷与资源的这种关系可能倒置过来。因此投产批量的设置必须在一个可控的范围内,既不能批量过小导致当前设备利用率过低,也不可以批量过大而导致在制品库存过大,影响到其下道工序的投产时间。在制订作业计划时如果没有考虑系统瓶颈,当出现异常情况,瓶颈发生漂移时,也没有相应的应对措施,就无法实现均衡生产。

(5)PAC和组织管理方式不当。

生产组织管理方式不恰当容易引起生产线能力不平衡,设备维护不到位,因此造成各工段的工作进度不协调,出现等工现象或者堆满了物料等待加工。PAC安排不合理,负荷分布不均衡,无法做到均衡生产,企业的PAC执行率低下。物料的生产和采购期量系统不够健全,物控跟催采购物料进厂状况,在核查时疏忽或责任没到位造成停工待料。而供应商来料不合格、技术资料延迟、采购计划错误、材料标准错误和合同评审程序失效所引致的PAC的时常变更,导致采购部与供应商无法跟上。生产需求的随机性导致生产需求变化和生产瓶颈无法预测时,人工生产排程困难,资源不能充分利用。此外,原材料短缺对PAC带来很大冲击,使企业不能正常安排生产,计划不能按时完成,有些企业为了保证信誉度,保证订单的交货期,不得不以高价购进原材料来维持正常的生产,从而造成经济损失。物料在系统中通过时间太长,设备利用率低,紧急订单得不到及时处理。备料导致无法跟进生产计划而促使计划变动,计划、生产及物料进度不能协调同步进行。物控工作失控造成生产物料不足或过多。销售计划淡旺季预测不准确,造成人员招聘的无计划,影响企业士气,还影响生产效率和资源的利用。客户天天催货,计划部频繁更改出货计划,生产部门时而待料,时而通宵加班等,造成客户抱怨、取消订单甚至索赔。这些由于生产计划的频繁变化所致使的生产现场和生产循环的混乱,严重影响客户满意度。生产经营紊乱引发质量失控造成经常性返工或返修,进而影响PAC的执行。面对频繁的计划变化,生产计划部的工作任务极其艰巨复杂,很难保证计划与控制的质量,生产计划员苦不堪言,加上对实际生产控制缺乏理解,因此常出现所谓的“车间经验”的问题,即忽视目标与实际能力之间的相互关系,导致生产控制恶性循环。如果需要通过加急任务和特别行动才能将最重要的任务按时完成,企业往往采取的措施是进一步加长生产周期,这个循环将会变成一个恶性时间螺旋,它只有在远远高于实际所需的生产周期和更大的偏差水平上才能够稳定下来,从而造成更大的浪费与等待。

(6)调度业务考评办法不合理。

以结果为导向的经济责任制考核办法未体现调度考核职能,它主要考察该单位部门是否完成PAC的各项任务,而对实际生产过程中各项生产指令执行情况以及生产中出现的问题存在不报或延时报告现象没有进行考核,造成车间调度指令经常得不到落实或落实不及时,政令不畅通,影响生产顺利进行。同时,调度在日常检查工作发现工艺过程中存在的问题很难及时纠正,下达的调度指令缺乏“震慑”力,调度室对调度员尚未建立考核办法和相应的考核机制来充分调动调度员工作积极性。

3 PAC的编制流程、方法与调度原则

3.1 PAC的来源及编制流程

编制PAC要解决两方面的问题:一方面保证交货期;另一方面保证企业在生产车间相互衔接。它反映两个主要的变量关系:期与量。期,即计划的时间变量;量,即生产计划的数量。一个典型的制造车间生产活动主要工作流程是:

(1)生产订单由销售订单分解及综合重组而得,它是销售订单与生产之间的中介。计划人员根据原料供应情况、车间设备状况对某一时间段内(如一周、三天等)到达的所有客户订单进行分析,如产品类型、数量、客户重要程度等因素,采用一定的算法,将多个合同进行归并,并根据交货期、设备能力和生产工艺等限制性要求进行最佳组合,使前后工序紧密衔接,减少等待时间。根据交期与资源,对订单进行评估,当出现生产不能满足订单要求时,生产部门需要和销售部门进行信息交流和沟通,最后得出生产订单,即MPS。

(2)PAC依据MPS完工时间,物料需求计划中各零件计划到位时间以及产品的加工次序进行任务分解,然后根据一定的规则,确定各子任务的加工设备,而任务单的开工时间则根据订单下达日期、任务单计划入库日期、相关的工艺信息、生产技术准备工作以及各加工单元的当前加工计划来统一决定,实现PAC有赖于各项工作的落实。在编制出理论计划以后,就形成了各加工单元的负荷。

(3)平衡各加工设备的加工能力与工作负荷,制订派工计划和相关物料准备计划。初步确定若干种可行方案,在计算出各方案的总成本后择优选择,确定加班、转包等生产能力。同时,根据物料、工装等条件及各加工单元的反馈信息,制订出正式可行的作业计划,分配到各工段或班组中,充分利用瓶颈环节生产能力,准时提供零部件,同时尽量使设备负荷均衡并使在制品库存尽量减少,保证生产中心按期完工。车间计划、车间作业、车间调度根据车间生产能力和资源状况信息,为计划资源作优化调度。当生产作业的加工对象不止一种时,为了加快生产进度、缩短加工时间,需要合理地安排生产作业顺序。

(4)车间分配任务有两种方式:一种是将零件的所有加工任务分配到一个工段或班组;另一种是根据各工段或班组设备、人员的特点将零件加工的工序分别分配到不同班组。前一种方式需要班组调度人员同车间调度人员密切协作,以便将不能在本班组加工的工序安排到其他班组或外车间进行加工,后一种方式需要车间的车间调度人员及时了解生产的执行情况,随时根据具体情况重新调度和安排生产。现车间大多数都采用第一种方式进行任务的安排,以方便对班组进行统一考核和人员、生产质量的管理。在复杂的车间里,调度人员接到厂区下达的PAC以后将这些任务分解成零件任务分发到各个工段,由工段调度员根据本工段的当前任务将零件任务分派到各个班组或工人,班组严格遵照生产制造单组织生产。

3.2 PAC日程计划的制定要求

如何对计划进行生产预先设定时间、顺序、不同产品和批量衔接等,是日程计划要明确的事项。企业的生产活动是一个涉及面广而复杂的体系,要使该体系顺畅运作,计划部门需要与销售、研发、生技和资材等相关职能部门合作,经过系统的生产日程计划和安排,为各部门的生产提供依据,确保全面、有序且高效地运作。

(1)生产流程的衔接。

同一件产品在生产流程的时间安排上需要衔接,以保障半成品的顺畅流动,部门与部门之间需保留1/3或半天的缓冲量,以避免出现衔接不上或堆积太多等问题。任何PAC总是在某个时间点上开始执行并跨越某个时段,它总是在前一个计划的基础上(初态)进行调整和修订,故计划问题实际上是再计划,它必须能够适应和兼容生产系统的初态,它还应该为下一个计划留有余地,这就要求计划具有继承性、可扩展性和兼容性。

(2)操作顺序的安排。

在实际生产环境中,操作顺序十分复杂甚至是动态变化的,因不同的设备有不同的加工时间、加工特性(如新设备与旧设备、通用设备与专用设备等),所以加工操作顺序依赖于设备的选择。一个好的作业计划的各种加工操作顺序有高度的弹性。

(3)作业分配的确定。

依据作业日程计划,将作业分配到每个作业者和设备中,同时指派有关部门或人员准备作业。作业分配一般以指令单形式发放,操作员要与所分配的工作相适应,头道工序需要由判断能力强、稳定性好的人员操作,难度系数高的工序应分配给技能熟练的工作操作者,与主流程结合的工序要安排注意力集中且判断能力强的人员操作,此外,人际关系不和谐的作业人员应尽可能分开工作,缺勤率高的员工应安排做辅助性工作。

(4)短缺和富裕的生产能力调整。

由于生产的一次性、经验性及生产系统中诸多意外扰动事件,企业不可能将所接订单任务和剩余生产能力匹配到十分精确的程度,加上客户不愿妥协于企业生产系统的现状而改变交货期,那么在订单确定的交货期条件下,计划期内的所需设备的生产负荷率不可能恰好等于100%。对负荷率超过100%的设备,可以通过对某些零件进行适当、可行的工艺更改或组织外协来转移部分生产负荷,还可通过组织加班来提高设备的剩余生产能力,从而达到降低设备负荷率的目的;对于所有设备负荷率均较低的情况,可以通过将计划的终止期适当提前和降低计划期内的剩余生产能力等途径,达到提高设备的负荷率的目的。

3.3 PAC的编制方法与柔性调度原则

PAC的编制应根据不同生产类型采用不同的编制方法,企业应建立合理的作业计划,实现均衡生产,完成生产任务,进而实现企业的绩效指标有重要作用。PAC中的排产方法主要有正排法、倒排法、平行排产法以及偏置法和覆盖法等。另外企业还可根据实际生产情况,采用固定周期计划法和投产计划法相结合的方法编制PAC,既可以保证企业生产的连续性和稳定性,又能兼顾计划制定的灵活性[5]。多品种中小批量生产企业的PAC管理受许多方面复杂因素的影响,要编制出满意的PAC,不仅要求及时、准确、完整地收集大量的内外部信息,采用先进的计划方法,还需要结合PAC管理决策人员与专家的知识。

在敏捷化、全球制造的新形势下,车间调度研究面临着许多新问题,迫切需要科学的调度方法和调度机制来解决。虽然企业最终采取的排序方式取决于决策部门的排序目标,但完成这些目标,还取决于设备、工艺以及人员的柔性,而获得这种柔性,与作业方法改善、设施规划、缩短作业交货期、制造单元技术和群组技术等相关。因此,柔性车间调度需要注意以下原则:

(1)创建时间原则,即按订单创建时间来排序,其优点是操作简单,缺点在于忽视了数量不同所需的加工时间也不同,同时还忽视了生产的均衡性;

(2)处理时间原则,即优先处理加工时间最短的订单,优点是能有效降低订单的平均等待时间,缺点是忽略了交货时间和设备的利用率;

(3)交货期原则,根据订单的截止期限来排序,即优先执行到期时间最早的订单,此原则表面看可以尽可能地满足交货期限,但实质上忽视了产品之间加工难易程度及所需加工时间;

(4)剩余时间原则,即优先选择剩余处理时间最短的订单来执行,该原则虽提高了系统的整体性能,但可能导致单个订单的执行被延误。

由此,我们可以得出PAC工序的柔性调度规则如表1所示:

由表1调度优化规则,综合某几个调度指标加以平衡,现优化归纳如下:

(1)剩余能力量最大的瓶颈设备先安排;

(2)当瓶颈设备正在加工的负荷量相同时,交货期早的工件优先安排;

(3)当瓶颈设备正在加工的负荷量、工件交货期均相同时,优先安排剩余加工时间最长的工件;

(4)当瓶颈设备正在加工的负荷量、工件交货期、工件剩余加工时间均相同时,优先安排剩余工序数最多的工件;

(5)当瓶颈设备正在加工的负荷量、工件交货期、工件剩余加工时间和工件剩余工序数均相同时,优先安排瓶颈工件;

(6)将等待加工的n个工件,按交货期从小到大排列;交货期相同的工件,按工件剩余加工时间从大到小排列;剩余加工时间相同的工件,按工件剩余工序数从多到少排列;剩余工序数相同的工件,按将要安排的工序的加工时间从大到小的次序排列[6,7]。

4 PAC的评价指标

制造业是一个微观的经济系统,除了以宏观经济系统作为自己的依存环境,还需在产、供、销、储、运等方面搞好内部与外部的协调和配合,才能保证企业的生存和发展,获得良好的经济效益和社会效益。因此,必须用科学的决策手段来制定科学的PAC以保证企业未来的生产经营活动正常、均衡、连续地生产。由于生产过程与生产环境的动态性、生产领域知识的多样性和车间调度影响因素的复杂性,计划人员必须将制造人员、制造资源、约束条件、数学方法、信息技术、生产规模和车间调度方法综合考虑,对车间调度结果进行定量分析与评价,然后根据定量评价结果反过来指导车间调度。

PAC评价的目的是为了判断计划的优劣。但在评价过程中由于评价指标不唯一将带来一系列问题,这些问题可以通过建立“计划围着合同转,生产围着计划转”的体系,以及计划调度对车间领导负责,车间调度对计划调度负责,班组长对车间调度负责,工人对班组长负责的生产控制体系,使各种关系明确,从而为PAC评价的执行提供有力保障。

PAC和车间调度性能目标大致可以归结为3大类:(1)最大能力指标,包括最大生产率、最短生产周期等;(2)生产成本指标,包括最大利润、最小化运行费用、最小投资、库存最小、最大收益等;(3)客户满意度指标,包括最短延迟时间,最小提前或者最小拖后时间等。快速准时的交货要求已影响了这些目标的权重,更加强调交货期、产销率和低库存。PAC指标体系如表2所示。

车间作业计划调度篇2

当今,面对竞争激烈、动态多变和订单驱动的市场,制造企业的竞争优势在于快速反应产品和需求的动态变化,而采用机群或(常规)成组技术组织生产,无法根据任务的变化动态调整,不再是实现每一次加工任务的最佳配置,影响了系统柔性和快速反应的性能,同时还造成了资源的浪费。20世纪80年代美国提出虚拟制造的概念,虚拟制造单元主要的机器共享和布局上与传统的制造单元存在差异[1]。同时在成组技术基础上的虚拟单元在计划和控制能减少机器准备时间,增强系统柔性,及时应对突变的情况[2]。而且虚拟制造单元还能有效利用企业内外部资源,提高系统生产率,通过对制造资源优化组合,可以缩短任务的完成时间,其目标就是利用不同位置的现有资源,快速、高质量、低成本地完成加工任务。因此,如何组织虚拟制造单元以及在这种组织下如何安排作业计划与调度是面临的一个问题。

随着多代理技术在先进制造系统中的应用得到迅速发展,Agent所具有的自主性、交互性、反应性等特点为解决车间任务的计划与调度问题的求解提供了一个非常有效的方法。在基于代理的计划与调度中主要有招投标的方法和非招投标的方法,而前者是代理(管理者)将任务分解为可操作的子任务,具有能力完成子任务的其他代理对这些子任务进行招投标,以满足目标函数。在基于招投标的计划与调度研究中,普遍采用都是由上层Agent(单元控制Agent等) 直接根据工序任务对设备 Agent进行招标[3,4,5,6],而设备Agent只考虑的是本工序的加工任务,忽略了整体任务的前后工序间的联系,最终产生的不一定是最优的方案。因此,本文采用面向任务的虚拟制造单元的方式来组织生产,在任务计划时考虑前后工序的约束,同时为更好地满足交货期的要求,设计推动式/拉动式的招投标策略,在确定计划方案时,不能以某个竞标资源完成单个任务最优为评定依据,而应以整个任务总体完成效益最佳为目标。

1基于招投标机制的车间任务计划模型

在车间中,虚拟制造单元是随着任务的产生而产生随任务的结束而消亡的,具有一定的生命周期。其生成针对某一个具体的生产任务,由这些加工设备不在同一位置,在逻辑上形成一个虚拟制造单元,更确切地说应该是面向任务的动态虚拟单元。本文通过任务而组建的虚拟制造单元是建立在代理的基础之上的,采用招投标的形式确定任务的加工设备而形成任务计划。主要有车间代理(shop agent)、任务管理代理(task management agent)、任务调度代理(task scheduling agent)、虚拟单元代理(virtual cell agent)、资源管理代理(resource management agent)、资源代理(resource agent),模型如图1所示。

上述模型中,GA相当车间主任的角色,是上层生产计划的接口,主要负责任务的接收。TMA负责任务的评估与分解,确定任务的优先级,并由此形成任务对应的VCA。VCA是面向任务动态生成的,任务完成时自动解体,并且有一个由TMA赋予的优先级。根据优先级大小来启动任务招投标活动,选择完成任务所需的资源。TSA负责任务的调度,当有多个相同优先级的任务需要招标时,根据其封装的算法来确定调度结果。RMA负责车间中资源管理、配置及监控,记录其数量、位置、功能及状态等信息。RA代表车间中资源实体,主要根据自身状态对任务进行招投标。

2任务计划的招投标过程

面向任务组建的虚拟制造单元的目的就是根据生产的实时信息进行任务动态分配,任务分配的结果就相应地形成了任务的作业计划。作业计划的制定是资源代理之间相互招投标来实现的。在准时化生产下,为更好地保证任务按时交货。在考虑任务前后约束的基础上,设计了拉动式与推动式招投标策略。

定义:工件Ji的第j道工序为当前工序,则工件Ji的第j道工序之前的所有工序称为前继工序,工件Ji的第j道工序之后的所有工序称为后续工序,Ji,j-1为Jij的紧前工序,Ji,j+1为Jij的紧后工序,工件Ji的第一道工序称为首工序,最后一道工序称为尾工序。

2.1招标策略

2.1.1 拉动式招标策略

拉动式招标策略定义为:以任务的工序为正向,调度Agent根据任务的交货期或紧后工序要求的最迟完工时间etj_latest向任务工序的可用设备进行招标,由于这些机器代理只有能力完成自己的任务工序,对选择投标的机器代理,根据招标信息和自己完成该道工序所需的加工时间推算出该工序的最迟开始时间stj_latest 并将不能完成的前道任务工序向紧前工序的机器代理招标,依次循环,直至首工序完成招标活动。尾工序的确定规则是尽可能接近交货期(因为可能会出现提前或拖期的状况),工序的最迟开始时间stj_latest通过公式(1)来计算,根据公式(2)计算紧前工序的最迟完工时间,以此对紧前工序的招标参数。在公式(2)中,tranj,j-1是设备之间的运输时间,具体由车间实际情况而定。

$\begin{array}{l} s t_{j_l a t e s t} = e t_{j_l a t e s t} + t_{j_基本加 ⌶ 时间} + \\ t_{j_加 ⌶ 辅助时间} + t_{j_加 ⌶ 调整时间} (1) \\ e t_{j_l a t e s t} = s t_{j} + t r a n_{j, j - 1} (2) \end{array}$

2.1.2 推动式招标策略

推动式招标策略定义为:调度代理首先向任务的首工序的可用资源代理发出招标信息,首工序的设备招标不给定招标参数,由资源Agent根据当前时刻确定本工序最早开始时间,并计算完成本工序的结束时间,以此作为招标参数向紧后工序招标,直至尾工序。假设紧前工序的虚任务(没有进行评标的任务)的完工时间为etj-1, 那么当前工序j可以按照公式(3)、式(4)分别计算本工序的最早开始时间和完工时间。

$\begin{array}{l} s t_{j_e a r l i e s t} = t r a n_{j, j - 1} + e t_{j - 1} (3) \\ e t_{j_e a r l i e s t} = s t_{j_e a r l i e s t} + t_{j_基本加 ⌶ 时间} + \\ t_{j_加 ⌶ 辅助时间} + t_{j_加 ⌶ 调整时间} (4) \end{array}$

2.2投标策略

投标者的投标策略是由其自身的负载、资源利用状况及其所拥有的竞争者的信息和对任务的执行力共同决定的。当资源Agent收到招标信息时,首先阅读任务描述信息和任务约束信息,然后查询自身可能完成任务资源的能力表,自主决策是否投标。

拉动式投标策略如下:收到紧后工序的资源代理的招标信息的首工序资源代理,通过核定自身的能力,选择是否投标,若是投标,根据虚任务,向紧后工序的资源代理投标,以此类推,直至尾工序。最后尾工序代理向调度代理提交整个任务的投标信息,则得到该任务的所有可行的加工路线;否则,采用推动式招标。推动式投标过程与拉动式投标过程相反。

现实生产车间中,由于拉动式招标比推动式招标能更好地满足准时制生产方式(JIT)对交货期的要求,往往首先采用拉动式招标。但拉动式招标可能由于紧后工序限制了紧前工序的最迟结束时间而导致紧前工序找不到可用时间间隔,而导致招标失败,此时停止招标,同时调度Agent启动推动式招标,在该种方式中紧前工序只是向紧后工序提供了自己的结束时间,并没有限制其开始时间,因此推动式招标一定有时间段安排工序,最终一定能得到计划结果。

图2展示了拉动式招投标过程。假定将分配的零件任务有3个工序,调度Agent查询得到的完成该零件各个工序任务的可用设备均有2个,假设每个可用设备均投标的情况下,拉动式招投标过程展示图如图2。

2.3招投标过程

2.3.1 拉动式招投标步骤

Step1 根据优先级,虚拟单元代理向调度代理发出招标请求,且调度代理通过查询任务的相关可用资源后,启动拉动式招标;

Step2 尾工序的资源代理根据交货期,选择完成该工序的可用时间段,形成虚任务;计算紧前工序的最迟完工时间,并根据该时间向紧前工序的可用资源代理发出招标信息;

Step3 当前工序代理依据紧后工序的招标信息,选择自身的时间段,如果有可用时间段,则安排此虚任务;

Step4 当前工序所有代理都没有可用时间段,直接进入Step 10;否则,进入step5;

Step5 安排虚任务的资源代理计算紧前工序的最迟完工时间,依据该时间向紧前工序的资源代理招标;

Step6 当前工序为首工序对应的资源代理;否则重复step2—5;

Step7 首工序资源代理进行投标,根据自己的虚任务,向紧后工序代理投标;

Step8 当前工序代理收到紧前工序的投标信息,根据自己的虚任务,向紧后工序代理投标;否则,投标值设置为空;

Step9 当前工序为尾工序,收到紧前工序投标信息的尾工序资源代理,向调度代理提交投标信息。若所有尾工序代理收到紧前工序的投标信息否为空,则进入step10;

Step10 拉动式招标失败,启动推动式招标。

2.3.2 推动式招投标步骤

拉动式招标失败之后启动推动式招标,因此,推动式招标的步骤如下:

Step1调度代理通过查询任务的相关可用资源后,启动推动式招标;

Step2 首工序的资源代理根据当前时刻,确定本工序的最早开始时间,计算本工序的完成时间,并根据该时间向紧后工序的可用资源代理发出招标信息;

Step3 当前工序根据紧前工序的招标信息,确定本工序的最早开始时间,计算完成本工序的完成时间,并根据该时间向紧后工序的可用资源代理发出招标信息;

Step4当前工序为尾工序;否则重复step3;

Step5尾工序资源代理进行投标,根据自己的虚任务,向紧前工序代理投标;

Step6当前工序为首工序,收到紧后工序投标信息的首工序资源代理,向调度代理提交投标信息。

Step7 推动式招标结束。

3任务计划的评标函数

在车间计划与调度决策性能评价指标多是注重加工时间,随着市场需求的变化,制造企业关注的指标出现多样化,如时间指标、经济指标和性能指标。实际生产中,不同的企业,甚至同一个企业在不同的时间、不同的环境下,其目标要求往往也不同,在任务的招投标过程中车间更注重的是任务加工时间短,同时生产成本低,有较大的获利空间,因而,评标函数关系着整个系统的性能是否能达到最优。所以根据本文所研究的对象,选取了加工时间、生产成本、运输费用等因子来评价投标信息。经过推拉式招投标过程,将得到任务的可行加工路线,对资源进行评判时并不是以单个工序任务的时间、成本最小为主,而是以完成整个任务的时间、成本最小为主,在满足交货期的要求下, 采用以下公式:

$\begin{array}{l} \min {α_{1} (\sum_{j = 1}^{j} α_{2} C_{j} + \sum_{j = 1}^{j - 1} S_{j + 1}) + \\ α_{3} (\sum_{j = 1}^{j} α_{4} t_{m j} + \sum_{j = 1}^{j - 1} t_{w j + 1})} (5) \end{array}$

加工时间Tj=tm+tw, Tj表示第j道工序的加工时间;tm表示基本加工时间;tw表示辅助时间和调整时间。加工成本Cj=cd+ch+cr, 其中,Cj表示加工成本;cd表示设备成本;ch表示人力成本;cr表示能源成本。运输费用Sj=Z1ξts。其中,Sj表示从零件的第j-1工序的设备位置到第i到工序的设备位置所需要的运输费用。ξ表示时间相对费用的折算系数,它由车间的实际情况给出;ts表示从零件的第j-1工序的设备位置到第j工序的设备位置所需要的最短运输时间,它根据车间的时间情况给出。Z1=1,表示零件的第j-1工序的设备位置与第i工序的设备位置不在同一位置,否则为0。

由于时间和成本是不同量纲函数,α1,α3为常数,目的在于将2个不同量纲的代数表达式进行无量纲化处理,α2,α4为时间和成本的不同权系数,这需要根据具体生产要求以及车间的实际情况来确定。

4案例

为验证所提出的招投标算法的有效性,文中的任务计划招投标模型是在Windows XP操作系统中,在Visual Studio 2010和.Net Framework 4.0的开发平台下,采用面向对象的C语言结合SQL Server2005数据库技术开发而成的,实现代理间任务的招投标,以广州某精密加工厂的车间进行系统应用,该车间中共有设备11台分别编号为M1,M2,M3…M11,其中下料机2台,数控冲床3台,数控折床3台,压铆机3台,分别建立各自的机器代理,并将各个机器的现有状态存入系统数据库,在某时刻,车间将对2个任务进行分配,根据车间调度员的经验和优先级规则,对2个任务分别进行任务招标,任务的数据如表1。

经查询车间中所有机器都可用,但由于设备的的新旧情况和机型的不同,同时各个零件的加工精度、批量、交货期各不相同,导致了各道工序在其可选机床集中的加工时间并不相同。招标规则依照前面所述,2个任务的最终的投标信息如表2。

在评标中,时间和成本的权重设为0.6和0.4,α1设为2,α3设为1.5,对可行加工路线进行评定之后,2个任务最终的加工路线为M1—M3—M8—M11;M1—M4—M8—M9。任务的加工时间分别为30 min和18 min,加工成本分别为75.9元,22.1元,比不采用招投标方法,任务的加工时间缩短了4.5%,加工成本节约了3.8%。

5总结

多品种小批量的生产方式下,为提高制造系统的柔性和快速反应能力,本文采用面向任务的虚拟制造单元的方式组织生产,针对以往基于Agent的调度研究中没有考虑任务前后工序之间联系的缺点,在满足交货期要求下,采用推拉式招投标策略,在评标中采用综合指标以使整体任务完成的时间和成本最小,实现了任务的动态分配,最后以一个案例来说明该方法的有效性。

参考文献

[1] Rechard Y K,Liang F,Jiang Zhibin,et al.A multistage methodologyfor virtual cell formation oriented agile manufacturing.Int J AdvManuf Technol,2008;(36):798—810

[2] Nomden G,der Zee D J.Virtual cellular manufacturing:configuringrouting flexibility.International Journal of Production Economics,2008;112(1):439—451

[3] Li Shujuan,Li Yan,Liu Yong,et al.A GA-based NN approach formakespan estimation.Applied Mathematics and Computation,2007;185(2):1003—1014

[4] Lim M K,Zhang Z.A multi-agent system using iterative biddingmechanism to enhance manufacturing agility.Expert Systems with Ap-plications,2012;160(10):957—972

[5]黄萍,宋海生,朱金达.基于多Agent机制的制造单元调度系统的研究.现代制造技术与装备,2008;5:66—67

基于遗传算法的柔性车间作业调度篇3

【关键词】柔性车间作业调度；活性调度；遗传算法

1.引言

在基本的车间作业调度问题(Job Shop Problem，简称JSP)中，所有工件的工序都只能由指定的某一台机器进行加工。随着加工技术、自动化技术的发展，特别是柔性制造系统的出现，此传统限制已被突破，工件具有多个可选择的加工路线，即路径柔性已经成为生产的实际需求。生产技术的进步推动着调度理论研究的进深，具有柔性路径的柔性车间作业调度(Flexible Job Shop Problem，简称FJSP)研究也开始进入人们的视野并引起重视[1-3]。

目前，遗传算法以其优良的计算性能和显著的应用效果，在求解JSP问题和FJSP问题中获得了很大的成功[4-11]。本文使用遗传算法来求解FJSP问题，提出了多维矩阵的编码方式，以及相应的选择、交叉、变异操作设计，保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。最后用一个调度实例验证了算法的正确性和有效性。

2.调度问题描述

n种工件J={Ji|i=1，…，n}在一个由m台不同的加工机器组成的制造系统中进行加工。加工工件Ji需要p(i)道工序，每道工序都有一个可选的机器集合，其加工时间随机器的选择不同而变化。调度目标是确定每台机器上各工件的加工顺序及开工时间，使得系统的最大完成时间Cmax最小，同时给出满足要求的活动调度。假设：

(1)各工件经过准备时间后即可开始加工；

(2)每个工件在某一个时刻只能在一台机器上加工，中途不能打断；

(3)每台机器每次只能加工一个工件；

(4)不考虑工件之间的加工优先权。

3.遗传算子设计

3.1 适应度函数f(i)

染色体i的适应度值由以下公式给出，其中C是一个大的正整数。

f(i)=C-Cmax

3.2 编码

op=å(i=1，…，n)p(i)：所有工件工序数量总和。

定义染色体为矩阵ch[3][op]，该染色体蕴涵工序和机器选择的双重信息。

第一行是基于工序的编码：数字i代表工件Ji。从左到右扫描，数字i的第j次出现代表工件Ji的第j道工序，记为Oij。

第二行是基于机器的编码：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]，其中kij表示工序Oij所选择的机器号码。

第三行提供了加工时间的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]，其中tij代表工序Oij在机器kij上进行加工所需要的加工时间。

3.3 交叉与变异

为了避免交叉操作之后产生非法个体(某道工序选择了不可用的机器)，规定仅仅对染色体的第二行、第三行数据，以概率pc进行两点交叉操作。

设计两种变异算子。

对染色体第一行数据，以概率pmop进行互逆变异操作，其目的在于生成新的调度。

对染色体第二行数据，以概率pmch改变某基因的值，注意要保证选择的机器合法。之后改变染色体第三行相应位置上的值，赋予其新机器上的加工时间。

以上的编码方式结合交叉、变异操作可使得生成的染色体在工序和机器选择方面都是合法染色体。

3.4 活动调度的调整

对染色体解码时，从左到右依次扫描第一行基于工序的编码串，确定工序信息Oij，之后在第二行的编码串中找到该工序选择的机器号码，扫描完毕即得到了该染色体对应的调度形式。按照这种解码方式一般只能得到半活动调度，而不是活动调度[12]。因此，将一种插入式算法嵌入到适应度计算过程中，在有必要时调整染色体的基因序列，使其解码后生成活动调度。

这种插入算法针对所有工件的非首道工序进行处理，将其插入到对应机器上最佳可行的加工时刻安排加工，以这种方式保证所有工序都安排在最佳可行的地方，使得机器利用率最大化。

stij：当前工序Oij的开工时间；

opij：当前工序Oij的加工时间，j>1；

fti(j-1)：同一工件前道工序Oi(j-1)的完工时间，j>1；

ftm：工序Oij所选用机器目前的可用时间；

stm：同一机器上前道工序的开工时间；

在基于工序的编码方式下，各个工件的加工已经按照其工艺顺序进行。给定染色体，设系统中所有机器的可用时间为0，所有待加工工件的初始可用时间为0。从左到右扫描染色体第一行数据，确定工序Oij的加工开始时间：

for(k=1 to op)

{对每一道工序ch[0][k-1]，判断其工序信息Oij；

if(j=1)stij=ftm；

else{

if(fti(j-1)³ftm)stij=fti(j-1)；

else{

if((fti(j-1)+opij)£stm){stij=fti(j-1)；调用染色体调整过程；}

else stij=ftm；}}

}

调整过程：代表当前工序Oi的数字为a，代表同一台机器上前道工序的数字为b。在染色体第一行编码串中，将a提到b之前。

图1的甘特图中，字符串“i–j”表示工序Oij。图1(a)显示：工序O11的完工时间ft11=2；工序O21在st2=5时刻开始加工，加工完毕后有ft2=8；工序O12的加工时间op12=2。因满足条件(ft11+op12)

3.5 选择

采用适应度比例方法，并执行保优策略。即当进行交叉、变异等操作时，生成的子代种群和父代种群合并成一个新的种群，对新种群应用适应度比例方法，即轮盘赌方法进行选择，且保存当代最优个体，即适应度最大且所有机器的总完工时间最小的染色体。

4.实例仿真

以表1所示的调度问题为例，表格中的数字代表各工序在相应机器上的加工时间。

遗传算法的参数设置为：交叉概率Pc=0.85，变异概率Pmop=0.012，Pmch=0.2，种群规模popsize=40，运行次数maxrun=10，每次运行最大进化代数maxgen=100。最终得到的调度结果makespan=17。

观察表1，令每道工序都选择最小加工时间的机器，可得到工件J1、J2、J3和J4的完工时间分别为5、9、17和12，所以对于该问题，若不限制工件访问同一台机器的次数，且系统缓冲区无限，makespan=17已经是最优的调度结果。

在makespan=17的调度中，得到的最小的总完工时间为63。图2中，字符串“ij”表示工序Oij的开始加工时间是a，完工时间是b。调度的甘特图见图3，字符串“i-j”表示工序Oij。因任何工序都不可能提前操作而同时保证其他工序不延迟，因此该调度是活动调度。

5.结论

本文使用遗传算法来求解柔性车间作业活动调度问题。首先将基于工序的编码和基于机器的编码方式结合，同时对交叉操作和变异操作的对象作了规定，这些改进方法可以保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。为了得到活动调度的形式，在适应度计算的过程中对染色体的基因序列进行调整。用4工件6机器的柔性车间作业调度问题为例进行仿真，得到的调度结果为最优；在所有最小makespan值的调度中，进一步给出了机器总完工时间最小的调度。仿真结果表明，本文设计的遗传算法在求解柔性车间作业调度问题时是有效的。

参考文献

[1]Zribi N,Kamel AE,Borne P.Scheduling in a flexible job shop under machine availability constraints[J].APII-JESA Journal Europeen des Systemes Automatises,2007,41(6):651-671.

[2]Guohui Zhang,Liang Gao,Yang Shi.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications,2011,4(38):3563-3573.

[3]白俊杰,龚毅光,王宁生,唐敦兵.批量生产柔性作业车间作业优化调度研究[J].机械科学与技术,2010,3(29):293-298.

[4]Kacem I.Genetic algorithm for the flexible job-shop scheduling problem[C],IEEE International Conference on Systems,Man and Cybernetics,OCT 05-08,WASHINGTON D.C.2003,1-5:3464-3469.

[5]Kun Y,Zhu JY.Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J].China Mechanical Engineering,2007,18(2):156-160.

[6]光熠,刘心报,程浩.求解车间作业调度问题的一种改进遗传算法[J].计算机技术与发展,2007,11(17):171-174,178.

[7]陈亮,王世进,周炳海.柔性作业车间调度问题的集成启发式算法[J].计算机工程,2008,34(1):256-258.

[8]席卫东,乔兵,朱剑英.基于改进遗传算法的柔性作业车间调度[J].哈尔滨工业大学学报,2007,39(7):1151-1153.

[9]杨红红,吴智铭.混合遗传算法在柔性系统动态调度中的应用研究[J].信息与控制,2001,30(5):392-397.

[10]方红雨,崔逊学.基于遗传算法的调度问题研究[J].电脑与信息技术,2001(2):1-5.

[11]Ferrolho A,Crisostomo M.A hybrid and flexible genetic algorithm for the job-shop scheduling problem[C].IEEE International Symposium on Computational Intelligence in Robotics and Automation.IEEE Piscataway.NJ.USA Jacksonville.FI.USA,2007:421-426.

[12]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.



作者简介：白康（1982—），女，河北保定人，硕士研究生，华北电力大学自动化系讲师，研究方向：智能调度与优化。