具有缓冲区约束的流水车间调度问题综述

Internal Combustion Engine & Parts• 51•柔性流水车间有限缓冲区排产问题综述陈世佳(沈阳建筑大学信息与控制工程学院，沈阳110168)摘要:针对柔性流水车间有限缓冲区排产问题提出了三种优化算法，进行比较指出各算法的优缺点，给出数学模型并提出以最大 完工时间为目标，总结了近年来在该领域的研究现状，并对今后研究方向进行展望。

关键词：柔性流水车间；有限缓冲区；优化算法;最大完工时间0引言柔性流水车间有限缓冲区排产问题在化工，制药，汽车配件制造等中普遍存在，有很强的工业背景，是一 类非常复杂的调度问题。

本文提出了 LBFFSP的数学模 型，指出了有限缓冲区的研究现状，参考大量文献总结 了解决该问题的相关算法，并对今后的研究方向提出了 设想。

1问题描述与数学模型1.1 LBFFSP问题描述柔性流水车间有限缓冲区排产问题可以描述为：如图1所示，包含n个工件的加工队列在车间顺序进行m 道工序的加工，m道工序中至少有一道工序包含两个或气脱硝处理中。

3.2非催化还原法脱硝技术在进行烟气脱硝反应的过程中，经常采用非催化还原 法脱硝技术，这种技术在实际应用过程中其反应的烟气温 度能够高达850益到1100益之间。

通过还原剂的添加和催 化，能够及时的将烟气处理中的物质实现氧化还原，并且 能够及时的分解，生成NH3并且能够与反应室内的NO2发生还原反应，生成N2。

在实际烟气脱硝的工艺处理实施 中，要考虑到瓦斯发电的基本容量，这样才能在其容量的 允许范围内进行发电生产，并且形成专门的生产——脱 硝--还原--氧化等反应链条。

如果在脱硝过程中，瓦斯发 电机的容量较小，那么就会导致其在实际的应用中，不能 对其进行优化处理，所以这时的烟气脱硝率也会随之下 降，最高可脱硝的烟气率为80%。

因此在实际的烟气脱硝 反应处理中，应该充分的考虑到瓦斯发电机的基本容量，然后才能有针对的进行脱硝工艺选择。

车间作业调度(JSSP)技术问题简明综述l 引言生产调度是CIMS 研究领域生产管理的核心内容和关键技术，车间作业调度问题(JSSP)是最困难的约束组合优化问题和典型的NP 难问题，其特点是没有一个有效的算法能在多项式时间内求出其最优解． 现代经济日益强化的竞争趋势和不断变化的用户需求要求生产者要重新估价生产制造策略，如更短的产品生产周期和零库存系统等，而JSSP 生产环境最适宜满足现有经济和用户的需求． 利用有限的资源满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和时间，以保证所选择的性能指标最优，能够潜在地提高企业的经济效益，JSSP 具有很多实际应用背景，开发有效而精确的调度算法是调度和优化领域重要的课题．研究JSSP 问题最初主要采用最优化方法，但计算规模不可能很大，且实用性差．近年来，基于生物学、物理学、人工智能、神经网络、计算机技术及仿真技术的迅速发展，为调度问题的研究开辟了新的思路． 本文根据JSSP 问题的大量文献，对研究理论与方法进行系统的分类并介绍这一领域的最新进展，讨论进一步的研究方向．2 JSSP 问题的一般框架2．1 问题描述JSSP 问题可描述为：m 台机器(用集合()m j j M M 1==表示)加n 个工件(用集合|()ni i J J 1== 表示)，每个工件包含由多道工序组成的一个工序集合． 工件有预先确定的加工顺序，每道工序的加工时间t 在给定的时间每个机器只能加工一个工件，并且每个工件只能由一台机器处理． 不同工件的加工顺序无限制，工序不允许中断；要求在可行调度中确定每个工序的开始时间ij s 使总完工时间max C 最小，即(){}M M J J t s C C j i ij ij ∈∈∀+==,:max min )min(max *max 求解满足以上条件的工件加工顺序即构成JSSP 调度问题．流水作业调度问题(FSSP)是JSSP 问题的特殊形式(即所有工件有相同的加工工序)． 此外目标函数可选取等待时间、流程时间和延期时间的平均值或者最大值等，或多个目标组合形成的多目标问题．2．2 JSSP 的模型表示2．2．1 整数规划(IP)模型整数规划模型由Baker 提出，需要考虑两类约束：工件工序的前后约束和工序的非堵塞约束． 用jk t 和 jk c 分别表示工件 j 在机器k 上的加工时间和完工时间．如果机器h 上的工件加工工序先于机器K （用k h J J <表示），则有关系式jh jk jk c t c ≥-；反之，如果h k J J <，有jk jh jh c t c ≥-。

车间调度问题综述报告车间调度问题是指在一个车间内进行多道工序的生产加工，需要合理安排工序的先后顺序、工序所需的设备和人力资源，以及调度时间等因素，以最大限度地提高生产效率和资源利用率的问题。

车间调度问题在生产操作管理、资源优化和生产效率提升等领域具有重要的应用价值。

车间调度问题通常涉及到多个工序的安排顺序和时间安排。

其中，工序顺序的安排决定了每个工件在车间内的加工流程，工序时间安排则涉及到各工序之间的等待时间和加工时间。

合理的工序安排和时间安排可以最大限度地减少生产过程中的空闲时间和非生产时间，提高生产效率。

对于车间调度问题的研究，主要涉及到以下几个方面：1. 调度策略与算法：研究如何制定合理的调度策略和设计高效的调度算法，以最小化完成整个生产过程所需的时间和资源成本。

常用的调度策略包括最早截止时间优先、最小松弛度优先、最小工期优先等，而调度算法则可以基于规则、启发式算法、精确算法等不同的方法进行求解。

2. 调度问题的建模与求解：研究如何将实际的车间调度问题转化为数学模型，以便于进行求解。

常用的调度模型包括流水线调度、柔性作业车间调度、多品种多装配线平衡调度等。

而求解方法则可以使用线性规划、整数规划、模拟退火、遗传算法等不同的优化方法进行求解。

3. 调度系统与软件开发：研究如何开发车间调度的信息系统和软件工具，以便于帮助生产调度员进行实时的车间调度。

这些系统和软件可以将关键数据进行集中管理和监控，可以自动化生成调度方案，并可以进行实时调整和优化。

4. 车间调度问题的应用领域：车间调度问题在不同的生产场景中都有广泛的应用，包括制造业、物流配送、交通运输等领域。

在制造业中，合理的车间调度可以最大限度地提高生产效率和资源利用率；在物流配送中，合理的调度可以最小化货物的运输时间和成本；在交通运输中，合理的调度可以最大限度地减少交通拥堵和行车时间。

综上所述，车间调度问题是一个综合性的问题，涉及到多个因素的综合优化。

１８１０系统工程理论与实践第３０卷从图中可以看出，该结果保证了物料的供应，是符合生产要求的可行调度结果．在产线连续性方面，除了该计划旬内因为存在定修造成的被迫中断外，计划调度最大程度的避免了产线上合同的生产中断，同时调度尽量将相同规格的合同安排临近加工，以降低飙格转换时间和成本，比如合同１１和１２，属于同规格，在１、３、４、５生产中心的生产均为紧邻加工．因而，改进遗传算法可以有效且高效地帮助调度员在短时间内获得较为理想的调度结果．但是，正如第３节中的分析，改进遗传算法的编码形式决定了“合同在各生产中心的加工顺序是一致的”，上述调度结果存在尚需改善的方面，包括：①为了保证供料，第—个生产中心需要提前近８个时间单位开始生产供料，阻碍了生产中心的同步启动生产；②合同前后工序的衔接不够紧密，造成部分合同的工序间等待时间较长，比如：２号合同经过１＿４＿５生产中心，工序间间隔的等待时间共计１１．２０５个时间单位（约两天），这势必造成缓冲库存的压力．鉴于此，辅以局部搜索优化算法，对合同的生产顺序加以调整，可得改进后的调度结果，此结果也得到了钢管企业生产排程人员的认同，以甘特图显示如图５（每一格表示一天）．图４改进遗传算法下的生产计划调度程序结果显示图图５辅以局部搜索优化算法的计划调度结果显示图比较单一使用改进遗传算法的结果与局部优化后的结果，不难发现：①调度结果保证了产线的生产连续，相同属性的合同尽量连续加工，以降低转换造成的生产中断；②每条产线上的合同加工顺序相对灵活，生产中心最早开始时间与最迟开始时间相差仅４个时间单位，尽量保证所有生产的同步启动；⑦改善了合同的前后工序衔接状况，使得合同在前道工序加工完毕后尽早进入下道工序的生产加工，减轻缓冲库存的压力，比如：２号合同在局部搜索优化算法运算后，经过１—４—５生产中心，工序间等待时间从１１．２０５个时间单位（约两天）降至３个时间单位．不仅如此，图６＿９较为详尽的比较了两种算法调度结果相关的缓冲库存量．单纯使用改进遗传算法所得到的各缓冲库存平均量为：２０７．２３８吨（２号生产中心缓冲库）、５５２．５６吨（３号生产中心缓冲库）、１２６６．３１（４号生产中心缓冲库）和４９３９吨（５号生产中心缓冲库）．而辅以局部搜索算法后的各缓冲库存平均量为：１７９．２０吨（２号生产中心缓冲库）、４７６．４６吨（３号生产中心缓冲库）、１０１７．１７吨（４号生产中心缓冲库）和４６２６．３吨（５号生产中心缓冲库）．分别降低了１３．４％、１３．８％、１９．７％和６．４％．因而，上述两种算法的调度结果均可以有效控制库存，防止涨库，而后者更可以进一步地降低缓冲库存量．带有限容量缓冲库的多目标柔性作业车间调度优化作者：李琳， 霍佳震， LI Lin， HUO Jia-zhen作者单位：李琳,LI Lin(华东理工大学,商学院,上海,200237;同济大学经济与管理学院,上海,200092)， 霍佳震,HUO Jia-zhen(同济大学经济与管理学院,上海,200092)刊名：系统工程理论与实践英文刊名：SYSTEMS ENGINEERING-THEORY & PRACTICE年，卷(期)：2010,30(10)被引用次数：2次1.Pinedo M Scheduling Theory,Algorithms and Systems 20052.李建祥;唐立新;庞哈利热轧无缝钢管生产作业计划研究[期刊论文]-系统仿真学报 2003(09)3.李建祥;唐立新;吴会江热轧钢管主生产计划模型与算法研究[期刊论文]-系统工程学报 2005(05)4.Ouelhadj D A multi-agent system for the integrated dynamic scheduling of steel production 20035.Chang S Y;Chang M R;Hong Y A lot grouping algorithm for a continuous slab caster in an integrated steel mill[外文期刊] 2000(04)6.Tang L X;Liu J Y;Rong A Y A mathematical programming model for scheduling steel making-continuous casting production[外文期刊] 2000(02)7.唐立新;杨自厚;王梦光炼钢--连铸最优炉次计划模型与算法 1996(04)8.宁树实;王伟;潘学军一种炼钢--连铸生产计划一体化编制方法[期刊论文]-控制理论与应用 2007(03)9.Gao Z;Jin H;Xu N N An optimization model for the production planning of overall refinery[期刊论文] -Chinese Journal of Chemical Engineering 2008(01)10.石苓;窦延平基于生产计划排单的遗传算法的优化与应用[期刊论文]-计算机仿真 2005(22)11.Zanoni S;Zavanella L Model and analysis of integrated production inventory system:The case of steel production 2005(93/94)12.Witta A;Stefan V Simple heuristics for scheduling with limited intermediate storage 200713.李建祥;唐立新;吴会江带运输和设置时间的无等待并行流水车间调度问题研究[期刊论文]-系统工程理论与实践 2006(01)14.Jaln A S;Meeran S A state of the art review of job shop scheduling techniques 199815.Kacem I;Hammadi S;Borne P Pareto-optimality approach for flexible job-shop scheduhng problems hybridization of evolutionary algorithms and fuzzy logic 2005(3/5)16.夏蔚军;吴智铭基于混合微粒群优化的多目标柔性Job-Shop调度[期刊论文]-控制与决策 2005(02)17.吴秀丽;孙树栋;杨展多目标柔性Job-Shop调度问题的技术现状和发展趋势[期刊论文]-计算机应用研究2007(03)18.Pezzella F;Morganti G;Ciaschetti G A genetic algorithm for the flexible Job-Shop scheduling problem[外文期刊] 2008(10)19.Tang L X;Liu G L A mathematical programming model and solution for scheduling production ordersin Shanghai Baoshan Iron and Steel Complex[外文期刊] 2007(3)20.钟海嫣;霍佳震钢管冷区生产调度的一种启发式算法[期刊论文]-工业工程与管理 2008(02)21.李琳;霍佳震钢管生产计划中的多目标柔性Job-Shop调度问题[期刊论文]-系统工程理论与实践 2009(08)1.魏巍.谭建荣.冯毅雄.张蕊.WEI Wei.TAN Jian-rong.FENG Yi-xiong.ZHANG Rui柔性工作车间调度问题的多目标优化方法研究[期刊论文]-计算机集成制造系统2009,15(8)2.李琳.霍佳震.LI Lin.HUO Jia-zhen钢管生产计划中的多目标柔性Job-shop调度问题[期刊论文]-系统工程理论与实践2009,29(8)3.刘明周.张明伟.蒋增强.葛茂根.张铭鑫.Liu Mingzhou.Zhang Mingwei.Jiang Zengqiang.Ge Maogen.Zhang Mingxin基于混合粒子群算法的多目标柔性Job-Shop调度方法[期刊论文]-农业机械学报2008,39(5)4.吴秀丽.孙树栋.余建军.蔡志强.Wu Xiuli.Sun Shudong.Yu Jianjun.Cai Zhiqiang多目标柔性作业车间调度决策精选机制研究[期刊论文]-中国机械工程2007,18(2)5.刘晓霞.谢里阳.陶泽.郝长中.LIU Xiao-xia.XIE Li-yang.TAO Ze.HAO Chang-zhong柔性作业车间多目标调度优化研究[期刊论文]-东北大学学报（自然科学版）2008,29(3)6.白俊杰.龚毅光.王宁生.唐敦兵.BAI Jun-jie.GONG Yi-guang.WANG Ning-sheng.TANG Dun-bing多目标柔性作业车间分批优化调度[期刊论文]-计算机集成制造系统2010,16(2)7.张铁男.韩兵.于渤.ZHANG Tie-nan.HAN Bing.YU Bo生产能力约束条件下的柔性作业车间调度优化[期刊论文]-系统工程理论与实践2011,31(3)8.鞠全勇.朱剑英.JU Quanyong.ZHU Jianying多目标批量生产柔性作业车间优化调度[期刊论文]-机械工程学报2007,43(8)9.张超勇.饶运清.李培根.邵新宇.ZHANG Chaoyong.RAO Yunqing.LI Peigen.SHAO Xinyu柔性作业车间调度问题的两级遗传算法[期刊论文]-机械工程学报2007,43(4)10.袁坤.朱剑英.鞠全勇.王有远.Yuan Kun.Zhu Jianying.Ju Quanyong.Wang Youyuan多目标柔性作业车间调度的集成算子遗传算法[期刊论文]-南京航空航天大学学报（英文版）2006,23(4)1.林建正.王军.李正伟冷藏集装箱维修中的车间调度问题和方法[期刊论文]-物流技术 2012(5)2.张煜.李文锋.Robert H.Storer.严新平多工件族无缓冲混合Flow Shop问题的模型和算法构建[期刊论文]-系统工程理论与实践 2013(8)本文链接：/Periodical_xtgcllysj201010009.aspx。

关于流水车间调度问题的综述关于流水车间调度问题的综述.曲媛-杨晓伟z摘要:流水车间调度问题,也被称为同序作业调度问题,是许多实际流水线生产调度问题的简化模型.它无论是在离散制造工业还是在流程工业中都具有广泛的应用.因此,对其进行研究具有重要的理论意义和工程价值.本文介绍了流水车间调度问题的研究现状和几种解决方法.关键词:流水车间;遗传算法;启发式算法引言自从Johnson1954年发表第一篇关于流水车间调度问题的文章以来.流水车间调度问题引起了许多学者的关注.流水车间调度问题一般可以描述为n个工件要在m台机器上加工.每个工件需要经过m道工序,每道工序要求不同的机器.n个工件在m台机器上的加工顺序相同.工件i在机器j上的加工时间是给定的,设为t(I.j).问题的目标是求n个工件在每台机器上最优的加工顺序,使最大流程时间达到最小.对该问题常常作如下假设.(1)每个工件在机器上的加工顺序是1,2.…,m;(2)每台机器同时只能加工一个工件;(3)一个工件不能同时在不同的机器上加工;(4)工序不能预定:(5)工序的准备时间与顺序无关,且包含在加工时间中;(6)工件在每台机器上的加工顺序相同,且是确定的.基本算法1.一种基于扩展采样空间的混合式遗传算法将邻域搜索与遗传算法相结合求解流水车间调度问题,提出了一种邻域结构.使之更适合求解流水车间问题;设计了一种基于扩展采样空间的混合式遗传并通过计算机模拟验证其有效性.其中,邻域搜索使用定义(由给定的染色体通过随机移动一个基因到一个随机的位置.得到的是染色体的集合)所描述的邻域.采样空间为父代P(t),改进的父代s(t),交叉的后代C(t),变异的后代M(t).交叉和变异的父代是种群的父代P(t),而不是改进的父代S(to具体的混合式算法框架BEGINt=0初始化P(t)WHILE不满足终止条件Do①下降搜索.应用多点最速下降法改进P(t),得到改进的父代S(t);24中小企业科技2007.07②用P(t)进行单点交叉生成C(t);③用P(t)进行移动变异生成M(t);④采样从P(t),S(t),C(t),M(t)中选出最好的不重复的下一代染色体:t=t+1END2.改进的DNA进化算法改进的DNA进化算法中引入了交换操作(交换操作就是在DNA单链中随意产生一个位置.然后将位置前的DNA链与位置后的DNA链相交换.组成一条新的链)以更好地搜索解空间,并采用黄金分割率控制变异个体的数目.同时为了进一步提高搜索性能.采用一种新颖的启发式规则.具体算法如下:对于每个工件都有3个时间指数:t为工件j在所有机器上的加工时间之和;t1i为工件j在第一台机器上的加工时间; t为工件j在最后一台机器上的加工时间;tj为工件j的加权加工时间.B,C是[0,1]之间的数.当随机生成一个A,再在[0,1一A]之间随机产生一个B便能确定tj的大小.然后每个工件按照Tj的降序排列.这样就会产生一个可行解.生成不同的A,就会得到不同的可行解.将启发式算法得到的可行解作为DNA进化算法的初始群体.具体算法如下:①计算每个工件tmi的及tlI;@)For(I=1,2.7.n)(n表示要产生的可行解的个数);A=random(0,1);B=random(0,1一A):tⅡ=At~j+Btlj+(1一A—B)tmj;End③根据每个工件计算出的t.进行降序排列.得到对应的工件排序,即可行解.通过仿真可以验证.加入启发式算法能够快速地接近最优解.提高算法的收敛速度.产生初始种群.3.一种基于遗传算法的求解方法一种基于遗传算法的求解方法.在由染色体转换成可行调度的过程中引入工件插入方法.同时设计了一种新的交叉算子(这里设计了一种新的交叉算子.从种群中按交叉概率随机选取两个个体作为父体.对于每个个体随机寻找两个不同的基因位置.选择这两个位置及其之间的基因作为交叉部分.两个交叉部分的长度可以不同.首先将两个交叉部分进行交换.然后按照父体中原来基因排列的顺序补齐交叉部分没有包含的基因.经过交叉之后产生的子代个体一部分基因保留了在一个父辈个体中的绝对位置,另部分基因则保留了在另一个父辈中的相对位置.该操作具有较好的遗传特性,同时也能够产生足够的搜索空间.计算表明该算子优于PMX交叉算子.)通过大量的数值计算表明.该算法优化质量大大优于传统的遗传算法和NEH启发式算法.4.一个无等待流水车间调度启发式算法采用一个经典的全局任务插入算法构造初始解,应用局部搜索方法对其进行改进.通过4000个不同规模实例将提出算法与目前求解该问题最好的几个算法从性能和计算时间方面进行全面比较.实验结果表明:提出算法的性能是目前最好的,多项式复杂度的计算时间适合实际生产需求.此启发式算法包括两个阶段:初始序列的产生阶段和改进阶段.(1】在初始序列的产生阶段.采用任务插入的方法,它类似于NEH[3]算法.(2)在初始序列的改进阶段,定义V=(X,Y)为序列s中的一对位置,其中:,Y∈{l,2….刀),≠Y.V的移动将S中第X个任务插入到第y个位置,位置对集合:Z={(J,)J,Y∈{l,2,…),Y壁{,—l}},其中包括(n一1)(n一1)个位置对.算法描述如下:①令k=1,计算所有任务ji(I=1,2…,n)的F2值.选择最小值对应的任务放入S中,将其余n一1个任务放入R 中;(K=K+1;③从R中任意取出一个任务j,将其插入到S的K个不同位置.产生K个不同的序列.计算这K个序列的F1值,选择最小值对应的序列作为一个候选序列,将任务j从R中移除;④如果R≠,返回第3步,否则转到第5步;⑤在产生的(n—K+I)个候选序列中,计算各自的F值.选择最小值对应的序列替换S.将序列S以外的所有任务存放到集合R中;⑥如果K=n,结束,S即为最终初始序列;否则回到第2步继续;⑦生成序列S的位置对集合并进行插入操作,产生(n一1)个新的任务序列,计算所有新产生序列的F1值,将最小值对应序列记为S;⑧如果F,(S)=F,(S),则S=S.返回第7步重新开始;否则转入第9步;⑨序列S即为最终任务序列.5.混合禁忌搜索算法(HTS)(1)混合禁忌搜索HTs算法的主要思路为:通过一个有效的启发式算法为TS算法提供一个较好初始解,并可加快TS 算法的收敛速度;采用禁忌搜索算法改进初始解以搜索到更好的近优解.初始解生成算法:①任意产生一个初始序列Q.;②利用双插入启发式算法[5](DIH)对序列Q进行改进获取一个序列S.DIH基于全局插入操作和局部插入操作的思想来产生局部种子序列并对当前调度进行改进.该算法具有较高效率的搜索能力.得到一个较好的近优解;③将序列S进行一次全局成对交换,得到初始序列P.(2)HTS算法描述:基于已得到的序列P作为初始解T0和以上禁忌搜索算法,关键参数的设置,下面给出HTS算法:①调用初始解生产算法产生初始解P并赋予To;②将初始解T作为当前解利用成对交换(Swap)产生的邻域结构得到多个邻域解;③将所有邻域解对应的目标函数值从小到大排序,然后选取前e个邻域解作为候选解;④从第1个候选解开始,如果满足藐视准则,则将此邻域解作为当前的序列T,;否则在候选解中选非禁忌的最佳状态序列作为当前序列T,;⑤保存每个当前序列T,及其目标函数值,并找出其中最优的目标函数值及对应的序列W,;⑥若满足终止条件,则比较最后得到的当前序列T,与序列w,所对应的目标函数值大小,选取目标函数值小的序列作为算法最终所得到的近优解,算法停止;若不满足终止条件则To=T,,则转向2.6.混合规划针对不确定条件下流水车间调度问题(Flowshopschedul—ing),研究了含有随机参数和灰色参数的混合机会约束规划模型的建立及求解方法.提出了灰色模拟的概念和方法,为含有灰色参数的机会约束规划提供了求解途径.通过理论推导及仿真实例,结合遗传算法,验证了基于随机模拟和灰色模拟的混合机会约束规划的调度模型及求解方法的有效性.结束语从目前来看,还没有一个求解流水车间问题最优解的简明算法.整数规划和分枝定界技术是寻求最优解的常用方法.然而对于一些大规模甚至中规模的问题,这两种方法仍然不是很有效.以遗传算法,模拟退火,禁忌搜索以及人工神经网络为代表的智能化优化技术迅速发展来解决流水车间调度问题,受到人们的普遍关注.其中,遗传算法以其优良的计算性能和显着的应用效果而特别引人注目,所以很多启发式混合方法都是在此基础上发展起来的.刁参考文献1梁黎明,汪国强.求解流水车间调度问题的一种混合式遗传算法[I].华南理工大学,2001;(t1):85～882俊林.薛云灿,邵惠鹤.求解混合流水车间调度问题的一种遗传算法[I].计算机工程与应用.2003;(35):186～1873牛群,顾幸生.基于启发式规则的新型进化算法在流水车间调度中的应用[I].华东理工大学,2006;(12):1472～1477(作者简介:1.华南理工大学数学科学学院硕士研究生.2.华南理工大学数学科学学院副教授,博士.)2007.07中小企业科技25。

流水车间调度问题的研究机械工程学院 2111302120 周杭超如今,为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式.与过去大批量、单一的生产方式相比,多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此,受到越来越多的企业管理者的重视。

特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品.在这种环境下,对于不同批次的产品生产进行合理调度排序就显得十分重要。

在传统的生产方式中,企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产.这样，必然会一次大批量生产同一产品，很容易造成库存的积压。

在实际生产中如果需要生产A， B, C，D四种产品各100件，各种产品的节拍都是1分钟,如果按照传统的做法，先生产出100件A产品，其次是B,然后是C，最后生产产品D。

在这种情况下，这四种产品的总循环时间是400分钟.然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件），那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费.这种生产就是非均衡的，如图1所示.比较均衡的生产方式（图2 ）是：在一条流水线上同时将四种产品混在一起生产，并且确定每种品种一次生产的批量.当然，如果在混合生产时不需要对设备进行转换,那么单件流的生产方式是最好的。

然而,在实际生产A ， B ， C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换.单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。

同时,由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。

当同一流水线加工多产品，并且每种产品在各道工序（各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。

柔性流水车间有限缓冲区问题分析作者：杜佳奇韩忠华李同来源：《电脑知识与技术》2021年第13期摘要：柔性流水车间的实际生产过程中，相邻的两个工序间通常设置缓冲区用以存放在制品，其不仅可以用来存放来自上一道工序的完工工件，还可以根据实际生产需求对加工工件进行排序和分类。

在大规模生产模式下，缓冲區的作用更为明显。

而通常情况下由于实际生产企业流水线中，由于生产车间空间、仓储设施容量等因素限制，在生产车间只能设置容量有限的缓冲区，当生产车间出现任务需求产能波动、各个工序间的生产节拍不一致时，有限缓冲区容量容易达到其上限，使得工件不能进入缓冲区，导致出现生产堵塞的现象，进而会影响到整体的生产进程。

同时，由于在生产企业中加工产品的多样化，其规格尺寸、加工工艺、存储方式的差异等原因，导致生产线中存在多种类型的有限缓冲区，本文主要讨论柔性流水车间中的多序列有限缓冲区、公共缓冲区和路由缓冲区三种复杂的有限缓冲区。

对其各个的特征和在实际生产过程中工作状态进行分析，为具有有限缓冲区的柔性流水车间排产优化问题的研究打下坚实的基础。

关键词：柔性流水车间;多序列缓冲区;公共缓冲区;路由缓冲区中图分类号：TH186 文献标识码：A文章编号：1009-3044（2021）13-0009-03Abstract：In the actual production process of the flexible flow workshop， a buffer zone is usually set up between two adjacent processes to store the products in progress. It can not only be used to store the finished parts from the previous process， but also can sort and classify the processed parts according to actual production requirements. In mass production mode， the role of the buffer zone is more obvious. In general， due to the actual production enterprise assembly line， due to factors such as production workshop space and storage facility capacity， only a buffer with limited capacity can be set in the production workshop. When the production workshop has task demandcapacity fluctuations and inconsistent production tempo between various processes， the limited buffer capacity can easily reach its upper limit， so that workpieces cannot enter the buffer area，resulting in production jams， which will affect the overall production process. At the same time，due to the diversification of processed products in production enterprises， the differences in their specifications and sizes， processing techniques， storage methods and other reasons， there are many types of limited buffer zones in the production line. This article mainly discusses three complex limited buffers in the flexible flow shop： multi-sequence limited buffers， common buffers and routing buffers. The analysis of the various characteristics of the buffer zone and the working status in the actual production process and lays a solid foundation for the future research on the optimization problem of flexible flow workshop with limited buffer zone.Key words： Flexible flow shop; multi-sequence buffer; public buffer; routing buffer柔性流水车间排产问题一直以来都是制造企业生产车间排产优化的重要的环节之一，柔性流水车间包含着多道加工工序且每道工序都有着一台或者多台可以同时进行生产的加工设备。

林业工程学报，２０２３，８（３）：１９８－２０４ＪｏｕｒｎａｌｏｆＦｏｒｅｓｔｒｙＥｎｇｉｎｅｅｒｉｎｇＤＯＩ：１０．１３３６０／ｊ．ｉｓｓｎ．２０９６－１３５９．２０２２０９０３８收稿日期：２０２２－０９－２６㊀㊀㊀㊀修回日期：２０２３－０１－３１基金项目：国家自然科学基金（３１９７１５９４）㊂作者简介：王金鑫，男，博士，研究方向为木制品数字化制造技术㊂通信作者：曹平祥，男，教授㊂Ｅ⁃ｍａｉｌ：ｎｊｆｕｃｐｘ＠１６３．ｃｏｍ带有缓冲约束的板式家具混合流水车间调度求解方法王金鑫，伍占文，胡伟，宋超军，郭晓磊，曹平祥∗（南京林业大学材料科学与工程学院，南京２１００３７）摘㊀要：探讨板式家具生产在缓冲约束下的混合流水车间调度问题，建立缓冲约束，并研究求解方法，为解决由于当前家具生产调度方法缺乏考虑缓冲约束使得现代调度技术难以实际应用的问题提供科学依据㊂以板件数量作为缓冲约束中容量的表征，根据混合流水车间调度问题的特征，建立工序间有限缓冲约束，并将其编码进遗传算法的适应度函数中；设计满足调度问题特征的交叉操作㊁变异操作㊁个体评估与选择操作㊂其中，交叉操作采用部分映射法，变异操作采用单点插入法，个体评估采用已建立的适应度函数，选择操作则采用精英保留策略和轮盘赌方法㊂最后利用ＭＡＴＬＡＢ对遗传算法各模块进行编程，通过文献中的案例进行算法的可行性验证㊂通过对已有文献的调度规则和方法（先进先出原则㊁ＮＥＨ算法㊁模拟退火算法㊁粒子群算法㊁蚁群优化算法和改进布谷鸟搜索算法）进行对比试验，结果显示本研究提出的遗传算法在以完工时间为优化目标的前提下均优于其他方法㊂同样在考虑缓冲约束的案例场景中，本研究提出的方法也具有有效性㊂基于遗传算法的工序间有限缓冲约束下板式家具多产线混合流水车间调度问题的结果具有一定的可行性，可以为板式家具生产调度技术提供新的解决思路，但仍需综合考虑更多的生产动态因素来提高其实际应用能力㊂关键词：板式家具；生产调度；混合流水车间调度；有限缓冲；遗传算法中图分类号：ＴＳ６６４．１㊀㊀㊀㊀㊀文献标志码：Ａ㊀㊀㊀㊀㊀文章编号：２０９６－１３５９（２０２３）０３－０１９８－０７ＨｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｉｎｐａｎｅｌｆｕｒｎｉｔｕｒｅｗｉｔｈｂｕｆｆｅｒｃｏｎｓｔｒａｉｎｔＷＡＮＧＪｉｎｘｉｎ，ＷＵＺｈａｎｗｅｎ，ＨＵＷｅｉ，ＳＯＮＧＣｈａｏｊｕｎ，ＧＵＯＸｉａｏｌｅｉ，ＣＡＯＰｉｎｇｘｉａｎｇ∗（ＣｏｌｌｅｇｅｏｆＭａｔｅｒｉａｌｓＳｃｉｅｎｃｅｓａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮａｎｊｉｎｇＦｏｒｅｓｔｒｙＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００３７，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｔｅｃｈｎｏｌｏｇｉｅｓｈａｖｅｓｉｇｎｉｆｉｃａｎｔｌｙｉｍｐｒｏｖｅｄｔｈｅｐｒｏｄｕｃｔｉｏｎｐｒｏｃｅｓｓｅｓｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅｂｙｓｈｏｒｔｅｎｉｎｇｔｈｅｐｒｏｄｕｃｔｉｏｎｃｙｃｌｅｓ，ｌｅａｄｉｎｇｔｏｅｎｌａｒｇｅｄｐｒｏｆｉｔｍａｒｇｉｎｏｆｅｎｔｅｒｐｒｉｓｅｓ．Ｔｈｅｅｘｉｓｔｉｎｇｊｏｂｓｈｏｐａｐｐｒｏａｃｈｅｓｆｏｒｐａｎｅｌｆｕｒｎｉｔｕｒｅｐｒｏｄｕｃｔｉｏｎａｓｓｕｍｅｕｎｌｉｍｉｔｅｄｓｔｏｒａｇｅｓｐａｃｅｓｂｅｔｗｅｅｎｐｒｏｄｕｃｔｉｏｎｐｒｏｃｅｓｓｅｓ，ｂｕｔｔｈｉｓｉｓｎｏｔｐｒａｃｔｉｃａｌｌｙｔｈｅｃａｓｅａｎｄｔｈｕｓｌｉｍｉｔｉｎｇｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅｓｅａｐｐｒｏａｃｈｅｓｆｏｒｒｅａｌ⁃ｗｏｒｌｄａｐｐｌｉｃａｔｉｏｎｓ．Ｔｈｉｓｒｅｓｅａｒｃｈｄｉｓｃｕｓｓｅｄｔｈｅｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｌｉｍｉｔｅｄｂｕｆｆｅｒｃａｐａｃｉｔｙｉｎｔｈｅｐａｎｅｌｆｕｒｎｉｔｕｒｅｐｒｏｄｕｃｔｉｏｎ，ｅｓｔａｂｌｉｓｈｅｄｔｈｅｃｏｎｓｔｒａｉｎｔｏｆｌｉｍｉｔｅｄｂｕｆｆｅｒｃａｐａｃｉｔｙ，ａｎｄｉｎｖｅｓｔｉｇａｔｅｄｔｈｅｓｏｌｕｔｉｏｎｍｅｔｈｏｄｓ，ｗｈｉｃｈｐｒｏｖｉｄｅｄａｓｃｉｅｎｔｉｆｉｃｂａｓｉｓｆｏｒｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｓｔｈａｔｍｏｄｅｒｎｓｃｈｅｄｕｌｉｎｇｔｅｃｈｎｏｌｏｇｉｅｓｗｅｒｅｄｉｆｆｉｃｕｌｔｔｏｂｅａｐｐｌｉｅｄｉｎｐｒａｃｔｉｃａｌｍａｎｕｆａｃｔｕｒｅｓｄｕｅｔｏｔｈｅｌａｃｋｏｆｃｏｎｓｉｄｅｒａｔｉｏｎｏｆｂｕｆｆｅｒｃａｐａｃｉｔｙｃｏｎｓｔｒａｉｎｔｓｉｎｃｕｒｒｅｎｔｆｕｒｎｉｔｕｒｅｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇｍｅｔｈｏｄｓ．Ｔａｋｉｎｇｔｈｅｎｕｍｂｅｒｏｆｐｌａｔｅｓａｓｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｃａｃｈｅｃａｐａｃｉｔｙ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｔｈｅｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂ⁃ｌｅｍ，ｔｈｅｃｏｎｓｔｒａｉｎｔｂａｓｅｄｏｎｔｈｅｌｉｍｉｔｅｄｃａｃｈｅｃａｐａｃｉｔｙｂｅｔｗｅｅｎｐｒｏｃｅｓｓｅｓｗａｓｅｓｔａｂｌｉｓｈｅｄ，ａｎｄｉｔｗａｓｅｎｃｏｄｅｄｉｎｔｏｔｈｅｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎｏｆｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅｎｔｈｅｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｉｏｎ，ｖａｒｉａｔｉｏｎｏｐｅｒａｔｉｏｎａｎｄｉｎｄｉｖｉｄｕａｌｅｖａｌｕａ⁃ｔｉｏｎａｎｄｓｅｌｅｃｔｉｏｎｏｐｅｒａｔｉｏｎｗｅｒｅｄｅｓｉｇｎｅｄｔｏｍｅｅｔｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ．Ａｍｏｎｇｔｈｅｍ，ｔｈｅｃｒｏｓｓ⁃ｏｖｅｒｏｐｅｒａｔｉｏｎａｄｏｐｔｅｄｔｈｅｐａｒｔｉａｌｍａｐｐｉｎｇｍｅｔｈｏｄ，ｔｈｅｍｕｔａｔｉｏｎｏｐｅｒａｔｉｏｎａｄｏｐｔｅｄｔｈｅｓｉｎｇｌｅｐｏｉｎｔｉｎｓｅｒｔｉｏｎｍｅｔｈｏｄ，ｔｈｅｉｎｄｉｖｉｄｕａｌｅｖａｌｕａｔｉｏｎａｄｏｐｔｅｄｔｈｅｐｒｅｖｉｏｕｓｌｙｅｓｔａｂｌｉｓｈｅｄｆｉｔｎｅｓｓｆｕｎｃｔｉｏｎ，ａｎｄｔｈｅｓｅｌｅｃｔｉｏｎｏｐｅｒａｔｉｏｎａｄｏｐｔｅｄｔｈｅｅｌｉｔｅｒｅｔｅｎｔｉｏｎｓｔｒａｔｅｇｙａｎｄｒｏｕｌｅｔｔｅｍｅｔｈｏｄ．Ｆｉｎａｌｌｙ，ＭＡＴＬＡＢｗａｓｕｓｅｄｔｏｐｒｏｇｒａｍｅａｃｈｍｏｄｕｌｅｏｆｔｈｅｇｅｎｅｔｉｃａｌｇｏ⁃ｒｉｔｈｍ，ａｎｄｔｈｅｎｔｈｅｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｗａｓｖｅｒｉｆｉｅｄｂｙｔｈｅｒｅｐｏｒｔｅｄｃａｓｅｓｉｎｔｈｅｌｉｔｅｒａｔｕｒｅ．Ｔｈｅｃｏｍｐａｒａｔｉｖｅｔｅｓｔｓｏｆｓｏｍｅｓｃｈｅｄｕｌｉｎｇｒｕｌｅｓａｎｄｍｅｔｈｏｄｓｉｎｔｈｅｅｘｉｓｔｉｎｇｌｉｔｅｒａｔｕｒｅ，ｓｕｃｈａｓｔｈｅｆｉｒｓｔｉｎｆｉｒｓｔｏｕｔｐｒｉｎｃｉｐｌｅ，ＮＥＨａｌｇｏ⁃ｒｉｔｈｍ，ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍ，ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ，ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｉｍｐｒｏｖｅｄｃｕｃｋｏｏｓｅａｒｃｈａｌｇｏｒｉｔｈｍｗｅｒｅｃａｒｒｉｅｄｏｕｔ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｅｄｔｈａｔｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｐｒｏｐｏｓｅｄｉｎｔｈｉｓｓｔｕｄｙｗａｓｄｕｅｔｏｏｔｈｅｒｍｅｔｈｏｄｓｏｎｔｈｅｐｒｅｍｉｓｅｔｈａｔｔｈｅｃｏｍｐｌｅｔｉｏｎｔｉｍｅｗａｓｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｔａｒｇｅｔ．Ｎｏｔａｂｌｙ，ｉｔｗａｓｓｈｏｗｎａｂｏｕｔａ２７．９％ｄｅｃｒｅａｓｅｉｎｐｒｏｄｕｃｔｉｏｎｃｏｓｔｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｆｉｒｓｔｉｎｆｉｒｓｔｏｕｔｒｕｌｅｔｈａｔｉｓｃｏｍｍｏｎｌｙｕｓｅｄｉｎｔｈｅ㊀第３期王金鑫，等：带有缓冲约束的板式家具混合流水车间调度求解方法ｆｕｒｎｉｔｕｒｅｍａｎｕｆａｃｔｕｒｉｎｇｉｎｄｕｓｔｒｙ．Ｉｎｔｈｅｃａｓｅｓｃｅｎａｒｉｏｃｏｎｓｉｄｅｒｉｎｇｃａｃｈｅｃｏｎｓｔｒａｉｎｔｓ，ｔｈｅｓｃｈｅｄｕｌｉｎｇｍｅｔｈｏｄｐｒｏｐｏｓｅｄｉｎｔｈｉｓｒｅｓｅａｒｃｈｗａｓｅｆｆｅｃｔｉｖｅ．Ｔｈｅｒｅｓｕｌｔｏｆｔｈｅｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅｗｉｔｈｌｉｍｉｔｅｄｂｕｆｆｅｒｃａｐａｃｉｔｙｂｅｔｗｅｅｎｐｒｏｃｅｓｓｅｓｂａｓｅｄｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｈａｄｃｅｒｔａｉｎｆｅａｓｉｂｉｌｉｔｙａｎｄｃｏｕｌｄｐｒｏｖｉｄｅａｎｅｗｓｏｌｕｔｉｏｎｆｏｒｔｈｅｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇｔｅｃｈｎｏｌｏｇｙｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅ，ｉｍｐｒｏｖｉｎｇｉｔｓｐｒａｃｔｉｃａｌａｐｐｌｉｃａｔｉｏｎａｂｉｌｉｔｙ．Ｈｏｗｅｖｅｒ，ｉｔｉｓｅｘｐｅｃｔｅｄｔｏｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙｃｏｎｓｉｄｅｒｍｏｒｅｐｒｏｄｕｃｔｉｏｎｄｙｎａｍｉｃｆａｃｔｏｒｓｉｎｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈ．Ｋｅｙｗｏｒｄｓ：ｐａｎｅｌｆｕｒｎｉｔｕｒｅ；ｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇ；ｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇ；ｓｔｏｒａｇｅｓｐａｃｅｌｉｍｉｔａｔｉｏｎ；ｇｅｎｅｔｉｃａｌ⁃ｇｏｒｉｔｈｍ㊀㊀板式家具是以各种贴面人造板作为板式部件，借助五金联接件㊁圆榫等结合方式组装而成的［１］㊂家具产品与人们的生活息息相关，而随着人们生活和消费水平的提高，顾客逐渐参与设计家具风格，体现了 我的家，我做主 的消费理念㊂同时，板式家具的市场焦点已经从早期的降低劳动力成本和产品成本的竞争转向产品新颖性及其质量㊁价格㊁交货期与服务的竞争，其中缩短产品生产周期则直接影响到产品利润［２－３］㊂为降低产品生产周期，现代生产调度技术对车间生产线的资源进行了整合与重新分配［４－５］㊂尽管板式家具的产品种类繁多，但是其生产工艺非常相似㊂一块板件的加工顺序可包括开料㊁封边㊁钻孔㊁分拣和包装，其中开料㊁封边和钻孔是三大主要工序［６－７］㊂此外，至少有一道工序会包含多台加工设备㊂因此，板式家具的生产调度问题可以归类为混合流水车间调度问题［８－９］㊂鉴于此类问题属于ＮＰ难（ｎｏｎ⁃ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙｎｏｍｉａｌ⁃ｔｉｍｅｈａｒｄｎｅｓｓ，ＮＰ⁃ｈａｒｄｎｅｓｓ）问题，对于求解家具生产混合流水车间调度问题方法的研究，求解方法一般分为精确求解法㊁启发式算法和元启发式算法㊂传统的整数规划方法目前只适用于小规模案例的精确求解［１０］㊂随着混合流水车间调度问题由两阶段衍生到ｋ阶段，并且阶段间的复杂约束以及机器数量和板件种类上的差异，使得整数规划的求解速度下降㊂具体表现为：解空间随着问题规模的增大而急剧增加，并且问题的复杂度呈指数增长，因此，整数规划难以在有效时间内获得最优解㊂启发式算法主要包括分派规则和局部搜索算法㊂分派规则主要包括最短加工时间优先㊁最早交货期优先㊁最早设备可用㊁先进先出（ｆｉｒｓｔｉｎｆｉｒｓｔｏｕｔ，ＦＩＦＯ）等［１１－１２］㊂但通过这些规则并不能针对复杂多样的混合流水车间调度问题获得较好的解㊂局部搜索算法主要通过更新当前已有解的关键路径来获取更优解，常用的有变领域搜索［１３］㊁迭代本地搜索［１４］和迭代贪婪［１５］等方法㊂这些方法能切入实际案例求解大规模问题，但搜索较慢而且效果一般㊂最后一种为元启发式算法，与启发式算法不同的地方在于该方法将随机因素嵌入整个搜索过程，并多次调用算法来产生更优解㊂常用的元启发式算法有遗传算法（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ＧＡ）［１６］㊁蚁群优化算法（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）［１７］㊁模拟退火算法（ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ，ＳＡ）［１８］㊁粒子群算法（ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）［１９］㊁改进布谷鸟搜索算法（ｉｍｐｒｏｖｅｄｃｕｃｋｏｏｓｅａｒｃｈａｌｇｏｒｉｔｈｍ，ＩＣＳ）［２０］等一系列方法㊂遗传算法作为该系列方法的经典代表，通过对算法框架的搭建㊁编解码的设计㊁适应度函数的问题导向设计㊁算法参数设定以及全局搜索与局部搜索间的权衡，可求得混合流水车间调度问题的优化解㊂依据文献研究，板式家具生产调度问题的研究更多聚焦在对完工时间的优化呈现出良好的结果，但均假设了无限工序间的缓冲区域㊂而在实际家具生产过程中缓冲区域的容量是有限的，并且当容量超出其承载力后就会造成生产阻塞，影响生产效率［２１］㊂因此，对于板式家具制造过程中考虑有限缓冲约束的混合流水车间调度问题的研究具有现实意义㊂综上所述，笔者提出了一个基于遗传算法解决板式家具生产中有限缓冲约束的混合流水车间调度问题的方法㊂具体采用基于操作的编码方式将有限缓冲约束编码在适应度函数中，聚焦于缓冲约束的影响，而不考虑其他诸如设备故障和紧急插单等因素㊂利用ＭＡＴＬＡＢ对遗传算法各模块进行编程，通过文献中的案例进行算法的可行性验证，为板式家具生产调度的理论建模和数学求解提供新的解决思路㊂１㊀缓冲约束１．１　问题表述对板式家具制造的３道主要工序进行研究，即开料㊁封边和钻孔的有限缓冲约束生产调度问题㊂假设每道工序都包含相同数量的设备，并且同一工序下每台设备为同型机，即加工相同的板件所需时间一致㊂而对于同一工序下设备不尽相同的情况会在后续研究中进一步探讨㊂因此，一块板件的加工时间只和它所处的工序有关㊂对于开料工序而９９１林业工程学报第８卷言，板件的加工时间即从标准原料板件送入电子开料锯切割，到切割后的小板件被送离该设备的时间；对于封边工序，加工时间即从板件进入封边机封边到板件离开封边机的时间，其主要由封边机的进给速度和板件的尺寸决定；对于钻孔工序，加工时间即从板件被装夹上钻孔机钻孔到钻孔完成离开钻孔机的时间，其主要由孔的数量㊁位置及尺寸决定㊂最后，两相邻工序间缓冲区的容量设置为相等㊂因此，该问题可被视为考虑缓冲约束的混合流水车间调度问题㊂对于经典混合流水车间调度问题的描述已有文献报道［９］，而对于考虑板式家具有限缓冲约束的混合流水车间调度问题则定义如下㊂假设有一工件集合Ｊｊ，ｊ＝１，２， ，ｎ{}表示工件编号；一个工序集合Ｍｋ，ｋ＝１，２，３{}依次代表开料㊁封边和钻孔工序；一个设备集合ｍｋ，ｌ，ｌ＝１，２， ，Ｌｋ{}代表工序ｋ的第ｌ台设备㊂定义一项操作Ｏｊ，ｋ代表工件Ｊｊ在工序Ｍｋ上加工㊂每个工件Ｊｊ都需要执行相同的加工顺序，一次只能在一台设备ｍｋ，ｌ上加工，并且只有该工件的前道工序加工完成后才能进行后道工序的加工㊂最后，ＰＯｊ，ｋ()㊁ＳＯｊ，ｋ()和ＣＯｊ，ｋ()分别代表工件Ｊｊ在工序Ｍｋ的加工时间㊁开始加工时间点和结束加工时间点㊂１．２㊀基于工序间的有限缓冲约束对于非钻孔工序的设备ｍｋ，ｌ，都允许其暂时存储一定数量的板件，直到下道工序的设备可用㊂其中，当前存储容量用ｂ＝１，２， ，Ｂ{}表示㊂如果经过机器ｍｋ，１加工并存储在机器ｍｋ，ｌ后的缓冲区板件数量小于Ｂ时，机器ｍｋ，１可以继续加工后续的板件直到其数量满足最大数量Ｂ㊂如果经过机器ｍｋ，１加工并存储在机器ｍｋ，ｌ后的缓冲区板件数量等于Ｂ时会出现２种情况，分别是ｋ＝１，２{}或者ｋ＝３㊂当ｋ＝３时，所有机器上的已加工工件都会被立即转移，因此缓冲约束不会对该工序的加工有任何影响㊂当ｋ＝１，２{}时，为了不失一般性，作如下假设：１）工件Ｊｊ为安排在机器ｍｋ，１上的下个待加工工件；２）如果ｋ＝２，则ｋ＝１或者操作Ｏｊ，ｋ－１已经完成加工，因此可以随时加工操作Ｏｊ，ｋ；３）当完成操作Ｏｊ，ｋ的加工后，工件Ｊｊ被安排到下道工序的机器ｍｋ＋１，１上处理，且该机器在加工Ｏｊ，ｋ＋１之前已经完成了操作Ｏｊᶄ，ｋ＋１的加工㊂其中，工件ｊᶄ为工件ｊ在工序（ｋ＋１）的紧前工件㊂如果机器ｍｋ，１存储的ｂ块板件无法被传递到下道工序的ＣＯｊᶄ，ｋ＋１()之前加工，则必须遵循条件ＣＯｊᶄ，ｋ＋１()ɤＣＯｊ，ｋ()，从而满足缓冲区最大容量Ｂ的约束，如图１所示㊂因此，ＳＯｊ，ｋ()可精确表示为：ＳＯｊ，ｋ()ȡＣＯｊᶄ，ｋ＋１()－ＰＯｊ，ｋ()（１）如果有存储在机器ｍｋ，１后的工件Ｊｊᵡ能够被传递到下道工序的ＣＯｊᶄ，ｋ＋１()之前加工，且ｊʂｊᵡ，则ＳＯｊ，ｋ()会提前为：ＳＯｊ，ｋ()ȡＳＯｊᵡ，ｋ＋１()－ＰＯｊ，ｋ()（２）因此，Ｏｊ，ｋ的调度可表示为：Ｓ（Ｏｊ，ｋ）＝ｍｉｎＣ（Ｏｊᶄ，ｋ＋１）－Ｐ（Ｏｊ，ｋ），Ｓ（Ｏｊᵡ，ｋ＋１）－Ｐ（Ｏｊ，ｋ）[]图１㊀工序间有限缓冲约束示例Ｆｉｇ．１㊀Ａｎｉｌｌｕｓｔｒａｔｉｏｎｏｆｌｉｍｉｔｅｄｓｔｏｒａｇｅｓｐａｃｅｂｅｔｗｅｅｎｐｒｏｃｅｓｓｅｓ其他情况也可以通过类似的方式解决，但由于篇幅限制，此处进行了省略㊂调度的目标是优化完工时间㊂１．３㊀问题建模混合整数规划模型常被用来表征生产调度问题，其中也包括混合流水车间调度问题㊂本研究的优化目标为完工时间，具体如下：ｆ＝ｍａｘＣＯｊ，３()[]＝ｍａｘＳＯｊ，３()＋ＰＯｊ，３()[]（４）ðＬｋｌ＝１ｘｊ，ｋ，ｌ＝１，∀ｊɪ１，２， ，Ｊｊ{}；ｋɪ１，２，３{}（５）ｙｊ，ｊ－，ｋ＋ｙｊ－，ｊ，ｋɤ１，∀ｊ－ɪ１，２， ，Ｊｊ{}，ｊ－ʂｊ（６）Ｔ＝Ｕ３－ｙｊ－，ｊ，ｋ－ｘｊ－，ｋ，ｌ－ｘｊ，ｋ，ｌ()，∀ｌɪ１，２， ，Ｌｋ{}（７）ＳＯｊ，ｋ()－ＳＯｊ－，ｋ()＋ＰＯｊ－，ｋ()[]＋Ｔȡ０（８）ｘｊ，ｋ，ｌɪ０，１{}（９）ｙｊ－，ｊ，ｋɪ０，１{}（１０）Ｓ（Ｏｊ，ｋ）＝ｍｉｎ[Ｃ（Ｏｊᶄ，ｋ＋１）－Ｐ（Ｏｊ，ｋ），Ｓ（Ｏｊᵡ，ｋ＋１）－Ｐ（Ｏｊ，ｋ）]，ｊʂｊᶄ，ｊʂｊᵡ，ｋ＝１，２{}（１１）式中：Ｕ为一个极大的正数；ｘｊ，ｋ，ｌ是一个决策变量，表示如果工件ｊ在工序ｋ的第ｌ台机器上加工，其值取１，否则为０；ｙｊ－，ｊ，ｋ是一个决策变量，表示如果工序ｋ上的工件ｊ在工件ｊ－之后加工，其值取１，否则为０㊂００２㊀第３期王金鑫，等：带有缓冲约束的板式家具混合流水车间调度求解方法式（４）是目标函数，表示最后一道钻孔工序上最后一个工件的结束时间；式（５）表示每个工件都要经历相同的工序，并且只能在每道工序的一台设备上加工；式（６）表示同道工序上不同工件的先后约束关系；式（７）表示应满足工件ｊ和工件ｊ－都在工序ｋ的第ｌ台设备上加工，且工件ｊ－在工件ｊ前加工，否则式（８）无效；式（９） （１０）定义了决策变量；式（１１）表示满足有限缓冲约束时工件ｊ的开始加工时间，其计算逻辑见１．２节㊂２㊀遗传算法求解本研究的遗传算法流程见图２，以下分步骤阐述该算法的具体操作与参数选择㊂图２㊀遗传算法流程Ｆｉｇ．２㊀Ａｆｌｏｗｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ步骤１：初始化种群Ｐ中的个体Ｉｉ，ｉɪ１，２， ，ｐ{}，如图３所示㊂个体只与工件和工序相关，并且操作Ｏｊ，ｋ只能在操作Ｏｊ，ｋ－１之后加工㊂种群数量设置为１０㊂图３㊀一个包含３个工件的个体Ｉｉ示例Ｆｉｇ．３㊀ＡｎｉｌｌｕｓｔｒａｔｉｏｎｏｆａｎｉｎｄｉｖｉｄｕａｌＩｉｗｉｔｈｔｈｒｅｅｊｏｂｓ步骤２：采用部分映射法进行交叉操作㊂交叉概率设置为０．６，当满足交叉概率时进行交叉操作㊂当交叉操作完成后，需要对子代进行可用性检查，即满足步骤１中加工操作Ｏｊ，ｋ只能在操作Ｏｊ，ｋ－１之后加工的要求㊂如满足条件则跳至步骤３，否则交换基因顺序，使其满足条件㊂步骤３：采用单点插入法进行变异操作㊂变异概率设置为０．４，当满足变异概率时进行变异操作㊂变异操作结束后也需对子代进行可行性检查，方法同步骤２㊂步骤４：采用精英保留策略和轮盘赌方法进行个体的评估与选择㊂其中的评估准则为表示所有工件全部完成时间的适应度函数，其表达式为ｆ＝ｍａｘＣＯｊ，３()[]＝ｍａｘＳＯｊ，３()＋ＰＯｊ，３()[]㊂如果Ｏｊ，３是某钻孔机上的第１个工件，则ＳＯｊ，３()仅取决于它在前道封边工序的完工时间，即ＣＯｊ，２()，则有ＳＯｊ，３()＝ＣＯｊ，２()；否则，ＳＯｊ，３()还需与该机器上它的紧前工件加工情况相比较，该紧前工件的操作记为Ｏｊ－，３，则有Ｓ（Ｏｊ，３）＝ｍａｘ［Ｃ（Ｏｊ－，３），Ｃ（Ｏｊ，２）］㊂而Ｃ（Ｏｊ，２）则可通过Ｃ（Ｏｊ，２）＝Ｓ（Ｏｊ，２）＋Ｐ（Ｏｊ，２）来计算㊂如果加工Ｏｊ，２的机器达到了缓冲上限，则可通过式（１１）来计算Ｓ（Ｏｊ，２）㊂整个计算过程可用递归法实现，但不在本研究讨论范围内，故省略详细计算过程㊂在对每个个体使用上述方法进行适应度计算后，按照适应度值升序排序；然后选择前５的个体作为精英保留，对其余的个体采用轮盘赌的方法再生成下一代种群㊂步骤５：算法进行终止或者循环的条件取决于本次循环中最优个体的适应度值与过去迭代中的最优个体进行比较㊂如果与过去迭代中的平均值相比，最优个体适应度值的整体改善没有显著变化，则算法将终止，并返回最优个体作为调度的最终解决方案；否则该算法返回步骤２㊂为了避免算法潜在的不间断运行，本工作中还应用了最大迭代次数１００㊂如果达到最大迭代次数，则无论结果质量如何，算法都将终止㊂３㊀应用实例３．１㊀有限缓冲约束的案例分析以Ａ公司某经典板式家具产品单开门床头柜生产线作为本次试验对象来验证本研究方法的可行性，该产线的设备布置如图４所示㊂其中，封边工序和钻孔工序均有２台同型机㊂图４㊀板式家具有限缓冲约束案例的设备布局Ｆｉｇ．４㊀Ｅｑｕｉｐｍｅｎｔｌａｙｏｕｔｏｆｌｉｍｉｔｅｄｂｕｆｆｅｒｃａｓｅｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅ该产品包含１０块板件，以及若干五金件和１个拉手，但五金件和拉手不在本研究考虑范围内㊂故每块板件可算作一个独立工件，其加工时间依据该公司实际数据得出，开料㊁封边㊁钻孔的加工时间１０２林业工程学报第８卷分别为１０ １５，３０ ３５，３０ ４０ｓ／块㊂每道工序的加工时间均是一个范围，并且服从均匀分布㊂工序间缓冲区的容量设置为１，试验结果如图５所示㊂当开料与封边工序间的容量达到上限时，共有４块板件的开始加工时间点需要调整，分别是工件１㊁工件２㊁工件３和工件４㊂图５中虚线部分的工件表示该工件在缓冲区的等待时间㊂由于工件７完成开料工序后缓冲区内有工件２正在等待，并且下道封边工序的设备均在加工，所以工件７必须留在该设备上等待，直至缓冲区或下道工序的设备两者间最早可用的一方出现后，工件７才能离开开料设备㊂因此，后继工件１必须调整开始开料的时间㊂在本案例中，根据式（１１），其最早可用时间为工件７进入缓冲区的时间；同理可得其他需要调图６㊀考虑缓冲约束的板式家具混合流水车间三产线调度结果甘特图Ｆｉｇ．６㊀Ｇａｎｔｔｃｈａｒｔｓｏｆｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｉｎｔｈｒｅｅｐｒｏｄｕｃｔｉｏｎｌｉｎｅｓｗｉｔｈｌｉｍｉｔｅｄｂｕｆｆｅｒｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅ图５㊀考虑缓冲约束的板式家具混合流水车间调度结果甘特图Ｆｉｇ．５㊀Ｇａｎｔｔｃｈａｒｔｏｆｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｌｉｍｉｔｅｄｂｕｆｆｅｒｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅ整时间的工件㊂因此，该调度优化结果验证了本研究的遗传算法对解决板式家具混合流水车间调度问题具有可行性㊂该公司为了应对大量订单下的生产压力，采用３条生产线来协同完成生产计划㊂不同产线相同工序的设备均为同型机，且板件不会跨产线生产，各产线设备数量如表１所示㊂表１㊀３条生产线各工序的设备数量Ｔａｂｌｅ１㊀Ｌａｙｏｕｔｓｏｆｔｈｒｅｅｐｒｏｄｕｃｔｉｏｎｌｉｎｅｓ工序设备数量产线１产线２产线３开料２２１封边２２１钻孔３３１㊀㊀本次试验共有３０块板件，且板件在各工序的加工时间沿用表１的数据㊂相邻工序间的缓冲区容量设置为２㊂试验结果如图６所示，在产线１，当开料与封边工序间的容量达到上限时，共有４块板件的开始加工时间点需要调整，分别是工件７㊁工件１８㊁工件２１和工件２５㊂当工件６完成开料时，缓冲区已满，并且下道封边工序的设备均在加工㊂因此，后继工件２１无法直接开料，必须等到工件６顺利进入缓冲区后才能开始加工，工件２１的开始时间需调整为缓冲区中的最早可用时间，也就是工件６进入缓冲区的时间；同理可得需要调整开始加工时间的其他板件㊂该调度优化结果验证了本研２０２㊀第３期王金鑫，等：带有缓冲约束的板式家具混合流水车间调度求解方法究的遗传算法对解决板式家具混合流水车间多产线有限缓冲约束的调度问题具有可行性，并且具备一定的实际应用意义㊂３．２㊀对比试验选取最大完工时间作为本次对比试验的评估目标㊂根据前人研究家具制造混合流水车间调度问题的方法［２０］，提出了一种改进布谷鸟搜索算法（ＩＣＳ），与其他当前企业常用的诸如先进先出（ＦＩＦＯ）㊁ＮＥＨ㊁模拟退火（ＳＡ）㊁蚁群优化（ＡＣＯ）和粒子群算法（ＰＳＯ）等方法对比具有一定优势㊂本研究采用文献［２０］中的案例数据，一个批次２０个工件的加工时间数据如表２所示㊂文献［２０］同时处理６０个批次，即１２００个工件的调度㊂该对比试验采用本研究提出的方法进行求解，具体为相同的工件数量㊁相同的工序数量㊁相同的设备布局及数量㊁相同的工件加工时间和相同的约束，从而保证在相同背景下仅对本研究的遗传算法进行有效性验证㊂最大完工时间的方法对比见表３，采用本研究的遗传算法可获得完工时间为９８３５ｓ的调度结果，该结果优于其他方法㊂相比其他方法中最短的ＩＣＳ为１０７７７ｓ，本研究提出的方法仍然缩短了大约８．７％的时间㊂因此，该方法在解决一般家具制造混合流水车间调度问题上具有较好的可行性㊂表２㊀一个批次工件在不同工序的加工时间Ｔａｂｌｅ２㊀Ｐｒｏｃｅｓｓｉｎｇｔｉｍｅｓｏｆｄｉｆｆｅｒｅｎｔｊｏｂｓｉｎｏｎｅｂａｔｃｈｓｉｚｅ单位：ｓ工件工序冲孔（５）弯曲（８）焊接（５）加压（３）钻孔（１）１５４４８０００２３５６３１６００３５９２２６１００４６０００００５２２３６０００６５７１１７２００７３１００００８１９００６８０９４８７２５９００１０５７２０２４００１１０００９１０１２０００２８０１３４７７６０００１４０００６４０１５０００２９０１６７２５３００３９１７０００７８０１８０００６００１９０００４２０２００００７５０㊀注：工序名称括号内的数字表示该工序内的设备数量，且为同型机㊂表３㊀最大完工时间的方法对比Ｔａｂｌｅ３㊀Ｃｏｍｐａｒｉｓｏｎｏｆｍｅｔｈｏｄｓｆｏｒｍａｘｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ方法加工顺序最大完工时间／ｓ本研究方法１６，８，７，１９，１２，１３，１５，１０，４，５，１１，２０，１８，２，１，３，６，１４，９，１７９８３５ＩＣＳ１５，８，５，１８，１９，９，１２，２０，４，６，７，３，１６，１３，１４，１７，２，１１，１０，１１０７７７ＰＳＯ１２，４，１９，５，１４，１７，３，２，１５，６，９，１１，１６，１０，１８，１３，８，７，１，２０１０９３４ＳＡ１９，８，１４，４，１３，６，１８，９，１５，１１，２０，１６，３，２，７，１７，１２，１，５，１０１１００７ＡＣＯ１４，５，１３，４，１５，２０，１９，１２，１，１６，１８，１１，６，７，８，１０，１７，２，９，３１１０３９ＮＥＨ２０，１９，８，７，１１，１２，３，５，４，１８，１３，１７，９，１６，６，１０，１４，１，２，１５１１２５２ＦＩＦＯ１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１７，１８，１９，２０１３６４０㊀注：加工顺序表示２０个工件的加工顺序㊂㊀㊀为了进一步评估本研究遗传算法的性能，采用百分比偏差（Ｄ）作为测量标准，计算方法如下：Ｄ＝Ｃｘ－Ｃ０Ｃｘˑ１００％（１２）式中：Ｃｘ表示其他方法（分别为ＩＣＳ㊁ＰＳＯ㊁ＳＡ㊁ＡＣＯ㊁ＮＥＨ和ＦＩＦＯ）的完工时间；Ｃ０表示本研究遗传算法得到的完工时间㊂经式（１２）计算后的结果如表４所示㊂本研究提出的遗传算法对比当前企业常用的ＦＩＦＯ而言，缩短了大约２７．９％的完工时间，间接表明采用本研究方法可以减少２７．９％的生产成本，这对于家具制造企业具有实际意义㊂表４㊀最大完工时间的百分比偏差Ｔａｂｌｅ４㊀Ｐｅｒｃｅｎｔａｇｅｄｅｖｉａｔｉｏｎｆｏｒｍａｘｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ其他方法ＦＩＦＯＮＥＨＡＣＯＳＡＰＳＯＩＣＳＤ／％２７．９１２．６１０．９１０．６１０．１８．７４㊀结㊀论对工序间有限缓冲的板式家具混合流水车间调度问题的方法进行了研究㊂具体为：首先对缓冲约束的特性进行了研究，讨论满足缓冲约束的２种临界情况，提出相应处理策略并形成统一的缓冲约束；其次，将缓冲约束编码进遗传算法的适应度函数中，并设计其余的算法参数与操作，形成了本研３０２林业工程学报第８卷究的求解方法；最后，通过２个案例来验证本研究方法的可行性㊂第１个案例考虑了缓冲约束的板式家具多产线混合流水车间调度问题，试验结果良好，表明其具有一定的可行性；第２个案例则对比了其他的解决方法，以最大完工时间为评估目标㊂试验结果显示本研究方法均优于其他方法，这表明本研究方法具有较好的有效性㊂但要提高该方法的实际应用能力，则需引入更多的实际板式家具生产线中存在的其他约束来改进该方法，例如可考虑非同型机㊁各工件的工艺存在差异以及各工序间的缓冲区容量不同等情形㊂参考文献（Ｒｅｆｅｒｅｎｃｅｓ）：［１］曹平祥，王福辕．板式家具数字化制造技术浅谈［Ｊ］．木材工业，２０１３，２７（１）：３５－３８．ＤＯＩ：１０．１９４５５／ｊ．ｍｃｇｙ．２０１３．０１．０１２．ＣＡＯＰＸ，ＷＡＮＧＦＹ．Ａｐｐｌｉｃａｔｉｏｎｏｆｄｉｇｉｔａｌｍａｎｕｆａｃｔｕｒｉｎｇｔｅｃｈ⁃ｎｏｌｏｇｙｉｎｐａｎｅｌｆｕｒｎｉｔｕｒｅｉｎｄｕｓｔｒｙ［Ｊ］．ＣｈｉｎａＷｏｏｄＩｎｄｕｓｔｒｙ，２０１３，２７（１）：３５－３８．［２］ＩＲＩＴＡＮＩＤＲ，ＳＩＬＶＡＤＡＬ，ＳＡＡＶＥＤＲＡＹＭＢ，ｅｔａｌ．Ｓｕｓ⁃ｔａｉｎａｂｌｅｓｔｒａｔｅｇｉｅｓａｎａｌｙｓｉｓｔｈｒｏｕｇｈＬｉｆｅＣｙｃｌｅＡｓｓｅｓｓｍｅｎｔ：ａｃａｓｅｓｔｕｄｙｉｎａｆｕｒｎｉｔｕｒｅｉｎｄｕｓｔｒｙ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｌｅａｎｅｒＰｒｏｄｕｃｔｉｏｎ，２０１５，９６：３０８－３１８．ＤＯＩ：１０．１０１６／ｊ．ｊｃｌｅｐｒｏ．２０１４．０５．０２９．［３］ＷＡＮＧＬ，ＨＥＪＦ，ＸＵＳＪ．Ｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｉｎｄｕｓｔｒｙ４．０ｉｎｃｕｓｔｏｍｉｚｅｄｆｕｒｎｉｔｕｒｅｍａｎｕｆａｃｔｕｒｉｎｇｉｎｄｕｓｔｒｙ［Ｊ］．ＭＡＴＥＣＷｅｂｏｆＣｏｎｆｅｒｅｎｃｅｓ，２０１７，１００：０３０２２．ＤＯＩ：１０．１０５１／ｍａｔｅｃｃｏｎｆ／２０１７１０００３０２２．［４］ＹＡＮＧＬＺ，ＬＩＪ，ＣＨＡＯＦ，ｅｔａｌ．Ｊｏｂｓｈｏｐｐｌａｎｎｉｎｇａｎｄｓｃｈｅｄｕ⁃ｌｉｎｇｆｏｒｍａｎｕｆａｃｔｕｒｅｒｓｗｉｔｈｍａｎｕａｌｏｐｅｒａｔｉｏｎｓ［Ｊ］．ＥｘｐｅｒｔＳｙｓｔｅｍｓ，２０２１，３８（７）：ｅ１２３１５．ＤＯＩ：１０．１１１１／ｅｘｓｙ．１２３１５．［５］ＹＡＮＧＬＺ，ＬＩＪ，ＨＡＣＫＮＥＹＰ，ｅｔａｌ．Ｍａｎｕａｌｔａｓｋｃｏｍｐｌｅｔｉｏｎｔｉｍｅｅｓｔｉｍａｔｉｏｎｆｏｒｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｕｓｉｎｇａｆｕｚｚｙｉｎｆｅｒｅｎｃｅｓｙｓｔｅｍ［Ｃ］／／２０１７ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓ（ｉＴｈｉｎｇｓ）ａｎｄＩＥＥＥＧｒｅｅｎＣｏｍｐｕｔｉｎｇａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎｓ（ＧｒｅｅｎＣｏｍ）ａｎｄＩＥＥＥＣｙｂｅｒ，ＰｈｙｓｉｃａｌａｎｄＳｏ⁃ｃｉａｌＣｏｍｐｕｔｉｎｇ（ＣＰＳＣｏｍ）ａｎｄＩＥＥＥＳｍａｒｔＤａｔａ（ＳｍａｒｔＤａｔａ）．Ｊｕｎｅ２１－２３，２０１７，Ｅｘｅｔｅｒ，ＵＫ．ＩＥＥＥ，２０１８：１３９－１４６．ＤＯＩ：１０．１１０９／ｉＴｈｉｎｇｓ⁃ＧｒｅｅｎＣｏｍ⁃ＣＰＳＣｏｍ⁃ＳｍａｒｔＤａｔａ．２０１７．２６．［６］ＢＡＲＢＵＭＣ，ＲＥＨＲ，ＩＲＬＥＭ．Ｗｏｏｄ⁃ｂａｓｅｄｃｏｍｐｏｓｉｔｅｓ［Ｍ］／／ＲｅｓｅａｒｃｈＤｅｖｅｌｏｐｍｅｎｔｓｉｎＷｏｏｄＥｎｇｉｎｅｅｒｉｎｇａｎｄＴｅｃｈｎｏｌｏｇｙ．Ｈｅｒｓｈｅｙ：ＩＧＩＧｌｏｂａｌ，２０１４：１－４５．ＤＯＩ：１０．４０１８／９７８－１－４６６６－４５５４－７．ｃｈ００１．［７］熊先青，李荣荣，白洪涛．中国智能家具产业现状与发展趋势［Ｊ］．林业工程学报，２０２１，６（１）：２１－２８．ＤＯＩ：１０．１３３６０／ｊ．ｉｓｓｎ．２０９６－１３５９．２０２００３００２．ＸＩＯＮＧＸＱ，ＬＩＲＲ，ＢＡＩＨＴ．ＲｅｓｅａｒｃｈｓｔａｔｕｓａｎｄｄｅｖｅｌｏｐｍｅｎｔｔｒｅｎｄｏｆｉｎｔｅｌｌｉｇｅｎｔｆｕｒｎｉｔｕｒｅｉｎＣｈｉｎａ［Ｊ］．ＪｏｕｒｎａｌｏｆＦｏｒｅｓｔｒｙＥｎｇｉｎｅｅｒｉｎｇ，２０２１，６（１）：２１－２８．［８］ＺＨＡＯＹＲ．ＯｐｔｉｍａｌｏｐｅｒａｔｉｏｎｏｆｐａｎｅｌｆｕｒｎｉｔｕｒｅｒｅｃｏｎｆｉｇｕｒａｂｌｅｍａｎｕｆａｃｔｕｒｉｎｇｓｙｓｔｅｍｂａｓｅｄｏｎＴＣＰＮａｎｄＧＡ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆ２０１１ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＥｌｅｃｔｒｏｎｉｃ＆ＭｅｃｈａｎｉｃａｌＥｎ⁃ｇｉｎｅｅｒｉｎｇａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ．Ａｕｇｕｓｔ１２－１４，２０１１，Ｈａｒｂｉｎ，Ｃｈｉｎａ．ＩＥＥＥ，２０１１：２１７９－２１８２．ＤＯＩ：１０．１１０９／ＥＭＥＩＴ．２０１１．６０２３４７１．［９］ＭＡＲＩＣＨＥＬＶＡＭＭＫ，ＰＲＡＢＡＨＡＲＡＮＴ．Ｐｅｒｆｏｒｍａｎｃｅｅｖａｌｕａｔｉｏｎｏｆａｎｉｍｐｒｏｖｅｄｈｙｂｒｉｄｇｅｎｅｔｉｃｓｃａｔｔｅｒｓｅａｒｃｈ（ＩＨＧＳＳ）ａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉｓｔａｇｅｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｍｉｓｓｉｎｇｏｐｅｒａｔｉｏｎｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＩｎｄｕｓｔｒｉａｌａｎｄＳｙｓｔｅｍｓＥｎｇｉｎｅｅｒｉｎｇ，２０１４，１６（１）：１２０．ＤＯＩ：１０．１５０４／ｉｊｉｓｅ．２０１４．０５７９４６．［１０］ＳＡＷＩＫＴ．Ｂａｔｃｈｖｅｒｓｕｓｃｙｃｌｉｃｓｃｈｅｄｕｌｉｎｇｏｆｆｌｅｘｉｂｌｅｆｌｏｗｓｈｏｐｓｂｙｍｉｘｅｄ⁃ｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＲｅｓｅａｒｃｈ，２０１２，５０（１８）：５０１７－５０３４．ＤＯＩ：１０．１０８０／００２０７５４３．２０１１．６２７３８８．［１１］ＧＯＮＺÁＬＥＺ⁃ＮＥＩＲＡＥＭ，ＧＡＲＣÍＡ⁃ＣÁＣＥＲＥＳＲＧ，ＣＡＢＡＬ⁃ＬＥＲＯ⁃ＶＩＬＬＡＬＯＢＯＳＪＰ，ｅｔａｌ．Ｓｔｏｃｈａｓｔｉｃｆｌｅｘｉｂｌｅｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｕｎｄｅｒｑｕａｎｔｉｔａｔｉｖｅａｎｄｑｕａｌｉｔａｔｉｖｅｄｅｃｉｓｉｏｎｃｒｉｔｅｒｉａ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＩｎｄｕｓｔｒｉａｌＥｎｇｉｎｅｅｒｉｎｇ，２０１６，１０１：１２８－１４４．ＤＯＩ：１０．１０１６／ｊ．ｃｉｅ．２０１６．０８．０２６．［１２］ＲＡＨＭＡＮＩＤ，ＨＥＹＤＡＲＩＭ，ＭＡＫＵＩＡ，ｅｔａｌ．Ａｎｅｗａｐｐｒｏａｃｈｔｏｒｅｄｕｃｉｎｇｔｈｅｅｆｆｅｃｔｓｏｆｓｔｏｃｈａｓｔｉｃｄｉｓｒｕｐｔｉｏｎｓｉｎｆｌｅｘｉｂｌｅｆｌｏｗｓｈｏｐｐｒｏｂｌｅｍｓｗｉｔｈｓｔａｂｉｌｉｔｙａｎｄｎｅｒｖｏｕｓｎｅｓｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＭａｎａｇｅｍｅｎｔＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇＭａｎａｇｅｍｅｎｔ，２０１３，８（３）：１７３－１７８．ＤＯＩ：１０．１０８０／１７５０９６５３．２０１３．８１２３３２．［１３］ＲＡＨＭＡＮＩＤ，ＲＡＭＥＺＡＮＩＡＮＲ．Ａｓｔａｂｌｅｒｅａｃｔｉｖｅａｐｐｒｏａｃｈｉｎｄｙｎａｍｉｃｆｌｅｘｉｂｌｅｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｕｎｅｘｐｅｃｔｅｄｄｉｓｒｕｐｔｉｏｎｓ：ａｃａｓｅｓｔｕｄｙ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＩｎｄｕｓｔｒｉａｌＥｎｇｉｎｅｅｒｉｎｇ，２０１６，９８：３６０－３７２．ＤＯＩ：１０．１０１６／ｊ．ｃｉｅ．２０１６．０６．０１８．［１４］ＳＣＨＵＬＺＳ，ＮＥＵＦＥＬＤＪＳ，ＢＵＳＣＨＥＲＵ．Ａｍｕｌｔｉ⁃ｏｂｊｅｃｔｉｖｅｉｔｅｒａｔｅｄｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｆｏｒｃｏｍｐｒｅｈｅｎｓｉｖｅｅｎｅｒｇｙ⁃ａｗａｒｅｈｙ⁃ｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｌｅａｎｅｒＰｒｏｄｕｃｔｉｏｎ，２０１９，２２４：４２１－４３４．ＤＯＩ：１０．１０１６／ｊ．ｊｃｌｅｐｒｏ．２０１９．０３．１５５．［１５］ＹＩＮＧＫＣ，ＬＩＮＳＷ．Ｍｉｎｉｍｉｚｉｎｇｍａｋｅｓｐａｎｆｏｒｔｈｅｄｉｓｔｒｉｂｕｔｅｄｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｍｕｌｔｉｐｒｏｃｅｓｓｏｒｔａｓｋｓ［Ｊ］．ＥｘｐｅｒｔＳｙｓｔｅｍｓＷｉｔｈＡｐｐｌｉｃａｔｉｏｎｓ，２０１８，９２：１３２－１４１．ＤＯＩ：１０．１０１６／ｊ．ｅｓｗａ．２０１７．０９．０３２．［１６］ＯĜＵＺＣ，ＥＲＣＡＮＭＦ．Ａｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｈｙｂｒｉｄｆｌｏｗ⁃ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍｕｌｔｉｐｒｏｃｅｓｓｏｒｔａｓｋｓ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｃｈｅｄｕｌｉｎｇ，２００５，８（４）：３２３－３５１．ＤＯＩ：１０．１００７／ｓ１０９５１－００５－１６４０－ｙ．［１７］ＴＡＲＩＧＡＮＵ，ＳＩＲＥＧＡＲＩ，ＳＩＲＥＧＡＲＫ，ｅｔａｌ．Ｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇｕｓｉｎｇａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｉｎｆｕｒｎｉｔｕｒｅｉｎｄｕｓｔｒｙ［Ｊ］．ＩＯＰＣｏｎｆｅｒｅｎｃｅＳｅｒｉｅｓ：ＭａｔｅｒｉａｌｓＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，２０２１，１１２２（１）：０１２０５６．ＤＯＩ：１０．１０８８／１７５７－８９９ｘ／１１２２／１／０１２０５６．［１８］ＷＡＮＧＨＭ，ＣＨＯＵＦＤ，ＷＵＦＣ．Ａｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇｆｏｒｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍｕｌｔｉｐｒｏｃｅｓｓｏｒｔａｓｋｓｔｏｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎ［Ｊ］．ＴｈｅＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＡｄｖａｎｃｅｄＭａｎｕｆａｃｔｕ⁃ｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，２０１１，５３（５）：７６１－７７６．ＤＯＩ：１０．１００７／ｓ００１７０－０１０－２８６８－ｚ．［１９］ＴＳＥＮＧＣＴ，ＬＩＡＯＣＪ．Ａｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒｈｙｂｒｉｄｆｌｏｗ⁃ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍｕｌｔｉｐｒｏｃｅｓｓｏｒｔａｓｋｓ［Ｊ］．Ｉｎ⁃ｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＲｅｓｅａｒｃｈ，２００８，４６（１７）：４６５５－４６７０．ＤＯＩ：１０．１０８０／００２０７５４０７０１２９４６２７．［２０］ＭＡＲＩＣＨＥＬＶＡＭＭＫ，ＰＲＡＢＡＨＡＲＡＮＴ，ＹＡＮＧＸＳ．Ｉｍｐｒｏｖｅｄｃｕｃｋｏｏｓｅａｒｃｈａｌｇｏｒｉｔｈｍｆｏｒｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｔｏｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎ［Ｊ］．ＡｐｐｌｉｅｄＳｏｆｔＣｏｍｐｕｔｉｎｇ，２０１４，１９：９３－１０１．ＤＯＩ：１０．１０１６／ｊ．ａｓｏｃ．２０１４．０２．００５．［２１］ÇＯＬＡＫＭ，ＫＥＳＫＩＮＧＡ．Ａｎｅｘｔｅｎｓｉｖｅａｎｄｓｙｓｔｅｍａｔｉｃｌｉｔｅｒａｔｕｒｅｒｅｖｉｅｗｆｏｒｈｙｂｒｉｄｆｌｏｗｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＩｎｄｕｓｔｒｉａｌＥｎｇｉｎｅｅｒｉｎｇＣｏｍｐｕｔａｔｉｏｎｓ，２０２２，１３（２）：１８５－２２２．ＤＯＩ：１０．５２６７／ｊ．ｉｊｉｅｃ．２０２１．１２．００１．（责任编辑㊀莫弦丰）４０２。