考虑批量装配的柔性作业车间调度问题研究

巴　黎　李　言　曹　源　杨明顺　刘　永

西安理工大学，西安，710048



考虑批量装配的柔性作业车间调度问题研究

巴黎李言曹源杨明顺刘永

西安理工大学，西安，710048

摘要：柔性作业车间调度是生产调度领域中的一个重要组合优化问题，由于取消了工序与加工设备的唯一性对应关系，因而相较于作业车间调度问题，具有更高的复杂度。针对该问题在批量装配方面的不足，考虑将批量因素与装配环节同时集成到柔性作业车间调度问题当中。以成品件的完工时间为优化目标，对该批量装配柔性作业车间调度问题进行了数学建模。针对该模型，提出一种多层编码结构的粒子群算法，并对该算法的各个模块进行了设计。最后，以实例验证了该数学模型的正确性及算法的有效性。

关键词：柔性作业车间调度问题；批量；装配；6层编码结构

0引言

作业车间调度问题(job-shop scheduling problem，JSP)作为生产调度领域的研究热点，是最具普遍性的问题之一，属于典型的NP-Hard问题[1]。柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)由Brucker和Schlie于1990年提出[2]，是JSP的扩展，与JSP不同的是，FJSP取消了工序与加工设备的唯一性对应关系，因而相较于JSP，具有更高的复杂度，已被证明为NP-Hard问题[3]。由于FJSP更加符合实际生产环境，因此研究FJSP具有重要的理论意义和实际价值[4]。

近年来，学者们对多目标FJSP进行了大量的研究。文献[4]以makespan、加工成本和提前/拖期惩罚值为优化目标，建立了相应的优化模型，针对该问题，提出了一种多目标粒子群算法，最后以实例对所建模型及算法进行了验证；文献[5]以makespan、机器总负载及机器最大负载为目标，提出了一种基于Pareto优化的离散自由搜索算法，并通过两个实例验证了算法的有效性；文献[6]以makespan及设备最大负载为目标，将生产能力约束考虑到约束条件，对问题进行建模，提出了一种改进的遗传算法，最后以标准算例对模型及算法进行了验证；文献[7]以makespan、设备总负载和设备最大负载为目标，提出了一种基于粒子群算法和局部搜索算法的混合智能算法，并以实例对该算法进行了验证；文献[8]以makespan、设备总负载和设备最大负载为目标，通过对各优化目标赋予相应的权重，将多个优化目标合并成单一优化目标，提出了一种混合遗传退火算法。

在FJSP的算法改进方面，文献[9]提出了一种基于遗传算法及启发式规则的混合遗传算法，通过启发式规则，对不符合约束的解进行修正，最后，以实例对该算法进行了验证；文献[10]提出了一种基于知识的可变邻域搜索算法，最后以实例对该算法进行了验证；为提高种群质量，文献[11]提出了一种基于Bayesian统计推理的分布估计算法，最后，采用标准算例对该算法进行了验证。

目前，FJSP的相关研究主要集中在多目标FJSP以及FJSP的算法改进方面。实际生产中，由于订单的多样性以及各工件加工数量上的不同，为提高生产效率，往往对工件进行分批加工。显然，若对所有工件都默认整批加工，并不符合实际生产要求。

文献[12]针对多目标柔性作业车间批量调度问题，以完工时间、机器总负载、机器最大负载、总加工成本及工件拖期惩罚为优化目标，建立了该问题的数学模型，并提出了一种基于差分进化算法的多目标柔性批量调度算法对该问题进行求解；文献[13]针对考虑模糊交货期的多目标批量生产柔性作业车间调度问题，以加工批次完工时刻的加权平均隶属度及加工批次流程时间价值总量为优化目标，对该问题进行建模，并提出了一种改进的非支配排序遗传算法对该问题进行求解；文献[14]同时将机器、模具及操作人员作为调度资源，针对多资源作业车间批量调度问题，以生产周期为优化目标，建立了该问题的数学模型，提出了一种由多目标混合差分进化算法与多目标局部搜索策略相结合的混合算法；文献[15]针对以makespan为优化目标的柔性作业车间批量调度问题，将粒子群算法与模拟退火算法相结合，提出了一种改进的粒子群算法。

近年来，已有一些文献将批量因素考虑到柔性作业车间调度问题当中。但是，相关文献大都以工件的加工过程作为问题的主要考虑环节，并未考虑到其他可能影响到生产过程的环节。实际生产中，工件制造仅为制造过程的最底层，完工的各类工件将会通过设备或人工的方式组装成组件，最后总装成成品。无论是组件，还是成品件的组装，都有其BOM(bill of material)需求及相关的装配设备，而各组件及成品的BOM需求，以及装配环节的相关设备必然会对生产流程产生影响，显然，若仅考虑工件制造环节，难以符合实际的生产情况。

综上所述，为使FJSP更加贴合实际，本文将批量因素及装配环节同时考虑到FJSP当中，将制造环节从仅考虑工件制造扩展到由工件制造、组件装配及完成件装配组成的完整制造过程，提出一种批量装配柔性作业车间调度方法。以成品件的完工时间为优化目标，对该批量装配柔性作业车间调度问题进行数学建模，提出一种多层编码粒子群算法，对该算法的各个模块进行设计，最后，以一个实例对模型及算法进行了验证。

1问题描述

某制造企业有一笔订单，需要加工多种工件，并将其中的一些工件组装成不同的组件，最终将各组件及工件组装成成品。各工件的批量不尽相同，每道工序对应多台可用的加工设备，组件及成品的装配由若干台装配设备完成。在此情况下，以成品的完工时间为优化目标，通过确定批次数、各道工序在加工序列中的位置以及各工序对应的加工设备，以获得完工时间最小的调度方案。该问题中各变量及其符号表示如下：n表示工件数；d表示组件数；f表示成品数，默认所有工件/组件组装成一种成品；nG表示订单需求的成品数量；m表示加工设备数；s表示装配设备数；pS表示工序数；bi表示工件i的总批量，i=1,2,…,n；bCi表示工件i的批次数；bSil表示工件i的第l批次工件对应的批量，l=1,2,…,bCi；TMSj表示加工设备j的可开工时间，j=1,2,…,m；TSJilvj表示工件i的第l批次工件的第v道工序在加工设备j上的开工时间，v=1,2,…,pS；TMJilvj表示工件i的第l批次工件的第v道工序在加工设备j上的单件加工时间；TFJilvj表示工件i的第l批次工件，第v道工序在加工设备j上的完工时间；TFFJil表示工件i的第l批次工件的完工时间；TASu表示装配设备u的可开工时间，u=1,2,…,s；TMAeu表示组件e在装配设备u上的单件装配时间，e=1,2,…,d；TSAeu表示组件e在装配设备u上的开工时间；TFAeu表示组件e在装配设备u上的完工时间；TMEu表示成品在装配设备u上的单件装配时间；TSEu表示成品在装配设备u上的开工时间；TFEu表示成品在装配设备u上的完工时间；BOMGJi表示单件成品与工件i的数量对应关系；BOMGAe表示单件成品与组件e的数量对应关系；BOMAJei表示单件组件e与工件i的数量对应关系；NSAe表示当前可进行预装的组件数，初始状态下为0；NSG表示当前可进行预装的成品数，初始状态下为0；NFJi表示当前已完工的工件i的数量，初始状态下为0；NFAe表示当前已完工的组件e的数量，初始状态下为0；NFG表示当前已完工的成品的数量，初始状态下为0；RJPilvj为布尔变量，表示工件工序与加工设备的对应关系，若工件i的第l批次工件的第v道工序选择加工设备j进行加工，其值为1，否则为0；RAAeu为布尔变量，表示组件与装配设备的关系，若组件e由装配设备u装配，其值为1，否则为0；REAu为布尔变量，表示成品与装配设备的关系，若成品由装配设备u装配，其值为1，否则为0。

2问题建模

以成品完工时间最小为目标，可得目标函数：

minTFEuu=1,2,…,s

(1)

对上述模型，考虑以下约束。

(1)各工件分批后工件对应的批量总和等于相应分批前工件的总批量，即

(2)

(2)假设工件i′的第l批次工件的第v′道工序在加工设备j上加工，若本道工序对应加工设备的可开工时间大于该批次工件上道工序的完工时间，则该批次工件第v′道工序的开工时间等于设备j的可开工时间；否则，该批次工件第v′道工序的开工时间等于该批次工件上道工序的完工时间。表达式如下：

若RJPi′lv′j=1，则有

(3)

针对约束(2)，需计算以下参数的数据。

计算TFJi′lv′j及更新TMSj：

TFJi′lv′j=TMSj=TSJi′lv′j+TMJi′lv′jbSi′l

(4)

若v′=pS，则记录TFFJi′l：

TFFJi′l=TFJi′lv′j

(5)

更新当前已完工的工件i′的数量：

NFJi′←NFJi′+bSi′l

(6)

若BOMAJe′i′>0，计算当前可预装的组件e′的数量。约定符号“//”，对于两个非负整数a、b，若a>b且b>0，则a//b表示a除以b，其得数只取整数部分；若a0，则a//b=0；若b=0，则a//b=+∞。得到当前可预装的组件e′的数量：

NSAe′=min(NFJi//BOMAJe′i)

(7)

对于任意装配设备u，若RAAe′u=1，则更新组件e′在装配设备u上的开工及完工时间：

TSAe′u=max(TASu，TFFJi′l)

(8)

TFAe′u=TSAe′u+TMAe′uNSAe′

(9)

更新装配设备u的可开工时间TASu：

TASu=TFAe′u

(10)

对于任意工件i，若BOMAJe′i>0，更新已完工的工件的数量NFJi：

NFJi←NFJi-NSAe′BOMAJe′i

(11)

更新当前已完工的组件e′的数量NFAe′：

NFAe′←NFAe′+NSAe′

(12)

若BOMGAe′>0，计算当前可预装的成品的数量：

NSG=min(min(NFJi//BOMGJi)，min(NFAe//BOMGAe))

(13)

对于任意装配设备u，若REAu=1，则更新成品在装配设备u上的开工及完工时间：

TSEu=max(TASu，TFAe′u)

(14)

TFEu=TSEu+TMEuNSG

(15)

更新装配设备u的可开工时间TASu：

相比日本和韩国，同样作为中国的邻居，国人对印度这个国家却始终显得有些陌生，神秘，宗教是对它的印象，说到美食，远不如对日韩美食那样如数家珍。顿顿吃咖喱？吃饭直接用手？印度爱吃米饭还是面食？素食国度，不能吃肉？各种各样的局限印象和疑问，使得游客无法好好审视一下印度的食物。

TASu=TFEu

(16)

对于任意工件i，若BOMGJi>0，更新已完工的工件的数量NFJi：

NFJi←NFJi-NSGBOMGJi

(17)

对于任意组件e，若BOMGAe>0，更新已完工的组件的数量NFAe：

NFAe←NFAe-NSGBOMGAe

(18)

更新当前已完工的成品的数量NFG：

NFG←NFG+NSG

(19)

若NFG=nG，则获得到最终完工时间，即TFEu。

由于考虑了批量因素，因而，提出约束(1)对各工件的批量进行约束；对于各批次工件各道工序的开工时间，则通过约束(2)进行确定；对于分批后工件的加工环节，通过式(4)~式(6)分别确定分批后工件各道工序的完工时间及加工设备的可开工时间、分批后工件的最终完工时间、已完工工件的数量；对于组件装配环节，通过式(7)~式(12)分别确定可进行组装的组件的数量、各组件的开工时间、各组件的完工时间、装配设备的可开工时间、剩余工件的数量、已完工组件的数量；对于成品组装环节，通过式(13)~式(19)分别确定可进行组装的成品的数量、成品的开工时间、成品的完工时间、装配设备的可开工时间、剩余工件的数量、剩余组件的数量、已完工成品的数量。

3算法设计

由上述问题描述及建模可知，考虑批量装配的FJSP属NP-Hard问题，通常的整数线性规划难以对其进行求解。本文针对考虑批量装配的FJSP，提出一种新的粒子群优化算法，以下针对该算法的编码、位置更新操作、位置变换操作及相关参数依次进行说明，并给出算法的流程图。

(1) 编码。本文提出一种6层编码结构，对可行方案进行编码。该结构由原工件层、分批后工件层、批量层、加工设备层、加工方法层及加工时间层组成。①原工件层为工件的原始编码；②分批后工件层为分批后不同批次工件的编码，由工件原始编码和分批批次组成。例如，对于工件2，其被分为了两批，则一批的编码将命名为21，另一批则命名为22，其他工件依此类推；③批量层为工件不同批次的批量，其总和应等于该工件的总批量，即对应第2节中的约束(1)，本文将对各工件进行等批划分，即不同工件对应的批次数相同，同一工件对应的各子批工件的批量相同；④加工方法层为分批后工件各道工序选择的加工方法，如车、铣、刨、磨、钻等；⑤加工设备层为不同批次工件对应的加工设备编码；⑥加工时间层为各设备对应不同工件各道工序的单件加工时间，将单件加工时间乘以对应的批量，即可获得分批后工件在相应工序上的整批加工时间。基于上述定义，以2种工件、3道工序、3种加工方法、6台加工设备的批量装配FJSP为例，其编码示例如表1所示。表1中，各层第1个位置上的码值解释为：分批后工件21所属原工件为2，批量为10件，由于分批后工件编码21第1次出现在分批后工件层，即代表该工件的第1道工序，对于分批后工件21的第1道工序，选择加工设备5进行加工，加工方法为3，对应的单件加工时间为0.8分钟/件。其他依此类推。装配工序不体现在编码部分，随着各分批工件被加工完毕，将按照BOM需求实时对已完工的工件进行装配操作。

表1　批量装配FJSP完整编码示例

图1　位置更新操作

图2　加工顺序的位置变换及修正操作

假设随机产生一个位置为3，该位置对应工序的可选设备为1、2，则加工设备的位置变换操作实例如图3所示。

图3　加工设备的位置变换操作

图4　粒子群算法流程

基于上述对算法相关模块的描述，绘制算法流程图，如图4所示。其中，M表示种群规模，控制种群中个体的数量；D表示迭代次数，控制算法进行迭代的次数，若迭代达到该次数，则算法停止；PAlpha表示当前个体与全局最优解进行位置更新操作的概率，为(0，1)区间的小数；Pbeta表示当前个体与个体历史最优解进行位置更新操作的概率，为(0，1)区间的小数，本文取Pbeta=1-PAlpha；Pm表示对种群中的个体进行位置变换操作的概率，为(0，1)区间的小数；Ps表示对当前个体所对应的加工顺序进行位置变换的概率，为(0，1)区间的小数；Pa表示对当前个体所对应的设备进行位置变换概率，为(0，1)区间的小数。

4实例分析

(1) 实例说明。某企业有一笔订单，共需要加工5种工件，表示为J1~J5，各工件对应批量依次为20、10、10、30、20。共有10台加工设备，表示为M1~M10，3台装配设备MA1~MA3，6种加工方法P1~P6。以成品的完工时间最小为目标，使用上述算法对该问题进行求解。成品G的BOM如图5所示，括号中所示数字即为单件成品或组件需求的组件或工件的数量。加工方法与加工设备对应关系、各工件对应的加工路线、各加工方法对应的单件加工时间及各组件及成品对应各装配设备的单件组装时间分别如表2~表5所示。

图5　成品G的BOM

加工方法加工设备M1M2M3M4M5M6M7M8M9M10P11111P2111P311P41P511P611

表3　各工件对应的加工路线

(2) 假设条件。① 所有设备从零时刻起均为空闲状态；② 工件严格按照工艺顺序加工；③ 允许工件在工序之间等待，允许机器在工件未到达时闲置；④ 各工件的批次数相同；⑤ 设备不出现故障。

(3) 求解结果与分析。取种群规模为500、迭代次数为300、批次数为4、PAlpha为0.5、Pbeta为0.5、Pm为0.1。使用C#语言实现算法编写，在以上参数不变，取等批分批的批次数分别为4、3、2，以及不分批的情况，各分批情况分别计算50次，汇总结果如表6所示。

表4　各加工方法对应的单件加工时间　min

表5　各组件及成品对应各装配设备的

CPU 1.81 GHz、RAM 2 GB的PC主机上运行，所得最优完工时间为162.6 min，迭代图见图6，最优解对应甘特图见图7。

图6　迭代图

以下根据图7及表6所示的求解结果，从考虑装配环节及考虑分批加工两个角度，对求解结果进行分析。

(1) 考虑装配环节。由图7可知，将装配环节考虑到FJSP中，各装配设备及加工设备均被智能调度。若不考虑装配环节，仅会得到工件的最终完工时间，而实际的完工时间却是成品的完工时间，由于缺少了对装配环节的调度，使调度方案无法充分契合实际的生产情况，因而，对完整的制造过程进行调度更为合适。

图7　最优解对应的甘特图

(2) 考虑分批加工。①分批与不分批情况。由图7可知，当已完工的工件或组件的数量满足BOM时，即可安排进行组件或成品的装配，而并非是在加工环节全部完工后，再进行装配环节。

表6　求解结果汇总　min

若不对工件进行分批加工，一方面，将导致一些设备的持续使用时间过长，被加工的工件须等到整批被加工完毕，才可进入下一道工序，因而延后了工件的完工时间；另一方面，须等到所需工件及组件整批加工完毕，才可进行对应的组件或成品的装配，从而导致了装配工序的延后，延长了最终的完工时间。由表6可知，不分批情况下所获得的最优完工时间为303 min，劣于表6中考虑分批情况所获得的最优完工时间。对工件进行分批加工，一方面，实现了所属原工件相同的各分批后工件的并行加工，从而有效缩短了工件的完工时间；另一方面，只要当前完成的工件满足对应组件的BOM需求、或当前完成的工件及组件满足对应成品的BOM需求，即进行装配，使装配操作不必等到整批工件完工后进行，从而缩短了最终的完工时间。

②等批分批情况。由表6可知，对工件进行等批4批加工，所获得的最优完工时间为162.6 min，优于表中其他分批情况。若工件的批次数过小，无法充分对各分批工件进行并行加工，因而无法充分缩短工件的完工时间，从而延后了组件及成品的装配。但是，若批次数过大，则可能不符合实际的分批要求，因而，实际生产中，可根据实际的分批要求进行模拟调度，以获得合适的分批调度方案。

此外，对工件进行等批4批加工，算法平均耗时为3.7 min，劣于表6中其他分批情况。若增加工件的批次数，则会同时增加搜索域的范围，提高了问题的复杂度，从而增加了算法的计算时间。

5结论

(1) 针对批量装配FJSP，以成品件的完工时间最小为目标，建立了该问题的数学模型。

(2) 鉴于该问题的复杂性及离散性，提出了一种6层编码结构的粒子群算法，对算法的各个模块进行设计，给出了该算法的流程图。

(3) 以实例验证了所建模型的正确性及算法的有效性。求解结果表明，一方面，对工件进行分批加工，实现了所属原工件相同的各分批后工件的并行加工，提前了组件及成品的装配时间，因而缩短了最终的完工时间；另一方面，将装配环节考虑到FJSP中，使制造环节从仅工件制造扩展到从工件、至组件、乃至最终成品的完整制造过程。若不考虑装配环节，仅会得到工件的最终完工时间，而实际的完工时间却是成品的完成时间，因而，对完整的制造过程进行调度更为合适。综上所述，将批量因素及装配环节考虑到FJSP中是必要的，对于实际调度方案的制定，其优化结果具有更好的参考及指导作用。

参考文献：

[1]Garey M R, Johnson D S, Sethi R. The Complexity of Flow Shop and Job Shop Scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129.

[2]Bruker P, Schlie R. Job-shop Scheduling with Multi-purpose Machines[J]. Computing, 1990, 45(4): 369-375.

[3]Binh Ho N, Cing Tay J, MKLai E. An Effective Architecture for Learning and Evolving Flexible Job-shop Schedules[J]. European Journal of Operational Research, 2007, 179(2): 316-333.

[4]王云, 冯毅雄, 谭建荣, 等. 基于多目标粒子群算法的柔性作业车间调度优化方法[J]. 农业机械学报, 2011, 42(2): 190-195.

Wang Yun, Feng Yixiong, Tan Jianrong, et al. Optimization Method of Flexible Job-shop Scheduling Based on Multiobjective Particle Swarm Optimization Algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2011, 42(2): 190-195.

[5]彭建刚, 刘明周, 张玺, 等. 基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J]. 中国机械工程, 2015, 26(5): 620-626.

Peng Jiangang, Liu Mingzhou, Zhang Xi, et al.Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem[J]. China Mechanical Engineering, 2015, 26(5): 620-626.

[6]张铁男, 韩兵, 于渤. 生产能力约束条件下的柔性作业车间调度优化[J]. 系统工程理论与实践, 2011, 31(2): 505-510.

Zhang Tienan, Han Bing, Yu Bo. Flexible Job-shop Scheduling Optimization Based on Improved Genetic Algorithm[J]. Systems Engineering-Theory & Practice, 2011, 31(2): 505-510.

[7]Moslehi G, Mahnam M. A Pareto Approach to Multi-objective Flexible Job-shop Scheduling Problem Using Particle Swarm Optimization and Local Search[J]. Int. J. Production Economics, 2011, 129: 14-22.

[8]Shahsavari-Pour N, Ghasemishabankareh B. A Novel Hybrid Meta-heuristic Algorithm for Solving Multi Objective Flexible Job Shop Scheduling[J]. Journal of Manufacturing Systems, 2013, 32: 771-780.

[9]Gutierrez C, Garcia-Magarino I. Modular Design of a Hybrid Genetic Algorithm for a Flexible Job-shop Scheduling Problem[J]. Knowledge-based Systems, 2011, 24: 102-112.

[10]Karimi H, Rahmati S H A, Zandieh M. An Efficient Knowledge-based Algorithm for the Flexible Job Shop Scheduling Problem[J]. Knowledge-based Systems, 2012, 36: 236-244.

[11]何小娟, 曾建潮. 基于Bayesian统计推理的分布估计算法求解柔性作业车间调度问题[J]. 系统工程理论与实践, 2012, 32(2): 380-387.

He Xiaojuan, Zeng Jianchao.Solving Flexible Job-shop Scheduling Problems with Bayesian Statistical Inference-based Estimation of Distribution Algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(2): 380-387.

[12]王万良, 范丽霞, 徐新黎, 等. 多目标差分进化算法求解柔性作业车间批量调度问题[J]. 计算机集成制造系统, 2013, 19(10): 2481-2492.

Wang Wanliang, Fan Lixia, Xu Xinli, et al. Multi-objective Differential Evolution Algorithm for Flexible Job-shop Batch Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2013, 19(10): 2481-2492.

[13]曾强, 杨育, 沈玲, 等. 基于准时交货的批量生产FJSP多目标优化[J]. 计算机集成制造系统, 2011, 17(8): 1780-1789.

Zeng Qiang, Yang Yu, Shen Ling, et al. Mutiobjective Optimization for Batch Production FJSP Based on Just in Time Delivery[J]. Computer Integrated Manufacturing Systems, 2011, 17(8): 1780-1789.

[14]王海燕, 赵燕伟, 王万良, 等. 两级差分进化算法求解多资源作业车间批量调度问题[J]. 控制与决策, 2010, 25(11): 1635-1644.

Wang Haiyan, Zhao Yanwei, Wang Wanliang, et al. New Parallel Algorithm Based on DE for Batch Splitting Job Shop Scheduling under Multiple-resource Constraints[J]. Control and Decision, 2010, 25(11): 1635-1644.

[15]张静, 王万良, 徐新黎, 等. 基于改进粒子群算法求解柔性作业车间批量调度问题[J]. 控制与决策, 2012, 27(4): 513-518.

Zhang Jing, Wang Wanliang, Xu Xinli, et al.Improved Particle Swarm Algorithm for Batch Splitting Flexible Job Shop Scheduling[J]. Control and Decision, 2012, 27(4): 513-518.

(编辑袁兴玲)

Research on Flexible Job-shop Scheduling Problem with Consideration of Batch Splitting and Assembly

Ba LiLi YanCao YuanYang MingshunLiu Yong

Xi’an University of Technology,Xi’an,710048

Abstract：FJSP was a quite important combinatorial optimization problem in the field of production scheduling. Because of the one-to-one relationship among processes and machines was canceled in FJSP, FJSP was more complex than job-shop scheduling problem (JSP). Aiming at the shortages of FJSP in batch and assembly, batch factor and assembling processes were integrated in FJSP simultaneously. Makespan of finished product was the main target which will be optimized. A particle swarm optimization (PSO) with a multi-layer encoding structure was proposed. Each module of the PSO was designed. Finally, the model and algorithm were proved through an application case.

Key words：flexible job-shop scheduling problem(FJSP); batch; assembly; 6-layer encoding structure

基金项目：国家自然科学基金资助项目(61402361)；陕西省教育厅科学研究计划资助项目(14JK1521)；陕西省科学技术研究发展计划项目(科技新星)(2012KJXX-34)；西安理工大学青年科技创新团队建设计划项目(102-211408)

收稿日期：2015-06-12

中图分类号：TH166；TH186DOI：10.3969/j.issn.1004-132X.2015.23.014

作者简介：巴黎，男，1986年生。西安理工大学机械与精密仪器工程学院博士研究生。主要研究方向为生产计划与调度。发表论文8篇。李言，男，1960年生。西安理工大学机械与精密仪器工程学院教授、博士研究生导师。曹源，男，1991年生。西安理工大学机械与精密仪器工程学院硕士研究生。杨明顺，男，1974年生。西安理工大学机械与精密仪器工程学院副教授。刘永，男，1981年生。西安理工大学机械与精密仪器工程学院副教授。