第３８卷第６期 ２００８年１１月 东南大学学报（自然科学版） ＪＯＵＲＮＡＬ ＯＦ ＳＯＵＴＨＥＡＳＴ ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏ１．３８ ＮＯ．６ ＮＯＶ．２００８ 最小化总完工时间的流水作业调度混合算法 齐学梅 ’ 李小平 王 茜 （’东南大学计算机科学与工程学院，南京２１００９６） （ 安徽师范大学数学计算机科学学院，芜湖２４１００３） （ 东南大学计算机网络和信息集成教育部重点实验室，南京２１００９６） 摘要：针对有效求解ＮＰ难的总完工时间最小流水作业调度问题，提出了一个有效的混合启发式 算法产生初始解，并使用禁忌搜索算法对初始解邻域进行搜索的算法框架．基于不同的启发式 算法，获得了３个混合禁忌搜索算法ＨＡ１，ＨＡ２和ＨＡ３．使用Ｔａｉｌｌａｒｄ’Ｓ基准程序随机产生的大 量实例，进行模拟实验，结果表明，所提出的３个算法通过扩大搜索范围提高了解的质量，在性能 上均优于目前最有效的启发式算法．与目前最有效的算法相比，产生最好解的平均百分比偏差 均下降至少３０％，最优解所占比例皆有显著提高． 关键词：流水作业调度；启发式算法；禁忌搜索；总完工时间 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ 文章编号：１００１—０５０５（２００８）０６－０９６０－０５ Ｈｙｂｒｉｄ ｔａｂｕ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗ ｓｈｏｐｓ ｔｏ ｍｉｎｉｍｉｚｅ ｔｏｔａｌ ｆｌｏｗｔｉｍｅ Ｑｉ Ｘｕｅｍｅｉ ’。Ｌｉ Ｘｉａｏｐｉｎｇ ＇ Ｗａｎｇ Ｑｉａｎ ＇ （‘Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００９６，Ｃｈｉｎａ） （ Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ａｎｈｕｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈｕ ２４１００３，Ｃｈｉｎａ） （ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｉｎｔｅｇｒａｔｉｏｎ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ，Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００９６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｗｅｌｌ ｋｎｏｗｎ ＮＰ—ｈａｒｄ ｐｅｒｍｕｔａｕｏｎ ｆｌｏｗ ｓｈｏｐｓ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｏｔａｌ ｆｌｏｗｔｉｍｅ ｍｉｎｉｍｉｚａ— ｔｉｏｎ ｉｓ ｃｏｎｓｉｄｅｒｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ａｎ ａｌｇｏｒｉｔｈｍ ｆｒａｍｅｗｏｒｋ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｗｈｉｃｈ ａｎ ｉｎｉｔｉａｌ ｓｏｌｕｔｉｏｎ ｉｓ ｇｅｎｅｒａｔｅｄ ｂｙ ａｎ ｅｆｉｃｉｅｎｔ ｈｙｂｒｉｆｄ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｍｐｒｏｖｅｄ ｂｙ ａ ｔａｂｕ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ．Ｂａｓｅｄ ｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｈｅｕｒｉｓｔｉｃｓ，ｔｈｒｅｅ ｈｙｂｒｉｄ ｔａｂｕ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ＨＡ１，ＨＡ２，ａｎｄ ＨＡ３ ｒｅ ｐｒｏｐｏｓｅｄ．Ｔａｉｌｌａｒｄ’Ｓ ｂｅｎｃｈｍａｒｋ ｐｒｏｇｒａｍ ｉｓ ｕｓｅｄ ｔｏ ｇｅｎｅｒａｔｅ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ａｒａｎｄｏｍ ｉｎｓｔａｎｃｅｓ． Ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｓｏｌｕｔｉｏｎｓ ｉｓ ｉｍｐｒｏｖｅｄ ｕｓｉｎｇ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ ｆｌ ｂｉｇｇｅｒ ｓｅａｒｃｈｉｎｇ ｓｃｏｐｅ．Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｒｅｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄｓ ａｒｅ ａｌｌ ｓｕｐｅｒｉｏｒ ｔｏ ｔｈｅ ｍｏｓｔ ｅｆｉｃｉｆｅｎｔ ｈｅｕｒｉｓｔｉｃｓ ｃｕｒｒｅｎｔｌｙ ｕｓｅｄ．Ｃｏｍｐａｒｉｎｇ ｗｉｔｈ ｔｈｅ ｒｅｓｕｌｔ ｒｏｍ ｔｆｈｅ ｂｅｓｔ ｅｘｉｓｔｉｎｇ ｈｅｕｒｉｓｔｉｃｓ，ｔｈｅ ａｖｅｒａｇｅ ｒｅｌ— ａｔｉｖｅ ｐｅｒｃｅｎｔａｇｅ ｄｅｖｉａｔｉｏｎ ｆｒｏｍ ｔｈｅ ｂｅｓｔ—ｋｎｏｗｎ ｓｏｌｕｔｉｏｎ ｉｓ ｒｅｄｕｃｅｄ ａｂｏｕｔ ３０％ａｎｄ ｔｈｅ ｐｅｒｃｅｎｔ ｏｆ ｏｐ— ｔｉｍａｌ ｓｏｌｕｔｉｏｎｓ ｉｎｃｒｅａｓｅｓ ｏｂｖｉｏｕｓｌｙ． Ｋｅｙ ｗｏｒｄｓ：ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗ ｓｈｏｐｓ；ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ；ｔａｂｕ ｓｅａｒｃｈ；ｔｏｔａｌ ｆｌｏｗｔｉｍｅ 流水作业调度广泛存在于工业环境中，该问题 可描述为：ｎ个任务在ｍ台机器上执行，且每个任 务的加工顺序相同，任务ｉ在机器 上的加工时间 应的流水作业调度问题分别记为Ｆ Ｊ ｐｒｍｕ ｌｃ 和 Ｆ Ｊｐｒｍｕ ｆ∑ （ｐｍｕ表示所有作业的每一工序的 ｒ加工顺序都相同），两者都是ＮＰ难问题…．启发式 是给定的，调度的目标是求解ｒ／个任务的最优加工 顺序，使总完工时间最小．Ｍａｋｅｓｐａｎ和Ｔｏｔａｌ 和元启发式算法是用来求解ＮＰ难问题较常用的 方法．迄今为止，已经提出了许多解决流水作业调 Ｆｌｏｗｔｉｍｅ是流水作业调度的２个重要性能指标，相 收稿日期：２００８－０６－１７． 作者简介：齐学梅（１９６３～），女，副教授，ｑｘｍｈｊ＠ｍａｉｌ．ａｈｎｕ．ｅｄｕ．ｃｎ． 基金项目：国家自然科学基金资助项目（６０６７２０９２，６０５０４０２９）、国家高技术研究发展计划（８６３计划）资助项目（２００８ＡＡ０４Ｚ１０３）． 引文格式：齐学梅，李小平，王茜．最小化总完工时间的流水作业调度混合算法［Ｊ］东南大学学报：自然科学版，２００８，３８（６）：９６０—９６４ 第６期 齐学梅，等：最小化总完工时间的流水作业调度混合算法 ９６１ 度问题的启发式算法，ＮＥＨ是目前解决Ｆ ｌｐｒｍｕ Ｉ Ｃ 的最好启发式算法 Ｊ，但对 ２混合算法 混合算法主要思想是：提出一个有效的混合启 发式算法产生初始解，使用禁忌搜索算法对初始解 邻域进行搜索，有意识地避开已找到的局部最优 Ｆ Ｉ ｐｒｍｕ ｌ∑ｃｆ问题ＮＥＨ不十分有效 ］．构造启 发式算法ＦＬｌ ，ｗＹ［ 和ＲＺ［ 是求解 ＦＩｐｒｍｕ Ｊ ｃ，的有效算法，实验证明ＦＬ是最好 的构造启发式方法，ＦＬ优于ｗＹ和ＲＺ；目前，比 构造式算法更有效的是复合启发式算法，如ＩＨ１～ ＩＨ７ ，ＩＨ７一ＦＬ ，ＦＬＲ１和ＦＬｌ 等，其中后３ 个算法是最有效的算法．传统的搜索方法易陷入 局部最优解，元启发式算法通常以一定的时间开销 克服该缺陷以得到较好解，禁忌搜索算法就是其中 一种具有很强搜索能力的全局逐步优化算法ｌ９ Ｊ． 禁忌搜索通过记忆近期操作，尽量避免相同问题的 重复计算，实现全局快速搜索．但不足的是，它对 初始解有较强的依赖性，单独使用通常难以达到令 人满意的结果． 结合启发式算法的快速性和禁忌搜索算法的有 效性，本文改进ＦＬＲ２算法，结合禁忌搜索算法，提 出３种混合算法，有效地解决Ｆ ｌｐｒｍｕ ｌ∑ｃ，问题． １ 问题描述 流水作业调度问题描述为ｎ个任务要在ｍ台 机器上加工，每个任务需通过ｍ道工序，每道工序 要求在不同机器上加工， 个任务在ｍ台机器上加 工顺序相同，且满足如下的约束条件： １）每个任务在机器上加工顺序相同，且给定． ２）每台机器同时只能加工一个任务． ３）一个任务不能同时在不同的机器上加工． ４）工序的准备时间与顺序无关，且包含在加 工时间内． ５）允许任务在工序之间等待，允许机器在任 务未到达时闲置． 最小化总完工时间的流水调度问题 （Ｆ１ｐｒｍｕ Ｉ∑ｃＪ）的优化目标是要找出这 个任务 的一个加工顺序，使其总完工时间最小．下面给出 计算总完工时间的计算方法： Ｃｆ０＝０，ＣｏＪ＝０ ，Ｃｆ，』＝ｍａｘｔ ＣｆＪ－ｌ，Ｃ ， ｝＋ｔｆ， ｉ＝１，２，…，ｎ； ＝１，２，…，ｍ ＝∑Ｃ ｉ＝１ 式中，ｔ √为第ｆ个任务在第 台机器上的加工时问； Ｃ 为任务ｆ在机器 上的完工时间； 为总完工 时间，即所有任务完工时间之和． 解．不同的初始解产生策略对算法的性能产生不同 的影响，本文采用３种不同初始解产生策略生成初 始解，相应地提出３个混合算法ＨＡ１，ＨＡ２和 ＨＡ３． 本文提出的初始解生成算法步骤如下： ①调用ＬＲ（ ）算法¨。。产生一个初始序列ｓ． ②利用ＦＬ插入方法对初始序列 进行构造， 最后形成序列Ｒ． ③利用ＲＺ插入方法对序列Ｒ进行改善，得到 当前较优的序列Ｑ． 序列Ｑ作为初始解序列．ＬＲ（ ）算法取不同 参数时，其计算性能不同，ＨＡ１，ＨＡ２，ＨＡ３初始解 算法中的Ｘ参数分别为Ｘ＝Ｉ，ｎ／ｍ和ｎ． 由于禁忌搜索算法是局部邻域搜索算法的推 广，参数设置很重要，通过大量仿真实验，选择参数 如下：①邻域结构．采用ＦＰＥ 操作产生邻域．② 候选解选择．采用动态方式，设Ｃ为候选解的数量． 当０＜ｎ≤５０时，Ｃ＝ｎ；当５０＜ｎ≤１００时，Ｃ＝ １０ｎ．③禁忌表长度．设Ｌ为禁忌长度，采用动态获 取方式，Ｌ＝ ，ｚ／３，若Ｌ＜３，则Ｌ＝３．④采用特 赦准则．若某个状态的性能优于当前最好的状态， 则无视禁忌属性，直接选取它作为当前状态．⑤ 终止条件．采用某个对象的禁忌次数，一旦某个对 象的禁忌次数大于给定禁忌次数的最大值，那么算 法停止．设最大禁忌次数为ｍ，即禁忌搜索迭代到 的最大步数为ｍ． 在进行禁忌搜索之前，先定义禁忌表Ｉ，（），初 始为空，表上半三角存储禁忌对象（ ，Ｙ）的禁忌长 度，用Ｊ（ ，Ｙ）的值表示，在下半三角（Ｙ， ）位置 上存储禁忌对象的禁忌次数，即禁忌对象每禁忌一 次禁忌次数加１，用Ｊ（ｙ，Ｘ）的值表示，当禁忌次数 达到ｍ时，算法结束．算法在求解过程中解的质量 具有不确定性，因此设一个表 。 来存储执行算 法过程中取得的最优解即当前最好解． 基于以上分析，所提出的３个混合算法步骤： ①调用初始解生成算法产生初始解 ． ②将 作为当前解，利用ＦＰＥ方法产生 的 邻域． ③将所有邻域解按式（１）计算出对应的目标 函数值，并将其从小到大排序，然后选取前ｃ个邻 域解作为候选解． ９６２ 东南大学学报（自然科学版） 第３８卷 一帆 ④从第１个解开始，若满足特赦准则，则将其 帆 列 与序列Ｂ。所对应的目标函数值，选取目标函 作为当前序列Ｔ．，否则在候选解中选非禁忌的最 佳状态序列作为当前序列 ． 如 昌昌罟８ ●２ ３ ４ ５ ６ ７ ８ ９ ｍ¨数值小的序列作为算法得到的近优解，算法停止； 若不满足终止条件，则７＂０＝ ，转向②． 为说明提出的混合算法的计算过程，给出一个 掩 １２个任务、８个机器的实例（ｎ＝１２，ｍ＝８）在ＨＡ２ ⑤保存当前序列 及其目标函数，并找出其 中最优的目标函数值及对应的序列Ｂ ∞ ⑥若满足终止条件，比较最后得到的当前序 加 加 Ｊ４ Ｊｓ ６ 算法上的执行过程，其加工时间矩阵见表１． Ｓ ｊ９ Ｊ ｎ ｊｕ ｊＩ２ ３， Ｊｓ 表１ 不同任务在不同机器上的加工时间 勰 Ｏ ０ ０ Ｏ Ｏ ０ Ｏ Ｏ ２ ２ ０Ｏ ０ Ｏ Ｏ ０ ０ Ｏ Ｏ Ｏ Ｏ ０％８ 加％ 矾 注：Ｊ 为第ｉ个任务；Ｍ 为第ｉ台机器． 盯 ：２ Ｋ—Ｏ Ｏ ０ ０ Ｏ Ｏ ０ ２ ３ ０●钉 鳃帅 选择候选解集的个数Ｃ＝１２，最大禁忌次数 序列为（Ｊ，，Ｊ ，Ｊ ，Ｊ Ｊ ，Ｊ ，Ｊ ，Ｊ 。， ，Ｊ ，Ｊ ）， ｍ＝８，禁忌长度Ｌ＝３，ＨＡ２的计算过程如下： 首先调用ＬＲ（ｎ／ｍ）产生初始序列为（ＪｌＪ ， 鲫盯ｍ ２，， ， ，目标函数值为９ ００１，调用ＲＺ插入方法改进，得到 目标函数值为８ ９６１．将其作为初始解 ，然后进 ¨一０ Ｏ ０ Ｏ Ｏ Ｏ Ｏ Ｏ ０ ０ Ｏ序列为（Ｊ，，Ｊ。 ，Ｊ４，Ｊ２，Ｊ。，Ｊ ， ，Ｊ ，Ｊ Ｊ６， ）， 一０ ０ Ｏ ０ Ｏ Ｏ ０ Ｏ ０ Ｏ％ 行禁忌搜索．算法执行到ｌ９步时的情况见表２． ８ ９ ６ ９ｍ ¨¨ 厶， ， ，￣， ， ，Ｊ６），目标函数值即 鼹“ 拍 总完工时间为９ １９９．利用ＦＬ插入方法构造，得到 行号 禁忌表 表２ １次搜索的禁忌表与候选解集 ｍ ５ ｍ ５ ９ ８ Ｊ ｍ候选解集 骺 舛 互换对 目标值 ８ ８ ８ ８ ８ ９ ９ ９ ９ ９ ９３ ４ ３ ４ ６ ５ ８ ５ ８ ５ ３卯 叭叭 ∞晒嘶∞ 铝＂ ” 据一 ∞ ＂ ∞此时 表中存储的最优目标值为８ ９５４，在 的近优解，算法结束．本实例的近优解为（ ， ， ， ， ， ，候选解集中最优解为８ ９２３，此时不论禁忌表中（５， １０）禁忌长度为多少，最佳互换对为（５，１０），因为 目标值８ ９２３优于８ ９５４，选择它为下一个状态，互 换（５，ｌ０）后，得到当前解为（ ．，， ， ， ， ，Ｉ， Ｉ，。， ， ， ，， 。， ），目标值为８ ９１６． ３ 实验结果 将ＨＡ１，ＨＡ２和ＨＡ３算法与ＩＨ７．ＦＬ，ＦＬＲ１ 和ＦＬＲ２算法的性能基于同一测试实例组进行比 较，所有算法均用ＶＢ６．０进行实现，并在Ｐｅｎｔｉｕｍ Ｉ，，， ， ， ， ， ）．继续执行，第４３步时，当前解 为（Ｊｌ２， ， ，Ｊ２，Ｊ４，Ｊ１１，Ｊｌ，Ｊ６，Ｊｌｏ， ， ，Ｊ９），目标 值为８ ９７３．在候选解集非禁忌的最佳候选对为 （１２，３），互换（１２，３）后，得当前解为（，３， ， ， ， ， ，２．４ ＧＨｚ×２，２ ＧＢ内存的机器上执行．实验平台 的任务数为ｌ０，２０，…，１００；机器数为５，ｌ０，ｌ５， ２０．每一个任务数与机器数的组合均随机产生１００ ‘， ， ，Ｉ，。。， ， ， ），并将（３，１２）加入 禁忌表，此时互换对（１２，３）禁忌次数已达８次，满 个实例，总共有４ ０００个实例．每个任务在各台机 器上的加工时问使用著名的Ｔａｉｌｌａｒｄ’Ｓ基准程 序… 随机产生并均匀分布在１～９９之间． 足终止条件，退出循环．将 表中存储的最优值 与当前解比较，取较小目标值对应的解作为得到 第６期 齐学梅，等：最小化总完工时间的流水作业调度混合算法 ９６３ 从相对于最好解的平均百分比偏差（ａｖｅｒａｇｅ ｒｅｌａｔｉｖｅ ｐｅｒｃｅｎｔａｇｅ ｄｅｖｉａｔｉｏｎ，ＡＲＰＤ）和给定问题获 ＯＰＴ：墼 ×１００％ 得最好解次数的百分比（ｔｈｅ ｐｅｒｃｅｎｔ ｏｆ ｏｐｔｉｍａｌ ＳＯ— 其中，Ｎ＝１００，为任务数和机器数的组合所运行的 ｌｕｔｉｏｎｓ，ＯＰＴ）比较和分析了６个算法．ＡＲＰＤ表明 实例个数；Ｆ （Ｈ）表示算法ＨＡ１～ＨＡ３在第ｉ个实 算法所得调度的平均质量，最好解Ｇ是６个算法 例中所得调度的总完工时间；Ｇ 表示第ｉ个实例在 所求得调度中总完工时间 最小的调度．算法 ６个算法中所得调度总完工时间的最小值；Ｂ（ ） ＡＲＰＤｌ】 和ＯＰＴ的定义如下： 表示算法ＨＡ１～ＨＡ３在ＪＶ个实例中得到最好解的 ∑Ｎ ｆ 一 ） 个数． ＡＲＰＤ： ＝—————— ——一０— ×１×００％ ％ 表３为６个算法在测试实例上的计算结果． 表３ ６个算法性能比较 ％ ９６４ 东南大学学报（自然科学版） 解的比例趋于稳定． 第３８卷 从表３可以看出：①在ＡＲＰＤ方面，除６０×５ 踟组实例ＦＬＲ２（ＡＲＰＤ为０．４０１％）比ＨＡ２（ＡＲＰＤ 为０．４６６％）和ＨＡ３（ＡＲＰＤ为０．４２３％）略好外， 对其他所有实例组，所提出的３个算法都优于 ＩＨ７．ＦＬ，ＦＬＲ１和ＦＬＲ２；平均而言，ＩＨ７一ＦＬ，ＦＬＲ１ 和ＦＬＲ２的ＡＲＰＤ分别为０．７９１％，１．１９１ ４％和 ０．６２２％，而ＨＡ１，ＨＡ２和ＨＡ３的ＡＲＰＤ分别为 ０．３８％，０．４３％和０．４６１ ８％，故所提出的３个算法 在平均性能上比其他３个算法有较大的改进，其中 ＨＡ１是平均性能最好的算法．②在ＯＰＴ方面，对 于所有测试实例组，所提出的ＨＡ１，ＨＡ２和ＨＡ３ 都能比ＩＨ７一ＦＬ，ＦＬＲ１和ＦＬＲ２找到更多的最优 解；平均而言，ＨＡ１，ＨＡ２和ＨＡ３的ＯＰＴ分别为 ４ｌ％（实例４ ０００个），３５％和３３％，而ＩＨ７一ＦＬ， ＦＬＲＩ和ＦＬＲ２的ＯＰＴ则分别为１６％；３％和９％， 可见所提出的３个算法显著超过其他３个算法，甚 至超过３个启发式算法最优解所占比例之和，其中 ＨＡ１找到的最优解最多． 同时，表３也表明：性能指标ＡＲＰＤ和ＯＰＴ随 任务数，ｚ的变化而变化．图１给出了当ｍ＝２０时， ＡＲＰＤ和ＯＰＴ随任务数ｎ的变化情况． ＼ 删 堡 任务数，ｖ （ａ）ＡＲＰＤ ｌＯ ２ｏ ３Ｏ ４ｏ ５ｏ ６ｏ ７Ｏ ８０ ９ｏ １０ｏ 任务数Ⅳ （ｂ）ＯＰＴ 图１ ＡＲＰＴ和ＯＰＴ随任务数的变化曲线（ｍ＝２０） 由网１（ａ）可以看出ＡＲＰＤ在相同机器数时随 任务数的增加呈上升趋势，当任务数超过３Ｏ时，性 能几乎不再随任务数的增加而变化；同样，由图１ （ｂ）可以看出，ＯＰＴ在相同机器数时随任务数的增 加呈下降趋势，即找到最优解的比例随任务数的增 加而下降；当任务数超过２０时，不同算法找到最优 ４ 结语 本文针对流水作业调度问题最小化总完工时 间，提出了３个性能较好的混合算法ＨＡ１，ＨＡ２ 和ＨＡ３，将它们与目前较好的算法ＩＨ７－ＦＬ，ＦＬＲＩ 和ＦＬＲ２按ＡＲＰＤ和ＯＰＴ性能进行了比较，结果 表明ＨＡ１，ＨＡ２和ＨＡ３在性能上都要优于目前最 好的启发式算法，可有效地求解以总完工时间最小 化的流水作业调度问题． 参考文献（Ｒｅｆｅｒｅｎｃｅｓ） ［１］Ｇａｒｅｙ Ｍ Ｒ，Ｊｏｈｎｓｏｎ Ｄ Ｓ，Ｓｅｔｈｉ Ｒ．Ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｌｆｏｗｓｈｏｐ ａｎｄ ｊｏｂｓｈｏｐ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．Ｍａｔｈｅｍａｔｉｃｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，１９７６，ｌ（２）：ｌ１７—１２９． ［２］Ｋａｌｃｚｙｎｓｋｉ Ｐ Ｊ，Ｋａｍｂｕｒｏｗｓｋｉ Ｊ．Ｏｎ ｔｈｅ ＮＥＨ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｍｉｎｉｍｉｚｉｎｇ ｔｈｅ ｍａｋｅｓｐａｎ ｉｎ ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗ ｓｈｏｐｓ ［Ｊ］．Ｏｍｅｇａ，２００７，３５（１）：５３—６０． １ ３ ｌ Ｆｒａｍｉｎａｎ Ｊ Ｍ，Ｌｅｉｓｔｅｎ Ｒ，Ｒａｊｅｎｄｒａｎ Ｃ．Ｄｉｆｆｅｒｅｎｔ ｉｎｉｔｉａｌ ｓｅｑｕｅｎｃｅｓ ｆｏｒ ｔｈｅ ｈｅｕｒｉｓｔｉｃ ｏｆ Ｎａｗａｚ，Ｅｎｓｃｏｒｅ ａｎｄ Ｈａｍ ｔｏ ｍｉｎｉｍｉｚｅ ｍａｋｅｓｐａｎ，ｉｄｌｅ ｔｉｍｅ ｏｒ ｆｌｏｗｔｉｍｅ ｉｎ ｔｈｅ ｓｔａｔ— ｉｃ ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗｓｈｏｐ ｓｅｑｕｅｎｃｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｔｅｒ－ ｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆｐｒｏｄｕｃｔｉｏｎ Ｒｅｓｅａｒｃｈ，２００３，４１（１）： ｌ２１—１４８． ［４］Ｆｒａｍｉｎａｎ Ｊ Ｍ，Ｌｅｉｓｔｅｎ Ｒ．Ａｎ ｅｆｉｆｃｉｅｎｔ ｃｏｎｓｔｒｕｃｔｉｖｅ ｈｅｕ— ｒｉｓｔｉｃ ｆｏｒ ｆｌｏｗｔｉｍｅ ｍｉｎｉｍｉｓａｔｉｏｎ ｉｎ ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗ ｓｈｏｐｓ［Ｊ］．Ｏｍｅｇａ，２００３，３１（４）：３１ｌ一３ｌ７． １５ １ ＷＯＯ Ｈ Ｓ，Ｙｉｍ Ｄ Ｓ．Ａ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｅａｎ ｆｌｏｗｔｉｍｅ ｏｂｊｅｃｔｉｖｅ ｉｎ ｌｆｏｗｓｈｏｐ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．Ｃｏｍｐｕｔ－ ｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，ｌ９９８，２５（３）：１７５一ｌ８２． ［６］Ｒａｊｅｎｄｒａｎ Ｃ，Ｚｉｅｇｌｅｒ Ｈ．Ａｎ ｅｆｉｆｃｉｅｎｔ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ａ ｆｌｏｗｓｈｏｐ ｔｏ ｍｉｎｉｍｉｚｅ ｔｏｔａｌ ｗｅｉｇｈｔｅｄ ｌｆｏｗｔｉｍｅ ｏｆｊｏｂｓ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆＯｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，１９９７，１０３（１）：ｌ２９—１３８． ［７］Ａｌｌａｈｖｅｒｄｉ Ａ，Ａｌｄｏｗａｉｓａｎ Ｔ．Ｎｅｗ ｈｅｕｒｉｓｔｉｃｓ ｔｏ ｍｉｎｉ— ｍｉｚｅ ｔｏｔａｌ ｃｏｍｐｌｅｔｉｏｎ ｉｎ ｍ—ｍａｃｈｉｎｅ ｆｌｏｗｓｈｏｐｓ［Ｊ］． 一 ｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｒｏｄｕｃｔｉｏｎ Ｅｃｏｎｏｍｉｃｓ。２００２．７７ （１）：７１—８３． ［８］Ｆｒａｍｉｎａｎ Ｊ Ｍ，Ｌｅｉｓｔｅｎ Ｒ，Ｒｕｉｚ－Ｕｓａｎｏ Ｒ．Ｃｏｍｐａｒｉｓｏｎ’ ｏｆ ｈｅｕｒｉｓｔｉｃｓ ｆｏｒ ｆｌｏｗｔｉｍｅ ｍｉｎｉｍｉｓａｔｉｏｎ ｉｎ ｐｅｒｍｕｔａｔｉｏｎ ｌｆｏｗｓｈｏｐｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， ２ｏｏ５，３２（５）：１２３７一ｌ２５４． ［９］Ｂｅｎ—Ｄａｙａ Ｍ，ＡＩ—Ｆａｗｚａｎ Ｍ．Ａ ｔａｂｕ ｓｅａｒｃｈ ａｐｐｒｏａｃｈ ｆｏｒ ｈｔｅ ｌｆｏｗ ｓｈ０ｐ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，１９９８，１０９（１）：８８—９５． １０ Ｉ Ｌｉｕ Ｊ，Ｒｅｅｖｅｓ Ｃ Ｒ．Ｃｏｎｓｔｍｃｔｉｖｅ ａｎｄ ｃｏｍｐｏｓｉｔｅ ｈｅｕｒｉｓ— ｔｉｃ ｓｏｌｕｔｉｏｎｓ ｔｏ ｔｈｅ Ｐ／／∑Ｃ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆＯｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ．２００１，１３２ （２）：４３９—４５２． ［１１］Ｔａｉｌｌａｒｄ Ｅ．Ｂｅｎｃｈｍａｒｋｓ ｆｏｒ ｂａｓｉｃ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｇｒａｍｓ ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ， １９９３，６４（２）：２７８—２８５． ［１２］Ｌｉ Ｘ Ｐ，Ｗａｎｇ Ｑ，ｗｕ Ｃ．Ｅｆｉｆｃｉｅｎｔ ｃｏｍｐｏｓｉｔｅ ｈｅｕｒｉｓ． ｔｉｃｓ ｆｏｒ ｔｏｔａｌ ｆｌｏｗｔｉｍｅ ｍｉｎｉｍｉｚａｔｉｏｎ ｉｎ ｐｅｒｍｕｔａｔｉｏｎ ｆｌｏｗ ｓｈｏｐｓ［Ｊ］．Ｏｍｅｇａ，２００９，３７（１）：１５５—１６４．（ｔｏ Ｉｄｐ— ｐｅａｒ）