调整时间与顺序相关的等同并行机调度

第４７卷第１６期

２０１

机械工程学报

ＪＯＵＲＮＡＬＯＦ

Ｖｂｌ．４７Ａｕｇ．

Ｎｏ．１６２０ｌ１

１年８月

ＭＥＣＨＡＮＩＣＡＬＥＮＧＩＮＥＥＲＩＮＧ

Ｄｏｈ

１０．３９０１肭Ｅ．２０１１．１６．１６０

调整时间与顺序相关的等同并行机调度木

胡大勇

姚振强

（上海交通大学机械系统与振动国家重点实验室上海２００２４０）

摘要：调整时间与顺序相关的等同并行机调度在生产服务业与制造业中有着十分广泛的应用背景，具有计算复杂性的主要特点。调整时间与顺序相关的等同并行机调度是将被加工工件集的各工件分配给等同并行机资源，并安排工件的加工次序。它是决策的一种形式，其目的足优化一个或多个目标。研究以最小化被加工工件最大完工时间为目标的调整时间与顺序相关的等同并行机调度，建立该Ｉ’廿Ｊ题的数学规划模硝，根据问题的结构特点开发基于两段式染色体表达的遗传算法以获得该问题的

近似最优解：在所建立数学规划模型的基础Ｅ，引入所求解问题的下界对近似最优解的质量进行评价。对具有不同规模的问

题实例进行计算试验，计算结果表明所设计的遗传算法能够在可接受的计算时间内获得合理的解。

关键词：等同并行机调度

中图分类号：ＴＰ２９

调整时间与顺序相关数学规划模犁

下界遗传算法

ＩｄｅｎｔｉｃａｌＰａｒａｌｌｅｌ

Ｍａｃｈｉｎｅｓ

ＳｃｈｅｄｕｌｉｎｇｗｉｔｈＳｅｑｕｅｎｃｅ・ｄｅｐｅｎｄｅｎｔ

ＳｅｔｕｐＴｉｍｅｓ

ＨＵＤａｙｏｎｇ

ＹＡＯＺｈｅｎｑｉａｎｇ

（Ｓｔａｔｅ

ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＭｅｃｈａｎｉｃａｌＳｙｓｔｅｍａｎｄＶｉｂｒａｔｉｏｎ，

ＳｈａｎｇｈａｉＪｉａｏＴｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００２４０）

Ａｂｓｔｒａｃｔ：Ｉｄｅｎｔｉｃａｌｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇｗｉｔｈｓｅｑｕｅｎｃｅ・ｄｅｐｅｎｄｅｎｔｓｅｔｕｐｔｉｍｅｉｓｅｘｔｅｎｓｉｖｅｌｙａｐｐｌｉｅｄｉｎｐｒｏｄｕｃｔｉｖｅｓｅｒｖｉｃｅａｎｄｍａｎｕｆａｃｔｕｒｉｎｇ

ｉｎｄｕｓｔｒｙ

ａｎｄｉｔｓｍａｉｎｃｈａｒａｃｔｅｒｉｓｔｉｃ

ａ

ｉｓ

ｔｏ

ｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙ．Ｉｄｅｎｔｉｃａｌ

ｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇｗｉｔｈ

ｓｅｑｕｅｎｃｅ－ｄｅｐｅｎｄｅｎｔｓｅｔｕｐｔｉｍｅｉｓｔｏａｌｌｏｔｍａｃｈｉｎｅ．Ｉｔｉｓ

ａ

ｓｅｔ

ｏｆｊｏｂｓｂｅｐｒｏｃｅｓｓｅｄｉｎｔｏｉｄｅｎｔｉｃａｌｐａｒａｌｌｅｌｍａｃｈｉｎｅｓａｎｄｓｅｑｕｅｎｃｅｔｈｅｊｏｂｓ

０ｎ

ｅａｃｈ

ｔｙｐｅｏｆｄｅｃｉｓｉｏｎｍａｋｉｎｇｗｉｔｈｔｈｅｐｕｒｐｏｓｅｏｆｏｐｔｉｍｉｚｉｎｇｓｉｎｇｌｅ

ｏｂｊｅｃｔｉｖｅ

ｏｒ

ｍｕｌｔｉｐｌｅ

ｏｂｊｅｃｔｉｖｅｓ．Ｉｄｅｎｔｉｃａｌ

ｐａｒａｌｌｅｌ

ｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇｗｉｔｈｓｅｑｕｅｎｃｅ－ｄｅｐｅｎｄｅｎｔｓｅｔｕｐｔｉｍｅｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｘｉｍｕｍｊｏｂｃｏｍｐｌｅｔｉｏｎｔｉｍｅｉｓｓｔｕｄｉｅｄ．Ｔｈｅｐｒｏｂｌｅｍｉｓ

ｆｏｒｍｕｌａｔｅｄ

ｏｎ

ａｓａ

ｍａｔｈｅｍａｔｉｃａｌｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌ．Ａｃｃｏｒｄｉｎｇ

ｒｅｐｒｅｓｅｎｔａｔｉｏｎｉｓ

ｄｅｖｅｌｏｐｅｄｔｏ

ｔｏ

ｔｈｅｓｔｒｕｃｔｕｒｅｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｔｈｅｐｒｏｂｌｅｍ，ａｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ

ｎｅａｒ

ｂａｓｅｄ

ｔｗｏ－ｐａｒｔ

ｃｈｒｏｍｏｓｏｍｅｏｂｔａｉｎ

ｏｐｔｉｍａｌ

ｓｏｌｕｔｉｏｎｓ．Ｂａｓｅｄ

ｎｅａｒ

０ｎ

ｔｈｅｐｒｏｐｏｓｅｄ

ｍａｔｈｅｍａｔｉｃａｌ

Ｃａｎ

ｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌ，ａｌｏｗｅｒｂｏｕｎｄｆｏｒｔｈｅｐｒｏｂｌｅｍｉｓｉｎｔｒｏｄｕｃｅｄ

ｅｘｐｅｒｉｍｅｎｔｓ

ａｒｅ

ｔｏ

ｅｖａｌｕａｔｅｔｈｅｑｕａｌｉｔｙｏｆ

ｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｓ．Ｃｏｍｐｕｔａｔｉｏｎａｌ

ｃｏｎｄｕｃｔｅｄ

ｏｎ

ｉｎｓｔａｎｃｅｓｏｆｄｉｆｆｅｒｅｎｔｓｉｚｅｓ，ａｎｄｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅ

ａｎ

ｄｅｓｉｇｎｅｄ

ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ

ｏｂｔａｉｎｒｅａｓｏｎａｂｌｅｓｏｌｕｔｉｏｎｓｗｉｔｈｉｎ

ａｃｃｅｐｔａｂｌｅｃｏｍｐｕｔａｔｉｏｎａｌｔｉｍｅ．

Ｋｅｙｗｏｒｄｓ：Ｉｄｅｎｔｉｃａｌｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇ

Ｌｏｗｅｒｂｏｕｎｄ

Ｓｅｑｕｅｎｃｅ－ｄｅｐｅｎｄｅｎｔ

ｓｅｔｕｐｔｉｍｅＭａｔｈｅｍａｔｉｃａｌｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌ

Ｇｅｎｅｔｉｃ

ａｌｇｏｒｉｔｈｍ

以实现优化目标。以最小化被加工工件最大完工时

０前言

调整时间与顺序相关的等同并行机调度是指作为稀缺资源的若干台等同并行机器加工一组给定的不同工件。每一个工件可以在任何一台机器上进行加工，并需要不中断的单一操作；每一台机器在加工不同的工件时需要进行调整：调整时间与工件的加工顺序相关：确定每一台机器所加工的工件序列

间为目标，使用调度问题的三元组符号Ｉｌ】，可以将

这一问题描述为弓Ｉ吩Ｉｆｃ一。己Ｉ％Ｉ七一是组合优

化问题，也是ＮＰ．ｈａｒｄ问题，即使是ｍ＝ｌ的单机情况１２】，一般很难精确地求出其最优解。另一方面，

己Ｉ％ｌｆｃ一在生产服务业与制造业中有着十分广泛的应用背景。因此，研究有效的只１％Ｉｆｃ呲求解

算法具有重要的理论意义和应用价值。

ＭＯＫＯＴＯＦＦｌ３】对以最小化最大完工时间为目标的等同并行机调度的求解算法进行了较为全面的

‘国家科技支撑计划资助项１目（２００６ＢＡＨ０２Ａ１７）．２０１００８２３收到初稿，２０１１０４２０收到修改稿

．

阶段性综述，并在此基础上提出了研究与应用的发

万方数据

ｋＮ∈Ｗ

２０１１年８月胡大勇等：调整时间与顺序相关的等同并行机调度

１６ｌ

展方向。对于调整时间在生产调度中重要性的认识，日益受到关注，ＡＬＬＡＨＶＥＲＤＩ等【４４】以典型生产调度问题为背景，综述了现阶段具有调整时间约束的生产调度问题研究内容、方法与应用现状。现有研究中所使用的求解算法可以分为精确算法和近似算法两类，精确算法一般使用组合优化问题的分枝定界策略以获得问题的最优解，但求解费时并受限于问题的规模：近似算法兼顾求解的速度与质量，在合理的时间内寻找尽可能好的满意解和尽可能大的问题规模【ｏＪ。

作为一种基于智能计算的近似算法，遗传算法不依赖问题表达的梯度信息，直接对结构对象进行操作，具有内在的隐并行性和全局寻优能力，并通过概率化寻优方法，自动获取和优化搜索空间，自适应地调整搜索方向，是一种可以用于复杂系统优化计算的鲁棒搜索算法【７喝Ｊ。

评价近似算法求解质量的方法可以归纳为相对

性评价和确定性评价两类。现有研究中多采用相对性评价，即比较不同近似算法的计算目标值，虽然能区分其间相对优劣，但是不能反映求解精度。确定性评价的一个直观标准是问题的最优解，但是求解大规模ＮＰ．ｈａｒｄ问题的最优解是非常困难的；对于最小化的目标，解决这个难点的一个有效方法是通过所求解问题的下界，用计算目标值同下界的背离程度反映近似算法求解精度。

本文首先建立只Ｉ％Ｉｆｃ呲的数学规划模型，然

后在该数学规划模型基础上，构建已Ｉ％Ｉｆｃ一的下

界。其次，设计染色体编码方式和遗传算子求解

己Ｉ％Ｉｆｃ一。最后，通过具有不同问题规模的算例，验证所提出遗传算法的有效性。

１数学模型

用数学语言描述名Ｉ％ｌｆｃ一，是对其进行定性研究分析的基础。ＬＯＰＥＳ等【９Ｊ建立了以最小化加权滞后和为目标函数的并行机调度模型，描述了工件到达时间、工件交货期、机器调整时间和机器可用时间约束的加工特征。进一步拓展ＬＯＰＥＳ等【９】的建

模研究，可建立只Ｉ％Ｉｆｃ一的数学规划模型。

只Ｉ％Ｉｆｃ一的数学表达式为

ｍｉｎ

ｍＭａｘｔｏ

（１）ｓ．ｔ．∑一三。砖＝１。

’

（２）

ＥＭｌＥ｛ｏ）ＵⅣ

∑碥＝ｌ

Ｖ七ｅ

Ｍ

（３）

ｊＥＮ

万方数据

∑磅＝∑砖Ｗ∈Ｎ

Ｖ尼∈Ｍ（４）

』Ｅ｛０｝ＵＮ

ＩｅＮＵ｛ｎ＋ｌ｝

ｆｃ，＝∑∑（ｂ＋勖＋ｏ煳

Ｗ∈Ｎ

（５）ｋ６Ｍｆ∈｛ｏ｝Ｕ．＾，

ｆｃｏ，ＳＯ，＝０

Ｗ∈Ｎ

（６）

砖＝ｏ，１Ｖｉ∈｛ｏ）ＵⅣｗ∈ＮＵ｛ｎ＋１）Ｖｋ∈Ｍ

Ｎ一－Ｉ－件集合，Ｎ＝｛ｌ，２，…，刀｝

（７）

Ｍ——机器集合，Ｍ＝ｆ１，２，…，ｍ｝

ｔｔ——．工件ｆ的加工时间

ｓ。——先后连续加工工件ｆ与．，，同一机器

的调整时间

０——机器的初始状态聆＋ｌ——机器的终止状态ｔｃ，——工件ｉ的完工时间

孵——如果机器七先后连续加工工件ｉ与，，

孵＝ｌ；否则，霹＝０

目标函数式（１）是最小化被加工工件最大完工时间；约束条件式（２）表示每个工件由一台确定的机器加工一次；约束条件式（３）确定参与加工机器的首个工件；约束条件式（４）表示工件在相应加工序列中存在确定性的先后关系；约束条件式（５）表示在每一台机器所加工的工件序列中，两个连续工件之间的完工时间关系。约束条件式（６）表示每一台机器在其初始状态都可以使用。且加工首个工件不需要进行调整。约束条件式（７）是二维变量约束。

２下界

下界是代替最优解以确定性评价近似算法求解质量的另一直观标准。ＹＡＬＡＯＵＩ等【１０１设计启发式算法用于求解以最小化被加工工件最大完工时间为目标的具有工件可拆分和调整时间与顺序相关加工特征的并行机调度问题，其下界可以直接作为

艺Ｊ％Ｉｆｃ一的下界，证明如下。

定义决策变量‘为机器七的完工时间，显然

工件最大完工时间等于机器最大完工时间

ｍ。。ａⅣｘｔａ

２珊ｋ

（８）

机器的最大完工时间一定不小于所有机器的平

均完工时间

Ｉｐ警厶＞业

∑气

＾Ｅ朋

ｍ

（９）

每一台机器的完工时间取决于其加工序列的加

式中

机械工程学报第４７卷第１６期

工时间和该机器的调整时间。所有机器的完工时间和可以由式（１０）确定

∑“＝∑ｔｉ＋∑∑∑砖×％

（１０）

ｋＥＭ

ｔ∈Ｎ

ｋ∈Ｍｔ∈ＮｊｅＮ

Ⅵ∈Ｎ，令ｓｊ＝ｍ—ｉｎ｜ｓｒ，；按照ｓＪ：１≤Ｓ｛ｚ．１‘≤ｓｊ。

。

Ｊ

ｔ；Ｎ

・

Ｊ‘

Ｊ＾

ｉ｝ｊ

的排序条件，可以得到工件集合的一个全排列

（ｊ『。，五，…，五）。所有机器的调整用时和满足式（１１）

∑∑∑砖ｘ～≥∑黾∑∑磁

（１１）

ｋ∈ＭｉｅＮｊＥＮ

ｔｅＮ

ｋ∈Ｍ

ｉ∈Ｎ

式中，Ｖｔ∈Ｎ，工∈Ⅳ，用表达式∑∑磁来确

定工件上在加工序列中的位置。由约束条件式（６）ｎ－７知，如果工件Ｚ是加工序列中的首个工件，那么机器加工工件Ｚ不需要进行调整：否则，机器加工工件Ｚ需要进行调整。

为进一步证明的需要，引入由ＹＡＬＡＯＵＩ等‘１０】

提出的最小值问题定理，其中国＝｛ｌ，２，…，Ｈ｝，臼是

自然数集合。

ｍｉｎ∑Ｌｈ×％０２）

ｈ∈毋

ｓ．ｔ．０≤厶≤厶≤…≤厶

（１３）％＋最≥ｌ

Ｖｈ∈函

（１４）∑最≤Ｒ

（１５）＾Ｅ中

Ｒ≤Ｈ

（１６）

ｕ＾．只Ｒ∈ｐ

Ｖｈ∈口

（１７）

目标函数式（１２）的最小值是∑厶。

ｈ＝ｌ

Ｖｔ∈Ｎ，令巧＝∑∑磁，Ｑ＝∑砖ｖＪｊｒ。如‘‘√‘＿一Ｖｆ

ｋＥＭｌ∈＾，

一‘』＿一

七ＥＭ

果工件ＪＩ是加工序列中的首个工件，Ｋ＝０，Ｑ，＝ｌ；否则，Ｋ＝Ｉ，Ｑ＝０。

Ｋ＋Ｑ＝ｌ

Ｖｔ∈Ｎ

（１８）

由约束条件式（３）可知，加工序列的数目应该等于参与加工机器的数目。

∑Ｑ＝ｍ

（１９）

ｆＥ．ｖ

按照以上最小值问题定理，式（２０）成立。

∑毛∑∑砖≥Ｅ毛

（２０）

ｔＥＮ

ｋ∈ＭｌＥＮ

ｔ＝ｌ

那么工件的最大完工时间，满足式（２１）

万方数据

搿乞＝黔９如‘＋薯已］Ⅲ，

根据以上讨论，下界的构造如式（２２）所示

岛＝去（驴喜屯］

∞，

３遗传算法

３．１两段式染色体表达

为了减少搜索空间中的冗余解，提高遗传算法搜索效率，可行解的染色体表达采用两段式编码方式【ｌ¨。第一段编码的长度为ｎ，等于被加工工件的数目，是工件集合的一个全排列，构成了各台机器的加工序列；第二段编码的长度为ｍ，等于机器的数目，各基因值代表相应机器所加工的工件数。两段编码分别表达了工件问加工顺序信息和工件与机器间分派信息。两段式染色体表达的示例如图ｌ所示，１２个工件由３台机器加工，工件６、１、５由机器ｌ依序加工：工件９、４、７、３由机器２依序加工；同样，工件１０、２、１２、８、１１由机器３依序加工。

图１两段式染色体表达示例图

适应度用来评价个体的优劣程度。按照生物进化思想，适应度较高的个体遗传到下一代的概率就较大：适应度较低的个体遗传到下一代的概率就小一些。适应度函数用来度量遗传算法中染色体的适应度，设置为目标函数值的倒数（ｍａｘ乞）－１（ｆ∈Ｎ），引导遗传算法的寻优方向。

选择操作按照染色体的适应度函数值复制出较适应环境的染色体。采用轮盘赌模型实现选择操作，在这种选择机制下，将使适应度函数值高的染色体复制到下一代的数目较多，而适应度函数值较小的染色体，复制到下一代的数目较少。

为了保证子染色体的合法性，只在两个父染色体的第一段基因组间进行交叉操作，交叉方式采用

染色体ｌ第一段基因组中基因片段，保存父染色体３．２适应度函数和选择

３３交叉

顺序交叉。两个父染色体顺序交叉时，通过选择父２第一段基因组中基因值的相对顺序生成子染色体

２０１１年８月胡大勇等：调整时间与顺序相关的等同并行机调度

１６３

１；通过选择父染色体２第一段基因组中基因片段，保存父染色体１第一段基因组中基因值的相对顺序生成子染色体２。顺序交叉过程的示例如图２所示。

图２顺序交叉不例图

３．４变异

首先在染色体的第一段和第二段分别进行交换变异。交换变异通过相互交换各段编码串中两个随机选取的基因之间的基因值来实现。两段式染色体

交换变异过程的示例如图３所示。

为了保持种群多样性，继续对染色体的第二段

进行基本组变异，通过重新随机生成第二段中各基

因的基因值来实现。染色体第二段基因组变异过程的示例如图４所示。染色体第二段基因组变异前，

机器ｌ依序加工工件６、５、１０，机器２依序加工工

件２、１２、ｌ、９、４、３，机器３依序加工工件７、８、

ｌｌ；染色体第二段基因组变异后，机器ｌ依序加工

工件６、５、１０、２，机器２依序加工工件１２、ｌ、９；

机器３依序加工工件４、３、７、８、ｌｌ。

与丽耐滚祈爿打１丽硫裔

图４

染色体第二段基冈组变异示例图

万方数据

３．５精英策略

精英个体是种群进化到当前为止遗传算法搜索到的适应度值最高的个体。精英策略是把精英个体直接复制到下一代中，并淘汰下一代中适应度值最小的个体。精英策略不仅可以改善遗传算法的收敛性，同时也可以避免迄今为止的最优个体不会被选择、交叉和变异操作所破坏和丢失。

４计算试验

为了验证所提出的遗传算法的有效性，用Ｃ语

言对所提出的遗传算法进行编程，在Ｐｅｎｔｉｕｍ（Ｒ）４ＣＰＵ２．６６ＧＨｚ、５１２ＭＢ内存的计算机上实现计算

试验。计算试验流程的伪代码描述如下。

ＢＥＧｒＮ

输入加工参数和遗传算法参数；进化代数计数变量ｇ初始化为Ｏ；随机生成初始种群Ｐ（０）；

ＷＨＩＬＥ（ｇ＜最大进化代数）ＤＯ

ｇ＝ｇ＋ｌ：

选择Ｐ（ｇ一１）中个体构成Ｐ（ｇ）：顺序交叉算子应用于Ｈｇ）；交换变异算子应用于Ｐ（ｇ）；Ｐ（ｇ）中个体第二段基因组变异；

精英个体替换尸（ｇ）中适应度值最小个体：

ＥＮＤＤＯ

输出最优个体目标函数值和运行时间：

‘

ＥＮＤ

加工参数设置：机器数目ｍ∈ｆ３，４，５ｌ，工件数目刀∈｛２０，３０，４０，５０，６０，７０，８０，９０｝；根据某港口技术

装备的实际生产数据，工件加工时间为【６０，１５０】区

间均匀分布的随机数，机器调整时间为［１０，１５】区间

均匀分布的随机数。

遗传算法参数设置：种群规模脚×１００，交叉概

率０．６５，交换变异概率Ｏ．３５，染色体第二段基测组变异概率０．１５，最大进化代数ｍ×３００。

机器数目与工件数目的不同组合构成不同的问

题规模；为消除随机因素对计算结果的影响，每种

问题规模下产生５０个计算实例，并报告甲均计算结

果，如下表所示，其中以背离程度来表达遗传算法计算目标值同最优解的差异，背离程度定义为（遗传算法计算目标值一下界）Ｘ１００／下界。

１６４

机械工程学报

表数值计算结果

试验编号

机器数目耐台

工件数目ｎ／ｄ＂

第４７卷第１６期

问题规模。×。————————』墅壁塑Ｌ————一

平均运行时间‘／ｓ

平均背离程度ＧＩ／％

１７１８１９２０２１２２２３２４

５５５５５５５５

２０３０４０５０６０７０８０９０

５Ｘ２０５×３０５×４０５Ｘ５０５Ｘ６０５×７０５Ｘ８０５×９０

２．８７５３．８８５５．４４７６．７８３８．４６５１０．３８７１２．４６８１４．９４８

１．６５Ｉ．７９１．９ｌ１．９８２．０２２．０７２．１２２．１８

从表中可以看出，所有计算试验中遗传算法的平均运行时间都小于１５ｓ；且遗传算法计算目标值・５同下界的最大和最小平均背离程度分别为２．１８％和１．１７％。随着问题规模的增长，遗传算法平均运行时间、计算目标值同下界平均背离程度的变化趋势分别如图５和图６所示，其中算法运行时间基本呈现线性增长的趋势，而背离程度的增长趋势趋于平缓。

芝

结论

（１）以最小化被加工工件最大完工时间为目

标，对调整时间与顺序相关的等同并行机调度中的工件分配与排序进行决策，提出了该问题的数学规划模型，并解析证明了该问题的一个下界。

（２）针对可行调度方案具有排列属性的结构特

。

点，开发了基于两段式染色体表达的遗传算法，减

少了搜索空间冗余解的产生与相应的冗余搜索，提高了算法的搜索效率。

（３）对ｌ２００个基于生产实际的随机问题实例

星譬七

嫂

露

饼－

进行试验分析，通过与引入的下界进行比较，表明了设计的遗传算法具有较好的求解性能，能够在较

短的时间内获得满意解。

逞Ｓ趟跫霹藿

霹

参考文献

【１】ＧＲＡＨＡＭ

工件数目，ｌ，个

ｓｅｑｕｅｎｃｉｎｇ

Ｒ

Ｌ，ＬＡＷＬＥＲ

ａｎｄ

ＥＬ，ＬＥＮＳＴＲＡＪ

ｉｎ

Ｋ

ｅｔ

ａ１．

斗

Ｏｐｔｉｍｉｚａｔｉｏｎａｐｐｒｏｘｉｍａｔｉｏｎ

ｄｅｔｅｒｍｉｎｉｓｔｉｃ

ｏｆ

ａｎｄ

ｓｃｈｅｄｕｌｉｎｇ：Ａ

ｓｕｒｖｅｙ［Ｊ］．Ａｎｎａｌｓ

图６计算目标值同下乔背离程度变化曲线

ＤｉｓｃｒｅｔｅＭａｔｈｅｍａｔｉｃ，ｓ，１９７９，５１

２８７・３２６．

万方数据

２０１１年８月胡大勇等：调整时间与顺序相关的等同并行机调度

１６５

【２】ＰＩＮＥＤＯ

Ｍ．Ｓｃｈｅｄｕｌｉｎｇ：Ｔｈｅｏｒｙ，ａｌｇｏｒｉｔｈｍｓ，ａｎｄ

ｓｙｓｔｃｍｓ【Ｍ】．Ｎｅｗ

Ｊｅｒｓｅｙ：Ｐｒｅｎｔｉｃｅ・Ｈａｌｌ，ＥｎｇｌｅｗｏｏｄＣｌｉｆｆｓ，

１９９５．

［３】ＭＯＫＯＴＯＦＦ

Ｅ．Ｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ：Ａ

ｓｕｒｖｅｙ［Ｊ］．Ａｓｉａ－Ｐａｃｉｆｉｃ

ＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，

２００１，１８（２）：１９３－２４２．

［４】ＡＬＬＡＨＶＥＲＤＩ

Ａ，ＧＵＰＴＡＪＮＤ，ＡＬＤ０ｗＡＩＳＡＮＴ．Ａ

ｒｅｖｉｅｗ

ｏｆ

ｓｃｈｅｄｕｌｉｎｇ

ｒｅｓｅａｒｃｈ

ｉｎｖｏｌｖｉｎｇ

ｓｅｔｕｐ

ｃｏｎｓｉｄｅｒａｔｉｏｎｓ［Ｊ］．Ｏｍｅｇａ，１９９９，２７（２）：２１９－２３９．【５】ＡＬＬＡＨＶＥＲＤＩ

Ａ，ＮＧＣ

Ｔ，ＣＨＥＮＧ

ＴＣＥ，ｅｔａ１．Ａｓｕｒｖｅｙ

ｏｆ

ｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ

ｗｉｔｈ

ｓｅｔｕｐ

ｔｉｍｅｓ

ｏｒ

ｃｏｓｔｓ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，２００８。

１８７（３）：９８５－１０３２．

［６】何霆，刘飞，马玉林，等．车间生产调度问题研究叨．机

械工程学报，２０００，３６（５）：９％１０２．

ＨＥＴｉｎｇ，ＬＩＵＦｅｉ，ＩｄＡＹｕｌｉｎ，ｅｔａ１．Ｓｔｕｄｙ

ｏｎ

ｓｈｏｐ－ｆｌｏｏｒ

ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．

ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＭｅｃｈａｎｉｃａｌ

Ｅｎｇｉｎｅｅｒｉｎｇ，２０００，３６（５）：９７—１０２．

【７】周明，孙树栋．遗传算法原理及应用［Ｍ】．北京：国防工

业出版社，１９９９．

ＺＨＯＵＭｉｎｇ，ＳＵＮＳｈｕｄｏｎｇ．Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ：Ｔｈｅｏｒｙ

万方数据

ａｎｄａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｎａｔｉｏｎａｌ

ＤｅｆｅｎｓｅＩｎｄｕｓｔｒｙ

Ｐｒｅｓｓ，１９９９．

［８］

ＧＯＬＤＢＥＲＧＤ

Ｅ．Ｇｅｎｅｔｉｃ

Ｍｇｏｆｉｔｈｍｓ

ｉｎ

ｓｅａｒｃｈ，ｏｐｔｉｍｉｚａｔｉｏｎ

ａｎｄｍａｃｈｉｎｅｌｅａｒｎｉｎｇ［Ｍ］．Ｎｅｗ

Ｊｅｒｓｅｙ：

Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ，１９８９．

［９】

ＬＯＰＥＳ

Ｍ

ＪＰ．ＣＡＲＶＡＬＨＯＪＭＶＤ．Ａｂｒａｎｃｈ．ａｎｄ．ｐｒｉｃｅａｌｇｏｒｉｔｈｍ

ｆｏｒｓｃｈｅｄｕｌｉｎｇｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｗｉｔｈｓｅｑｕｅｎｃｅｄｅｐｅｎｄｅｎｔ

ｓｅｔｕｐ

ｔｉｍｅｓ［Ｊ］．

Ｅｕｒｏｐｅａｎ

Ｊｏｕｒｎａｌ

ｏｆ

Ｏｐｅｒａｔｉｏｎａｌ

Ｒｅｓｅａｒｃｈ，２００７，１７６（３）：１５０８－１５２７．

【１０】

ＹＡＬＡＯＵＩＦ＇ＣＨＵＣ．Ａｎｅｆｆｉｃｉｅｎｔｈｅｕｒｉｓｔｉｃａｐｐｒｏａｃｈｆｏｒ

ｐａｒａｌｌｅｌ

ｍａｃｈｉｎｅ

ｓｃｈｅｄｕｌｉｎｇｗｉｔｈ

ｊｏｂ

ｓｐｌｉＲｉｎｇ

ａｎｄ

ｓｅｑｕｅｎｃｅ－ｄｅｐｅｎｄｅｎｔ

ｓｅｔｕｐ

ｔｉｍｅｓ［Ｊ］．１ｉＥ

Ｔｒａｎｓａｃｔｉｏｎｓ，

２００３，３５（２）：１８３－１９０．

ＣＡＲＴＥＲＡＥ，ＲＡＧＳＤＡＬＥＣＴ．Ａｎｅｗａｐｐｒｏａｃｈ

ｔｏ

ｓｏｌｖｉｎｇｔｈｅｍｕｌｔｉｐｌｅｔｒａｖｅｌｉｎｇｓａｌｅｓｐｅｒｓｏｎｐｒｏｂｌｅｍｕｓｉｎｇ

ｇｅｎｅｔｉｃ

ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌ

Ｒｅｓｅａｒｃｈ，２００６，１７５（１）：２４６－２５７．

作者简介：胡大勇，男，１９７５年出生，博士研究生。主要研究方向为制

造系统调度规划与管理・

Ｅ‘ｍａｉｌ：ｄｙｈ恤ｉｌ＠１６３．ｔｏｍ：ｄｙｈｕ＠ｓｊｍ．ｅｄｕ．皿

调整时间与顺序相关的等同并行机调度

作者：作者单位：刊名：英文刊名：年，卷(期)：

胡大勇， 姚振强， HU Dayong， YAO Zhenqiang

上海交通大学机械系统与振动国家重点实验室 上海 200240机械工程学报

JOURNAL OF MECHANICAL ENGINEERING2011,47(16)

1. GRAHAM R L;LAWLER E L;LENSTRA J K Optimizationandapproximationindeterministic sequencing and scheduling:A survey 19792. PINEDO M Scheduling:Theory,algorithms,and systems 1995

3. MOKOTOFF E Parallel machine scheduling problems:A survey 2001(02)

4. ALLAHVERDI A;GUPTA J N D;ALDOWAISAN T A reviewofschedulingresearchinvolvingsetup considerations[外文期刊] 1999(02)5. ALLAHVERDI A;NG C T;CHENG T C E A survey of scheduling problems with setup times or costs[外文期刊] 2008(03)6. 何霆;刘飞;马玉林 车间生产调度问题研究[期刊论文]-机械工程学报 2000(05)7. 周明;孙树栋 遗传算法原理及应用 1999

8. GOLDBERG DE Genetic algorithms insearch,optimization and machine learning 1989

9. LOPES M J P;CARVALHO J M V D A branch-and-price algorithm for scheduling parallel machines with sequencedependentsetuptimes 2007(03)

10. YALAOUI F;CHU C An efficient heuristic approach for parallelmachine scheduling with job splitting and sequence-dependentsetup times[外文期刊] 2003(02)

11. CARTER A E;RAGSDALE C T A new approach to solving the multiple traveling salesperson problem using genetic algorithms[外文期刊] 2006(01)

1. 闫萍. 唐立新 基于时间槽的并行机调度连续时间建模方法[会议论文]-20082. 刘志雄. 杨光祥 基于轮盘赌概率分配编码方法的并行机调度优化[会议论文]-2010

本文链接：http://d.g.wanfangdata.com.cn/Periodical_jxgcxb201116026.aspx