混合流水线调度问题研究综述

混合流水线调度问题研究综述

1流水作业相关研究混合线条处理（hybrid接口，hfsp）或柔性线性排列问题，1973年，salvador根据石油工业的背景提出了这一问题。HFSP具有很强的工程背景,广泛存在于化工、冶金、纺织、机械、半导体、物流、建筑、造纸等领域,大量生产、制造、装配、运输、合成过程中的调度问题以及互联网服务、集装箱搬运等问题均可归结为HFSP。鉴于流水作业特征以及某些工序上存在并行机的特点,HFSP是传统流水线调度与并行机调度的综合,具有更大的求解难度,在数学上已被证明为NP-hard问题。因此,HFSP的研究具有重要的学术意义和应用价值。迄今,HFSP得到了广泛和深入的研究与应用,尤其近十年在算法方面取得了较大进展。本文将介绍HFSP的数学模型、分类及其推广,重点综述其算法研究的进展,并对HFSP的应用给予总结,最后提出若干有待进一步研究的方向和内容*。2工件数、工序及调度记Ji为工件序号,i=1,2,…,n,其中n为工件总数;mj为每一阶段的机器数,j=1,2,…,S,其中S为阶段总数;pij为工件Ji在进行j道工序的加工时间;wij为工件Ji进行第j道工序的等待时间;wi=∑Si=1wij为工件Ji的总加工等待时间;di为计划完成时间或交货期;sij为工件Ji在第j道工序的开始加工时间;ri为工件Ji可进行第一个操作的时刻,即为释放时间或准备时间;eij为工件Ji的第j道操作的完成时间;Ci为工件Ji的加工完毕时间,Ci=eiS,即Ci=ri+∑Sj=1(wij+pij);Cmax=max{C1,…,Cn}为最大完成时间;Fi=Ci-ri为工件Ji的流经时间;Li=Ci-di为工件Ji的推迟完成时间;Ti=max{Li,0}为工件Ji完成的拖后时间;Ei=max{-Li,0}为工件Ji完成的提前时间;Nw(t)为t时刻处于等待状态的待加工工件数;Np(t)为t时刻正在加工的工件数;Nc(t)为t时刻已加工完毕的工件数;Nu(t)为t时刻未加工完毕的工件数;L为足够大的数。HFSP可描述为:n个工件在流水线上进行S个阶段的加工,每一阶段至少有一台机器且至少有一个阶段存在并行机,同一阶段上各机器的处理性能可相同也可有所区别,在每一阶段各工件均要完成一道工序,但各工件的每道工序可在相应阶段上的任意一台机器上加工,已知工件各道工序的处理时间,要求确定所有工件的排序以及每一阶段上机器的分配情况,使得调度指标最小。生产调度的目标通常是对企业资源进行优化配置以提高经济效益,调度指标可以根据影响企业成本费用和生产效率与效益的主要因素来确定。典型性能指标包括[3~13]:基于加工完成时间的性能指标:譬如最大完成时间Cmax、平均完成时间-C、最大流经时间Fmax、平均流经时间-F、加权流经时间∑ni=1ωiFi等。基于交货期的性能指标:譬如最大推迟完成时间Lmax、平均拖后时间-T、最大拖后时间Tmax、拖后工件个数nT等。基于库存的性能指标:譬如平均待加工工件数-Nw、平均正在加工工件数-Np、平均已完成工件数-Nc、平均未完成工件数-Nu等。多目标综合性能指标:譬如流经时间与总拖后时间的综合F-+λ∑ni=1Ti、最大完成时间与总拖后时间的综合Cmax+λ∑ni=1Ti、E/T指标∑ni=1(αiEi+βiTi)等。经典HFSP通常考虑如下假设:任意工件一旦开始加工均不可中断;一台机器同一时刻只能加工一个工件;一个工件同一时刻只能在一个阶段的一台机器上加工;任意工件可在任意阶段的任意一台机器上加工,且同一工件在同一阶段不同机器上的加工时间相同;目标函数为最小化最大完成时间。则,HFSP的混合整数线性规划模型可描述如下:其中,式(1)表示调度指标;式(2)确保每个优先级位置只能对应一个工件;式(3)确保每个工件只有一个优先级位置;式(4)表示任一阶段每个工件只能有一台机器加工;式(5)表示同一阶段上工序完成时间和开始时间的关系;式(6)表示同一工件在进行下一道工序之前必须完成当前工序;式(7)表示同一阶段调度排列中排位越前的工件开始处理时间越早;式(8)表示同一阶段分配在同一机器上的排位靠后的工件必须等靠前的工件加工完后才可进行;L足够大使当处于不同排位的工件不在同一机器上加工时式(8)才成立。3多目标混合云图的研究传统HFSP按照并行机的类型可以分为三类:相同并行机混合流水线,即每一阶段上工件Ji在任一台并行机器上的加工时间相同;均匀并行机混合流水线,即每一阶段上工件Ji在任一台并行机器上的加工时间与该台机器的加工速度成反比;不相关并行机混合流水线,即每一阶段上工件Ji在任两台并行机器上的加工时间互不相关,而取决于工件与机器的匹配程度。考虑到实际加工环境和工艺约束,近年来研究人员对HFSP进行了扩充和推广,提出了若干新的HFSP调度问题及模型。限于篇幅,下面仅介绍研究较多的若干推广HFSP,还有一些文献讨论特定的HFSP,在此不再一一赘述。(1)基本HFSP假设每一阶段内每个工件都只需要在一台机器上加工,即要满足工件唯一性约束。随着现代生产技术和并行计算机系统的发展,许多实际多阶段调度问题要求在某些阶段上工件由几台机器同时加工,例如多个机器手同时对一个零件进行装配,从而提出了带多处理器任务的HFSP。(2)流程工业生产中广泛存在无等待约束,要求工件在前一操作完成后直接传送到下一机器进行操作。为了衔接相邻两个操作以保证加工的连续性,工件的操作可能会延迟。譬如钢铁生产,在连铸-热轧过程中加热器对板坯边缘进行加热,热板坯直接被传送到热轧厂,无需经过加热炉加热,该过程不仅要考虑铁水流动的及时性,同时也对实时操作提出了较高的要求。由于等待时间会导致温度降低而需要再加热,因此熔化的铁水必须在冷却前连续进行操作以免降低钢的成分,进而出现了零等待HFSP。(3)现实情况中工件的到达受到各种意外情况的影响,生产调度过程必须考虑动态因素或动态的影响,从而提出了动态混合流水线调度问题。(4)实际调度问题涉及多个目标,而目标之间往往存在冲突,因而多目标混合流水线调度问题的研究更具有现实意义。譬如,Alfieri等以硬纸板生产为背景研究了多目标HFSP。(5)实际调度过程中有时没有中间缓冲库存,譬如印刷电路板生产线,但工件可以留在机器上直到下一阶段的一台机器空闲,从而提出了带阻塞的混合流水线调度问题。(6)通常工件的加工时间是确定的,但实际生产中由于机器原因或者操作错误而导致加工时间不确定,从而提出了不确定或随机HFSP。如果不确定性用模糊数表示,则称为模糊调度问题。譬如,Hong等研究了模糊HFSP的一种模糊启发式规则。(7)基本HFSP假设每一台机器每次只能加工一个工件,即要满足机器唯一性约束,但在钢铁生产等现实生产中广泛存在一台机器同时可处理多个工件的情况,即组批处理,从而提出了带组批的混合流水线调度问题。4改进拉格朗日松弛算法相对于建模研究,HFSP的算法研究更为丰富。归纳而言,主要分为精确求解算法、启发式方法和智能算法三大类。下面逐一给予简要综述。(1)精确求解算法。精确算法尽管在理论上能够得到最优解,但其计算时间通常无法接受,因此算法一般只适用于解决小规模问题。对于精确算法,求解HFSP最常用的是分支定界法(B&B),算法利用树形结构将问题的解空间按照给定规则分解成不同的解分支,然后通过定界方法去除不必要的解分支以缩小搜索范围。在两阶段HFSP方面,文献针对第一阶段存在并行机的HFSP提出了一种与启发式算法相结合的B&B算法,可在250个工件10台机器的情况下仍保持良好的性能;文献提出了一种基于改进搜索策略的B&B算法,当工件数最大达到1000时跟下限偏差仍保持在0.1%以内,但对于工件数在20~50的中等规模问题其性能有待提高;文献讨论了带约束的两阶段HFSP的复杂性。在多阶段HFSP方面,主要思路是将B&B与其它算法相结合来解决问题。譬如,文献提出了一种与遗传算法相结合的B&B算法,用遗传算法获得一个有效上界,再用B&B算法进一步进行求解;类似地,文献、文献提出了与启发式算法相结合的B&B算法,用启发式算法获得有效上界,用B&B算法进一步进行局部搜索。另外,文献~文献应用混合整数规划的方法对问题进行了深入研究;文献提出了一种基于次梯度的拉格朗日松弛算法,解决了以最小化总拖期时间为目标的HFSP;唐立新等以钢铁生产为背景研究了实时无等待HFSP,建立了整数规划模型并提出了一种改进拉格朗日松弛算法,可在较少迭代数内取得满意的优化性能,尤其对于大规模问题;进而,文献应用改进拉格朗日松弛方法研究多处理器任务的动态HSFP,对多达100个工件的问题进行了测试并取得了较好性能。(2)启发式方法。启发式算法基于特定启发规则能够快速得到问题的解,但难以保证解的质量。启发式算法通常采用基于优先级的规则。由于HF-SP属于NP难问题,精确算法的执行时间会随着问题规模的增加而呈指数增长,因而很多学者致力于研究启发式算法。在两阶段HFSP方面,注意力主要在于应用启发式规则处理复杂HFSP,在推广问题的同时改进已有的启发式方法。在前向调度生成机制的基础上,文献提出了逆向生成机制并形成了正向-逆向交替调度算法;针对两阶段不相关并行机问题,Riane等提出了一种基于动态规划的启发式方法;针对均匀并行机的加工环境,Kyparisis等在文献的基础上提出了一种改进启发式算法,当组内并行机速度相差很明显时依然可以保持良好的性能;文献提出了一种基于改进Johnson规则的启发式方法,有效解决了带不相关并行机的两阶段HFSP;针对带模糊加工时间HFSP,文献提出了一种模糊启发式规则;针对具有多处理机的HFSP,文献提出多种启发式规则;针对具有不可用时间(包括故障和定期维修)的HFSP,文献提出了三种启发式方法,并通过与分支定界的比较验证了三种算法的有效性。另外,文献~文献分别应用启发式方法对带有并行组批的HFSP进行了求解。最近,Yang对两阶段HFSP的计算复杂性提出了一种新的证明方法。在多阶段HFSP方面,由于问题的复杂性,启发式方法的研究并不多见。Santos等受到求解作业车间调度的互换规则的启发,提出了一种适合求解HFSP的改进互换规则,基于右移、左移和重组三种规则实施搜索,通过对大量问题的测试验证算法的有效性。文献对多种求解流水线调度的常用启发式规则进行推广,提出了多种适合求解HFSP的启发式方法。文献针对带工艺约束的HF-SP,对流水线调度的常用启发式规则进行改进,提出了六种启发式规则。文献提出了一种基于NEH规则的列表调度启发式方法,对以最大拖期为目标的HFSP进行了求解,并考虑了准备时间和工件的优先约束条件。Hong等提出了一种改进的模糊启发式规则,对包含模糊数据问题进行了研究。最近,Ying等应用启发式方法对具有多处理机的多阶段HFSP进行了研究,而文献对启发式方法进行了一定程度的总结。(3)智能算法。启发式方法的优势在于可在较短时间内快速得到解,但难以保证解的质量的满意性。随着计算智能的发展,多种智能优化方法不断提出并有效解决了HFSP。目前,求解HFSP的常用智能算法包括遗传算法(geneticalgorithm,GA)、模拟退火(simulatedannealing,SA)、禁忌搜索(tabusearch,TS)、蚁群算法(antcolonyoptimiza-tion,ACO)、微粒群优化(particleswarmoptimiza-tion,PSO)及人工免疫系统(artificialimmunesystem,AIS)等。下面就近十年的文献给予简要综述。在GA方面,近些年的工作主要是注重对传统HFSP的扩充问题的应用以及实现并行算法。文献提出了一种结合启发式规则的GA,第一阶段机器的分配和排序采用GA解决,而第二阶段往后则采用先到先服务(FCFS)方法进行排序,进而生成可行调度。文献提出了一种随机键(randomkey)编码方式,采用单点交叉生成可行调度,其性能优于其它基于局部搜索的启发式算法。针对具有不相关并行机、独立准备时间及机器约束的HFSP,Figielska等提出了一种结合列生成法的GA,列生成法的作用在于在第一阶段生成一个次优调度,进而再利用GA进行求解。文献对GA的参数进行了实验设计,优选参数明显改善了算法的性能。另外,文献、文献应用GA对多目标问题进行了研究;文献用GA对具有有限中间缓冲区的带有批量分割的HFSP进行了研究;Belkadi等提出了解决多阶段HFSP的一种并行遗传算法(parallelGA,PGA),首先将种群分成若干子种群,然后在进化过程中让个体在种群之间流动,其性能明显优于传统GA;在此基础上,作者提出了大规模并行遗传算法(massivelyPGA,MPGA)的概念,在个体更新时引入模拟退火机制,其性能优于PGA。最近,Urlings等以实际瓷砖生产为背景,研究了具有工件优先约束、准备时间和时滞的复杂HFSP,提出了多种结合不同机器分配规则的GA,其性能明显优于其它基于局部搜索的启发式方法。在SA方面,Low对不相关并行机HFSP进行了研究,提出了一种结合启发式规则的SA算法,采用启发式算法初始化,而用SA进一步改进解;Jin等提出了两种SA方法,采用不同的分配规则对工件在机器上进行分配,同时提出了一种计算下限的方法;最近,Naderi等以最小化最大完成时间和最大拖期为目标,提出了一种基于迁徙机制的SA方法,并引入了一种“giantleap”算子加强算法跳出局部极小的能力;在此基础上,文献对文献中的问题进行延伸,考虑了阶段间运输时间,通过对不同问题的测试验证了算法的有效性。在TS方面,Tang等针对具有有限中间缓冲区的HFSP,以最小化所有工件的加权完成时间为目标提出了一种基于分散搜索机制的TS算法;文献以实际生产问题为背景,应用TS对带有时间窗的两阶段零等待HFSP进行了研究;针对具有多处理器任务的动态HFSP,文献以最小化最大完成时间为目标提出了一种基于动态规划的TS算法,通过仿真验证了有效性。另外,Akrami等应用TS对带有批量分割的HFSP进行了研究。在ACO方面,文献提出了一种基于局部和全局信息素评价的ACO,并采用串行调度策略进行求解,同时对ACO的参数进行了实验分析;文献应用ACO对具有多处理器任务的HFSP问题进行了求解,采取ACO对第一阶段的工件进行排序,第二阶段往后则按照先到先服务原则进行排列;最近,Khalouli等以最小化总提前拖后惩罚为目标提出了一种结合启发式的ACO算法,性能明显优于基于局部搜索的其他启发式算法。相对GA、SA、TS和ACO而言,其他智能算法的研究相对较少。在PSO方面,Tseng等针对具有多处理器任务的HFSP,提出了一种基于最小位置值编码的PSO,并应用变邻域搜索技术对其进行局部搜索。在AIS方面,Engin等以最小化最大完成时间为目标,提出了一种基于克隆选择原则和亲和力的AIS算法;针对具有准备时间的HFSP,文献提出了一种基于加速机制和约束机制的AIS算法,加速机制确保快速收敛到次优解,约束机制避免陷入局部极小。另外,Kahraman等针对多处理器HFSP提出了一种并行贪婪搜索算法,算法分成分解和构造两步实现,并将四种启发式规则引入算法以加强搜索。Behnamian等以最小化提前拖后总工件数为目标,针对具有准备时间的HFSP提出了一种混合智能算法,采用ACO进行初始化,采用SA避免陷入局部极小,采用变邻域搜索改进种群。另外,人工神经网络在HFSP中有所应用[78~80],在此不再一一赘述。5实际生产过程的仿真研究HFSP具有很强的工程背景,其研究成果已在许多领域得到了应用,同时很多学者将注意力集中于以实际生产过程为背景的HFSP。限于篇幅,在此仅介绍一些代表性的研究。唐立新等将炼钢过程归结为HFSP,建立了整数规划模型并提出了改进的拉格朗日松驰算法;轩华等对炼钢-连铸-热轧工序中出现的HFSP进行了研究,分别用启发式算法和拉格朗日松驰算法进行求解,通过对实际生产数据的分析达到了预期的效果;文献以加权拖期时间为目标,应用启发式方法对包含16个阶段的钢铁生产过程进行了研究,同时应用了组批的方法,通过仿真验证了算法的有效性。以集装箱处理系统为背景,Chen等建立了带阻塞HFSP的模型,以船只的服务时间最短采用TS进行求解。针对集装箱码头集卡调度问题,Zhang等讨论了基于属性(进口箱或出口箱)的带阻塞HFSP问题,建立了基于属性的多目标调度模型,采用基于工件和机器的编码构建了四段染色体结构,采用加权方法构建GA的适应度函数,并基于实例在仿真软件上建立了仿真模型。另外,Jin等建立了印刷电路板制造过程的三阶段HFSP模型,并应用GA进行求解。根据胶片生产的实际背景,Aghezzaf等研究了以库存成本最优为优化目标的两阶段HFSP,并应用启发式方法进行求解。Lin等建立了商标制造问题的两阶段HFSP模型,第一阶段带准备时间约束,第二阶段存在专用机,作者应用启发式方法通过调度一天内混合商标的生产来最小化加权最大拖后时间。针对混凝土砖的生产过程,文献建立了HFSP模型并进行了研究;文献以多层陶瓷电容器生产过程为背景,对一类HFSP进行了研究。6研究的意义和应用价值HFSP具有广泛的应用背景,同时问题本身属于NP难题,其研究具有重要的学术意义和应用价值。纵观HFSP模型、问题推广、分类、算法、应用各方面的研究现状,研究大多集中于建模和算法设计,大量工作有待进一步深入研究、探讨和完善。(1)研究并行机和多约束情况下hfsp的研究首先,尽管近年来HFSP的模型不断丰富,但仍存在许多假设和抽象,与实际问题还存在较大差距。笔者认为,应该强调模型的实用性和可扩展性,加强对实际问题中限制条件建模和分析,提出更符合实际的问题模型。其次,从目前文献来看,大多数HFSP的研究集中于相同并行机,而对均匀并行机、不相关并行机的研究相对较少,而后两者更符合实际生产。因而,有必要加强对均匀并行机、不相关并行机情况下的HFSP的研究。同时,从目前文献来看,多处理器任务HFSP的研究文章越来越多,同时许多学者考虑HFSP的特定约束条件,譬如准备时间、机器合格性、阻塞等,但大多仅考虑单一约束,没有考虑多种约束下的HFSP。显然,多约束情况下的HFSP研究更具有现实意义和挑战性。另外,目前的研究大多考虑以最小化最大完成时间为目标,而对其他目标涉及相对较少,譬如流经时间、提前/拖后、库存成本等,而这些目标更接近于生产的实际评价指标。另外,在多目标问题、不确定问题方面的HFSP建模研究也有待深入。(2)hfsp的研究首先,应该深入启发式规则的研究。HFS