启发式算法在服装生产线平衡中的应用现状

许 霄,夏 明,2,

(1.东华大学 服装与艺术设计学院,上海 200051;

2.东华大学 现代服装设计与技术教育部重点实验室,上海 200051)

生产线平衡是在考虑生产作业有效时间的前提下,对产量、质量和生产效率进行全面优化的过程[1]。长期以来,服装生产过程中流水线的设计及平衡的控制在很大程度上依赖于生产技术人员的个人经验[2]。然而,应用这种经验知识得到的生产线编排结果通常很不理想,难以确保每个工作站都可以达到相同的生产速度,从而实现真正的平衡,需要经过不断的调整试验,才能达到相对理想的状态[3]。

启发式算法在求解具有复杂组织结构的生产线系统问题上具有很大的优势。启发式算法是以直观或经验构造的,在可行的时间和计算空间内为问题提供可行的解决方案[4]。启发式算法在生产线平衡问题中得到了广泛应用,并取得了良好效果,可以有效实现生产线的自动化设计,提高企业的适应性和市场竞争力,对服装企业的发展和信息化管理具有重要意义[5]。

概括了生产线平衡问题的定义与分类、服装生产线平衡的目的与方法,综述了近年来国内外生产线平衡问题的研究进展,以及启发式算法在服装缝纫流水线优化编排研究中的应用现状,从研究对象、目标与方法层面对现有研究进行了系统的分析,并设想了未来服装生产线平衡优化研究的发展方向。

1 生产线平衡优化

1.1 生产线平衡问题

生产线平衡是通过均衡生产线各工序和作业负荷,使各作业时间与进度尽可能一致,从而降低生产成本、提高生产效率的重要手段。生产线平衡问题关系着生产活动中综合决策和企业生产的可持续性。

在实际的工业生产中,生产线可以有多种分类方法。从不同的布置方式来看,有直线型生产线、U型生产线和平行生产线;从加工产品的品种来看,有单模型生产线(只生产一种产品)、多模型生产线(不同种产品分批生产)和混合模型生产线(同一时间同时生产多种产品)。

生产线平衡问题[6]主要分为两类:第1类(Type-1)是在给定的循环时间内,以最小化工作站的数量为目标的平衡优化;第2类(Type-2)是对于给定数量的工作站,以最小化生产周期时间为目标的平衡优化。

1.2 服装生产线平衡原理

服装生产线平衡是指合理安排各工位的人员、设备及工序,使各工作地的生产时间和进度实现最大程度的平衡统一。目的是实现工作量的均衡分配,减少人员流动所需的时间,提高工作地的空间利用率。

具体的平衡优化方法[7]包括以下几种:(1)将可以在同一工作地的小工序合并,将难以协调完成的大工序拆分;(2)将综合技术能力强的工人安排在负荷较大的工作地;(3)减少生产作业过程中的无效动作;(4)改良工作组织结构;(5)制造或引入先进设备。

2 生产线平衡优化研究现状

2.1 以工作站数量最小化为目标

Neda Manavizadeh等[8]根据综合技术能力,将工人分为4类,每个工作站的标识标明了允许在该工作站工作的工人类型。将模拟退火算法应用在确定工作站数、合理化工人分配、设计平衡过程库存的基于看板的告警系统3个阶段中,可以有效提高混合模型生产线的效率。该算法考虑了永久和临时两种类型的操作人员,将工人进行分类,并设计了一个报警系统,对于问题的处理方面考虑得十分完善,可用于平衡同时生产由不同客户订购的不同商品的混合模型生产线,并最小化其直接人工成本。

Zixiang Li等[9]提出了两种新的压缩搜索空间的译码方案,以平衡匹配站内的工作负载,减少序列相关的空闲时间,并使用分级目标来保留对解决方案的微小改进。对双边装配线平衡问题扩展了一个简单的迭代贪婪算法(IG),得到了一个高质量的初始解,并进一步提出了改进的局部搜索算法,计算结果证明了所提出的译码方案、新的分级目标和改进的迭代贪婪算法的有效性。在未来的研究中,可以使用所提出的IG算法来研究其他双边装配线平衡问题,例如双边装配线中的动态、模糊和随机数据等。

唐秋华等[10]针对第1类混流双边装配线平衡问题,提出了一种改进的局部搜索迭代算法,在给定工位数的条件下,通过引入新的二级目标,改进最优解。提出了一种基于站点的启发式解码方法来平衡配对站点的负荷,在解码过程中,通过最终的配对站点调整策略进一步减少了站点数量。设计了一种改进的启发式初始化和局部搜索方法,并验证了该方法的合理性。后续可针对混流双边装配线平衡问题中存在的多约束或不确定因素问题开展进一步研究。

Jianping Dou等[11]提出了一种新型的面向任务序列(FTS)的粒子群算法(FTSOPSA),它直接记录一个粒子的FTS,命名为直接离散PSA(DDPSA),用于求解SALBP-1问题。在DDPSA中,提出了一种新的基于多片段交叉的更新机制,并将片段突变纳入到DDPSA中,提高了探索能力。通过对FTSOPSA和现有的两种遗传算法进行比较,发现提出的DDPSA对SALBP-1的性能有较高的期望,同时也表明FTS的直接编码似乎比基于优先级的间接编码的FTS对SALBP-1的解法更有优势。

2.2 以周期时间最小化为目标

Sebnem Demirkol Akyol等[12]提出了一种基于多规则的结构型随机搜索算法来求解生产线工人分配和平衡问题,使用39条工序优先级规则和4条工人优先级规则来排序工序和选择工人,将生产线的周期时间降到最低,并用该方法对文献中每一个测试实例进行试验。结果表明,提出的算法均优于文献中的所有其他算法,可应用于需要考虑人工效率的生产线。此外可以在启发式算法中加入一些其他任务或工序选择规则,将启发式算法扩展到解决不同生产线平衡问题,如U型、随机工人可用性、混合型生产线等。

Mayron César O等[13]针对残疾人工作中心装配线的工人分配和平衡问题,提出了一种基于任务和工人分配优先规则的启发式框架,并比较了在3种可能用途上的性能:作为独立方法、作为元启发法的初始解决方案生成器以及作为混合遗传算法的解码器。结果表明,该方法是快速的,可有效降低生产线的周期时间。

Xiaokun DUAN等[14]提出了一种改进的基于Max TF启发式规则的人工蜂群(IABC)算法,Max TF规则定义了优先级权重,使任务分配合理,初始解质量高,并进一步提出了一种设计合理的侦察蜂随机策略来规避局部最优解。试验结果表明,基于所提出的Max TF规则的IABC算法用于求解TALBP-2问题有良好的有效性和稳定性。但该模型没有考虑到一些现实因素,例如同步任务约束、概率任务时间、每个工作站的不同工人数量以及工人的行走时间。此外,还可以考虑其他目标优化,例如最大化平衡效率、最小化总空闲时间和最大化工作负载平滑度指数。

Qiaoxian Zheng等[15]提出了一种改进的工位蚁群优化算法,用于求解ALBP-2问题,蚁群算法被用来为每个工作站寻找不同任务的更好组合,并提出了一种迭代压缩机制来减少搜索空间,算法基于3个启发式因素:任务时间、后继者的数量及可发布后继者的数量,采用两种信息素及任务分配机制,为每个工作站寻找更好的组件解决方案,并通过与文献比较,验证了该算法的有效性。

Zixiang Li等[16]建立了双面机器人装配线的混合整数规划模型来最小化生产周期,针对非多项式性质的问题,提出了一种协同进化的粒子群优化算法,该算法利用全局最优个体的局部搜索来增强搜索强度,修改全局最优来强调搜索,重新启动机制来逃避局部最优。将所提出的算法与其他已有的5种著名的元启发式算法进行了比较,计算和统计结果表明,在研究中考虑的大多数问题上所提出的共同进化粒子群优化算法都优于其他大多数元启发式算法。今后的研究,可以通过在实际应用中考虑更多的约束条件来解决现实问题,研究多目标合作共进化算法来解决多目标双边机器人装配线平衡问题,例如多模型、混合多模型的双面机器人装配线或同时拥有机器人和工人的装配线等。

Hager Triki等[17]提出了ALBP-2问题的一个新扩展,即所谓的多目标装配线资源分配和2型平衡问题(MOALRABP-2),其目的是尽量同时减少一条线路的周期时间、平均绝对偏差和时间单位成本,以满足任务之间的优先次序和资源之间的兼容性限制。提出了混合多目标进化算法(HMOEA)来得到一组不同的最优解,试验结果表明,该方法具有良好的性能。

3 服装生产线优化研究现状

Selin Hanife Eryuruk[18]利用Arena仿真程序对某服装生产线进行了仿真,将“概率行平衡技术”和“最大集合规则算法”两种启发式生产线平衡技术综合应用于多模型生产线设计,通过迭代有效减少了工作站数量,获得有效的生产线平衡结果。但第一次应用概率行平衡技术后,进行操作合并和增加机器数量的过程没有运用合适的算法,而是通过人工进行修正,没能实现系统全过程自动化。该混合算法适用于解决仅生产一款产品的单模型生产线。

James C.Chen等[19]提出了一种使流水线平均绝对偏差最小化的分组遗传算法,算法考虑了具有劳动技能水平的人工神经网络,此外还对仿真结果进行描述性统计和方差分析,确定了性能评估的主要作用和相互作用的影响因素。该分组遗传算法适用于解决与该研究类似的单模型生产线平衡率问题,后续可将该算法原理进一步拓展应用在解决混合模型、多模型、单模型的生产线平衡率问题中。

Mahmut Kayar等[20]详细分析了某企业衬衫生产工艺,确定了操作匝数、使用时间和使用的机器,并采用霍夫曼法和仿真法分别对衬衫生产线进行了平衡,结果显示,这两种技术都可以有效用于生产线的平衡。仿真方法的最大优点是能够在生产线上尝试新的脚本,但同时需要考虑每个操作的不同时间的可能性;而霍夫曼法对每个操作只考虑一个时间,流水线根据优先级进行平衡,该方法不需要使用不同的脚本。因此需根据企业生产目标和产品模型特性对两种方法进行选择。

闫亦农等[21]分析了现有离散型服装生产线,并在此基础上建立了智能编制系统。以遗传算法为参考,改进了粒子群优化的迭代机制,建立了服装生产线编制的数学模型,为实现服装缝制生产线的智能编译,开发了相应的服装生产线编译软件,并应用了具体的服装生产实例。该研究结合服装吊挂系统,参考其他行业粒子群算法优化生产思想,对服装生产流水线进行平衡优化,服装企业可利用该系统将工序、人、机器进行智能化组合,减少员工等待时间,提高流水线整体效率。

张旭靖等[22]分别按照生产线3种不同的布置模式(工艺流程、工艺类型和服装部件),使用遗传算法对生产线进行平衡优化,有效减少了生产线缝制设备和人员的数量。其中,按工艺流程模式布置,对生产组织要求较高,适合单模型生产线;按照工艺类型模式布置,设备可同时用于多种工序,适合多模型生产线;按照服装部件模式布置,生产周期短,反应速度快,适合多品种小批量生产。以不同布置方式设计多种生产线方案,为企业的实际生产提供参考。

4 研究方法归纳与分析

通过对生产线平衡问题的研究,了解到生产线设计需要对工作站、设备、工人、工序进行分配,以达到预定的目标,可以通过最小化工作站的数量、最小化生产线周期时间和最大化生产线平衡率等方式实现。同时还发现,设备成本、生产效率、工人熟练度、任务时间与设备成本的相关性、柔性比等都需要引起重视。

ALBP问题的类型日益复杂,算法的高性能显得尤为必要。表1显示了生产线平衡优化研究中使用的算法,其中使用最多的是遗传算法和粒子群优化算法。表2显示了服装生产线平衡研究中使用的算法,其中遗传算法在服装生产线优化设计中应用最广。遗传算法和粒子群优化算法的高应用价值显示了这些方法在解决ALBP问题中的普及度和稳定性。文献中所选用的算法,包括著名算法和最新有效算法,在重新实施的过程中,都遵循着有效性和简单性的原则进行了一些必要的调整和改进。

表1 生产线平衡优化算法

表2 服装生产线优化研究算法

在以工作站数量最小化为目标的Type-1问题研究中,多数文献运用了改进的某种局部搜索算法(模拟退火、迭代局部搜索等)。局部搜索的做法是从初始解开始,对邻域执行搜索,如有更优的解,则移动至该解,并继续搜索该解的邻域,否则返回当前的解。局部搜索算法有简单灵活、易于实现的优点,但很容易陷入局部最优解,初始解和邻域结构直接影响求得解的质量。文献中提出的改进式局部搜索算法均已通过仿真模拟验证了有效性,因此局部搜索算法适用于寻找工作站的数量。

在以生产周期时间最小化为目标的Type-2问题研究中,多数文献运用改进的某种启发式仿生算法(遗传算法、人工蜂群算法、粒子群优化算法等)。由于搜索过程的不确定性,这些算法都是不确定的,它们都是通过仿生理论的记忆机制来强化局部搜索,或避免早熟收敛,得到全局最优解。其优点是获得全局最优解的机会较多,每个个体都通过相互互动来更好地适应环境,最终的最优目标总是在个体行为的运动中显现出来。在Type-2问题中,多数文献的研究对象都是单模型生产线,说明这类问题相较于第1类更加复杂,文献中提出的算法也都通过仿真模拟验证了有效性,因此这些启发式仿生算法适用于缩短单模型生产线的周期时间。

目前基于启发式算法的服装生产线平衡优化设计研究还较少,已有研究主要是针对只生产一款服装的单模型生产线,多以提高生产线平衡率为优化目标,且与其他领域的生产线平衡研究相比,运用的算法较传统且种类单一。虽然文献中的研究采用传统算法均得到了能够提高生产平衡率的可行解,但目前的研究范围还不够广泛,实际服装生产情况更为复杂,因此还需要进一步深入研究。

5 结束语

目前基于启发式算法的服装生产线平衡优化应用研究取得了一定的研究成果,但相比于其他领域,启发式算法在服装领域的研究较少,且研究对象、目标及算法较为单一,缺乏系统性和全面性。

服装生产具有小批量、多品种的特点,且生产中往往存在多个优化目标,而现有的研究多针对以提高生产线平衡率为目标的单模型生产线。未来可拓展研究范围,根据服装生产的实际需求,通过权重分配综合多方面的优化目标,进一步研究多模型、混合模型生产线。

现有的服装生产线平衡研究大部分直接采用传统的启发式算法,存在一定的局限性,少部分采用针对其他领域开发的改进算法,但与服装生产线的适配度不高。未来可结合各类算法的优缺点,针对性地开发适用于服装生产线的优化算法,进一步开展更符合服装生产实际的系统性研究。