基于两阶段调度的制造单元协同调度算法研究

Computer Engineering andApplications计算机工程与应用###工程 与应 用###基于两阶段调度的制造单元协同调度算法研究牛 力 ，韩小汀NIU Li 一，HAN Xiaoting1．中国人民大学 数据工程与知识工程教育部重点实验室，北京 1008722．中国人民大学 信息资源管理学院，北京 1008723．北京航空航天大学 经济管理学院，北京 1001911．Key Laboratory of Ministry of Education for Data Engineering and Knowledge Engineering，Renmin University of China，Beijing1 00872，China2．School of Information Resource Management，Renmin University of China，Beijing 1 00872，China3．School ofEconomics and Management，Beihang University,Beijing 100191，ChinaNIU Li，HAN Xiaoting．Two-phase co-scheduling algorithm solving celular manufacturing scheduling problem．ComputerEngineering and Applications，2013，49(19)：232—237.

Abstract：A two—phase scheduling algorithm including pre·scheduling phase and whole-scheduling phase focused on cellularmanufacturing problem is proposed．In order to solve the cellular manufacturing scheduling problem，process decomposition andalgorithm optimization technology are used to decompose the large-scale scheduling problem．This algorithm can reduce theproblem scale efi ciently while the scheduling result is of practical significance for manufacturing practice．Precise calculationand approximate solution is combined in the proposed algorithm，which can enhance computing efi ciency while achieving globaloptimization．The effect of the algorithm is validated by numerical experiments.

Key words：flexible manufacturing cell；two—phase scheduling；heuristic algorithm；metaheuristic algorithm摘 要：针对单元制造问题，提出了一种基于两阶段的调度算法，通过过程分解和算法优化两方面实现问题求解。调度过程分为“预调度”和“整体调度”两个阶段 ，对大规模调度进行调度 ，不仅有效地降低了问题规模，同时制造单元调度结果对实际生产具有现实意义；调度算法采用了“精确”计算和“近似”求解相结合的方式，既提高计算效率叉兼顾了全局优化 目标。数值实验结果表明了的这一设计思路的有效性。

关键词：柔性制造单元；两阶段调度；启发式算法；智能搜索算法文献标志码：A 中图分类号：TH165；TP39 doi：10．3778／j．issn．1002．8331．1207．0442l 引言作为成组技术(Group Technology，GT)的延伸 ，单元制造技术(Celular Manufacturing，CM) 结合工作车间方式的灵活性和流水线方式的高效率，能以近似刚性流水线的费用来生产多品种小批量的产品 ，以其特有的优势吸引了众多研究人员的注意 。CM在包括减少物料处理成本、准备时间、在制品库存、完工时问等方面有较大的优势 。

单元构建、单元布局和单元管理与调度是制造单元研究的三个主要方面 。当前大部分研究仍注重于单元构建和单元布局方面 ， '“ ，而生产调度和单元管理方面成果极其有限，特别在基于单元制造技术的调度算法研究方面的工作还没有深入展开。因此，如何将先进有效地制造单元技术运用到生产调度优化问题中，并在此基础上拓展调度算法研究，无论对于发展基于制造单元的调度问题理论研究还是丰富生产调度算法研究，都具有很强的理论价值和现实意义。

调度问题的NP．难属性决定了如果大规模的调度问题简单套用小规模问题的求解方法，计算时间和搜索空间产生的组合爆炸将使得求解性能很差 ，特别是面对多制造单元，且存在跨单元生产的制造环境下，现有的调度算法则无法直接进行求解。对于单元调度的求解方法，不同的基金项目：国家自然科学基金(No．71071008)。

作者简介：牛力(1982一)，男，博士，讲师，研究领域为系统工程，生产调度；韩小汀(1983一)，女，硕士，实验师，研究方向为复杂系统，社会网络。E-mail：rucniuli###gmail．com收稿日期：2012．07—30 修回日期：2012．09．28 文章编号：1002—8331(2013)19．0232—06牛 力，韩小汀：基于两阶段调度的制造单元协同调度算法研究学者给出了不同的解决方案。其中，在进行大规模调度分解方面，文献[101按照单元制造的思路对调度环境进行分解 ，然后对独立的制造单元单独调度，最后将结果整合成为整体问题调度方案；文献[111将单元调度问题整体视为一 个大规模调度问题，通过建立复杂的数学模型，运用多种数学方法进行求解 ，得到整个单元调度问题的调度结果 ；文献[12]给出了一种基于启发式规则框架的单元调度问题求解方法，可以根据不同调度性能要求，动态选入启发式规则，并对调度问题进行求解。在调度问题的求解算法方面 ，文献[131分别给出了两种遗传算法进行单元构造和单元调度；文献『14]使用了模拟退火算法进行了单元布局和动态制造单元调度问题的研究。虽然针对单元调度问题已经有了相当的研究成果 ，但是，现有的研究仍存在以下问题 ：(1)调度算法针对特定问题 、特定的调度性能进行设计，算法可变动性较差，一旦调度环境或者调度目标发生改变，调度算法往往无法动态调整；(2)大多数算法从整体问题出发，调度算法的设计重点偏重于整体调度结果，对制造单元的调度算法和调度结果都没有过多的关注；(3)在针对制造单元大规模调度问题中，现有的算法研究仍然不多，并且算法效率和稳定性相对不高。

启发式规则计算精度不高，无法完全满足调度性能的要求 ，而由于制造单元存在耦合 ，无法直接使用高效的智能搜索算法直接对其求解。因此，为了提高计算效率同时兼顾全局优化目标，本文将智能搜索算法的调度精度与启发式规则的计算效率相融合，设计了基于“预处理”和“整体调度”的两阶段的制造单元合作协同调度算法。

2 柔性制造单元调度问题背景本文所研究的制造环境如下：企业拥有多个不同的加工车间，并且拥有一定种类和数量的制造资源(机器)，这些制造资源分布在该企业的各个加工车间内，为了满足不同的生产任务，制造资源可以重新进行物理布局，且制造资源的移动将产生重布局费用。针对给定的加工任务集，待加工产品(工件)有多个种类且每个种类包含一定的加工批量，同时，每种产品的加工路径都不唯一，也即属于开放车间环境(Open Shop)，在对产品进行加工时，产品可以拆分为多个批次且按不同的加工路线进行 。

考虑如上的问题环境，通过有效的单元设计，应能达到以下目标：(1)通过对加工任务进行拆分与批量设置，并对相应的任务指派最佳加工路径，以提高加工资源的使用效率；(2)对分布在不同加工车间内的制造资源进行布局优化，考虑加工任务的路径、加工数量和单元构建，调整机器布局以实现最小的加工任务运输费用。

文献[8]在融合物理制造单元和逻辑制造单元优势的基础上，研究了加工车间资源布局可变且存在生产任务多加工路线环境下的柔性制造单元构建问题。在综合产品的加工成本 、加工车 间之间的运输成本 、加工车间内的运输成本、跨单元操作的额外成本、制造资源移动成本等，并且综合考虑了加工车间内资源限制、单元内资源限制、单元数量限制后，进行了加工产品的路径选择、批量设置、生产资源布局和制造单元构建的工作。通过数值实验对模型进行了分析和验证 ，实验证明柔性制造单元构建模型可以有效地减少总制造成本。

3 基于两阶段的混合调度框架3．1 基于两阶段混合调度框架设计针对上述问题，本文提出了基于“预处理”和“整体调度”两个阶段的调度问题求解过程。两阶段求解的思想是：第一阶段，将调度问题进行分割，选取调度问题的特征工件集 ，接着对特征工件集进行“预调度”处理 ，将“预处理”的排序结果 ，形成对整体调度问题的一种预测；第二阶段，根据“预调度”结果对整体问题进行“整体调度”，进而最终确定各个工件在机器上的加工顺序。基于以上设计思想，提出如图 1所示的基于两阶段的混合调度框架，通过两阶段对问题的处理 ，可以将大规模的问题分解为较小的问题进行处理 ，既能够保证一定的调度精度，又可以提高整体的计算效率。

IGAI SAIHSGA图 1 基于两阶段的混合调度框架图两阶段调度的制造单元合作协同调度算法的优势在于：(1)在调度过程，通过制造单元的分解，可以对各个制造单元并行调度 ，将原有的大规模调度问题，分解为制造单元内调度问题；(2)在预调度阶段 中，使用智能搜索算法既可以得到较好的调度性能，又可以减小计算规模；(3)在预调度基础上进行的启发式规则调度具有一定的“预测”能力，因此提高了启发式规则调度的精度，同时兼顾 了计算性能。

3．2 调度框架中算法的选取调度算法的性能将直接影响到调度结果的优劣，在基于两阶段的混合调度框架中，需要在每一个阶段内选取各自的调度算法进行问题调度。在以上的求解过程中，本文使用一种“精确”与“近似”计算相结合的计算思路，一方面，对特征工件集进行“精确”计算，使用智能搜索算法对一 预调度阶段 一整体调度阶段 一Computer Engineering andApplications计算机工程与应用问题求解 ，既降低了问题搜索空间，又有助于在合理的系统开销内得到理想的调度结果；另一方面，在“预调度”的指导下，对剩余工件集使用启发式规则进行“近似”求解，可以用较小的计算空问和时间空问得到精度较高的解。

通过“精确”与“近似”计算相结合的设计思路，既利用启发式规则求解效率高的优点，又通过“预调度”避免了启发式规则“预测距离”短，无法获取全局调度信息的劣势。

(1)“预调度”阶段算法选取在“预调度”阶段中，首先需要对特征工件集进行调度排序，因此，性能更优的调度算法将直接得到更好的调度结果 ，从而为进一步的整体调度打下良好的基础。在“预调度”阶段中，由于特征工件集的规模相对较小，因此，可以选择成熟的智能搜索算法进行计算 ，如遗传算法、模拟退火算法、神经网络算法等，上述算法在求解小规模调度问题中都被证明取得了较好的调度结果 。并且，仿真实验也证明，选择调度性能更优的调度算法能够取得更好的整体调度结果，因此，在预调度阶段，调度算法的选择策略为尽可能选取调度性能更优的智能调度算法。

(2)“整体调度”阶段算法选取整体调度是在“预调度”的基础上进行的，整体问题的调度性能在很大程度上依赖“预调度”的结果；且在对整体问题调度过程中，需要将“预调度”结果作为调度约束，因此不适合选用智能搜索算法。针对整体调度阶段的特点，可以选择启发式规则对基于“预调度”的整体问题进行求解。在整体调度阶段 ，以G．T[161活动调度生成器为调度框架，对特征工件集以外的剩余工序集，按照G．T方法选入竞争工序集；对特征工件集，以一定的规则按预调度结果将工序选入竞争工序集，然后对竞争工序集通过启发式规则选定优先级高的工序，统一进行排序。

4 基于两阶段调度的制造单元合作协同调度算法4．1 算法的预处理过程基于两阶段调度的制造单元合作协同调度算法的预处理过程需要对特征工件集、预调度计算方法进行确定，同时，需要在整体调度阶段之前得到预调度结果。

(1)制造单元特征工件集的选定特征工件集的大小没有一个固定的标准，需要根据调度问题的特性来动态制定特征工件集的规模。如果选入的特征工件集规模较大，虽然得到的预调度结果可以表示更全面的问题特征，容易得到最优的整体调度方案，但对预调度的计算开销较大，需要耗费较多的时间和资源；如果选入的特征工件集规模较小，虽然更容易进行预调度计算，但由于较小预调度结果可能无法完整的描述整体调度问题，从而造成整体调度性能不佳。

针对基于制造单元的调度问题，各个制造单元的工件都由单元内工件集合与跨单元工件集合构成，根据制造单元构建的原则，最优的单元构建将尽量避免跨单元工件的出现 ，也就意味单元内工件集合代表制造单元的工件特征。因此 ，在确定特征工件集的步骤中，可以将制造单元的单元内工件集作为制造单元的特征工件集。

(2)“预调度”结果处理方法经过调度计算，得到以特征工件集为子问题的调度方案，即特征工件在各个机器上的加工顺序。预调度结果的建立步骤为：首先将选入的特征工件集和对应的机器集合作为一个独立的调度子问题 ；其次，选择高效和稳定的调度算法对子问题进行求解；最后，去掉调度解中的时间信息，保留各个机器上工件的先后加工次序作为预调度结果。

(3)基于预调度结果的工序选入方法在“整体调度”阶段，需要将预调度阶段的结果体现在整体调度中，本节介绍在G．T活动调度生成器框架下的基于预调度结果的工序选入方法。在G—T活动调度生成器方法中，需要将所有待调度的工序选入待调度工序集，并根据待调度工序集进行调度，而基于预调度结果的两阶段调度过程中，特征工件集在各个机器上的先后加工次序已经确定，因此需要设计基于预调度结果的工序选入方法 ，将预调度结果与整体调度结合。首先，令 矩阵表示单元c 的预调度结果，第 行第f列的元素 [ ，i]表示机器上第 i个操作，其值为相应的工件号， ，．]表示机器m上的各个工件的先后加工次序。工序选入步骤如下：步骤 1初始化特征工件集 ， 是单元 C 的待调度工序集合， ，i】是单元c 的预调度结果。

步骤2(工件判断)遍历特征工件集CJ的所有工件，如果 s 中不包含工件 的待调度工序，转入步骤 3；否则，判断下一个工件。

步骤3工序0 是工件 的当前待调度工序，令m表示加I．TI~0i所在的机器，若 ，1】= ，则 = }，并转入步．骤j；否则，判断下一个工件。

U{Oi
．j
4步骤4(更新过程)将 W [ ，i]的第 行所有元素依次左移一位，尾部空出位置补0。

步骤 5若特征工件集 CJ的所有工件都已判断，则转入整体调度。

4．2 算法的流程基于两阶段调度的制造单元合作协同调度算法在制造单元预调度的基础上，以G—T活动调度器为基本框架，采用制造单元合作协同技术，对问题进行求解。两阶段算法流程如下：(1)制造单元预调度阶段步骤 1根据调度问题环境，选取各单元的单元内工件集为特征工件集 CJ。

步骤2针对各个单元的特征工件集 CJ，选用智能搜索算法，对以特征工件集为子问题的调度问题求解。

步骤3通过优化计算，得到各个单元特征工件集中各个工件在各个机器上的加工次序，并将此结果保存为各个制造单元的预调度结果。

(2)N造单元合作协同调度阶段步骤1(单元调度)单元C 已调度集合尸 ： = ，令牛 力，韩小汀：基于两阶段调度的制造单元协同调度算法研究： 是单元c 的待调度工序集合。

步骤2(待调度工序选入)对制造单元内的所有工件进行判断 ，对没有工序在 中的所有工件按如下工序选入方法操作：①如果该工件不属于特征工件集，则直接将该工件未加工的首道工序加入 ： ；②如果该工件属于特征工件集 ，按照特征工件集选入方法将工序入 。

步骤3(机器选择)计算当前部分调度集合 ： 中的最早完成时间：f( ： )=min
． ，+pI， (1)0
l∈S
月其中，，和 Pf．J分别为工序 0fIJ的释放时间和加工时间，并令 m 表示能够令 t(S )达到最小值的机器，如果存在多个，则任选其一。

步骤4令 表示机器 m 上所有操作的集合：L ={0 ， Ipn l=1} (2)其中p ={l0 薯 序 √在机器 n上加工。

步骤5在集合 中选择竞争机器 m 的冲突工序集：= {0

步骤7更新已调度的工序集合：P 1=P ： u{D ．，} (4)步骤8(单元协同)如果工序0：．属于代理工件，则根据单元协同技术” ，进行制造单元协同操作。

步骤9(更新预调度结果)如果工序 0 属于特征工件集内的工件 ，则更新工序 0 所使用机器的预调度结果 ，将该机器预调度结果的当前待加工首工件 删除，并依次将其他工件前提。

步骤10如果Ps； 为完整调度，则停止；否则返回步骤2。

5 仿真计算及分析通过两种规模不同的制造环境，使用基于两阶段调度的制造单元合作协同调度算法对问题进行仿真计算。在算法设置中，分别选取了两种预调度算法和两种整体调度规则，用来分析不同方法对调度结果的影响。两种仿真环境实验结果表明，使用基于两阶段调度的制造单元合作协同调度算法可以得到更优的调度结果。

5．1 仿真环境规模参数设置这里使用文献[12]提出单元调度仿真环境设计方法 ，随机生成工件的加工时间、加工路线等，并对工件设计相应的跨单元生产过程。首先通过小规模的问题环境1，展示算法的在不同预调度方法下的调度结果，然后通过大规模问题环境2，比较和分析算法的调度性能。两个仿真环境的参数设置如表 1所示。

表1 基于两阶段调度算法的仿真性能比较5．2 调度算法选取及参数设置(1)优化目标以所有工件的“最大完成时间”最小化为目标进行优化。

(2)预调度算法选取及参数设置预调度结果的优劣将直接决定问题的调度性能，为方便进行算法性能比较，本文选用传统遗传算法与一种改进遗传算法——和声遗传混合算法(Harmony Search GeneticAlgorithm，HSGA) ，通过这两种算法来分析预调度算法对整体调度结果的影响。

GA算法参数为：种群规模为300个 ，交叉概率取 1，变异概率取0．2，遗传代数为400代。

HSGA算法参数为：遗传算法参数为种群规模为300个，交叉概率取l，遗传代数为400代；和声搜索算法参数为记忆考虑概率 尸 M取0．85，曲调调整率 P。ifch取0．25，和声搜索代数为200代。

(3)整体调度规则选取通过与制造环境2中启发式规则仿真结果的对比 ，在优化最大完工时间时，‘LPT”规则在3个算例中得到最优解，“IMOD”规则n 在2个算例中得到最优解。因此 ，本文分别选取“LPT”规则和“IMOD”规则作为整体调度规则。

5．3 制造环境1的仿真结果分析与评价5．3．1 仿真环境1的仿真过程仿真环境 1分别使用GA算法和HSGA算法作为预调度方法，“LPT”规则和“IMOD”规则作为整体调度规则，组合成4种算法对此仿真案例计算，并与基于启发式规则得到的最优结果进行对比分析。

5．3．2 调度过程分析(1)调度结果整体分析基于两阶段调度的制造单元合作协同算法仿真实验结果，如表2所示。将各个算法的调度结果与使用启发式规则算法得到的各个调度性能的最优值进行比较 ，在以最小化“最大完工时间”为优化目标时，使用基于两阶段调度的制造单元合作协同算法整体调度性能优于启发式规则调度算法。4种不同的两阶段调度算法在优化“最大完工时间”目标时，“最大完工时间”平均缩短了21．5，效率平均提高 10．3％，其中HSGA+LPT的两阶段算法取得了最优结果，“最大完工时间”缩短了32，效率提高了15．5％。通过表2的调度结果可以看出，采用HSGA预调度算法平均效率提高了 12．1％，而采用GA预调度算法平均效率提高了8．7％；Computer Engineering and Applications计算机工程与应用采用不同的整体调度规则也会对调度结果产生较大的影响，从算例 1中数据可以得出，使用“LPT”规则的调度结果优于“IMOD”规则 。

表2 基于两阶段调度算法的仿真性能比较表2中的拖期工件只包含实际工件的拖期数，c 为启发式规则得到的最优值；C 为使用预调度算法得到的最优值；百分比为较启发式规则的改善率；“GA”、“HSGA”为预调度算法，“IMOD”、“LPT”为整体调度规则。

(2)预调度结果对比分析在使用基于两阶段调度的制造单元合作协同调度算法计算过程中，通过GA和HSGA算法，对每个制造单元中的特征工件集进行计算，得到的预调度结果如表 3所示。

通过对结果进行比较，两种算法在机器 1、机器4、机器 10中的调度次序不同。而不同的调度次序产生了不同的整体调度结果，说明了预调度对整体调度结果的影响。

表3 GA与HSGA算法预调度结果对比5．4 制造环境2的仿真结果分析与评价5．4．1 仿真环境2的仿真过程仿真环境2首先随机生成了规模为 100个工件，100台机器，10个单元的10个仿真算例，然后分别使用GA算法和HSGA算法作为预调度方法，“LPT”规则和“IMOD”规则作为整体调度规则，组合成4种算法分别对 10个仿真案例各自进行 l0次仿真计算，并对整体调度性能结果和制造单元内性能结果进行比较和分析。

5．4．2 整体调度性能比较及分析通过使用4种方法对 1O个算法分别进行 1O次仿真计算，得到每种算法的最优值、平均值、标准差和最优值相比规则调度最优值的改善率。表4给出了各种方法的结果对比(表中为部分结果)，可以得出以下结论：(1)基于两阶段调度的算法相比启发式规则得到可以得到更优的解 ，从数据中可以看出，相比使用启发式规则的到的最优解，使用两阶段调度的各个算例都有7％左右的性能提升，充分证明了基于两阶段调度的制造单元合作协同算法的有效性。

(2)通过结果可以看出，对使用“LPT”作为整体调度规则时，“HSGA”和“GA”预调度算法在调度性能上平均提升7．6％和5％，而使用“IMOD”作为整体调度规则时，“HSGA”和“GA”预调度算法在调度性能上平均提升6．4％和8．7％，在Benchmark实验中，“HSGA”算法的调度性能要优于“GA”算法 ，因此，性能较高的预调度算法将得到更好的整体调度结果。

(3)从表中标准差可以看出，基于两阶段调度的算法计算结果落在相对较小的范围内，显示出较强的稳定性。

这是由于使用“GA”和“HSGA”算法作为预调度算法时，制造单元的特征工件集相对整体问题规模较小(本文算例中，预调度算法的计算规模为 10×8，而整体调度问题规模为100x 100)，因此调度算法稳定性较高。

(4)从表中数据可以得出，“LPT”与“IMOD”整体调度规则在分别使用两种预调度算法时，调度性能相差分别为1．4％与1．1％，说明使用不同的整体调度规则对调度结果影响相对较小，而整体调度性能对预调度的结果依赖度较高。

表4 4种算法性能比较(部分)表4中，C’为启发式规则得到的最优值；百分比为算法最优值较启发式规则最优值的改善率；“GA”、“HSGA”为预调度算法，“IMOD”、“LPT”为整体调度规则。

图2展示了在仿真算例1～5中的各个算法的最优值比较。

5013?
!蚓 480． 460lI1 堪40一 420算 。 {算面 I算 {算例4 1¨j 确5-规则调度 470 503 450 477 452GA+IM OD 437 476 441 448 438GA+LPT 449 485 437 452 459·HSGA+IMOD 431 473 431 439 418HSGA+LPT 441 480 430 445 429图2 算例 1-5的调度结果对比牛 力，韩小汀：基于两阶段调度的制造单元协同调度算法研究 2013，49(19) 237从图中可以看出，基于两阶段调度的算法得到的调度结果都优于基于启发式规则的调度结果。

6 结束语针对大规模调度问题，本文设计了一种基于“预调度”和“整体调度”相结合的两阶段调度算法框架 ，通过引入“精确”与“近似”两类算法，既利用启发式规则求解效率高的优点，又通过“预调度”避免了其“预测距离”短，无法获取全局调度信息的劣势，仿真实验也证明了该算法框架的有效性和稳定性。该算法提出了一种求解大规模单元调度问题的思路 ，取得了以下的研究成果。

(1)通过制造单元对大规模问题进行分解 ，将复杂的调度环境分解为规模较小的单元调度问题。针对单元内部调度 ，设计了特征工件集 ，并设计了跨单元工件的调度规则，协调单元间调度，从而保证了整体调度。

(2)通过设计两阶段调度框架，避免了智能搜索算法效率不高 ，而启发式规则性能不足的问题，相较于使用启发式规则，通过不同算法组合的两阶段调度算法具有更优的调度性能和算法稳定性。

(3)“预调度”结果对整体调度结果有较大的影响，因此，使用性能更优的预调度算法能大幅提高整体调度性能。

(4)在预调度基础上进行的启发式规则调度具有一定的“预测”能力 ，因此提高了启发式规则调度的精度，同时兼顾了计算性能。

作为一个开放的调度算法框架，本文已经证明了两阶段调度算法的有效性，但该算法仍具有进一步深入研究的空间 ：(1)在今后的研究中可以将调度目标作为调度算法的选择依据，按照单 目标或多目标调度问题选择不同的调度算法；(2)可以把性能更优秀的调度算法引入到该算法框架中，并且将该算法框架进行调整修改引入到其他调度模型 中。

参考文献：[1]Naua S，Divakar R．Celular manufacturing systems design，planning and control[M]．London：Chapman& Hal1．1996.

[2]Wu Xiaodan，Chu Chaohsien，Wang Yunfeng，et a1．A geneticalgorithm for cellular manufacturing design and layout[J].

European Journal of Operational Research，2007，1 8 1(i)：156—167.

[3】Li Xiangyong，Baki M F，Aneja Y P．An ant colony optimi—zation metaheuristic for machine- part cell formation prob—lems[J]．Computers & Operations Research，2010，37(12)：2071—2081.

[4]Mahadavi I，Paydar M M，Solimanpur M，et a1．Genetic algo—rithm approach for solving a cel formation problem in eel—lular manufacturing[J]．Expert Systems with Applications，2009，36(3)：6598．6604.

[5]Xambre A R，Vilarinho P M．A simulated annealing approachfor manufacturing cell formation with multiple identicalmachines[J]．European Journal of Operational Research，2003，151(2)：434．446.

[6]Papaioannou G，Wilson J M．The evolution of cel formationproblem methodologies based on recent studies(1997—2008)：review and directions for future research[J]．European Journalof Operational Research，2010，206(3)：509—521.

[7]Ahi A，Aryanezhad M B，Ashtiani B，et a1．A novel approachto determine cel formation，intracellular machine layout andcel layout in the CMS problem based on T0PSIS method[J].

Computers& Operations Research，2009，36(5)：1478-1496.

【8】牛力．资源布局可变条件下的开放车间柔性制造单元构建技术研究[J】．科学技术与工程 ，2011，11(25)：6054—6059.

[9]金锋．吴澄．大规模生产调度问题的研究现状与展望[J]．计算机集成制造系统，2006，12(2)：161—168.

[10]Sun D，Batta R．Scheduling larger job shops：a decompositionapproach[J]．Intemational Journal of Production Research，1996，34(7)：2019—2033.

[1 1]Yang Wenhwa，Liao Chingjong．Group scheduling on two celswith intercel movement[J]．Computers&Operations Research.

1996，23(10)：997—1006.

【12]牛力，韩小汀．基于启发式规则的柔性制造单元合作协同调度算法研究[J]．科学技术与工程 ，2012，12(3)：514—520.

[13】Arkat J，Farahani M H，Hosseini L．Integrating cel formationwith cellular layout and operations scheduling[J]．The Inter—national Journal of Advanced M anufacturing Technology，2012，61：637—647.

【14]Kia R，Baboli A，Javadian N，et a1．Solving a group layoutdesign model of a dynamic system with alternative processroutings，lot spliting and flexible reconfiguration by simu—lated annealing[J]．Computers& Operations Research．2012.

39(11)：2642—2658.

[15]Pinedo M．Scheduling：theory，algorithms and systems[M]．NewYork：Springer-Verlag，2008.

[16][17】[18】Gif er B，Thompson G L．Algorithms for solving productionscheduling problems[J]．Operations Research，1960，8(4)：487—503.

牛力．柔性制造环境下的生产调度问题研究[D]．北京：北京航空航天大学 ，2010.

Raman N．M inimum tardiness scheduling in flow shops：con·struction and evaluation of alternative solution approaches[J].

Journal of Operations Management，1995，12(2)：131-151.