一类Jobshop多目标优化调度方法

格式：pdf
大小：743.32 KB
文档页数：6

下载文档原格式

基于混合粒子群算法的多目标柔性Job-Shop调度方法

基于混合粒子群算法的多目标柔性Job-Shop调度方法刘明周;张明伟;蒋增强;葛茂根;张铭鑫【期刊名称】《农业机械学报》【年(卷),期】2008(039)005【摘要】针对经典Job-Shop调度问题的局限性,提出了以时间、成本、质量三者综合为优化目标,具有柔性Job-Shop车间调度的优化模型.给出了优化目标的计算方法,并设计了混合粒子群算法,给出了使用此算法求解模型的具体实现过程.模型采用工序能力指数对质量目标进行量化,并采用综合评判线性加权模型解决柔性Job-Shop算法的权重选择问题,使决策者能够根据实际情况选择优化目标的偏好解.通过一个车间调度问题的实例验证了此调度模型和算法的有效性.【总页数】6页(P122-127)【作者】刘明周;张明伟;蒋增强;葛茂根;张铭鑫【作者单位】合肥工业大学机械与汽车工程学院,230009,合肥市;合肥工业大学机械与汽车工程学院,230009,合肥市;合肥工业大学机械与汽车工程学院,230009,合肥市;合肥工业大学机械与汽车工程学院,230009,合肥市;合肥工业大学机械与汽车工程学院,230009,合肥市【正文语种】中文【中图分类】TH186【相关文献】1.基于pareto方法的多目标柔性车间调度问题的研究 [J], 陈江波;曹爱霞;郑义;岳庆超2.基于免疫算法的多目标柔性job-shop调度研究 [J], 余建军;孙树栋;刘易勇3.基于分层蚁群遗传算法的多目标柔性作业车间调度方法 [J], 邹攀;李蓓智;杨建国;施烁;梁越昇4.基于多规则资源分配的柔性作业车间调度问题多目标集成优化方法 [J], 高丽;周炳海;杨学良;王吉霞5.基于混合微粒群优化的多目标柔性Job-shop调度 [J], 夏蔚军;吴智铭因版权原因，仅展示原文概要，查看原文内容请购买。

柔性作业车间调度问题简明分析

1、编码
1、编码
在遗传算法中，问题的解需要用二进制或十进制的编码来表示。在柔性作业车间调度问题中，我们可以将生产任务和生产设备分别用二进制或十进制的编码表示，每个编码对应一个任务或设备。
2、初始种群生成
2、初始种群生成
遗传算法的初始种群是随机的，可以通过随机分配任务和设备来生成。在生成初始种群时，需要保证每个任务都有对应的设备，每个设备都有对应的任务。
四、结论
四、结论
本次演示提出了一种新型的柔性作业车间调度方法——基于遗传算法的柔性作业车间调度方法。该方法通过采用遗传算法作为优化算法，能够找到最优的调度方案，提高生产效率和降低生产成本。通过应用案例的验证，该方法具有很高的实用价值和推广价值。
谢谢观看
柔性作业车间调度问题简明分析
01 引言
03 问题分析
目录
02 概念解析 04 技术实现
05 案例分析
07 参考内容
目录
06 总结
引言
引言
在现代化制造业中，柔性作业车间调度问题一直是生产过程中的核心难题之一。该问题的合理解决有助于提高生产效率、降低成本、增强企业竞争力。本次演示将对柔性作业车间调度问题进行简要分析，旨在帮助读者更好地理解和解决这类问题。
结论
结论
本次演示对车间作业调度的技术问题进行了简要的综述。尽管在调度算法、任务分配和调度优化等方面取得了一定的研究成果，但仍存在许多挑战和需要进一步探讨的问题。例如，如何针对实际生产环境中的动态变化进行调度优化，
结论
如何综合考虑多个优化目标等问题。此外，随着智能制造技术的发展，如何将先进的人工智能方法应用于车间作业调度也是一个值得研究的方向。
5、交叉操作

资源调度中的多目标优化算法设计

资源调度中的多目标优化算法设计资源调度是在现代社会中面临的一个重要问题，尤其是在信息技术高度发达的背景下，各种资源的分配与调度问题变得更加复杂。

由于资源调度的多样性和复杂性，传统的单目标优化算法已经不能满足需求，而多目标优化算法逐渐成为资源调度领域的研究热点。

本文将探讨资源调度中的多目标优化算法的设计和应用，以及一些常见的算法模型和解决方法。

资源调度中的多目标优化算法旨在通过有效地分配和调度资源，实现多个目标的最优化。

多目标优化的目标可以是经济效益、时间效率、质量优先、能源消耗、环境条件等等，针对不同的应用场景可以设计出不同的多目标优化算法。

下面将介绍几种常见的多目标优化算法及其设计原理。

1. 遗传算法：遗传算法是一种模拟自然界进化过程的优化算法。

通过将问题表示为染色体的形式，通过选择、交叉和变异等操作，逐代地优化染色体，以求得最优解。

在资源调度中，可以将资源与任务抽象为基因和染色体的形式，通过不断进化调整资源分配，实现多目标最优化。

2. 粒子群优化算法：粒子群优化算法来源于对鸟群中鸟群行为的模拟，通过模拟多个粒子的位置和速度，以及粒子间的信息传递和合作，来搜索最优解。

在资源调度中，粒子群优化算法可以用于寻找合适的资源分配策略，通过粒子间的交流和合作来优化资源的分配。

3. 蚁群算法：蚁群算法源于模拟蚂蚁寻找食物的行为，通过模拟蚂蚁释放信息素、寻找最短路径的行为，实现优化问题的求解。

在资源调度中，可以将不同的资源抽象为蚂蚁，通过信息素的释放和更新，来引导资源的分配和调度，以达到最优解。

以上只是几种常见的多目标优化算法，在实际应用中，需要根据具体问题的特点和需求，结合合适的算法模型进行设计。

同时，也需要考虑多目标优化算法的评价和选择方法。

在多目标优化算法中，如何评价和选择最优解是一个重要的问题。

常见的方法有帕累托解集、权重法和支配关系等方法。

帕累托解集是指在多目标优化中，某个解在所有目标上都优于其他解的解集。

基于ILOGSOLVER的Job_Shop调度算法实现

现代制造工程2006年第5期专题研究———生产调度系统基于I LO G S OL VER 的Job 2Shop 调度算法实现杨达玲,杨建军,白宏斌(北京航空航天大学机械工程及自动化学院,北京100083)摘要　通过使用约束规划方法对Job 2Shop 调度问题进行描述和建模,设计用于求解Job 2Shop 调度问题的禁忌搜索算法,在此基础上基于先进的约束规划系统I L OG 对算法进行实现。

实践证明基于约束规划将I L OG 优化组件应用于对Job 2Shop 调度问题的求解中,不仅可以大大提高编程效率而且最后结果也有显著提高。

关键词:Job 2Shop 约束规划　CSP I L OG S OLVER中图分类号:TP391　文献标识码:A 文章编号:1671—3133(2006)05—0022—030　引言根据车间内工件的工艺路线的不同,车间调度问题可分为所有工件工艺路线相同的Fl ow 2Shop 型和工件工艺路线不同的Job 2Shop 型,而Job 2Shop 调度问题是产品制造业中共存的问题,它是实际生产调度问题的高度抽象。

理论上,Job 2Shop 调度问题属于NP 问题,为了解决这一难题,产生了数学规划、系统仿真等一系列方法,取得了很大成绩[1],但是仍然存在求解规模小,时间长等缺点,而随着约束理论和约束规划系统的发展,约束规划技术已经应用于很多商用系统。

基于约束的规划方法是一个相对较新的领域,通常称为Constraint Logic Pr ogra mm ing 或Constraint Pr o 2gra mm ing (CP ),相应的软件工具被称为约束规划系统,其中最具代表性也是应用最为广泛的就是I L OG 优化组件。

约束规划起源于上世纪80年代中期,但直到近期才作为一种解决优化问题的方法被人们所认识,它尤其适合于运筹学领域的组合搜索和具有多种约束的问题。

约束规划将描述问题和解决问题分离,用户只需描述问题,剩余的工作全部由计算机来完图1　CSP 求解过程成。

面向工件的多目标柔性Job Shop调度问题研究

面向工件的多目标柔性Job Shop调度问题研究
吴秀丽;孙树栋;杨展;蔡志强
【期刊名称】《西北工业大学学报》
【年(卷),期】2006(024)004
【摘要】针对各工件目标不同的多目标柔性Job Shop调度问题,提出了一种基于混合遗传算法的优化求解方法.首先建立了该类问题的调度模型;然后,在基本遗传算法柜架的基础上,通过两层意义上的随机权重法,将多目标问题随机转化为单目标问题,同时为了保证算法的收敛性和Pareto解的多样性,混合遗传算法集成了精英保留策略和小生境技术;利用层次分析法与模糊综合评判集成的方法,从Pareto解集中选出最优妥协解.最后通过实验仿真,证明提出的方法可以有效解决该类多目标柔性Job Shop调度问题.
【总页数】5页(P477-481)
【作者】吴秀丽;孙树栋;杨展;蔡志强
【作者单位】西北工业大学,机电学院,陕西,西安,710072;西北工业大学,机电学院,陕西,西安,710072;西北工业大学,机电学院,陕西,西安,710072;西北工业大学,机电学院,陕西,西安,710072
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于规则组合的Job Shop多目标柔性调度方法 [J], 王海瑶;蒋增强;葛茂根
2.一种求解多目标柔性Job Shop调度的改进遗传算法 [J], 袁坤;朱剑英
3.多目标柔性Job Shop调度问题的技术现状和发展趋势 [J], 吴秀丽;孙树栋;杨展;翟颖妮
4.遗传算法在多目标柔性Job-Shop调度中应用 [J], 朱文龙;丁华福
5.基于混合粒子群算法的多目标柔性Job-Shop调度方法 [J], 刘明周;张明伟;蒋增强;葛茂根;张铭鑫
因版权原因，仅展示原文概要，查看原文内容请购买。

基于多目标优化的调度算法研究

基于多目标优化的调度算法研究随着社会的发展，机械化程度越来越高，而机器及设备的工作调度又是影响生产效率和质量的重要因素之一。

然而，传统的调度算法以单一目标为依据，难以满足现代生产需求。

如何在考虑多个因素的基础上有效地优化调度方案，成为业界关注的热点问题。

本文将围绕多目标优化的调度算法展开探讨。

一. 多目标优化的基本概念多目标优化是指在优化模型中同时考虑两个或两个以上的目标，这些目标一般相互独立，且彼此之间具有冲突或互补关系。

如何在满足不同目标的前提下，达到最优化的效果，是多目标优化需要解决的核心问题。

在调度领域，多目标优化的目标可以多种多样，如完成时间、等待时间、设备利用率、任务完成顺序等等。

其中，完成时间和等待时间是调度算法中常见的两个目标。

在实际调度中，完成时间往往是最优化的首要目标，而等待时间也是需要考虑的重要因素之一。

二. 多目标优化的调度算法研究针对多目标优化的调度算法研究，常见的方法有遗传算法、模糊逻辑算法、粒子群算法等。

遗传算法是通过模拟自然界的进化过程进行优化的一种算法。

在调度算法中，遗传算法通常通过对任务序列进行交叉、变异等操作，得到新的优化方案。

这种方法具有良好的鲁棒性和全局搜索能力，但也容易陷入局部最优解。

模糊逻辑算法则是基于模糊数学理论的一种算法。

在调度算法中，模糊逻辑算法通过对任务的权值和优先级进行模糊处理，得到最终的调度方案。

这种方法对于处理模糊问题具有一定的优势，但也有一定的计算难度。

粒子群算法则是模拟鸟群觅食行为的一种算法。

在调度算法中，粒子群算法通常通过对任务序列的位置进行移动和更新，得到新的优化方案。

这种方法具有快速收敛和高效率的优势，但对于复杂的调度问题仍有一定局限性。

三. 多目标优化的调度算法实际应用多目标优化的调度算法在实际生产应用中得到了广泛的应用。

例如，在汽车制造领域中，通过对装配线进行优化调度，可以实现生产效率和产出品质的提高；在半导体制造领域中，通过对晶圆的处理顺序进行优化调度，可以实现设备利用率和产量的最大化。

多目标柔性Job+Shop调度问题的技术现状和发展趋势

［ 0+ ］能的前提下提高任何一个目标的性能。对于多目标互相冲
这是一个混合 1?0 规划模型，并用枚举的方法进行求解。 T’?
［6］ U$M 等人研究了用拉氏松弛法近似求解单机环境下双目标
2-34；这种方法对于小规模问题尚可求解，一旦问题规模增加则很难求解，即使能求解也需要花费大量的计算时间。 !" %" !$ 启发式方法由复杂性分析可知，三个以上工件的 2-34 就变成 >4?:";@ 了。为了能在相对短的时间内获得近似最优解，所以很自然地想到用启发式算法求解。（0）分派规则法。采用该方法求解多目标 2-34 的研究较
万方数据男，山西晋城人，硕士研究生，研究方向为计算机敏捷制造；翟颖妮（ &-)*% ），女，山西运城人，博士研究生，研究方向为计算机敏捷制造.
・ =・
调度指标如下：
计算机应用研究I
=115 年
即所有工件的最大 ! !"#$%&"’ 是调度的最小生产周期，完成时间的最小值。这个指标用得最多，可参见文献［( ) *］等。 "流经时间是指工件最后一道工序完成时间与开始释放时间之间的差值，可分为工件的流经时间、整个调度任务的最大流经时间、平均流经时间和加权流经时间等。这类指标也比较常用，可参见文献［(， +］等。 #提前时间 , 延迟时间是指工件的完成时间与交货期时间的差值。差值为正时是延迟时间；差值为负时是提前时间。在 -./ 制企业中，这两个指标是最重要的。其变化形式有最大提前时间 , 最大延迟时间、平均提前时间 , 平均延迟时间，可参见 01 ) 0( ］等。文献［*， $机器总负荷 , 瓶颈机器的最大负荷。机器总负荷是指一个调度方案产生的所有机器负荷的总和；瓶颈机器的最大负荷是指负荷最大的机器的负荷值。在带有机器柔性的 2-34 中，这两个指标最常见，因为它们对于合理分配资源和提高生产效率有着重要的意义，可参见文献［5， 06 ］等。制 %成品存储成本是指工件提前完成又不能提前交货时，造商需要一定的费用保管成品，可参见文献［ 05 ］等。制造商需要 &拖工惩罚成本是指工件晚于交货期完成时，提供给客户额外的罚金和与拖期时间相关的罚金，可参见文献［ 05 ］等。（(）问题分类。由 2-34 的描述可以看出，该类问题可分

基于规则组合的Job Shop多目标柔性调度方法

关于柔性调度问题可以描述为：有ｍ类待设加工工件和台机器，表示工件ｉ含的工序包数；示工件ｉ的第Ｊ道工序在机器ｋ上加，表
目前常用的柔性调度方法主要集中在各种优化算法上，如微粒群算法、遗传算法、免疫算法、模拟退火算法及神经网络算法等＿］但是在实际１，应用中随着生产系统规模的扩大，这些优化算法普遍存在着运算量较大、速度较慢、不容易求取全局较优解的问题，以适应现场调度的实时性需难求。本文通过建立一种基于规则组合的多目标柔
ＷＡＮＧｉｙｏ，ＪＡＮＧｅｇｑａｇ，ＧＥＭａ — ｅＨａ— ａＩＺｎ－ｉｎｏｇｎ
（ｈｏｆＭａｈｉｒｎｔｍｏｉｇｎｅｉｇ，ＨｅｅｎｖｒｉｙｏｃｎｌｇＳｃｏｌｃｎｅｙａｄＡｕｏｂｌＥｎｉｅｒｎｏｅｆｉｉｅｓｔｆＴｅｈｏｏｙ，Ｈｅｅ３０９，Ｃｈｎ）Ｕｆｉ００２ｉａ
ｄｔｎｎｐｌｉｇｔｅｍａｉｍｅｉｔｎｔｎｌｚｈｕｅｓｈｄｌｇｒｓｌｓＦｎｌｉｉｓａｄａｐｙｎｈｘｍｕｄｖａｉｏａａｙｅｔｅｒｌｃｅｕｉｅｕｔ．ｉａｌｏｏｎｙ，ａｓｍｕａｉｌｔｎｅａｌｓｇｖｎｔｅｉｈａｉｉｙｏｈｓｓｈｄｌｇｍｅｈｄｉｘｍｐｅｉｉｅｏｖｒｆｔｅｖｌｔｆｔｉｃｅｕｉｔｏ．ｏｙｄｎ
的多目标权重，以选择符合现场实时工况的较优调度方案；通过仿真实例验证了该调度方法的有效性。关键词：规则组合；离差最大化；多目标；柔性调度中图分类号：Ｈ１６Ｔ６文献标识码：Ａ文章编号：０３５６（００００４０１０ —００２１）１０１ —５

时间与工序顺序相关的Job+Shop调度优化方法研究

Q" 引言
(3T #$3: （作业车间）调度目标是：针对工艺
收稿日期： OQQL ? QP ? QL 基金项目：国家自然科学基金资助项目（ SQ!SKQLQ ）
相关工件的相关工序的加工顺序和起始加工时间，以实现生产目标的最优化。 (3T #$3: 调度问
［ K］题是 -A ? $%1B 问题，很难求得它的最优解。由
研究了基于
工序排序的调整时间对不同性能指标的影响，并指出在调度决策中，应该明确地考虑调整时间； +,-.- 等
［ /］
利用分支定界法解决了调整时间与工
序排序有关的两台机器的 !"# $%"& 调度问题，目标是求取 !"#$%&"’ （完成时间）的最小值； 0%"1
［ 2］等提出了一种启发式算法，可以求解调整时间
式（ 6 ）中第 6 个约束条件表明每种工件必须遵循特定的工艺路线；第 * 个约束条件进一步定义了通过时间 2 ),; ；第 / 个约束条件给出了用相同机器顺序进行的两道工序的时间约束，即强调每台机器在某一时刻只能加工一道工序。
*9
求解调度问题的免疫算法
借鉴生物机体免疫抗体的多样性、浓度调节、
受工序排序约束的多工件、多机器的柔性制造单
［ 4］元调度问题。 3%"( 等将调整时间受工序排序
考虑工序调整时间的
约束的多工件、多机器的柔性制造单元调度问题；周泓等将启发式方法与遗
!"# $%"& 问题的混合整数规划如下：
作者简介：商建东，男， KFPM 年生。河南科技大学机电工程学院副教授、博士。主要研究方向为计算机集成制造、虚拟产品设计与开发、计算机网络与通讯等。发表论文 !Q 余篇。

并行机环境下的多目标Job—Shop调度问题研究

并行机环境下的多目标Job—Shop调度问题研究刘佳;刘林【期刊名称】《微型机与应用》【年(卷),期】2012(31)12【摘要】In the circumstance of multi machine Job_Shop scheduling, restricting to order-dependent setup-time and taking an overall consideration of the two factors-completion time and earliness/tardiness penalties ,this research proposes a hybrid genetic al- gorithm based on sequential coding of jobs on machines and interleaved mode in genes and integrates variable neighborhood search （VNS）and clusteranalysis ,making the Pareto solution set more effective in quality and distribution.%分析并讨论了带调整时间即换模具时间，综合考虑工件完工时间、不同交货期窗口下的提前／拖期惩罚、并行机环境下的多目标Job—Shop调度问题，提出了一种基于不同工件工序排序的染色体编码方式，利用稳步遗传算法求解，并融合变邻域搜索和依角度聚类的方法，使得求得的Pareto解集在质量和分布上均有较好的效果。

仿真实验表明了此种算法的可行性和有效性。

【总页数】4页(P64-67)【作者】刘佳;刘林【作者单位】合肥工业大学管理学院,安徽合肥230009;合肥工业大学管理学院,安徽合肥230009【正文语种】中文【中图分类】TP3-05【相关文献】1.面向工件的多目标柔性Job Shop调度问题研究 [J], 吴秀丽;孙树栋;杨展;蔡志强2.基于GASA优化算法的不确定条件下Job-Shop调度问题研究 [J], 陈勇;郑鑫帆;王亚良;鲁建厦3.约束满足混合算法求解并行机Job-Shop调度问题 [J], 李俊芳;李铁克;屈国强4.带有并行机的混合Job Shop调度问题 [J], 李俊芳;尹兆涛5.用遗传算法解决在并行机上带有不同交货期窗口的Job-Shop调度问题 [J], 童刚;李光泉;刘宝坤因版权原因，仅展示原文概要，查看原文内容请购买。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

每个工件有 1~m 道工序，所有工件最多有 n×m 道工序（记为 nm），作业i的加工设备 k 已确定（表 1 中的 Y 列）。优化目标是确定所有作业的最佳加工顺序、开工时间和完工时间，使工件平均流程时间及所有工件完工时间最短。问题假设（1）每台设备同一时刻只能加工一个作业；（2）某作业一旦开始加工不能中断；（3）一个工件在同一台机器上只加工一次，即在同一台机器上不会出现循环加工某个工件的情况；（4）工件之间具备相同的优先级；（5）某工件的上道工序加工完毕后，若其分配的设备空闲则立即开始加工下一道工序，无时滞；（6）设备初始状态全为闲。
ThE 的计算：如图 1 所示，第一步，对安排顺序为 h 的作业，由表 1 求得所属工件号（设为 c）、所属工件中的工序号（设为 k）、所分配的设备号（设为 j）、加工时间 tck；第二步，若k = 1，则将 0 赋给 a，若 k>1，求出 c 工件第 k - 1道工序的完工时间赋给 a；第三步，求出设备 j 上所有已分配作业完工时间的最大值赋给 b；第四步，按 ThB=max （a， b）求出作业 h 的开工时间 ThB；第五步，按 ThE=ThB+tck 求出作业 h 的完工时间。按照以上步骤，从安排顺序为 1 的作业开始，依次往后推算，求出所有作业的完工时间 ThE （h=1， 2， …， nm-1， nm）。
3
基于分阶段混合变异的禁忌搜索算法
（1）计算流程：图 2 是基于分阶段混合变异禁忌搜索算法
Y
f max > bsf ?
［二二皇
初始参数产生初解 S 并计算其适应度 f
epo最好个体 BSF 对应的满意解
化调度模型，并针对模型提出了一种分阶段混合变异的禁忌搜索算法。为增强算法收敛性，利用 “逆序变异” 和 “基因段交换变异” 找到了较好的初解，在此基础上利用 “基因交换变异” 继续搜索近优解。以 10 个算例验证了提出的 Job-shop 多目标优化调度方法的正确性和有效性。关键词： Job-shop 调度；禁忌搜索算法；分阶段混合变异 DOI： 10.3778/j.issn.1002-8331.2010.23.061 文章编号： 1002-8331 （ 2010 ） 23-0215-04 文献标识码：Ａ中图分类号： TP391； C93-03
算法结合从而取长补短[13-15]。本文提出了一类 Job-shop 多目标优化方法，构建了以工件平均流程时间和最大完工时间最短为优化目标的 Job-shop 多目标优化调度模型，针对模型特征及个体编码特殊性，提出并设计了一种分段混合变异禁忌搜索算法对模型进行求解。
1
问题描述及假设
问题描述车间要在 s 台设备中安排 n 个工件的加工作业，
作业工件 c 的 k-1 工序第 h 个安排的作业：作业（e）、工件（c）、工序（k）、设备（j）加工时间 tck
2
Job-shop 多目标优化调度模型
上述 Job-shop 调度问题的实质是安排最优的作业加工顺
序。一旦此加工顺序确定，则工件的开工时间和完工时间也同时确定，因此其决策变量可用向量 X 表示（表 1 中的 X 列）。为保证 X 为可行方案， X 须满足两个条件：（1）所有元素对应 1~nm 的一个整数排列，元素的值无重复；（2）为满足工件各工序的先后顺序， [ X i1
基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.70601037)；教育部 “新世纪优秀人才支持计划” （the Program for New Century Excellent Talents in University, China No.NCET-07-0908）。作者简介：曾强（1975-），男，博士研究生，河南理工大学工业工程系副主任，主要从事工业工程、生产管理相关领域的研究；杨育（1971-），男，教授、博士生导师，主要从事网络化协同制造、工业工程相关领域研究；王小磊，女，博士研究生，主要从事工业工程、产品协同设计相关领域的研究；梁学栋，男，博士研究生，主要从事工业工程、产品协同设计相关领域的研究。收稿日期： 2009-10-19 修回日期： 2009-12-05
之一[11]。近年来，学者对禁忌搜索算法进行了改进研究并加以了实际应用。改进主要着眼于两方面：（1）对禁忌搜索算法本
11-12] 身的参数进行改进 [1，；（2）将禁忌搜索算法与其他智能搜索
加工作业参数
安排顺序 X X11 X12 … X 1i … X 1， m-1 X 1m X21 X22 … X n， m-1 Xnm 加工设备 Y 1 2 … k … 3 5 2 1 … 5 4 加工时间 t11 t12 … t1 i … t1 ， m-1 t1 m t21 t22 … tn ， m-1 tnm
n i=1 n
图 1 T hE的计算示意图
（2）（3）
T max = max (Ti )
Ti 的计算：当求出所有作业的完工时间 ThE 后，每一个工件 i 的最后一道工序完工时间即为 Ti，即有： Ti=TkE（k=m， 2m ， 3m ， …， nm）。
其中， Tavg 为工件的平均流程时间， Tmax 为所有工件最大完工时间， Ti 为工件 i 的完工时间。
216
2010， 46 （23）
Computer Engineering and Applications 计算机工程与应用
表1
作业序号 1 2 … i … m-1 m m+1 m+2 … nm-1 nm 工件 1 1 … 1 … 1 1 2 2 … n n 工序 1 2 … i … m-1 m 1 2 … m-1 m
X i2
设备 j 上加工的最后作业 p
X im（ 2， …， n ）须为升序排列。 ] i=1，
a b ThE 时间
建立的数学模型如下：
OPT f ( X ) = OPT ( f1( X )，f 2 ( X ))＝(min T avg， min T max) （1） T avg = Ti å i=1 n
1.重庆大学机械传动国家重点实验室，重庆 400030 2.河南理工大学，河南焦作 454000 1.State Key Laboratory of Mechanical Transmissions， Chongqing University， Chongqing 400030， China 2.Henan Polytechnic University， Jiaozuo， Henan 454000， China E-mail： zengqiang@ ZENG Qiang， YANG Yu， WANG Xiao-lei， et al.Multi-objective optimization method for Job-shop puter Engineering and Applications， 2010， 46 （23）： 215-218. Abstract： A multi-objective optimization method for Job-shop scheduling is proposed.In the method， an optimal Job-shop scheduling model is established.The objective of the model is to minimize the Average Flow Time （AFT） and overall completion time （makespan） of all workpieces.Aiming at the model， a taboo searching algorithm based on multi-stage hybrid mutation is proposed.To improve the convergence of the algorithm， inverse order mutation and gene segment swap mutation is used to find a good original solution， based on which gene swap mutation is used to find the approximate optimal solution. The algorithm is applied to ten benchmark Job-shop examples， and the result validates the correctness and effectiveness of the optimization method proposed in this paper. Key words：Job-shop scheduling； taboo searching algorithm； multi-stage hybrid mutation 摘要：提出了一类 Job-shop 多目标优化调度方法。构建了一个以工件平均流程时间最短、全部工件完工时间最短的 Job-shop 优
导致工件最大完工时间较长，从而降低部分客户的满意度。理想的做法是在优化调度时考虑两个目标的结合，既要做到工件平均流程时间最短从而提高资金周转率，又要做到工件最大完工时间最短从而提高客户整体满意度。 Job-shop 优化调度是复杂的组合优化模型，对这类模型的 [10] 求解一般采用智能搜索算法，如遗传算法、模拟退火算法、禁忌搜索算法、蚁群搜索算法、粒子群搜索算法、混合搜索算法等，但这些智能搜索算法各有其优缺点，应用时需加以适当改进。禁忌搜索算法是对人类智力过程的一种模拟，该算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，同时通过特赦准则赦免一些优良解，进而保证多样化的有效搜索以最终实现全局的优化。与其他智能算法一样，禁忌搜索算法也有其局限性，对初始解有较强的依赖性是其缺点