调度作业计划 篇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
调度研究的问题是将稀缺资源分配给在一定时间内的不同任务,它是一个决策过程,其目的是优化一个或多个目标[1]。根据加工系统的复杂度,调度可以分为单机调度、多机器并行调度、Flow Shop调度、Open Shop调度、Job Shop调度等几个基本类型。实际的调度问题往往是由Flow Shop 和Job Shop等基本调度类型组合而成的[2]。最简单的单机模型是指有多个工件要经过同一台机器加工,调度的任务是合理安排各工件的加工顺序使生产性能指标最优。
在单机模型调度方面:文献[3]用自适应遗传算法来求解单机调度问题,模型考虑了作业交货期和作业顺序决定的机器准备时间的约束条件,实现了作业提前和滞后的惩罚最小;Jouglet[4]研究了工件到达时间不同且机器不允许有空闲的单机调度模型,并用约束规划方法来求解以达到总加权完成时间最短的目标;文献[5]提出了作业可中断的单机调度模型,并用启发式算法求解以实现最大滞后时间最小化的目标;Aubry等[6]在不确定的客户需求下,研究了有机器转换成本约束的多功能并行机器调度问题,并用分枝定界法求解来实现机器负荷均衡的目标。人员调度方面:张毕西等[7]提出了改进的蚁群劳动分工模型来解决企业人员调度问题;文献[8]利用动态规划求解基于工作顺序决定劳动力成本的人员安排问题;Pan等[9]提出了两阶段启发式算法的整数规划来解决人员调度问题。迄今为止,车间调度问题比较常用的求解方法有基于规则的启发式方法[10]、遗传算法[11]、整数规划法[12]等。其中遗传算法以其鲁棒性好、通用性强、计算性能优良,且具有隐含并行性和全局搜索能力等特点而在车间作业调度计算中被广泛应用。文献[13]用改进的遗传算法来求解车间调度问题,提出了利用析取图模型来对遗传算法的操作进行改进,并取得了很好的效果。Rahmani等[14]提出了一组有确定的作业到达时间、加工时间和交货期的单机调度问题,并用一种混合双种群的遗传算法来求解,实现了最大作业延迟时间最小的目标。
总结文献资料可知,大多数研究都是基于某种调度模型问题而提出不同的求解方法或在调度模型的基础上考虑一些约束条件再进行求解。也有很多研究是对求解某种模型问题的算法加以改进从而提高算法的效率。无论是单机模型还是Job Shop调度问题,都很少考虑人员安排的问题,一些学者对人员安排方面也做了一些研究,但大部分是单纯考虑人员安排以使成本最低。而在实际生产中,机器加工产品一般都需要人员来操作,而且不同的人员因技术原因在同一台设备上进行相同操作的加工时间和质量不同。因此本研究在产品工艺可变(客户动态需求)、人员具备多技能特性(劳动力成本)的条件下,提出并分析了“人-多台单机”的柔性作业调度问题,即综合考虑人员工作安排的机器作业调度问题,以提高订单灵活性,提高车间作业效率,缩短产品交货期。
1 “人-多台单机”模型柔性作业调度
1.1 问题描述
(1)问题描述如下:有m台不同的机器,分别对应加工m个不同的产品(单个产品的所有操作都只在一台机器上完成即多台单机模型);产品在机器上的工序加工顺序不确定(加工工艺的柔性提高了作业调度的柔性);产品的工序数为ni(产品的一个工序对应在机器上的一个操作,即一个产品在机器上要经过ni个操作才能加工好,下文提到的机器操作数就是指产品的工序数),其中i=1,2,…,m;产品的一个工序(即机器的一个操作)只需一人完成(员工操作的独立性);有k个员工(员工数至多为机器同时进行作业的台数),每个员工都可以加工任何一个产品的任一道工序,但每个人作业的时间不同(人员的多技能及专业化分工的统一)。
(2)研究还需满足以下假设条件:①每个员工在每个机器上加工同一个产品的工序不可中断;②单个产品的工序间可以中断;③同一机器在同一时刻只能由一个人加工;④同一个员工在同一时刻只能在一台机器上加工同一个产品的一道工序;⑤所有产品在零时刻都可以被加工。
(3)问题特点及难点:研究的问题考虑了人员的多技能及其机器操作的差异性和产品工序顺序的不确定性,即除了要确定单个产品本身的工艺顺序外,还要对员工和产品间的工序操作(即机器间的操作)进行作业匹配,从而确定员工对应加工产品的工序及其加工的顺序,实现对人员、产品机器作业、工艺柔性的统一调度,增加了问题的复杂性,提高了作业调度的难度,从整体上优化了作业调度,提高了作业调度计划的合理性。
(4)调度的任务:①确定产品的工艺加工顺序(即在每台机器上的操作顺序);②具体安排每个员工的工作,即每个员工什么时候在哪个机器上加工产品的哪个工序。
(5)调度的目标:最小化所有产品的总加权完成时间(最小化产品的总体交货期)。
1.2 参数设置
设机器编号为Mi,i=1,2,…,m,因机器与产品对应,因此产品编号与机器编号设为一样;产品的工序号为(或机器的操作编号)Gj,j=1,2,…,n1+n2+…+nm,每个产品有ni个工序,所以总共有n1+n2+…+nm个工序数;产品(机器)的权重为Wi,i=1,2,…,m,根据不同产品的交货期进行权重的设定;员工的编号Ar=1,2,…,k;第i个员工第j个操作的时间为Pi j,i=1,2,…,k;j=1,2,…,n1+n2+…+nm;每个产品(机器)的完工时间为Ci,i=1,2,…,m。
调度目标为
为便于计算,假设m=3,ni=4,k=3,即3台机器,3个产品,每个产品都是4个工序(即每台机器都是4个操作),3个员工。表1为员工与产品工序(机器操作)对应的加工时间表(假设表中的时间已经考虑了工序间转换准备时间等)。本例中产品的权重值如表2所示。假设工序1～工序4属于1号产品在1号机器上加工,工序5～工序8属于2号产品在2号机器上加工,工序9～工序12工序属于3号产品在3号机器上加工。
2 遗传算法设计及求解
2.1 染色体编码及解码
根据问题的特性,采用基于员工与工序的混合编码方法进行编码。染色体编码分为两个串:第一部分基因串为员工工作的确定,即员工操作哪台机器上产品的哪个工序(该部分基因顺序没有具体意义);第二部分基因串为产品工序(机器操作顺序)的确定。如图1所示。
第一部分基因按员工编号进行编码,1、2、3分别表示员工编号,基因长度为所有的产品工序数共12个(3个产品,每个4道工序),员工在第几个位置就表示加工第几道工序,第一个1表示员工1加工工序1,依此类推,可得出,1号员工操作工序数为(1,6,11),这里员工对应的操作工序没有顺序之分,而且有可能3个员工只安排2个,如基因1 3 3 3 1 1 3 3 1 1 3 1则表示没有员工2。
第二部分基因采用按产品工序进行编码,基因长度为所有产品工序数,如产品工序数总共为12个,则产生12个从1到12的不重复的整数。每一个编号代表产品的工序,由表1可知,工序1～4属于1号产品在机器1上加工,依此类推其他工序。编码顺序即所有产品工序先后加工顺序。对于图1来说,其中产品1的工序加工顺序(也即机器1的操作顺序)为(1,3,2,4),据此来确定每个产品的工序加工顺序。若工序1和5由同一个人操作,则员工要根据染色体第二部分基因顺序,先操作工序1,完成后再操作工序5,其他依此类推。结合第一部分基因,可得出每个员工加工产品工序的先后顺序。如3号员工,由第一部分可知3号员工操作工序数是(3,5,8,9,10),再由第二部分基因可知,其工序先后顺序应该为(3,5,10,9,8)。
本研究采用的基于人员与工序的两串式编码方案经后面实例证明是有效的,原因在于:第一部分采用人员编号进行编码,而其基因长度又是总的工序数,因此不会有漏掉的情况,而且是随机的,具有全局搜索性;第二部分采用工序编号编码,长度与工序数一样主要用于确定工序加工顺序,两串基因组合符合问题的特性。之所以采取这样的编码和解码方法,而不将员工的机器操作顺序按照员工在第一部分的基因位置顺序来解码, 主要是考虑如果采取后者的方法, 会出现员工机器操作顺序与机器本身的产品操作顺序不一致的情况, 从而产生无效解。如上述机器3的操作顺序为(10,9,12,11),而第一部分3号员工的操作数为(3,5,8,9,10),这样10和9的工作顺序就出现了矛盾。而本文提出的这种编码方法就没有这个问题, 更加便于后面的遗传操作。
2.2 种群初始化及适应度函数计算
本研究中采用目前比较常用的随机初始化方法进行种群初始化。
由于优化目标为最小化所有产品的总加权完成时间,易知其总大于零,因此个体的适应度函数可定义为
F(f(x))=f(x) (2)
其中,f(x)为原目标函数即式(1)中
(1)建立表1所示的员工对应的工序加工时间矩阵Pp(3行,12列)。再建立与矩阵Pp行列数相等的零矩阵T1,第一行代表1号员工,第二行为2号员工,第三行为3号员工,依此类推。
(2)以图1的染色体为例,可计算出结果如下:
(3)由于每个机器最后一个操作的完成时间即为该机器上产品的完成时间,故由T1的结果可知,机器1的操作4完成时间为35,机器2的操作7的完成为90,机器3的操作11的完成时间为123。由表2可知,每个机器产品的权重分别为3、7、6,所以根据式(2)可求得适应度函数值:
2.3 选择算子
为将适应度最好的个体尽量保留到下一代群体中,本文采用最优保存策略和轮盘赌选择相结合的方式。
2.4 交叉操作
交叉操作决定遗传算法的全局搜索能力。研究中第一部分基因的交叉操作采用常用的单点交叉法。第二部分基因的交叉操作采用张超勇等[16]确定的基于工件的交叉方法。根据问题的特殊性和编码的特性,本文将所有机器操作编号分成单数集合和双数集合,该交叉操作的具体过程为:
(1)将所有的机器操作编号分成单数和双数的基因集合S1和S2。
(2)将父代P1中包含在S1中的基因复制到子代C1中,同理将父代P2中包含在S1中的基因复制到子代C2中,同时保留它们的基因位置。
(3)将父代P2中包含在S2中的基因按顺序填充到C1中,父代P1中包含在S2中的基因按顺序填充到C2中。具体过程如图2所示。其中,“*”表示该基因为S2中的,且其顺序无规定,是随机的。
2.5 变异操作
第一部分变异采用可选员工集变异,即对个体编码串中随机指定的某几位基因座上的值做变异运算,由于每一道工序的可选员工是确定的,对于要变异的基因位,可变异为可选员工集中除该变异位所在员工外的其他员工编号。如2.1中的第一部分染色体为1 2 3 2 3 1 2 3 3 3 1 2,若第3位要变异,则将第三位基因3变异为1或2。对于第二部分染色体基因,由于操作编号是由连续整数组成的,为防止变异后出现无解现象,本研究采用互换变异,即随机选择同一个染色体的任意两个基因进行互换。
3 实例计算对比及结果分析
根据上面表中的数据,在MATLAB7.10.0(R2010a)平台下编写程序进行求解。实验选取的参数为:种群规模P=50,交叉概率pc=0.8,变异概率pm=0.5,最大进化代数为150。实验结果如下:最优染色体为2 3 3 1 1 1 2 1 3 32 1 9 7 4 3 11 6 2 10 8 5 1 12;机器操作顺序M=[4 3 2 1;7 6 8 5;9 11 10 12];员工操作顺序W=[1 4 8 5 12;7 11 1;9 3 2 10];最小化最大加权完成时间为855s。图3是经过50次迭代的种群染色体适应度值分布图,图4是经过150次迭代后最优解的变化和种群目标函数均值的变化图。调度问题的最优解甘特图见图5和图6。其中,图6中的数字表示员工编号及其加工的产品工序编号。
为验证研究结果的有效性,研究了一个不考虑人员交叉匹配作业的情况,即单纯考虑多台单机模型,而机器间没有联系(员工只在一台机器上作业)。首先计算每个员工加工每个产品的时间,如表3所示。
s
根据表3数据可知,2号员工加工1号产品时间最短为37s,产品2由1号员工加工时间最短为51s,员工2和3加工产品3的时间都为65s。因此最后选择加工方案为(1,2),(2,1)和(3,3)(第一个数代表员工编号,第二个代表产品编号(机器编号)),而产品内的工序加工顺序对结果没有影响,可根据产品需求而定。最后算出最小化最大加权完成时间为858s,大于研究的结果。
对于不考虑人员的情况,还可以采用加权最短时间优先(WSPT)的启发式规则[1]进行求解,即根据表3的数据和表2的产品权重表,分别算出每个员工不同产品的权重与加工时间的比值,值越大则该员工越应加工该产品。对于同一个产品由两个员工以上加工的情况,再比较两个员工的权重与加工时间的比值,值大的员工加工该产品。根据表2和表3的数据可算出员工的权重与加工时间的比值,如表4所示。
由表4可知,对于1号员工来说,产品2的权重比值最大,因此由1号员工加工2号产品,对于2号员工来说,同样是2号产品的权重比值最大,但由于1号员工的比值大于2号员工的比值,因此2号员工选3号产品,但考虑到3号产品的权重比值对于2号和3号员工来说值相等,而3号员工的权重比值最大的为2号产品但小于1号和2号员工的比值,因此3号员工选3号产品加工,所以2号员工加工1号产品。最终总加权完成时间也是858s,大于研究的结果。最优解甘特图见图7。
为了提高复杂度,增加可比性,利用所研究的算法和WSPT启发式算法对于5台机器,5个产品,每个产品有4道工序,5个员工的作业调度分别就考虑与不考虑人员因素的情况进行求解,1到5号产品的权重依次为5、6、8、9、7。具体数据如表5、表6所示,实验结果如表7所示。
s
s
由表7实验数据可知,考虑人员因素情况下总加权完成时间均小于不考虑人员因素情况下的结果,实验结果进一步说明了本研究的意义,并验证了本研究算法的有效性。
4 结束语
本文提出并分析了“人-多台单机”柔性作业调度问题,充分考虑了实际机器工作中人员操作的影响,在合理的人员数量和不同人员存在不同作业速度约束下对人员与作业进行综合柔性调度,以提高企业订单灵活性和缩短交货期,并采用遗传算法进行求解,并用WSPT启发式算法对人员进行独立安排作业情况进行对比研究,研究结果表明该算法的可行性。研究中假设每个操作只能一人完成,而实际中可能有多人同时加工一道工序,这方面有待于今后进一步研究。
基于遗传算法的柔性车间作业调度 篇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 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—），女，河北保定人，硕士研究生，华北电力大学自动化系讲师，研究方向：智能调度与优化。 摘要：采用博弈理论，建立了一种基于非合作博弈的作业车间任务调度模型，在该任务调度模型中，将源于不同客户的制造任务映射为非合作博弈模型中的局中人，并将与制造任务包括的工序集所对应的可选加工设备映射为可行方案集，将使各制造任务的加工完成时间和成本组合形成的多目标综合指标映射为收益函数，从而将对任务调度模型的求解转换为寻求非合作博弈模型的Nash均衡点，通过设计的爬山搜索混合自适应遗传算法、自适应交叉和变异算子，实现了对该任务调度非合作博弈模型的Nash均衡点的有效求解，同时算例仿真结果也验证了所提出的调度方法的正确性。 根据数学模型和假设条件，竞争驱动的作业车间任务调度目标就是寻求使得每个制造任务均能达到综合目标值最小、利益均衡的调度结果。 《基于自适应遗传算法的Job Shop 调度问题研究》 作者：沈斌，周莹君，王家海 Job Shop 求解过程的计算量随问题的规模呈指数增长，已被证明是NP完全问题。因此近年来倾向于利用人工智能的原理和技术进行搜索，寻找复杂问题的较优解，特别是以效仿生物处理模式以获得智能信息处理功能的遗传算法研究最为深入。但是也有不足之处，早熟收敛问题，局部搜索能力，算子的无方向性，正因为这些不足限制了以遗传算法的进一步推广和应用，因此对遗传算法进行改进显得尤为重要。本文提出一种新的自适应遗传算法用以求解Job Shop调度问题。 Job Shop问题描述 一个加工系统有m台设备，要求加工n个工件，第i个工件ji包含m个操作（工序），需要考虑如下假设： 1）每道工序必须按照工艺顺寻依次在指定的设备上加工，且必须在前一道工序（如果存在））加工完成后才一开始加工； 2）工件在一台设备上一旦开始加工，便不能中断，必须等到加工完成后，才能加工另外工件，即某一时刻一台设备只能加工一个工件； 3）同一个工件不能同时在两个设备上加工； 4）同一台设备不能同时加工两个工件； 5）每个工件在每台设备上必须加工一次，也只能加工一次； 6）各工件的工艺路线jsn和每到工序的加工时间jt已知，且不随加工排序的改变而改变，转移时间和辅助时间忽略不计或计入加工时间。 《A Hybrid Genetic Algorithm for Job Shop Scheduling Problem to Minimize Makespan》 作者：Lin Liu, Yugeng Xi In this paper, we present a hybrid genetic algorithm for the job shop scheduling problem to mimize makespan.How to improve GA performance is a critical issue when using a GA to solve optimization problems.The general way focuses on tuning its parameters such as population size, crossover rate and mutation rate.However, if all parameters have attained the useful bounds, the expected improvement is often not worth the efforts of finding even better parameters.More potential improvements can be only explored by modifying the size of search space.The set of active schedules is usually large and includes a lot of schedules with relatively large idle times on machines, and thus with relatively large idle times on machines, and thus with poor performance in terms of makespan.The proposed algorithm used the idea of hybrid scheduler to reduce the search space as well as the computational efforts.The search space can be reduced or increased by controlling the upper bound of idle times allowed on machines.Since the parameters of the hyubrid scheduler are unlikely to be determined appropriately in advance, we search better values of them in the hybrid GA evolution.Dissimilar to Gas in literatures, a chromosome includes not only genes representing the relative priorities of all operations but also genes representing the parameters to determine the upper bound of idle times permitted on a given machine before scheduling an operation.The random keys representation is used to encode a chromosome.Each element of the chromosome is a real number of [0,1].During the schedule generation phase, the SPV rule is used to convert a real number vector into a job repetition representation.Based on the hybrid scheduler, a chromosome is decoded into a feasible schedule.Finally, a local search is executed in the neighborhood determined by the critical active chain to improve the performance of the schedule generated in the schedule generation phase.nd In the 2section, we present the formulation of job shop scheduling problem to minimize makespan.In the 3 section, we describe the proposed hybrid genetic algorithm in detail.In the 4 section, the proposed algorithm is evaluated on benchmark instances.Finally, we conclude the paper with a summary in 5th section.《Hybrid Genetic Algorithm for Solving Job-Shop Scheduling Problem》 作者：S.M.Kamrul Hasan The Job-Shop Scheduling Problem(JSSP)is a well-known difficult combinatorial optimization problem.Many algorithms have been proposed for solving JSSP in the last few decades, including algorithms based on evolutionary techniques.However, there is room for improvement in solving medium to large scale problems effectively.In this paper, we present a Hybrid Genetic Algorithm(HGA)that includes a heuristic job ordering with a Genetic Algorithm.We apply HGA to a number of benchmark problems.It is found that the algorithm is able to improve the solution the solution obtained by traditional genetic algorithm.《Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm》 Most flexible job shop scheduling models assume that the machines are available all of the time.However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on.In this paper, we study the flexible job shop scheduling problem with availability constraints.The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure.We then propose a hybrid genetic alogorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints.The genetic algorithm uses an innovative representation method thrdand applies genetic operations in phenotype space in order to enhance the inheritability.We also define two kinds of neighbourhood for the problem based on the concept of critical path.A local search procedure is then integrated under the framework of the genetic algorithm.Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the the effectiveness and efficiency of the suggested methodology.《A Hybrid genetic algorithm for no-wait job shop scheduling problems》 作者：Jason Chao-Hsien Pan, Han-Chiang Huang 离散制造业车间调度问题目前已从相对简单的经典车间调度问题逐渐转化为柔性作业车间调度问题(Flexible Job-shop Scheduling ,FJSP),打破了经典车间调度对某一产品的每个加工工序只能由一台设备加工的约束,FJSP不仅要确定各产品加工工序的顺序,而且要将各工序分配给不同的设备,从而保证所有产品的最大加工时间最短,属于NP-hard难题。谢皓等[1]以最大完工时间最短为目标,采用遗传算法对一个8×8(8台加工设备,8种工件)的问题进行计算,并没有考虑在实际生产中调度问题是典型的多目标优化问题。王硕、曹岩等[2,3]采用了一种改进的蚁群算法对机器编码,控制冗余解的数量,提高算法的计算速度,计算模型则是经典的车间调度模型与实际生产有一定的差距。此外,有部分学者考虑了实际生产中车间调度问题属于多目标优化问题,如刘烽等[4]针对混合流水车间多目标调度问题,以最大流程时间和生产中所消耗的总能量最小为目标函数,建立了混合整数规划模型,采用NSGA2算法计算了12×8的调度问题。魏巍等[5,6]分别以加工成本、加工质量、制造工期最短、设备利用率最大为目建立多目标优化模型,采用智能算法求解小规模的调度问题。曾强等[7,8]针对柔性作业车间调度问题中加工路径的不确定性,以最长完工时间最小和加工费用最少以及设备利用率最高为目标,建立多目标调度问题模型。 综合上述研究发现,现有的文献主要存在两点不足之处,一是在建立车间调度模型时没有考虑足够的约束和目标,大多数研究目标没有考虑到在实际生产中应当尽量减少产品的搬运距离/次数;二是在解决车间调度问题的同时并没有考虑车间加工设备位置布局,造成车间内的物料无效搬运距离/次数增加。 针对上述不足,本文首先建立了以最大完工时间最小、总延期时间最小、总提前期时间最小、设备总负荷最小、单台设备的最大负荷最小、总生产成本最低以及工件搬运次数最少的多目标车间生产优化调度模型。然后,对于优化的pareto解集采用AHP确定其最优调度方案。再次,根据车间调度问题确定的产品加工工艺线路,以加工产品搬运距离最少为目标,对现有的车间设备布局进行优化,使车间无效的搬运量最小。最后,以大连某空调生产车间为例,通过对一个10×10的车间调度进行计算,验证了本文算法和模型的可行性。 1离散车间多目标调度数学模型 1.1问题描述 多目标FJSP是指在m台设备(M={mk|1,2,…,m,k=1,2,…,m})上加工n个工件(J={ji|j1,j2,…,jn,i=1,2,…,n),每个工件包含Ni个事先确定加工顺序的工序,每个工序可以在多台设备上加工,mij表示工件ji的第j道工序可使用的加工设备集合。Sijk为工件ji的第j道工序在设备k上开始加工时间,Eijk为工件ji的第j道工序在设备k上结束加工的时间,工件ji的第j道工序在设备k上的加工时间为tijk,Ti表示工件ji的最后一道工序的完工时间,Di表示工件ji的交货时间,α表示单位时间延期交货费用为。工件ji的原材料费用为Ci,不同设备单位时间的加工费用用pk表示,单位时间的调整费用为sk,用wijk表示工件ji的第j道工序在设备k上的调整时间。Xijk为决策变量,当工件ji的第j道工序在设备k上加工时,取值为1,否则为0;Yikk为决策变量,当工件ji的第j道工序与第j-1道工序都在设备k上加工时,取值1,否则为0;车间调度的目的是在有限的资源条件下,将各个工序分配到相匹配的设备上,从而达到车间生产的多个目标组合最优。 根据上述描述,本文作如下假设:1)一台设备同一时刻只能加工一个工件;2)若某一工件加工的上一道工序加工完毕后,对应的设备处于空闲状态,则立即开始加工下一道工序;3)工件在每台设备上的加工时间、装卸时间都确定,并都作为加工时间计算;4)工序在每台设备上的调整时间已知;5)工件加工一旦开始,就不能中断,除非设备出现故障;6)所有设备一开始均处于正常状态,即最初不存在故障设备;7)设备的故障率是通过长时间对设备的观测和维护所到的统计值,数据真实可靠;8)同一个工件,只有在上一道加工工序结束后才能进行下一道工序;9)工件的加工顺序不能改变。 1.2目标函数 1)最大完工时间最小: 2)总延期时间最小: 3)总提前期时间最小: 4)总生产成本最低: 5)设备总负荷最小: 6)单台设备的最大负荷最小: 7)工件搬运次数最少: 约束条件如下: 其中,式(8)表示:在同一时刻任意工件的某一工序只能由一台设备加工;式(9)表示:同一工件的下一道工序的开工时间必须大于或等于该工件上一道工序的结束时间;式(10)表示:任意工件的结束时间大于等于该工件的开始时间、加工时间以及调整时间之和;式(11)表示:任意设备上新任务的开始必须在上一任务结束之后;式(12)工件的最后完工时间的;式(13)同一工件前后加工工序在同一设备的约束。 2算法设计 由于车间调度问题属于NP-hard难题,每个目标之间存在复杂的关系,而且属于非线性优化模型,传统优化方法计算难度较大,因此本文采用一种基于双层(加工工序和加工设备)编码的改进遗传算法求解该问题。与传统遗传算法相比,确保染色体包含信息的全面性和完整性,同时采用最优保存策略、锦标赛选择、序值以及拥挤距离选择的方法,选择种群个体中适应度较高的遗传给下一代。交叉和变异操作均采用随机的两点交叉和变异。为了保证下一代种群中个体的多样性和防止搜索解陷入局部最优解的循环中,本文将适应度函数通过线性尺度转换方法。 2.1染色体编码 本文采用基于加工工序和加工设备的两层编码的方式对染色体进行编,确保染色体包含信息的全面性和完整性。染色体编码采用整数编码,每个染色体长度为(n表示加工工件数,Ni表示第i个工件的工序数)。染色体分为两部,前半部分表示工件的加工工序,后半部分表示加工工件的加工工序所对应的加工设备顺序。 2.2适应度函数 本文把适应度函数与目标函数的转化关系式定义如下: 在传统遗传算法的实际操作中会出现某一代中有一部分个体的适应度值很高,是到目前为止所有种群中适应度最高的个体,但是这些个体未必就是待优化问题的最优解或者近似最优解,而可能是解空间中的局部最优解。当出现这种情况时,如果仍然按照原种群中个体适应度函数来确定个体是否遗传到下一代中,就会出现从下一代开始,以后各代的个体几乎都不会改变。因为从上一代开始,在进行选择操作时,由于种群中适应度较高的个体会排斥适应度较低的个体,所以,以后每一代种群中适应度较高的那些个体占据种群的绝大部分。根据个体进化规则和选择操作中最优保存策略,这些适应度较高的个体直接遗传给下一代。所以,这种个体进化会使种群基因的多样性减小,甚至会出现上一代和下一代个体完全重合,这样就会使搜索解停留在某一局部最优点上。本文对某些适应度较高的个体进行人为的修订,降低其适应度,减小与其他个体适应度的差异,限制这些个体的遗传代数,增加适应度较小的个体被选择遗传的概率,从而增加种群基因的多样性,来避免这一现象的发生,达到使搜索解跳出局部最优点的约束。 本文对适应度函数采用线性尺度转换方法,转换公式如下: 其中,F为原适应度函数,F'为转换后的适应度函数,a,b为转换系数,一般c的取值范围是1.2~2,本文取1.15,F为所有个体适应度的平均值,Fmax为所有个体中适应度最高个体的适应度值。 2.3选择操作 本文采用MATLAB工具箱中的锦标赛选择函数(Selection tournament),采用最优保存策略,通过计算个体的序值和拥挤距离,选择种群中序值较小的个体遗传给下一代,当种群中两个个体的序值相同时,为了保持种群个体基因的多样性,选择拥挤距离大的个体遗传给下一代。当种群中个体的序值和拥挤距离都相等时,选择子目标中权系数较大的个体。通过多层次的比较、分析逐步对个体进行适应度排序,淘汰适应度小的个体,选择种群个体中适应度较高的遗传给下一代。 2.4交叉操作 种群中的个体通过按一定的交叉概率,将染色体上的基因随机的交叉,得到新的个体,增加了种群基因的多样性。随机从种群中选择两个染色体,根据染色体编码的方法,先取出染色体的前半部分,其长度为∑Ni,采用双点交叉的方法,随机的设定两个交叉点进行交叉操作。交叉后会出现某些工件的工序多余,某些工件的工序缺失,因此,需要按照原有基因将交叉后的基因对应的设备顺序进行调整。 2.5变异操作 根据种群个体前半部分染色体的长度随机的产生两个之间的整数i和j,将前半部分的i,j基因互换。在互换后的个体中按一定的变异概率随机的选择个体进行变异操作,并将对应的设备编码做相应的调整,产生新的个体,从而淘汰适应度较小的个体,达到进化种群的目的。 2.6解码操作以及终止代数的确定 本文采用的染色体解码方法是全自动动解码方法。对于给定的一个染色体S而言,先计算其基因个数,然后取其基因的前半部分,根据解码公式进行解码。例如染色体S[3 2 1 4 1 3 2 4 2 3 4 3 1 2 2 4],共有16个基因,因为采用的是基于加工工序和加工设备的两层编码方式,所以取其基因的前半部分,共有8个基因分别为[3 21 4 1 3 2 4]。从上述基因中可以看出有4种工件,工序总数为8,分别根据下面程序进行解码。 关于终止代数T的确定,本文采用综合评价指标相对偏差值确定。令表示遗传算法运算第t代后第j种调度方案的综合评价指标,则终止代数T可由下式确定: 2.7改进遗传算法 传统的遗传算法采用的是隐性精英解保留策略,虽然保证了种群个体基因的完整性,但是在求解多目标问题的时候,可能会使Pareto解集出现过早收敛的现象。本文对Pareto解集采用改进的是三层评判标准的选择策略,首先通过计算序值,其次计算拥挤距离,最后根据各目标的模糊评价决策得到的综合评价指标进行排序,选择最优的Pareto解集。改进的遗传算法流程图如图1所示。 3实例分析 本文以大连市某企业空调制造车间为例,该车间某一时刻的10个工件需要在10台设备上加工,每个工件都要经过6道加工工序,具体数据如表1~表5所示: 生产计划调度大作业 篇4
调度作业计划 篇5
本文的遗传算法参数为:种群中个体数目500,种群进化代数500,种群代沟0.8,交叉概率0.6,变异概率0.1。
经计算所得,传统遗传算法得到的pareto解集中最优解对应的最小加工时间为60分钟。
采用基于最优保存策略、序值排序、拥挤距离计算、综合指标排序、适应度函数转化以及工件加工工序和设备的两层编码方式的改进遗传算法的实例测试如图2和图3所示。
由于篇幅有限,本文只摘取6组比较优越的pareto解,如表6所示,然后通过AHP综合评价选择最佳的调度方案。各子目标的权重为:ω=(0.358, 0.2003,0.0872,0.2396,0.0461,0.0257,0.0431)T,最终选择调度方案3。
经计算所得的,改进遗传算法得到的pareto解集中最优解对应的最小加工时间为53分钟。根据计算结果可知,改进后的遗传算法的综合评价指标比改进前的优越。所以本文的调度方案更加适应解决离散车间多目标调度问题。
本文对车间的设备进行环形布局优化,建立如下数学优化模型。
s.t.
其中,wij为设备i到设备j的当量物流量,是根据工件加工工艺线路转化的,例如,工件1的加工工艺路线为3-1-2-7-8-5,则w31=w12=w27=w78=w85=1 。xij为0,1变量,如果设备i在生产线上的位置排在设备j前,取值为1,否则为0。目标函数(19)在保证所有工件加工完的前提下,使整个车间的逆向搬运物流量最小;约束(20)设备相对位置的约束,约束(21)确保设备位置在传递过程中不出现矛盾。
经计算得到图4加工设备环形布局图,其中(1)和(2)两个方案工件总的逆向搬运物流量都为17,总的无效搬运量都为237。与优化前的车间布局(设备摆放位置为1-2-3-4-5-6-7-8-9-10)相比,总的无效搬运量从270减为237。
4结束语
本文首先采用传统的遗传算法对空调制造车间10×10的案例进行求解,然后采用本文所提出的改进的遗传算法对上述给定的案例进行求解,通过对比两个方案的综合评价指标,可以证明本文提出的改进的遗传算法在求解同一车间调度问题中的优越性。最后根据车间调度确定的工件加工工艺路线,实现了对现有车间制造设备进行环形布局优化。
摘要：针对车间生产调度人员需要进行多目标的调度决策,以大连市某企业空调制造车间为例,首先建立了以最大完工时间最小、总延期时间最小、总提前期时间最小、设备总负荷最小、单台设备的最大负荷最小、总生产成本最低、工件搬运次数最少的多目标车间调度模型。然后提出了基于工件加工工序和加工设备的两层编码的改进遗传算法,再次通过层次分析法确定各个子目标的权重,对不同量纲的子目标进行模糊无量纲化处理,并通过综合评价指标确定pareto解集的最优调度方案。最后根据工件加工工艺线路对车间设备进行环形布局优化,建立了环形布局优化模型,并通过实例分析验证了该算法的可行性。
调度作业计划 篇6
作业车间调度问题 (Job Shop Scheduling Problem, JSSP) 是一类典型的NP难题, 也是CIMS领域中研究的重要课题, 其研究不仅具有重大的现实意义, 而且具有深远的理论意义。车间作业是指利用车间资源对某一对象进行生产的过程, 作业调度实际上是对车间作业进行有效的排序, 使某个目标函数最小[1,2]。柔性作业车间调度问题 (flexible job shop scheduling problem, FJSSP) 是传统JSSP的扩展, 与JSSP相比, FJSSP任务中每道工序可以在多台机床上进行加工, 如果每一道工序可以被任意机床加工, 则称之为全柔性, 否则称之为部分柔性。FJSSP除了要解决工件的加工顺序外, 还要先解决由哪台机床加工的问题, 因此, 使问题更加复杂[3,4]。
遗传算法 (Genetic Algorithms, GA) 是模拟自然选择和遗传的随机搜索的, 是一种仿生优化算法。由美国Michigan大学的John Holland提出, 这一算法的最初目的是研究自然系统的自适应行为并设计具有自适应功能的软件系统[5]。后来, 遗传算法因其不要求可微, 求解过程简单, 并行搜索, 适合范围广泛, 最近几年遗传算法作为问题求解和最优化的有效工具, 被广泛应用。1985年, Davis首次将遗传算法用于解决调度问题, Biegel研究了工序加工排序问题。遗传算法在作业调度上的应用, 包括车间作业调度、物流作业调度等。由于遗传算法所固有的全局搜索与收敛特性, 被认为是解决车间调度问题的有效方法。
2 用自适应遗传算法求解部分柔性车间调度问题
自适应遗传算法的pc和pm能够随适应度自动改变。当种群各个体适应度趋于一致或者趋于局部最优时, 使pc和pm增加, 以跳出局部最优解;而当群体适应度比较分散时, 使pc和pm减少, 以利于优良个体的生存。因此, 自适应的pc和pm能够提供相对某个解的最佳pc和pm。自适应遗传算法在保持多样性的同时, 保证遗传算法的收敛性。
2.1 染色体表示
染色体编码方法, 以工序为行、定单为列构造一个M×N维的机器分配矩阵:
机器矩阵的元素αij是整数, 表示定单j的第i个工序在第αij台机器上加工。根据定单和机器的实际参数随即产生αij, 从而保证后面生成的染色体合法以及在进行遗传操作后生成的子代也是合法的。
根据上述机器分配矩阵确定染色体为:
在染色体中, αi是实数, 小数部分表示定单, 整数部分表示定单所分配的机器, i值的大小表示同一台机器上定单先后顺序。
2.2 适应度函数
根据染色体的排序和机器的加工能力, 可以计算出定单每个工序在所分配机器上的加工时间, 写成矩阵TM×N:
矩阵中元素tij表示定单j的第i个工序在机器αij上的加工时间, 如果实际生产中, 定单不需要经过某个工序, 则该定单的加工时间tij=0。根据染色体排序, 各个定单在整个生产过程中的流程时间为[C1, C2, …Ci, …, CN], Cmax=max{C1, C2, …C, …, C},
由于调度的目标是最小化最大流程时间, 所以适应度函数为:Fitness (f) =。
2.3 遗传算法的求解方法
(1) 初始种群 (population) 的产生
根据染色体 (chromosome) 的编码方法和定单排序约束条件, 随机产生K个染色体构成初始种群, K是初始种群规模。
(2) 染色体选择 (selection)
首先根据适应度的好坏顺序对群体中的个体进行排序, 按下式分配选择概率:
式中q是一个常数, 表示最好的个体选择概率, i为个体排序的序号。然后, 按轮盘赌选择 (roulette wheel selection) 选择个体:按照个体顺序求出每个个体的累积概率, 根据累积概率产生一个轮盘, 然后产生一个随机数, 它落在累积概率的哪个区就选择相应的个体。显然, 选择概率大的个体被选中的可能性大, 最佳个体被保存的概率就大。
(3) 交叉 (crossover) 操作
按照交叉概率pc进行交叉操作:适应度, αvg是平均适应度, 是要交叉的两个个体中较大的适应度值。
(4) 变异 (mutation) 操作
按照变异概率Pm进行变异操作:
一般取Pm1=0.1, Pm2=0.001。max, αvg分别为最大适应度和平均适应度。
3 遗传算法的流程图
见图3。
4 运行实例
本文的自适应遗传算法采用delphi编程实现, 某注塑厂使实现车间调度的自动化。例子:有4道工序, 每道工序分别有3、2、4和3台机器, 12个定单, 加工时间如图1;算法中的参数:q=0.06, Pc=0.85, Pm=0.01, 种群规模为50, 迭代次数为50。运行后得到的最佳调度结果如图2, 最大流程时间为35, 各工序机器的加工任务比较均匀, 而且各机器加工时间基本保持连续, 可以减少加工时间, 表明调度结果是比较合理的。
5 结论
用自适应遗传算法可以有效地对FJSSP求解。本文遗传算法所提出的基因编码方法同时包含了调度的路线和定单序列, 而且使得产生的每个染色体都对应一个可行的调度方案, 进行遗传操作时也不会产生非法解, 从而取消了运用遗传算法求解FJSSP问题时为使基因合法化而进行的基因修复和重建过程。论文实现了注塑企业车间调度的自动化。运行结果表明该遗传算法在优化生产调度方面是非常有效的, 生成的车间调度计划, 缩短了制造周期, 减少了在制品库存, 提高了生产效率, 所以该算法在注塑企业应用, 具有较高的使用价值。
本文作者创新点:本文针对注塑企业生产过程的调度问题采用了遗传算法求解。所采用的染色体编码方法, 使得产生的每个染色体都是合法的, 取消了基因修复和重建过程, 提高了搜索能力和收敛速度。本文改变了注塑企业手工安排调度计划现状, 实现了编排调度计划的自动化, 并且优化了调度计划, 提高了生产效率, 为企业创造了经济价值。
摘要：针对柔性作业车间调度问题, 提出一种自适应遗传算法。该遗传算法所采用的编码方法, 使得产生的染色体和进行遗传操作后得到的染色体对应的都是可行的调度;使用的自适应交叉和变异概率, 使得最优个体能复制到下一代中, 提高了搜索效率。仿真结果表明用该遗传算法解决柔性作业车间调度是有效的。
关键词：柔性作业车间调度,遗传算法,自适应交叉和变异概率
参考文献
[1]安晶, 秦珂.一种基于遗传算法的车间调度算法求解.盐城工学院学报 (自然科学版) .2007, 20 (1) .
[2]王小平, 曹立明.遗传算法[M].西安;西安交通大学出版社.2005.
[3]袁坤, 朱剑英.一种求解多目标柔性Jop Shop调度的改进遗传算法.中国机械工程.2007, 18 (2) .
[4]王万良.人工智能及其应用[M].北京:高等教育出版社.2005.
调度作业计划 篇7
关键词：维修时间窗,柔性作业车间调度问题,“教与学”优化,模拟退火
0 引言
为消除实际生产中的设备失效和生产计划外中断等现象,需要定期或不定期地对设备进行预防性维护(preventive maintenance,PM)。 按照设备维护时间可将预防性维护分为周期性维护和非周期性维护两类。一般来说,设备维护不可能在正常作业时进行,必须是作业结束后或开始前进行,所以周期性维护相对来说很难满足实际生产需要。目前关于周期性维护的研究文献相对较少。Naderi等[1]分析了柔性流水线车间的周期性预防性维护问题,采用基于遗传算法和人工免疫系统的两种启发式方法优化最大完工时间(makespan)。设备的非周期性预防性维护计划受到国内外学者的广泛关注。李林等[2]建立了一种面向租赁设备的顺序预防维护策略,通过最小化期望总成本率获得了租赁设备的优化租赁期限及维护计划。夏唐斌等[3]建立了一种设备层的单设备动态预防性维护的多目标决策模型。Ni等[4]研究了生产过程中不影响产量的预防性维护机会,开发了一个识别维护机会的预测模型。非周期性预防性维护会影响实际生产计划,增加作业车间调度的难度,因此考虑设备非周期预防性维护的车间调度问题的研究也逐渐引起了人们的关注。Fitouhi等[5]研究了针对单机非周期性预防维护的生产计划;Allaoui等[6]研究了双机柔性车间中带预防性维护的最小完工时间优化问题,假设条件为其中一台设备在调度开始的T个周期内必须完成一次预防性维护。针对柔性作业车间调度和预防性维护的集成优化问题,本文以最大完工时间为优化指标,在周期性维护的基础上建立了基于维护时间窗的集成优化模型,并设计了一种混合“教与学”优化(hybrid teaching-learn-ing-based optimization,HTLBO)算法,对该问题进行求解。
1 考虑维修时间窗的柔性作业车间调度优化模型
1.1 问题描述
柔性作业车间调度问题(FJSP)可描述如下:n个工件在m台机器上加工,每个工件分为K道工序,每道工序可以在若干台机器上加工,并且必须按一些可行的工艺次序进行加工;每台机器可以加工工件的若干工序,并且在不同的机器上加工的工序集可以不同。调度的目标是将工件合理地安排到各机器,使系统的某些性能指标达到最优。
FJSP包括两个子问题:确定各个工件的加工机器和确定各个机器上各工件的加工先后顺序。调度的优化指标是最大完工时间,即所有工件都被加工完成的时间,其中Ci表示工件Ji的完工时间。
为了便于求解,本文假设以下条件:① 每台机床一次只能加工一个工件;② 机器的准备时间和工序间的转移时间可忽略不计;③ 所有工件均不包含可被打断的工序;④ 不同工件前后次序没有硬性要求;⑤ 分属不同工件的工序,其前后次序没有硬性要求;⑥ 对于隶属同一工件的所有工序,必须依照既定的顺序加工。
对于集成优化问题,假设每台机器在调度过程中均有固定的一个或者多个维护时间窗,所有机器均要在时间窗内进行预防性维护。在生产过程中,如果要进行设备的维护,必然要停止生产活动,这就造成了生产调度和设备维护的冲突。 本文在柔性作业车间调度中安排设备维护时借鉴Li等[7]的研究,提出一种“向前偏移”的预防性维护方法,如图1所示,PM表示预防性维护,Oij表示工件i的第j道工序,t′i表示机器i的预防性维护时段的末尾时刻。具体步骤如下:
(1)先按照传统柔性作业车间调度进行决策,不包含预防性维护,只包含工序的最初调度。
(2)将所有设备的维护安排在各个机器维护时间窗的末尾。
(3)如果某一台机器预防性维护的时间段和其他工序的加工时间不冲突,则将该机器的维护和加工环节合并调度,否则执行步骤(4)。
(4)如果某台机器的预防性维护时间段和某个工序加工的时间段发生冲突,则将维护环节尽量提前到前一道工序末尾或者机器开始加工的时刻,然后安排冲突的加工环节和之后的加工环节。
当然,预防性维护以后工件加工顺序如果改变,有可能会减小最大完工时间,但这些改变会在算法中的“教学”、“自学”及模拟退火环节中实现,因为这几个环节都对工序的排序情况进行变更。
1.2 数学模型
对设备的预防性维护和生产调度进行有机集成,把设备的维护考虑在作业计划之中,以最小化最大完工时间为目标,机器的预防性维护尽量安排在既定的时间窗内,制定设备维护和各个工序的生产计划。建立的数学模型如下:
式中,Mjk为工件j的第k工序可用的机器集合,;tijk为工件j的第k工序在机器i上的加工时间,;bejk为工件j的第k工序开始的时间;enjk为工件j的k工序完工时间;tpi为机器i预防性维护所需时间;MCi为机器i的维护结束时刻;L为一个足够大的正数;wbi和wei分别为机器i的预防性维护时段的开始和结束时刻。
式(1)为模型的目标函数,即最大完工时间最小;式(2)和式(3)表示每个工件的加工工序的顺序约束;式(4)表示机器约束,即同一时刻,一台机器能且只能加工一种工件的一个工序;式(5)表示在特定的时刻,一台机器只能加工一种工件的一种工序;式(6)表示同一台机器上设备预防性维护和工序的加工不能存在冲突;式(7)导入维修时间窗约束;式(8)说明只有分到同一机器上的各工序才需要进行排序。
2 HTLBO算法求解集成优化问题
2.1 初始化
对于该优化问题,初始化时解的整体质量直接影响算法的收敛速度以及最终最优解的质量,所以必须选择比较好的编码方式,力求使初始化时产生的解的整体质量比较高。
柔性作业车间调度需要将每台机器上的不同工件的工序分配到合理的机器上,因此柔性作业车间调度中HTLBO算法采用两条编码,一条是基于工序的编码,用于说明不同工件的不同工序的加工先后顺序;另一条是基于机器的编码,用来确定具体每个工件的每个工序在哪一台机器上加工。
(1)工序序列的编码。 在基于工序的编码中,每个数字代表一个工件,数字出现的次数等于该数字对应工序的个数,且第k次出现的一个数字代表该数字对应的工件的第k个工序,例如,编码[1 2 2 1 3 1 2 3]表示工件1有三个工序,工件2有三个工序,工件3拥有两个工序。HTLBO算法对基于工序的编码采用随机交换的方法,将所有工件的工序按照顺序依次排列,如[1 1 1 2 2 23 3],然后随机交换工序位置,产生该解内基于工序编码的序列,如[1 3 1 2 2 1 3 2]。
(2)机器序列的编码。 基于机器的工序中,将各个工件的工序按照顺序排列下来,然后每个位置上对应的机器就是对应工序所在的机器。例如,编码[1 3 1 2 2 1 3 2]表明工件1的三个工序分别在机器1、3、1上加工;工件2的三个工序在机器2、2、1上加工;工件3的两个工序在机器3、2上加工。
为每个工序分配机器时要考虑该工序在不同可加工机器上的加工时间,最好选择最小值对应的机器来安排,同时需要兼顾考虑每台机器已经分配的负载情况,不能使某台机器的负载过大。为了提高初始解的质量,借鉴Kacem等[8]提出的利用时间表的分配方法AL(approach by Localization)和Pezzella等[9]改进的分配规则来进行编码,使得编码的鲁棒性比较强,进而得到质量比较高的初始解。Pezzella等[9]改进的遗传算法编码是在Kacem等[8]分配方法的基础上增加随机交换工件位置或者机器位置,以及在时间表中优先安排拥有全局最小加工时间的工序及机器,但是他们都没有考虑不同工件以及同一工件的不同工序的加工顺序。
本文在Kacem等[8]分配方法的基础上对机器序列的初始化进一步改进,提出“基于工序加工时间最短”的机器序列初始化策略,即将加工时间的表格按照已经确定的工序排序从上到下对每行重新排序。 具体过程如下:首先分配排在第一位的工序,选择加工该工序时间最短的某台机器分配给该工序;然后将表中该机器对应的加工时间位于该行之后的所有值均增加该工序的加工时间,表示该机器负载已经增加;最后对剩下的每个工序都进行同样的操作,最终确定对应该工序编码的机器分配方案。 如表1所示,对于基于工序的序列[1 3 1 2 2 1 3 2],Mi为第i台机器,首先将工序O11安排到最小加工时间的M3,将M3剩余可加工的工序时间增加4,再安排O31,最终的安排如表1最右边三列所示,得到的基于机器编码的序列为[3 1 2 3 1 3 2 1]。
由两列编码就可以结合上述动态安排设备预防性维护的方法来进行预防性维护安排,在某台机器上安排某工序后,若再安排其下一道工序将使得预防性维护与该工序冲突,则在该工序之后进行预防性维护。 解码后画出对应的甘特图,见图2。
由于要保证初始解的多样性,本文算法中一半初始解的机器编码采用表1所示的方法,另一半初始解的机器编码采用在该工序可用机器集合中随机分配机器的编码方法。
2.2 “教与学”的过程
2.2.1 “教学”阶段
“教学”的过程和“学生”互相学习的过程借鉴遗传算法(GA)中交叉算子的思想,使得新解能从“教师”或者其他“学生”解的序列中“学习”到新知识。
由于要保证交叉变异以后得到的子代都是问题的可行解,因此一个解内的两条编码所需要的交叉变异方式是不相同的,表示工序次序的序列采用元素分集合的交叉方法,表示加工机器的序列采用多点交叉方法。交叉操作力求可以将较优秀序列的元素尽可能地保留在新得到的序列中。
(1)工序序列串的交叉。工序序列的交叉过程是:首先把需要调度的工件集合Q任意分为非空子集Q1和Q2,新解内的编码先继承“教师”集合Q1内的工件对应的元素,然后将“学生”集合Q2内的工件对应的元素分别填充到新解内的编码空缺的元素中,如图3所示,其中Q1={2,3}。
(2)基于机器编码的交叉采用多点交叉的方式,具体操作是:先随机产生一条和编码等长的0-1序列,将“教师”中与0-1序列中的0位置相同的所有元素复制到新解中,将“学生”中与0-1序列中的1位置相同的所有元素复制到新解中,如图4所示。
2.2.2 “自学”阶段
算法中除了“教与学”的过程外,还增加了学生“自学”的过程,即通过对“学生”解中的两条序列进行一定的操作,看是否能得到质量更优的解。自学的过程借鉴遗传算法变异操作的思想,对已有的序列进行一定的扰动来计算确定得到的解是否为更优解。
(1)工序顺序序列的变异。表示工序顺序的序列串采用Insert变异,即从编码串中任意选取某元素,然后随机调换到序列的其他位置,如图5所示。
(2)表示加工机器序列的变异。不同工件的不同工序可选择的机器各不相同,所以这部分编码的变异采用随机选取某个工件的某个工序的方式,将该工序的加工机器随机替换成该工序可选择机器集合中的其他机器,如图6所示。
在教与学和自学阶段,算法均会产生新解。如果新解S′比原来的解S目标函数值更优,则一定用S′将S替换掉;如果S′不比S的结果更优,则引入一个选择因子c=rand(0,1),如果c≥0.5则将S′保留在算法解集中,否则丢弃S′。这样可以使得到的更优解保留下来,选择性保留非更优解既可以保证算法中解的多样性,还可以避免算法中解的数量过于庞大,影响算法的空间复杂度。
2.3 模拟退火算法
基本TLBO算法求解一定时间后很可能会陷入局部最优,可以将邻域结构的局部搜索加入该算法中,以提高算法整体的搜索效率[10?12]。 本文将模拟退火(simulated annealing,SA)算法加入到TLBO算法中,在算法中“教与学”和“自学”之后,采用SA算法对所得的解进行局部搜索,搜索对象是原有解集和产生的所有解,这样会导致算法整体时间复杂度有所增加,但可以很大程度地提高解的质量。
SA算法是一种根据热力学统计定律得出的邻域搜索技术,在过去求解组合问题时产生了良好的效果[13]。标准的SA算法首先随机产生初始解,设定初始温度T0、终止温度Tf、温度衰减率α,然后运用特定的邻域结构对已得到的解进行邻域搜索,若得到的新解更优,就用新解将旧解替换掉。随着算法的进行,温度也以一定比例降低,直到达到设定的终止温度Tf。
在SA算法环节中,对于两条编码需要用不同的邻域结构进行局部搜索。采用两种基于工序编码的邻域结构,分别是反向(Inverse)和交换(Swap)。反向的邻域结构就是在编码中随机选择一段编码,将所有元素逆转反向排序;交换的邻域结构就是在编码中随机选择两个元素交换位置。两种邻域结构如图7所示。
对于已知解中基于机器编码的邻域结构,采用本文算法提出的机器编码的变异方式进行变异。混合算法中模拟退火的步骤如下:① 设定初始温度T0、终止温度Tf、温度衰减率α 的值;② 选择已有解S,运用SA算法的邻域结构对S进行局部搜索得到S′,令 ΔS =f(S′)-f(S);③ 如果ΔS <0则将S用S′ 替换掉,否则令P =exp(-ΔS/T)决定是否用S′替换S;④ 使温度以衰减率α 缓慢降低,即Tk+1=Tkα,其中α ∈ (0,1);⑤ 重复步骤 ① ~ ④,直至满足停止条件。
由于要保证算法空间和时间复杂度不至于过高,所以模拟退火阶段得到的新解S″ 只有比之前的解S′ 更优才会得以保留,若S″ 比之前的解S′更优则将S′ 替换掉。
2.4 算法执行流程
HTLBO算法流程如图8所示,P的值由混合算法中模拟退火的步骤 ③ 获取,该算法具体步骤如下:① 按照2.1节所述进行算法的初始化,产生初始解集Pt,此时t←0,令解集规模为N;② 在初始解集中选择n个目标值较好的解作为 “教师”;③ 按照2.2节所述对解集Pt进行“教与学”的过程和“自学”过程,得到新的解集Qt;④ 运用SA算法对Qt中的解进行搜索,得到新的解集Qt′;⑤ 如果t<tmax(最大迭代次数),则t←t+1,返回步骤 ③;否则算法终止;⑥ 输出算法求得的最终解集的最优解。
3 实例验证与分析
为验证HTLBO算法的有效性,首先对文献[14]中的10个MK算例进行测试,均以最小化最大完工时间为目标,并与其他文献中的算法的测试结果进行对比。同时参考其他文献的数据生成三个实际模型的算例进行求解,与基本TLBO算法和遗传算法求解的结果进行对比。
3.1 基准实例的测试
HTLBO算法采用C++语言编程,计算机运行环境为2.5GHz Intel Core i5多核CPU和2GB RAM,算法的有关参数设置如下:种群规模Popsize=200,遗传代数Generation=100;模拟退火环节中,本文取初始温度T=1000,温度衰减率α=0.8,终止温度Tf=1,在温度T时,每个已有解进行5次的扰动。
MK实例的HTLBO算法测试结果与其他文献算法结果对比如表2所示,其中,m和n分别表示每个问题中机器和工件的数量,GA-Chen表示Chen等[15]的测试结果,GA-Jia表示Jia等[16]的测试结果,GA-Pezzella表示Pezzella等[9]的测试结果,TSPCB表示Li等[17]的测试结果,C表示测试目标makespan的值;Div为最优解相对偏差的值,其计算公式为
式中,Ci为对比算法求得的makespan的值;C为HTLBO算法求得的makespan的值。
由表2 可以看出,HTLBO算法求解出了质量比较高的解(达到或者超过其他算法求解出的makespan最优值),在表中已用黑体突出显示。
从表2中数据可以看出,对于前6个基准问题以及MK08问题,HTLBO算法均求解出了已有文献中得出的最优解;对于MK10 问题,HTLBO算法得到的解比其他4 种算法的解更优;只有MK07问题和MK09问题没有得到其他算法的最优解,但相差不大。
3.2 考虑维修时间窗的实例测试
对于具体实例的测试,传统的FJSP测试数据来自文献[14]中的MK04、MK07和MK09的三组数据,三个实例分别是15×8、20×5以及20×10的FJSP问题。对于三个问题中各台机器的预防性维护时间窗和预防性维护需要的时间tpi,假定分别如表3~表5所示,PMmn表示第m台机器的n次维护。 先用HTLBO算法获得三个结果,再分别用GA算法的解进行对比。
三种算法对三个算例分别进行求解得到的结果对比如表6所示。 由表6可以看出,针对本文建立的单目标集成优化模型,HTLBO算法对三个算例求得的结果均优于对比算法GA算法的结果,因此,本文提出的HTLBO算法求解基于固定维护时间窗的柔性作业车间调度和预防性维护的集成优化问题是有效的。其中,对于第一个15×8的算例,HTLBO算法求解出的最优解的甘特图见图9,图中某些工序之后紧跟的“PM”小条即是预防性维护的环节。Jm表示第m个工件,工序的先后顺序由甘特图中的时间先后来决定。
4 结论
商砼部生产调度作业指导书 篇8
产 调 度 作 业 指 导
2013年12月12日
书
生
生 产 调 度 作 业 指 导 书
一、职责
负责监督检查罐车、泵工、操作班等部门工作人员，按其作业指导书中相应的程序进行工作的责任。有权对不服从指挥或不按程序工作的上述人员暂停其工作。严格执行工作程序。对罐车、泵车、搅拌机等机械设备影响质量的不良因素，有向上级汇报的责任和向有关部门通报的责任。在遇有机械、质量、交通或生产方面突发事件而对产品质量有严重影响的情况下，有通报、汇报的责任和采取相应措施的责任。负责对生产现场的日常管理及协调工作。
二、调度的日常工作程序
生产调度的任务是：按照生产任务单安排、组织、指挥、协调混凝土的生产。确保生产任务安全、按时、按质的圆满完成，并完成其他相关职责。
1、生产调度人员必须按时到岗，每次供混凝土开盘前必须做到：督促检查罐车、泵车、操作室人员到岗情况和设备清洁、完好情况。
会同实验室技术人员根据已领到的配合比和施工方案了解主要材料的储备情况，主要是水泥仓储量和外加剂的品种和数量。与工地联系，了解辅助工作人员到位情况和工地施工准备情况，并再次核对提供混凝土的标号、施工部位和数量，待上述工作准备就绪后，方可开盘供混凝土。
2、开盘后，供应混凝土生产过程中的工作程序。供混凝土开盘后，组织混凝土开盘鉴定，召集有关人员协同技术员做好开盘鉴定工作。
在混凝土生产安全过程中，检查监督罐车司机、泵工、操作室人员是否严格按照其相应的工作工作程序规范进行工作，如果检查出不合格的工序或不正确的操作应及时纠正，必要时应检查其是否造成对质量的影响，并通报（有关人员）或汇报上级处理。认真执行施工方案要求，根据过程控制工作程序，合理安排罐车、泵车、搅拌机的工艺流程，做到均衡生产。在生产过程中，应经常与用户及公司工长进行联系，及时掌握现场生产动态，避免长时间的压车、等车情况的出现，尽量满足顾客的合理要求。妥善做好每一次混凝土施工的收尾工作，满足用户实际所需用量（合同量之内或某一百分比超加量）。
每次生产结束后，调度人员一定要等全部车辆安全返站，回收全部票据，确定无误后方准许下班。负责日常的生产现场环境和涮车台使用管理，协调水泥桨的再利用。对发现的问题及时组织处理。
3、记录
调度要认真、准确填写本班次各类票据（外租车登记表、返料报废表、日生产登记表）施工日志及交接班记录。调度人员应及时回收结算本班次的各类票据，尤其是混凝土运输单是质量控制和财务结算的重要依据，应认真检查填写发车时间、审核运到现场时间、卸料回站时间，如发现问题，应查清后作好记录。应做到本班次由单班调度负责回收，在连续供混凝土的情况下，当班调度负责回收上一班全部票据，并做好结算工作。
调度作业计划 篇9
以适时、适量、零库存为特征的JIT生产模式属于一类绿色、节能、低成本的生产方式。而提前/拖期 (Earliness/Tardiness, E/T) 调度作为支撑JIT生产的核心技术之一, 现已成为车间调度领域的重要研究分支。E/T调度要求订单或零件在各自的交货期准时完工, 提前或拖期完工都会产生相应的惩罚成本。如果订单或零件提前完工, 则会产生零件成品库存成本;对于化学、食品、药品等时效性较强的产品, 过早完工则会产生变质、失效、挥发或产品性能退化等问题;另外, 订单或零件的拖期完工则会打乱整个制造链的生产节拍, 使得下游生产环节出现整机配套缺件、停工待料、设备闲置等诸多问题。因此, 关注订单或零件的交货期, 以满足订单或零件的准时化交付为目的, 通过E/T调度来实现制造车间的精细运作和低成本运营, 对于改善目前离散制造企业存在的高投入、低产出、低利润率等问题具有一定的现实意义。
文献[1,2]将车间E/T调度问题归结为单机E/T调度和多机E/T调度两类, 并指出现有研究主要集中在单机E/T调度领域, 针对多机E/T调度问题的研究相对较少;在多机E/T调度研究方面, 大多又侧重于并行机调度, 而对于经典的作业车间调度研究相对更少。在作业车间E/T调度相关研究中, 文献[3]针对带有释放期和交货期约束的Job shop调度问题, 以最小化总加权拖期成本为目标函数, 采用基于邻域搜索的遗传算法进行求解, 但其目标函数中未考虑提前成本这一指标;文献[4]针对动态装配型Job shop的提前/拖期调度问题, 采用一种惩罚加权系数呈阶梯分布的分配求解规则, 但这种基于规则的求解方法存在优化性能不足的问题;文献[5]基于模糊控制和遗传算法, 提出求解Job shop提前/拖期问题的联合算法, 但调度模型并没有涉及提前/拖期的惩罚系数的差异性;文献[6]将作业车间E/T调度转化为约束优化问题, 并运用约束满足方法进行求解。
本文在现有E/T调度模型的基础上, 添加了零件可接受的最晚完工时间 (即deadline) 约束条件, 形成了一类带有零件deadline约束的作业车间E/T调度问题 (以下简称E/T/D调度问题) 。在车间实际生产中, 零部件拖期在所难免, 但受下游整机装配或客户订单的容许拖期范围限制, 零件拖期不能突破零件的deadline, 一方面, 一旦零件交付延迟于deadline时限, 则会导致下游整机装配出现严重拖期或客户拒收等重大损失;另一方面, 在企业与客户进行订单交货期协商的过程中, 企业利用订单或零件的deadline来评估客户订单的可行性, 可以事先避免因订单交货期设置不合理而导致的客户信誉受损、丢失客户等问题。
在E/T调度中引入零件deadline约束后, 即可形成一类零件交货期窗口, 即零件的交货期和deadline之间的交货期容许范围。如果零件在该交货期窗口内完工, 则会产生拖期惩罚成本;如果零件实际完工时间突破该交货期窗口, 则调度结果被视为非法解。这种带有硬约束的交货期窗口和文献[7,8]提出的交货期窗口存在本质差异, 文献[7,8]中的交货期窗口实质上属于一类软约束, 即如果零件在此交货期窗口内完工则不受惩罚;若零件拖期完工则产生拖期惩罚成本, 但并不会产生非法调度解。因此, 这类带有交货期窗口硬约束的作业车间E/T调度问题对零部件交货期的控制更为严格, 也更符合JIT对准时制生产的管理理念, 它适用于对交货期控制严格的诸如军工类、外贸类和配件供应类制造企业或生产车间。
将零件deadline约束条件引入作业车间E/T调度问题后, 调度算法设计面临的首要问题是如何避免因零件完工时间违反deadline约束而出现非法调度解;另外, 在满足零件deadline约束的前提下, 接下来面临的主要问题就是如何降低E/T调度总成本。为此, 本文提出了一种改进型遗传算法 (enhanced genetic algorithm, EGA) , 以期解决这类对交货期控制更为严格的作业车间E/T调度问题。
1 作业车间E/T/D调度模型
对于作业车间E/T/D调度问题而言, 其调度任务是指在满足工艺路线、机床能力、零件释放期和零件deadline等约束的前提下, 合理安排承制零件在各机床上的加工序列和开工时间, 使得提前/拖期总惩罚成本最小。
1.1 相关变量说明
作业车间调度问题可以描述为:n个零件J={J1, J2, …, Jn}在m台机器M={M1, M2, …, Mm}上加工, 每个零件Ji包含li道工序{o (1) i, o (2) i, …, o (li) i}。假设每个零件在同一台机床上只能加工一次且不能中断, 每台机床在同一时刻只能加工一个零件。
相关变量说明如下:rdi为零件Ji的释放期;di为零件Ji的交货期;
1.2 数学模型
该问题的数学模型描述如下:
其中, 式 (1) 为目标函数, 使得整个调度任务集的提前/拖期惩罚总成本最小化。式 (2) 为零件Ji的提前惩罚成本。式 (3) 为零件Ji的拖期惩罚成本。式 (4) 为工艺路线约束, 即同一零件Ji内两道相邻工序之间的时序关系约束。式 (5) 为机床能力约束, 即同一承制机床上加工工序队列的时序关系约束。式 (6) 为零件释放期约束, 即Ji的开工时间不应早于其释放期rdi。式 (7) 为零件deadline约束, 即Ji的加工完成时间不能迟于该零件的
2 改进型遗传算法设计
针对作业车间E/T/D调度模型, 在标准遗传算法框架内, 重点对解码操作进行了改进, 形成了图1所示的EGA求解框架 (包含EGA算法的伪代码和染色体解码过程两部分) 。在EGA算法设计中, 染色体编码采用基于工序的编码方法[9];初始种群完全随机产生;选择操作采用精英保留策略和锦标赛方法[9];交叉操作采用文献[10]提出的POX交叉算子;变异操作采用逆转变异方法[9]。
在车间实际生产中, 零件拖期会带来诸如整机装配延迟、订单损失和企业信用度降低等弊端, 因此, 相对提前问题而言, 拖期问题更为严重。首先, 零件不拖期或少拖期可以避免或者减小发生违反零件deadline约束的概率, 因此, 如何减少零件拖期是求解E/T/D调度问题首先需要解决的问题;然后, 在零件拖期严重导致违反deadline约束时, 如何通过算法内部的修复机制来及时调整调度结果以尽可能满足deadline约束, 是E/T/D调度问题有别于传统E/T调度问题的特殊之处;最后, 在满足deadline约束条件下, 如何在降低零件拖期惩罚成本的基础上, 进一步压缩零件提前惩罚成本, 从而最终保证提前/拖期总惩罚成本最低, 这是求解E/T调度问题区别于传统正规性能指标调度问题的关键所在。
基于以上三个问题的分析, 同时为了降低E/T调度问题求解的复杂度, 在设计EGA算法时, 采取了拖期优先的调度策略, 即将E/T/D调度问题分解为拖期子问题、修复子问题和提前子问题, 并将一个染色体的解码过程划分为主动解码、染色体修复和逆向重调度三个阶段。
(1) 拖期子问题。基于拖期优先的调度策略, 可以将非正则性能指标的E/T调度问题转化为正规性能指标的拖期调度问题。文献[11]指出:对于正规性能指标的调度问题, 最优调度解必在主动调度集中。因此, 针对这类拖期调度子问题, 采用主动解码方法[11]得到主动调度结果, 以此来降低拖期惩罚成本, 同时可以降低违反deadline约束的发生概率。
(2) 修复子问题。针对第一阶段主动解码中出现的违反deadline约束的染色体, 采用左移修复和逆转变异[9]相结合的染色体修复方法来调整问题染色体的基因序列, 以促使修复后的染色体满足deadline约束条件。
(3) 提前子问题。在主动解码得到的主动调度结果的基础上, 针对提前子问题, 第三解码阶段采用逆向重调度方法, 促使第一阶段的主动调度结果尽可能向零件的各自交货期靠拢, 以期在保持已有零件拖期成本不变的基础上进一步压缩提前惩罚成本。
下面针对EGA算法中的染色体修复和逆向重调度两部分进行重点阐述。表1所示的调度算例用来辅助说明操作算子。
注:为了保证通用性和覆盖面, 表中没有限定时间的具体单位, 后同。
2.1 基于关键路径的染色体修复方法
在初始种群和经过交叉、变异等操作产生的新种群内, 因deadline约束的存在, 在染色体解码过程中有可能产生非法调度解。为此, 在EGA算法设计中, 一旦解码过程出现非法解, 则立即中断当前主动解码操作, 并转入染色体修复环节。
染色体修复操作包括定位产生非法解的源头和修复问题染色体两个环节。非法解的源头定位通过临界工序和关键路径来进行筛选和过滤;修复操作则通过染色体修复方法来完成。如果染色体修复成功, 即产生满足E/T/D调度模型全部约束的新染色体, 则用新染色体替换种群中的原不可行染色体。
定义1 临界工序是指在解码过程中, 导致其所属零件违反deadline约束所对应的当前工序。
定义2 关键路径是由临界工序依据“首尾相抵”原则逆向组成的工序链。
在关键路径{o1, o2, …, ol}中, ol为临界工序, o1为依据零件释放期开工的工序, “首尾相抵”的原则是指满足stl=stl-1+pl-1, stl-1=stl-2+pl-2, …, st2=st1+p1;另外, 若ok∈{o1, o2, …, ol}, oi和ok均属于同一零件, oj和ok由同一机床加工, 且满足 (stk=sti+pi) ∧ (stk=stj+pj) , 则选择oi作为关键路径上的工序。
定义3:关键块是指在关键路径{o1, o2, …, ol}内, 满足sti=sti-1+pi-1 (1<i≤l) , 且在同一台机床上加工的工序所组成的工序集。
对于表1中的调度算例, 假设有一初始染色体Xo= (3, 4, 1, 1, 4, 4, 2, 1, 2, 2, 3, 3) , 对其主动解码后结果如图2所示。若解码过程中出现
识别出非法解产生源头后, 若执行左移修复操作的次数Ml没有超出其上限值max (Ml) , 则继续执行左移操作;否则, 执行逆转变异[9]修复操作以大幅度更改染色体基因特征。
左移修复操作是将在关键路径上的临界零件的工序尽量向左移动, 使得临界零件在其deadline之前完工。若某个块Bi中有临界工件工序u, JP[u]为工序u的工件前续工序, v为块Bi中位于u左侧的工序;Cv和CJP[u]分别为工序v和JP[u]的完工时间;由满足Cv≥CJP[u]的工序v组成集合V。左移操作的具体步骤是遍历关键路径上的所有块, 若某块中有临界工件工序u, 且V≠∅, 那么任选一个v∈V, 将u移动到v的左侧。
在图2所示的关键块中, 只有块B2的o
2.2 逆向重调度
实际上, 在保持第一解码阶段拖期成本不变的基础上, 延迟零件和工序的开工时间有助于降低提前惩罚成本。为此, 在EGA算法设计中, 引入逆向重调度方法, 具体计算步骤如下:
(1) 确定逆向重调度的坐标原点。染色体完成解码后, 对于提前完工的零件集E={Ji|Ci≤di}, 选择其交货期最大值me;对于拖期完工的零件集T={Ji|Ci>di}, 选择其完工时间的最大值mt, 取坐标原点为Or=max (me, mt) 。
(2) 计算各零件的逆向释放期rdi。提前完工零件Ji∈E的逆向释放期rdi=Or-di;而拖期零件Ji∈T的逆向释放期rdi=Or-Ci。
(3) 逆向重调度操作:①逆转染色体和工艺路线。设原染色体为X= (g1, g2, …, gL) (L为染色体长度) , 则逆向染色体
(4) 顺向还原操作。由于逆向工艺路线和原工艺路线存在一一映射关系, 则原工序o (l) i的开工时间st (l) i=O r-C (li-l+1) i。
(5) 依据步骤 (4) 中各工序的开工时间计算目标值。以染色体X1= (2, 1, 3, 1, 2, 4, 4, 3, 1, 3, 4, 2) 为例, 其解码结果见图3。因4个零件均是提前完工的, 所以me=max (404, 319, 334, 279) =404, mt=0, 则Or=max (me, mt) =404, 那么4个零件的逆向释放期依次为0、85、70和125。依据逆向工艺路线对逆向染色体
3 仿真实验
为了测试EGA算法性能, 选择混合整数规划 (MIP) 方法和EGA算法进行比较。EGA通过MATLAB 7.0编程实现, 利用FICOTM Xpress软件对上述E/T/D调度模型进行MIP求解。二者都在1.73GHz、1.0GB RAM的计算机上运行。时间阈值为1200s, 即当求解某个调度子问题的计算时间超过1200s时, 则认为该调度问题无解。
3.1 调度用例
在文献[12]构造的算例基础上, 本文通过调整问题规模、交货期松弛度和deadline松弛度产生18组参数组合, 每个参数组合随机生成10个调度子问题, 则共有180个调度问题作为测试用例。
(1) 调度问题规模n×m分别为10×10、15×10和20×10。
(2) 每个零件随机遍历所有机器, 加工时间在[1]间随机产生。
(3) 所有零件的释放期为0。
(4) 各零件交货期在[0.75tl blf, 1.25tl blf]区间内随机产生。其中, tl b为零件的完工时间下限值, 由文献[13]中的公式计算得到;lf∈{1.3, 1.5}为交货期松弛度。
(5) 零件Ji的deadline为
(6) 提前惩罚系数和拖期惩罚系数在[1]区间内随机产生。
因此, 3个问题规模、2个交货期松弛度、3个deadline松弛度, 共同构成18种参数组合, 采用N-M-lf-d标记一种参数组合。
EGA算法的参数设置如下:种群规模为50, 最大迭代次数为100, 交叉概率为0.9, 变异概率为0.1, 锦标赛选择算子中的竞赛规模K从{2, 3}中随机选取, 最大修复次数max (Mr) =10000, 左移修复操作的上限次数max (Ml) =200。
3.2 评价指标
①有解数。
每组10个调度子问题中, 在1200s内求得调度解的个数。
②平均计算时间。
每组10个调度子问题计算时间的平均值, 无解子问题以1200s参与计算。
③最小成本值。
每组10个调度子问题中, 有解子问题对应的提前/拖期调度总成本的最小值, 用以评测调度算法的寻优能力。
④平均成本值。
每组10个调度子问题中, 有解子问题的提前/拖期调度总成本的平均值, 用以评测算法在某类调度环境下的搜索能力。
⑤平均空闲时间。
每组10个调度子问题中, 各零件最后两道工序之间的空闲时间的平均值, 用来评测调度结果的均衡性。
⑥平均流动时间。
每组10个调度子问题中, 所有零件流动时间的平均值。
3.3 仿真结果及分析
EGA和MIP的实验结果见表2, 表2中的N/A表示在限定时间1200s内算法未得到调度解。图6、图7所示分别为两种算法在平均空闲时间、平均流动时间两个指标方面的比较结果。
由表2可知, 除较小规模10-10-1.3-1.0组算例外, EGA算法在每组算例中的有解数均优于MIP方法;尤其当调度问题规模逐渐增大时, EGA解决问题数的优势愈加明显。在限定的1200s内, MIP方法在180个算例中只取得了92个算例的调度解, 这是因为MIP方法的计算代价随着调度问题规模的增大而呈指数增加, 导致MIP方法在限定时间内解决问题数量相对较少。从最小成本值指标来看, EGA算法和MIP方法在较小规模算例上取得的最优值一致, 由于MIP方法属于一类数学优化方法, 而EGA算法能取得与这类精确数学方法同样的结果, 证明EGA算法同样具有搜索到最优解的能力。
对比图6和图7可知, 在平均空闲时间和平均流动时间两项指标方面, EGA算法均优于MIP方法, 这得益于在染色体解码过程中引入了逆向重调度方法, 使得调度结果尽可能右移并接近零件的各自交货期, 从而使得零件中间工序之间的等待时间大大缩短。
4 结论
本文在传统E/T调度问题的基础上, 引入零件deadline时间约束条件, 形成了带有零件deadline约束的作业车间E/T/D调度问题, 这类问题的求解有助于解决目前E/T调度中存在的零件拖期没有上界的问题, 同时有利于评估订单交货期的可行性, 从而避免因零部件或订单交付严重拖期而导致的订单拒收、信誉受损等问题。
针对E/T/D调度问题, 采取拖期优先的调度策略, 将这类非正规性能指标的调度问题转化为拖期子问题、修复子问题和提前子问题, 并在染色体解码过程中分别采用主动解码、染色体修复和逆向重调度三种方法, 以此实现在满足零件deadline约束条件下尽可能降低提前/拖期惩罚总成本的目的。最后采用调度问题规模、交货期松弛度和deadline松弛度三个参数可调节的共计180个调度实例进行了仿真实验, 实验结果表明, EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。
调度作业计划 篇10
柔性作业车间问题(flexiblejob-shopschedulingproblem,FJSP)突破了经典作业车间调度问题(job-shopschedulingproblem,JSP)的资源唯一性约束,是复杂的NP-hard问题[1],FJSP比JSP更适应现实制造车间的调度需求。实际生产调度往往需要满足多个相互冲突的目标,因此,大量生产调度属于多目标优化问题,寻求多方利益的合理折中成为生产调度决策的重要问题[2]。多目标柔性作业 车间调度 (multi-objectiveFJSP,MOFJSP)是面向多 个目标进 行优化与 决策的FJSP,是实现先 进制造技 术的基础 和关键,对MOFJSP问题的深入研究具有重要的理论意义和应用价值。
目前,求解MOFJSP的方法主要有进化算法和群智能优化算法。鞠全勇等[2]研究批量生产中以生产周期、最大提前/最大拖后时间、生产成本以及设备利用率指标为调度目标的FJSP优化调度问题,结合多种群粒子群搜索与遗传算法优点提出了具有倾向性粒子群搜索的多种群混合算法,提高了搜索效率和搜索质量。张超勇等[3]采用多目标进化算法解决具有工件释放时间、工件目标差异的FJSP调度问题,设计改进的NSGAⅡ算法求解MOFJSP的Pareto解集,并运用层次分析法选出最优妥协解。王云等[4]应用改进的强度Pareto进化算法求解以制造工期、加工成本及交货期为目标函数的MOFJSP问题,并利用模糊集合理论的方法得到Pareto解的优先选择序列和一个最优解。Kacem等[5]采用基于模糊进化的Pareto优化法求解MOFJSP,将优化解质量的多目标评价转化成一个单一的适应度函数,通过模糊控制规则动态地计算适应度函数权重,使进化算法搜索方向朝Pareto前沿逼近,得到Pareto非支配解集,并通过适应度函数各个目标值的下边界值来评价最优解质量。张静等[6]采用基于工序排序和机器分配的粒子表达方式直接在离散域进行位置更新,并通过Pareto支配的概念来比较粒子的优劣性,提出了一种基于Pareto支配的混合粒子群优化算法求解MOFJSP问题。Li等[7]结合多种局部搜索方法,引入Pareto概念对种群进行快速非支配排序,提出了基于Pareto的离散蜂群算法求解MOFJSP问题。
从现有文献 可以看出,MOFJSP问题的求解,既要选择性能优良的优化算法,也要适合在离散空间与高效的局部搜索方法相结合,以提高算法效率、防止算法过早收敛;还要针对多目标优化特点,采用基于Pareto概念对种群进行非支配排序,寻求MOFJSP问题的Pareto非支配解 集。本文选择集成遗传算法优胜劣汰机制、蚁群算法信息素和个体观察范围理论、粒子群算法群体记忆功能等优点的自由搜索(freesearch,FS)算法搜索MOFJSP问题优化解。FS算法的研究相比遗传算法、蚁群算法和粒子群算法等起步较晚,尚未形成系统的分析方法和较好的数学基础,特别是利用有效的数学工具对算法的收敛性分析和收敛速度估计是亟待解决的课题。本文在分析FS算法及其结构基础上,将FS算法引入离散领域,结合Pareto优化技术,提出基于Pareto优化的离散自由搜索 算法 (discretefreesearchbasedonPareto-optimality,P-DFS)求解MOFJSP问题;利用P-DFS算法对应随机过程的Markov链性质证明了所提算法的收敛性、估计了算法的收敛速度、分析了算法的时间复杂度;通过算例仿真和结果对比,验证了所提出算法的可行性和有效性。
1MOFJSP数学模型
企业内部不同部门,诸如采购 部门、销售部门、制造部门、生产部门等从自身利益考虑,对生产调度提出不同期望,因此,通过优化部门之间相互作用且相互冲突的期望目标,寻求各方利益的合理折中成为解决MOFJSP问题的关键。求解MOFJSP,即为对存在多个相互冲突目标的柔性作业车间调度方案进行优化与决策。为便于分析与研究,调度过程作以下假设和约束:每个工件的各道工序只能按照事先给定的顺序加工;每个工件在t=0时刻都可以开始加工,所有机器在时间t=0时刻都可以使用;在给定的时间内,一台机器只能加工一道工序;一道工序只能在其前道工序加工完成后,才能从其候选机器集合中选择一台空闲机器加工。
本文针对n个工件在m台机器上 加工的MOFJSP的最大完工时间、机器总负荷和单台机器最大负荷等3种性能指 标进行优 化。建立MOFJSP的数学模型如下:
式中,ci为工件Ji的完工时间;Cmax为最大完工时间;WT为机器总负荷;max(Wh)为单台机器最大负荷。
2FS算法及其离散化
2.1FS算法基本原理
FS算法是Penev和Littlefair于2005年提出的一种源于高等群居动物的群聚进化算法[8]。FS算法通过个体在邻域附近多维连续空间的小步幅精确搜索和在全局空间的大步幅勘测两个搜索过程寻找目标函数的最优解。
FS算法结构由初始化、搜索过程和终止判定3个步骤组成。Penev等[8]的研究表明,FS在收敛速度上优于遗传算法,在求解约束优化问题上优于粒子群算法,在求解平板问题上优于差分进化算法。
2.2离散 FS算法
目前,FS算法的研究主要集中在连续型问题上,即描述FS算法个体及其运动状态规律的量是连续的,在离散领域,FS算法的应用文献甚少;而MOFJSP调度是典型的组合优化问题,为了将FS算法用于求解MOFJSP,本文提出离散FS算法(discretefreesearch,DFS)。FS离散化的关键是根据MOFJSP问题领域定义个体寻优的位置更新规则。
2.2.1DFS的编码
DFS算法采用基于工序和机器分配相结合的编码方式进行编码,如图1所示。工件的每道工序Oij在可用设备集Mij ⊆{1,2,…,m}中的一台设备上加工。第1条染色体编码表示的工序顺序为 (O21,O11,O22,O31,O23,O12,O32),第2条染色体编码表示的机器序 列为 (M1,M2,M3,M2,M4,M4,M3)。
2.2.2个体位置更新
在FS算法搜索空间中,个体位置Xi=(x1,x2,…,xr)是一个r维向量,结合MOFJSP特点和文献[9]提出的位置更新策略,定义FS算法个体位置更新公式为
式中,为搜索操作算子;xji为第j个个体的第i维分量;x0ji 为搜索起点;pk为信息素;sj为灵敏度;h(x0ji,,xji)、g(e,xji)分别为个体小步幅搜索、大步幅勘测产生的新位置。
(1)个体从小步幅搜索获得的寻优信息如下:
(2)个体从大步幅勘测获得的寻优信息如下:
(3)调度方案可行性判定[10]。由于个体位置移动产生的调度方案不一定是可行调度方案,故需进行调度方案可行性甄别,其操作为
式中,为第j个个体经移动d位置后产生调度方案πk的操作算子;σ为调度方案;l为调度方案中个体移动前后的位置差;ф为工件序列修正程序。
即在新调度方案中,扫描工件排列,若某一位置分配多个工件,则结合FIFO(first-in-first-out)规则、工序约束和机器约束将多余工件向后移动到最近的空位 上;若某位置 为空,则同样结 合FIFO规则、工序约束和机器约束从其后面最近的含有多个工件的位置上提取一个工件插入;最终得到可行调度方案。
3P-DFS算法设计
3.1符号说明
针对优化问题搜索过程的主要符 号说明如下:X为搜索空间;f:X→F ={f(x):x∈X}为搜索空间映射到解空间的适应度函数;F为优化问题的可行解集;F* 为最优解集;为偏序集;M为优化问题的Pareto非支配解集;A(·)为归档集。 {η(t)}t=0+∞表示随机搜索过程,对应于最优解集和搜索 灵敏度,即η(t):(X(t),S(t)),其中,X(t)为当前最优解集与当前随机搜索最优解集的并集,即X(t)=F*∪Xt,Xt为第t次搜索解集,S(t)为第t次搜索灵敏度。YX为最优解集X(t)所属状态空间;Ys为灵敏度S(t)所属状态空间;Y为随机过程η(t)所属状态空间;Y* 为随机过程η(t)所属最优状态空间。
3.2P?DFS算法
MOFJSP面向FJSP的多个相互冲突目标实施调度方案优化与决策,是复杂组合优化问题。本文将FS算法引入离散领域,在实现FS离散化的基础上,结合求解多目标优化问题的Pareto优化技术,提出P-DFS算法求解MOFJSP问题。在MOFJSP离散域内,P-DFS算法个体在邻域附近多维空间作小步幅精确搜索,在全局空间作大步幅勘测,目的是寻找目标函数优化解。个体将自己在邻域空间发现的最优解以信息素的形式保存起来,并利用信息素和灵敏度选择下一步搜索的位置。信息素反映多目标函数解的质量;灵敏度犹如“过滤器”,不仅保留优良个体,而且对不良个体重新初始化。不同的个体有不同的灵敏度,同一个体在不同的搜索步中有不同的灵敏度,个体选择适合其灵敏度的信息素作为下一步搜索的起始点。每次随机迭代搜索到的优化解进入归档集,通过非支配排序得到非支配解,最终构成Pareto非支配解集[11]。因此,P-DFS算法不仅有利于提高算法 种群质量,而且对寻 优搜索方 向朝Pareto前沿逼近有重要的导向作用。基于双目标P-DFS算法搜索方向如图2所示。
3.3P?DFS算法步骤
(1)设定搜索初始值。设定种群规模N,搜索代数G,搜索小步幅数T,邻域半径Rji。
(2)种群初始 化。随机产 生初始种 群{η(0)},并计算个体适应值。
(3)根据Pareto支配关系,生成初始种群归档集
(4)释放初始信息素pk →xjkp。
(5)计算灵敏度sj。
(6)选择新的搜索起点x′0j=xk(sj,pk)。
(7)计算搜索步个体适应值。
(8)生成迭代种群{η(t)}t≥0。
(9)种群个体非支配排序,生成新的归档集:
(10)释放信息素pk →xjkp。
(11)终止判定。
4P-DFS算法收敛性与收敛速度分析
4.1P?DFS算法的 Markov链
P-DFS算法对应的寻优过程中,个体根据信息素和灵敏度进行随机搜索,信息素和灵敏度在不同搜索步中不断更新,第t次搜索信息素和灵敏度由第t-1次搜索的当前最优解和搜索得到的解集所决定。
定义1当时,称{η(t)}t=0+∞为P-DFS算法对应的离散时间随机过程。
定理1P -DFS算法对应 的随机过 程{η(t)}t=0+∞满足η(t)=(X(t),S(t)),则{η(t)}t=0+∞为一个离散时间的Markov过程。
证明{η(t)}t=0+∞为离散时间随机过程,由P?DFS算法步骤(6)~ 步骤(8)知:第t次搜索的状态(X(t),S(t))只由第t-1次搜索状态(X(t-1),S(t-1))决定;由P-DFS算法步骤(2)知:(X(0),S(0))随机生成,因此有
即{η(t)}t=0+∞为一个离散时间的Markov过程。
证毕。
推论1P -DFS算法对应 的随机过 程{η(t)}t=0+∞是Markov链。
证明由P -DFS算法对应 的随机过 程{η(t)}t=0+∞为Markov过程,X(t)所属状态空间YX 为离散状态空间,且S(t)所属状态空间YS是由YX决定的,得到η(t)所属状态空间Y为离散状态空间,故{η(t)}t=0+∞是Markov链[12]。
证毕。
4.2P?DFS算法的收敛性分析
定义2[11]P -DFS算法搜索到的Pareto非支配解构成的 集合为Pareto非支配解 集,记为,即
Pareto非支配解集对应的状态空间称为最优状态空间,记为Y* 。
定义3[13]设A、B是有限基 础集X的子集,则d(A,B)=|A∪B|-|A∩B|是X的幂集距离。
定义4[12]若Markov链转移概率与初始时刻无关,则称Markov链为齐次的。
定义5[14]随机过程从一个状态经过有限步转移到达另一状态的条件概率大于0,则称随机过程的转移矩阵是不可约的。
引理1[14]齐次有限状态的离散时间参数Markov链的概率 特性主要 由一步转 移矩阵决定。
引理2[13]无论初始分布如何,一个具有有限状态空间和不可约转移矩阵的齐次Markov链经常以概率1无穷多次地访问每个状态。
定理2[13]若随机过程{η(t)}t=0+∞是转移矩阵不可约的齐次有限Markov链,则当t→∞时,d(f(η(t),F*)以概率1趋于0。
证明方法参见文献[13]。
定理3P-DFS算法对应的Markov链以概率1收敛到Pareto非支配解集。
证明P-DFS算法状态空间YX的状态有限性决定了P-DFS算法对应的随机过程是有限Markov链;P-DFS算法步骤(2)、步骤(6)解释了转移概率与初始状态无关,决定了P-DFS算法对应的Markov链是齐次的;P-DFS算法步骤(5)~步骤(9)决定了其转移矩阵是不可约的,由定义5和引理1可得:P-DFS算法对应的Markov链是不可约的。根据定理2,当t→∞时,d(f(η(t),F*)以概率1趋于0成立,由定义3可得:P-DFS算法对应的Markov链以概率1收敛到最优解集F*。由引理2可得:P-DFS算法对应的Markov链的每一个最优解将以概率1搜索到,并经过PDFS算法步骤(9)非支配排序获得Pareto非支配解集,因此,P-DFS算法对应的Markov链以概率1收敛到Pareto非支配解集。
证毕。
4.3P?DFS算法的收敛速度分析
则称{η(t)}t=0+∞为一个吸收态Markov链。
证明由推论1,P-DFS算法对应的随机过程{η(t)}t=0+∞是一个Markov链,当优化解 为Pareto非支配解进入归档集时,η(t)属于最优状态空间Y* ,{η(t)}t=0+∞∩Y*≠ø成立;由P-DFS步骤(9)知:
可得
所以
成立,即
成立。因此{η(t)}t=0+∞是一个吸收态Markov链。
证毕。
P-DFS算法对应 的随机过 程满足吸 收态Markov性,引入首达最优解期望时间 (expectedfirsthittingtime,EFHT)[16]表征P-DFS算法的收敛速度。
定理5给定P-DFS算法对应 的吸收态Markov链和最优状态空间且其首达最优解期望时间为
证明由定理4可得:{η(t)}t=0+∞是一个收敛的吸收态Markov链,若τ是首 达最优解 时间,t=1,2,…有
可得
可得
证毕。
4.4P?DFS算法复杂度分析
假设优化目标 函数个数 为r,种群规模 为N。从3.3节算法步骤可以看出,P -DFS算法寻优主要由5部分组成:第1部分计算个体适应值,其时间复杂度约为O(rN);第2部分与归档集中非支配个体比较,其时间复杂度为O(rN2);第3部分计算灵敏度,其时间复杂度约为O(rN);第4部分选择新的 搜索起点,其时间复 杂度约为O(rN),第5部分为个体小步幅搜索和大步幅勘测,其时间复杂度为O(rN)。因此,P -DFS算法的总时间复杂度为
P-DFS算法的时间复杂度与个体规模、优化目标函数个数有关,与基于Pareto非支配排序[17]的时间复杂度相同。
5P-DFS算法实验结果与比较
为验证算法寻优性能,采用文献[18]提供的10×10和8×8FJSP问题实例 进行寻优 测试。算法采用MATLABR2009a编程语言实现,微机运行环境为:CPUE6500,主频2.93 GHz,内存2G;搜索初始值设定为:种群规模N =50,搜索代数G =100,搜索小步幅数T =50,邻域半径Rji =2。P-DFS算法的流程如图3所示。
由于初始解质量对P-DFS算法求解的速度和质量影响较大,本文采用大部分初始种群个体随机生成,结合启发式规则生成部分优良个体,得到初始种群。其中,工序安排优先分配加工时间最短、分配剩余工作量最多的工件;机器分配优先安排加工时间短并且负荷低的设备给某个工序。文献[5,18-21]给出了两个实例在最大完工时间Cmax最小、机器总负荷最小和最大机器负荷Wh最小等3种性能指标函数的测试结果,其中文献[5]给出10×10FJSP问题实例的3个目标函数值下界分别为f1=7,f2=41,f3=5。以式(1)为目标函数,分别运行P-DFS算法10次,求解10×10FJSP和8×8FJSP问题实例的最优解,10次仿真结果均收敛到最优解,生成相应的归档集,并最终得到3个Pareto非支配解,与文献[5,18-21]结果比较详见表1和表2。
从表1和表2结果可以 看出,对于10×10FJSP和8×8FJSP问题实例,分别运行P-DFS算法获得的3个非支配解总体上不劣于文献算法给出的最优解(文献结果统称为最优解)。单目标函数值下界是衡量算法局部搜索能力的重要体现,针对本文实例,P-DFS算法搜索到了两个实例所有单目标函数值下界,并求解到相应的Pareto非支配解 集。因此,采用P -DFS算法求解10×10FJSP问题和8×8FJSP问题不仅可行而且效果良好。
6结论
(1)针对MOFJSP问题特点,将FS算法引入离散领域,在定义算法个体位置更新和判定调度方案可行基础上,结合Pareto优化提出了P-DFS算法。在MOFJSP离散域内,通过DFS算法小步幅精确搜索和全局空间的大步幅勘测,以及最优解的非支 配排序,使算法种 群的寻优 方向朝Pareto前沿逼近,最终求解MOFJSP问题的最优可行解。
(2)利用P-DFS算法的Markov链性质,证明P-DFS算法以概率1收敛到Pareto非支配解集;引入首达最优解期望时间和 吸收态Markov链性质分析P-DFS算法收敛速度;从P-DFS算法的主要寻优过程分析其时间复杂度。
【调度作业计划】推荐阅读：
车间作业计划调度07-07
作业车间调度问题09-16
调度员职责范围、工作标准、作业程序07-26
项目调度计划07-20
计划调度职责08-12
计划调度系统05-20
配网调度计划管理05-25
生产计划与调度06-29
电力调度计划管理07-20
电网调度安全管理计划06-05