面向云制造的混流混合车间调度问题

鲁建厦 胡庆辉 董巧英 汤洪涛

浙江工业大学机械工程学院，杭州，310014

面向云制造的混流混合车间调度问题

鲁建厦 胡庆辉 董巧英 汤洪涛

浙江工业大学机械工程学院，杭州，310014

为解决云制造环境下混流混合车间的生产调度优化问题，综合考虑混流装配与零部件加工的集成优化以及外协云任务与自制任务的协同调度，建立了以最小化最大完工时间、均衡化零部件生产和最大化零件车间机器利用率为优化指标的多目标车间调度模型。基于零件分批和车间调度的两阶段求解策略，设计了一种两级递阶结构的混合生物地理学优化算法，采用在迁移算子中嵌入差分进化算法的变异策略来提高算法的搜索效率。最后，通过实例验证了模型和算法的有效性。

云制造；混流混合车间；混合生物地理学优化算法；零件分批；车间调度

0 引言

混流混合车间是一类具有多种类产品混流生产和多类别车间混合集成特征的车间，是目前装配制造企业应对多品种、小批量生产的较好车间形式。实际的离散装配车间通常是由作业车间和流水车间组合而成的混合车间，产品生产过程一般包括零件加工、部件装配和产品总装。为适应多品种、小批量生产，该类混合车间多采用混流装配方式来平衡生产负荷，以减小流水车间产品切换对作业车间生产的影响，避免零件加工车间出现制造资源忙闲不均的现象。但是生产波动难以完全消除，相比于单独的作业车间，混流混合车间中的零件加工车间受后续流水车间混流装配的需求约束，更易出现资源闲置的现象。近年来兴起的云制造模式，为混流混合车间提升闲置资源的利用率提供了新的思路。云制造是一种利用网络和云制造服务平台，按用户需求组织网上制造资源，为用户提供各类按需制造服务的网络化制造新模式[1]。通过云制造平台的海量任务库，车间中的制造资源可以充分利用闲置时段对外提供云服务，从而提高资源利用率。但随着车间承接的外协云任务增多，企业自制任务受到的影响也越大，增加了自制产品零件加工与混流装配的协调难度。要想通过云制造模式充分提高闲置资源的利用率，就需要协调好自制任务与外协云任务，避免盲目参与云制造而影响自制任务的生产。因此，面向云制造的混流混合车间调度必须将外协云任务与自制任务一起综合考虑，进行协同调度。

2015年国务院出台了“中国制造2025”规划，明确提出加快推动信息化与工业化的深度融合，并把智能制造作为两化融合的主攻方向[2]。作为我国智能制造的重点研究领域，云制造在理论架构[3-4]和平台实现[5-6]上已取得了较多成果。对于资源闲置现象明显的混流混合车间，如何利用云制造模式提升制造资源利用率，构建一个面向云制造的车间调度环境，己经成为企业实施云制造模式转型急需解决的关键问题。

当前，面向云制造的车间调度研究主要是针对单独的作业车间构建云环境下的调度模型：王军强等[7]基于聚类算法提出了面向云制造的机器能力界定方法，并提出了一种云环境下的作业车间调度模型。孙月洲[8]建立了云环境下作业车间生产资源的动态调度模型，并采用改进遗传算法进行求解。杨屹[9]提出了事件驱动的云制造车间调度架构，通过对事件模式的匹配来处理调度过程中出现的扰动事件。现有的混流混合车间调度研究也均基于传统制造模式，简化了外协加工任务，在调度模型中只考虑自制任务。李修琳等[10]以在制品成本最小为目标，运用集成模拟退火算法的混合遗传算法来求解混流混合车间协同调度问题。胡恒等[11]运用多群体并行遗传算法求解混流混合车间模糊调度问题。目前关于面向云制造的混流混合车间调度研究，以及综合考虑外协云任务与自制任务的车间调度模型均未见报道。

本文选取与实际离散装配生产契合度较高的混流混合车间，以云制造模式为背景，以提升制造资源整体利用率为切入点，综合考虑车间承接的外协云任务与自制任务，探索一种云环境下混流混合车间协同调度问题的模型和求解方法。

1 问题描述

1.1 面向云制造的混流混合车间模型描述

云制造平台上的外协任务按照粒度大小可分为产品级、部件级、零件级和工序级。本文研究的面向云制造的混流混合车间主要承接零件级和工序级的外协云任务。该车间由三部分构成：第一部分为加工零件的作业车间，可对外提供云服务；第二、第三部分分别为装配部件和成品的流水车间，以生产自制产品为主。图1所示为面向云制造的混流混合车间简化模型。

图1 面向云制造的混流混合车间简化模型Fig.1 Simplified model of cloud manufacturing- oriented mixed-model hybrid shop

自制任务与外协云任务在零件加工车间的主要区别在于生产批量的变动性。自制零件的生产受混流装配最小生产循环的需求约束，在一定时间段内的需求量较为稳定，通常采用等量分批的策略，即每个批次的批量相等且固定。现有的混流混合车间调度研究在进行零件加工车间生产排序时均采用固定的生产批量[10-11]。完成外协云任务时，由于没有后续车间的约束，因此不同批次的生产批量可以变化。采用变动批量进行零件加工车间的生产排序有利于充分利用制造资源的闲置时段。

综上可得面向云制造的混流混合车间主要特点：①零件加工车间可对外承接外协云任务，同时生产自制产品和云服务产品(分别采用等量分批和柔性分批策略)；②部件装配车间和产品总装车间都以混流方式组织生产，只生产自制产品；③零件加工车间以批为单位组织生产，部件装配和产品总装车间以个为单位组织生产；④各车间通过物料需求约束关联，由缓冲区连接。

1.2 面向云制造的混流混合车间调度模型构建

面向云制造的混流混合车间调度问题数学描述如下：零件加工车间有M台机器，加工Z种自制产品的零件和Y种外协云任务的零件，每种零件工艺顺序已知，并且每种零件可分成若干批次，各个子批量当作一个整体来处理，共享同一批次的启动时间(包括准备时间和搬运时间)，自制任务等量分批、批量相等，外协云任务柔性分批、批量变动；部件装配车间有一条含N个工位的部件装配流水线，有R种不同型号的部件以相同顺序依次通过流水线的所有工位完成装配；产品总装车间有一条含S个工位的总装流水线，装配I种订单产品。生产调度就是确定产品总装车间和部件装配车间的装配序列，以及零件加工车间自制任务零件和外协任务零件的批次分割和生产顺序，使既定的调度目标最优。

1.2.1 目标函数

车间调度研究中常用的一个评价指标是最大完工时间，它能够体现出生产系统效率的高低，因此选取最小化最大完工时间为优化目标。混流生产的目的是使零部件的消耗速率尽可能稳定，从而保证零件加工车间和部件装配车间能够匀速稳定地进行生产，因此将均衡化零部件生产作为混流混合车间调度的一个特殊优化目标。此外，零件车间参与云制造的目的在于充分提升制造资源的整体利用率，因此将最大化零件车间资源利用率也作为优化目标。

(1)最小化最大完工时间。系统中存在两类生产任务，对于自制任务而言，产品总装是最后一道工序，取总装车间的最大完工时间为自制任务的最大完工时间；外协云任务只在零件加工车间生产，取外协任务在零件车间的最大完工时间为外协云任务的最大完工时间，建立最小化最大完工时间模型：

(1)

(2)均衡化零部件生产。参考文献[12]，将总装—部件两级流水车间进一步扩展到总装—部件—零件三级混合车间中，建立零部件消耗均衡化模型：

(2)

(3)

(4)

(5)

(6)

(7)

式中，Urj为完成装配序列中前j个产品需要部件r的数量；Pr为完成装配序列中所有产品需要部件r的总数量；Vzj为完成装配序列中前j个产品需要自制零件z的数量；Qz为完成装配序列中所有产品需要自制零件z的总数量；Gir为装配一件产品i需要部件r的数量；Liz为装配一件产品i需要自制零件z的数量；bi为产品i的需求数量；Wij为指示变量，用于判断产品在生产序列中的顺序。

(3)最大化零件加工车间机器利用率。为了与前述目标一致，将其转化成最小化机器闲置时间：

(8)

式中，Fm为机器m的闲置时间；Tm为机器m的最大加工时间。

1.2.2 模型约束

针对产品总装车间、部件装配车间和零件加工车间的不同特点建立各自的约束条件。

(1)产品总装车间约束。总装车间的调度主要是对投产序列进行优化，排序和调度的结果以第一个工位的投产序列表示。在生产序列中，每个位置只能出现一个产品；每种产品在序列中出现的次数等于该产品需要加工的数量，该约束表达式为

(9)

(10)

总装车间的装配工位只有在零部件齐套的情况下才能开始装配。此时，产品总装完工时间等于该产品进入工位的时间与装配操作时间以及在该工位停工待料的时间之和，该约束表达式为

WijEis=max(Ei(s-1),Wk(j-1)Eks)+tis+Δis

(11)

(12)

式中，tis为产品i在工位s上的装配时间；Δis为产品i在工位s上停工待料的时间；Azst、Azst′分别为在t和t′时刻产品总装车间工位s含有自制零件z的数量；Arst、Arst′分别为在t和t′时刻产品总装车间工位s含有部件r的数量；Cizs、Cirs分别为产品i在工位s上装配需要自制零件z和部件r的数量。

(2)部件装配车间约束。与总装车间一样，部件装配车间也存在生产序列约束和零件齐套约束，约束表达式为

(13)

(14)

(15)

HrkErn=max(Er(n-1),Wr′(n-1)Er′n)+trn+Δrn

(16)

(17)

式中，Ern、Er′n分别为部件装配车间部件r和r′在工位n上的完工时刻；trn为部件r在工位n上的装配时间；Δrn为部件r在工位n上停工待料的时间；Aznt、Aznt′分别为在t和t′时刻部件装配车间工位n含有自制零件z的数量；Crzn为部件r在工位n上装配时需要自制零件z的数量。

(3)零件加工车间约束。零件加工车间中，同批零件之间存在工艺顺序约束，即一批零件需完成前一道工序后，才能加工后一道工序，该约束表达式为

Edpm-tdpm+D(1-adpm′m)≥Edpm′

(18)

(19)

(20)

(21)

tdpm=wdm+Xdt″dm/cd

(22)

(23)

(24)

此外，不同批零件之间还存在资源约束，即在同一台机器上，完成前一批零件的加工任务后才能开始下一批加工，该约束表达式为

Ed′p′m-Edpm+D(1-bdpd′p′m)≥td′p′m

(25)

(26)

(27)

(28)

(29)

(30)

2 模型求解算法设计

生物地理学优化(biogeography-based optimization，BBO)算法[13]是一种模拟自然界种群迁移规律的新型智能优化算法，不同于其他智能算法每次迭代都要淘汰劣解、产生新解，它通过独特的迁移机制在种群中分享较优变量，并不直接产生新的子代，这种直接影响更有助于提高较差解的性能，加快全局搜索。本文研究的调度模型涉及多类型和多层级的混合车间，并且存在批量划分问题，解的搜索空间极大，需要搜索效率较高的求解算法。BBO全局高效搜索的特点对该问题具有较好的优化效果。目前，BBO在作业车间调度问题上已得到成功应用[14-15]，与差分进化(differential evolution，DE)算法结合的混合算法也取得了良好的效果[16]。因此，本文建立一种混合算法，以BBO算法为主体，在迁移算子中嵌入DE算法。DE算法可有效提高邻域搜索效率，弥补BBO算法在局部搜索方面的不足。

2.1 算法总体思想

面向云制造的混流混合车间调度模型涉及多个车间的调度策略，且零件加工车间中存在批量划分问题，批量划分的结果直接影响到后续各车间调度排序的优化效果，因此如何确定最佳批次以及各批次中的工件数量显得至关重要。参照分层法将调度过程分为零件分批和车间调度两个阶段：第一阶段考虑零件车间的加工任务如何分批；第二阶段对各车间进行调度排序。在分批阶段的一次迭代过程中，分批方案确定后，各零件的批数以及各批次的工件数量均已确定，故第二阶段的调度优化可视为常规性的混流混合车间调度问题，它以第一阶段的分批结果为调度对象，搜索当前分批结果的最优排产方案。因此，该算法采用两层嵌套的形式，外层产生分批方案，内层相当于解码函数，被外层频繁调用，产生调度方案。

2.2 算法关键及细节

2.2.1 算法编码

针对零件分批和车间调度两个阶段，采用不同的编码方式：第一阶段分别采用整数编码和二进制编码对零件车间中的自制任务和外协任务进行批量划分；第二阶段采用整数编码对3个车间进行调度排序。

2.2.1.1 零件分批阶段编码

批次划分的理想情况是将单个零件作为编码的最小单位。但这种方式会使解的搜索空间很大，不利于算法运行，而且考虑到机器调整时间，以单个零件为一个批次的情况不现实。因此，参考实际生产中的最小生产批量以某个固定量为编码的最小单位。

2.2.1.2 车间调度阶段编码

以上一阶段确定的分批结果为输入，建立一个三段式编码：第一部分为零件加工车间编号，第二部分为部件装配车间编号，第三部分为产品总装车间编号。其中，产品总装车间和部件装配车间是流水车间，可以根据各产品/部件的数量比例来确定最小生产循环，采用基于工件的编码方式对一个循环中的装配序列进行编号，相同数字代表相同工件，维度为工件数量。零件加工车间采用基于工序的编码方式，每位编码由两位数字组成，第一位数字代表零件，第二位数字代表批次，如“11”表示零件1的第一个批次。相同编码代表相同零件及批次，且出现次序表示加工顺序，如首先出现的“11”表示零件1第一个批次的第一道工序，第二个出现的“11”表示零件1第一个批次的第二道工序，维度为零件批次总数和工序总数的乘积。图2所示为两阶段编码的一个示例，第一阶段产生分批结果，第二阶段产生调度结果。

图2 两阶段栖息地编码示例Fig.2 Example of two level hierarchical structures coding

2.2.2 栖息地适宜指数

针对多目标优化问题，结合Pareto排序和密度信息来确定栖息地适宜指数：

IHS(i)=R(i)+D(i)

(31)

(32)

S(i)=|{j|j∈P+Q∧i≻j}|

(33)

(34)

(35)

其中，R(i)为原始适应度，表示有多少个解比该解更优；D(i)为密度值，用来比较具有相同R(i)值的解的优劣；符号|·|表示集合的规模；符号≻表示Pareto支配关系；S(i)为个体强度，代表其所支配个体的数目；σik为个体i与第k个相邻个体的欧氏距离。

2.2.3 迁移策略

为提高算法的搜索能力，在标准迁移算子中通过交叉参数的方式引入DE的变异策略。现有的BBO-DE混合算法研究主要是针对独立的连续型变量，而文本研究的调度问题中，栖息地编码是存在约束关系的离散变量。考虑到调度问题的特点，不对特征向量本身而是对其在编码中所处的位置进行差分扰动，混合迁移算子为

(36)

式中，h(k)为随机选取的工件k在编码中首次出现的位置；rbest为最优解；r1、r2为随机选择的两个不同解；rj为根据迁出概率选取的较优解；g为缩放因子；RC为交叉参数；ceil(·)表示向上取整函数。

针对零件分批和车间调度两阶段的编码特点，设计不同的迁移操作，具体如下：在零件分批阶段，随机选择一种零件，将迁出个体中该零件的分批编码整段替换到迁入个体中，如图3a所示；在车间调度阶段，分别对三段编码各自进行迁移，防止不同车间调度工件的串码。针对每一段车间编码，首先随机选择一种工件，再按式(36)确定该组工件首次出现的位置。该组工件的其余个体按其在迁出个体向量中的相应距离插入到迁入个体中，最后将剩余工件按在迁入个体向量中的顺序依次重新排列，如图3b所示。

(a)零件分批阶段迁移操作

(b)车间调度阶段迁移操作图3 两阶段迁移操作过程Fig.3 Two stage migration process

2.2.4 变异策略

针对零件分批和车间调度两个阶段分别设计不同的变异操作，具体如下：零件分批阶段，采用单点变异的方式，如图4a所示；车间调度阶段，分别对三段编码各自进行变异操作，采用子序列随机变异的方式，即从整段编码中任选两个编号不同的位置，将这两个位置之间的子序列进行随机排列，形成新的个体，如图4b所示。

2.3 算法流程

针对零件分批和车间调度两个阶段采用两层嵌套结构，外层算法产生分批方案，针对每个分批结果调用内层算法，产生相应的调度方案。图5所示为算法的整体流程，P、Q分别表示算法中零件分批阶段的内外部种群；P′、Q′分别表示车间调度阶段的内外部种群。

(a)零件分批阶段变异操作

(b)车间调度阶段变异操作图4 两阶段变异操作过程Fig.4 Two stage variant process

图5 两阶段混合生物地理学优化算法流程图Fig.5 Flow chart of two-stage hybrid biogeography-based optimization

3 实例验证

以某装配制造企业在云制造环境下的生产调度为例，对模型和算法进行验证。该企业的生产系统是由零件加工车间、部件装配车间和产品总装车间组成的混流混合车间。产品总装车间共有10个工位，装配P1、P2、P3三种产品，对应的工艺和作业时间如表1所示。装配1个产品P1分别需要零件Z1、零件Z2和部件R1各1个；装配1个产品P2分别需要零件Z2、零件Z3和部件R2各1个；装配1个产品P3分别需要零件Z1、零件Z3和部件R3各1个。部件装配车间有5个工位，装配R1、R2、R3三种部件，对应的工艺和作业时间如表2所示。装配1个部件R1需要1个零件Z4；装配1个部件R2需要1个零件Z5；装配1个部件R3需要1个零件Z6。零件加工车间除生产6种自制零件外，还参与云制造服务，并在此计划期内承接了3种外协零件的订单。表3、表4所示分别为外协零件和自制零件的工艺及作业时间，逗号前后分别为批次启动时间和单个零件加工时间。

表1 产品总装车间工艺及时间Tab.1 Process and time of product assembly shop s

表2 部件装配车间工艺及时间Tab.2 Process and time of parts assembly shop s

表3 零件加工车间外协零件工艺及时间Tab.3 Process and time of cloud service task in parts shop

表4 零件加工车间自制零件工艺及时间Tab.4 Process and time of self-made task in parts shop

计划期内，自制任务产品P1、P2、P3的生产任务分别为100、200、100。将其分解为部件级和零件级，则部件R1、R2、R3的生产任务分别为100、200、100；自制零件Z1、Z2、Z3、Z4、Z5、Z6的生产任务分别为200、300、300、100、200、100。外协云任务产品Y1、Y2、Y3的生产任务分别为150、200、200。各零件的最小生产批量均设为50。

设定算法参数：内部种群数量为50，外部种群数量为20，最大迁入率为1，最大迁出率为1，最大变异率为0.05，最大迭代次数为100，交叉参数为0.1。以MATLAB为算法平台进行求解运算。取最佳结果之一，得到分批编码{2-3-3-1-2-1}、{1-0-1-1-0-0-1-0}和三段式调度编码{11-11-11-51-51-21-21-51-51- 61-61-61-81-82-91-91-21-31-31-52-52-92-52-52-31-32-12-32-32-91-91-41-41-41-41-12-71-71-71-33-33-22-22-23-23-22-23-23-33-81-82-12-72-72-72-92-92-92-83-83}-{2-3-2-1}-{2-3-2-1}。对应6种自制零件的批次分别为2、3、3、1、2、1，批量均为100；外协零件Y1分为2批，批量分别为50和100；外协零件Y2分为3批，批量分批为50、50和100；外协零件Y3分为2批，批量均为100；最小化均衡系数为4.9375，最小完成时间为7926 s，零件车间设备最小闲置率为13.8%。其中，总装车间最小生产循环为{P2-P3-P2-P1}，部件车间最小生产循环为{R2-R3-R2-R1}，零件车间调度结果如图6所示。

图6 零件加工车间调度甘特图Fig.6 Parts shop scheduling Gantt chart

针对上述实例，分别采用基于矩阵编码的标准BBO算法与本文提出的两阶段混合BBO算法，求解结果如表5所示。

表5 求解结果对比表Tab.5 Results comparison table

表5所示结果表明，两阶段混合BBO比标准BBO求解效果更好、搜索时间更短。两阶段混合BBO算法先分批、后调度的策略避免了每次迭代时批次变动对调度编码长度的调整，且多阶段的搜索降低了重复搜索的概率，提高了搜索效率。混合迁移算子的设计也增强了算法局部搜索的能力，避免陷入局部最优。

4 结语

结合云制造模式，关注混流混合车间闲置资源制造能力的提升，研究外协云任务和自制任务的协同调度问题。以最小化最大完工时间、均衡化零部件生产和最大化零件车间机器利用率为目标建立调度模型，在零件车间中采用不同的批量划分策略，协调外协任务与自制任务。在求解算法上，采用先分批、后调度的两阶段求解策略，设计了一种集成差分进化的混合生物地理学优化算法。通过某离散装配制造企业在云制造环境下的车间调度实例，验证了所建模型和算法的有效性。所研究的面向云制造的混流混合车间协同调度问题，为车间协调自制任务和外协云任务的生产调度提供了有效方法，为提升车间整体效率提供了新的思路。云制造环境下，企业间的资源共享与协作十分频繁，不仅可以为其他企业提供本单位的闲置能力，也可以对外寻求本单位不足的加工资源。本文只考虑了对外提供云服务时，外协云任务与自制任务的协同调度问题。考虑同时接受和提供云服务情况下的协同调度问题将是下一步研究方向。

[1] 李伯虎，张霖，王时龙，等.云制造——面向服务的网络化制造新模式[J].计算机集成制造系统，2010，16(1)：1-7，16. LI Bohu，ZHANG Lin，WANG Shilong，et al. Cloud Manufacturing：A New Service-oriented Networked Manufacturing Model[J]. Computer Integrated Manufacturing Systems，2010，16(1)：1-7，16.

[2] 周济.智能制造——“中国制造2025”的主攻方向[J].中国机械工程，2015，26(17)：2273-2284. ZHOU Ji. Intelligent Manufacturing—Main Direction of “Made in China 2025” [J].China Mechanical Engineering， 2015，26(17)：2273-2284.

[3] ADAMSON G，WANG L H，HOLMA M，et al.Cloud Manufacturing—A Critical Review of Recent Development and Future Trends[J]. International Journal of Computer Integrated Manufacturing，2015：1-34.DOI: 10.1080/0951192x.2015.1031704.

[4] WANG X V，XU X W.An Interoperable Solution for Cloud Manufacturing[J]. Robotics and Computer-Integrated Manufacturing，2013，29(4)：232-247.

[5] 战德臣，赵曦滨，王顺强，等.面向制造及管理的集团企业云制造服务平台[J].计算机集成制造系统，2011，17(3)：487-494. ZHAN Dechen，ZHAO Xibin，WANG Shungqiang，et al. Cloud Manufacturing Service Platform for Group Enterprises-oriented to Manufacturing and Management[J]. Computer Integrated Manufacturing Systems，2011，17(3)：487-494.

[6] 顾新建，黄沈权，陈笈熙，等. 模具行业需求驱动的云制造服务平台[J]. 计算机集成制造系统，2012，18(7)：1650-1656. GU Xinjian，HUANG Shenquan，CHEN Jixi，et al. Cloud Manufacturing Service Platform Driven by Mold Manufacturing Industry Demand [J]. Computer Integrated Manufacturing Systems，2012，18(7)：1650-1656.

[7] 王军强，崔福东，张承武，等.面向云制造作业车间的机器能力界定方法[J]. 计算机集成制造系统，2014，20(9)：2146-2163. WANG Junqiang，CUI Fudong，ZHANG Chengwu，et al. Capacity Partition Method of Machines in Cloud Manufacturing-oriented Job Shops[J]. Computer Integrated Manufacturing Systems，2014，20(9)：2146-2163.

[8] 孙月洲.云制造车间资源调度与配置模型及优化研究[D].哈尔滨：哈尔滨理工大学，2012. SUN Yuezhou. Study on Modeling and Optimization Method of Resource Scheduling and Allocation in Cloud Manufacturing Workshop[D]. Harbin：Harbin University of Science and Technology，2012.

[9] 杨屹.事件驱动的云制造车间调度研究[D].广州：华南理工大学，2014. YANG Yi. Study on Event Driven Cloud Manufacturing Shop Scheduling[D]. Guangzhou：South China University of Technology，2014.

[10] 李修琳，鲁建厦，柴国钟，等. 基于混合遗传算法的混流混合车间协同调度问题[J]. 中国机械工程，2012，23(8)：935-940. LI Xiulin，LU Jiansha，CHAI Guozhong，et al. Hybrid Genetic Algorithm for Mixed-model Hybrid-shop Scheduling Problem[J]. China Mechanical Engineering，2012，23(8)：935-940.

[11] 胡恒，鲁建厦，李英德，等.基于多群体并行遗传算法的混流混合车间模糊调度研究[J].浙江工业大学学报，2012，40(5)：554-558. HU Heng，LU Jiansha，LI Yingde, et al. Study of Mixed-mode Hybrid Shop Fuzzy Scheduling Problem Based on Multi-populations Parallel Genetic Algorithm[J]. Journal of Zhejiang University of Technology，2012，40(5)：554-558.

[12] 王炳刚. 混流加工/装配系统集成优化研究[J]. 机械工程学报，2010，46(17)：114-121.

WANG Binggang. Research on Integrated Optimization for Mixed-model Fabrication/assembly Systems[J]. Journal of Mechanical Engineering，2010，46(17)：114-121.

[13] SIMON D. Biogeography-based Optimization[J]. IEEE Transactions on Evolutionary Computation，2008，12(6)：702-713.

[14] RAHMATI S H A，ZANDIEH M.A New Biogeography-based Optimization (BBO) Algorithm for the Flexible Job Shop Scheduling Problem [J]. The International Journal of Advanced Manufacturing Technology，2012，58(9/12)：1115-1129.

[15] 张国辉，聂黎，毛学港.生物地理学算法求解柔性作业车间调度问题[J].计算机应用研究，2014，31(4)：1005-1008. ZHANG Guohui，NIE Li，MAO Xuegang. Solving Flexible Job-shop Scheduling Problem Based on Biogeography-based Optimization Algorithm[J]. Application Research of Computers，2014，31(4)：1005-1008.

[16] 叶开文，刘三阳，高卫峰.基于差分进化的生物地理学优化算法[J].计算机应用，2012，32(11)：2981-2984. YE Kaiwen，LIU Sanyang，GAO Weifeng. Biogeography-based Optimization Algorithm of Differential Evolution[J]. Journal of Computer Applications，2012，32(11)：2981-2984.

(编辑 张 洋)

Cloud Manufacturing-oriented Mixed-model Hybrid Shop-scheduling Problem

LU Jiansha HU Qinghui DONG Qiaoying TANG Hongtao

College of Mechanical Engineering,Zhejiang University of Technology,Hangzhou,310014

To solve the scheduling problems for cloud manufacturing-oriented mixed-model hybrid shop, considering the integrated optimization of mixed flow assembly and part processing, and collaborative scheduling of cloud service tasks and self-made tasks, the model was presented based on three objectives: minimizing the makespan, production smoothing of parts, and maximizing the utilization rate of the job shop. Then, a hybrid BBO algorithm with two level hierarchical structures was proposed to solve the model. In the hybrid algorithm, batching strategy was put forward in the first level and hybrid shop scheduling was designed in the second level. Moreover, a mutation strategy of differential evolution algorithm was introduced to the transport operator of BBO to improve the searching efficiency. Finally, an example was given to test the model and algorithm, and the results demonstrat the feasibility and effectiveness of the method.

cloud manufacturing； mixed-model hybrid shop； hybrid biogeography-based optimization(BBO)； part batching； shop-scheduling

2016-03-02

浙江省自然科学基金资助项目(LY15G010009，LQ14E050004)

TB491

10.3969/j.issn.1004-132X.2017.02.011

鲁建厦，男，1963年生。浙江工业大学机械工程学院教授、博士研究生导师。主要研究方向为精益生产、智能制造。发表论文97篇。E-mail：ljx@zjut.edu.cn。胡庆辉，男，1991年生。浙江工业大学机械工程学院硕士研究生。董巧英，女，1977年生。浙江工业大学机械工程学院讲师、博士后研究人员。汤洪涛，男，1976年生。浙江工业大学机械工程学院副教授。