基于多目标粒子群算法的混合流水车间调度方法研究
- 格式：pdf
- 大小：300.77 KB
- 文档页数：5
CN4321258/ TP ISSN 10072130X
计算机工程与科学
COMPU TER EN GIN EERIN G & SCIENCE
文章编号 :10072130X(2009) 0820052205
2009 年第 31 卷第 8 期 Vol1 31 ,No1 8 ,2009
(1)
x ∈Rn
其中 , Rn 称为决策向量可行空间 , RQ 称为目标向量空间 。
定义 1 一个向量 u = ( u1 , u2 , …, uQ) 支配向量 v = ( v1 , v2 , …, vQ) ,当且仅当对任意 i ∈{ 1 ,2 , …, Q} , ui ≥ vi , 且 ϖ i ∈{ 1 ,2 , …, Q} ,使得 ui > vi 。
定义 2 一个解 x u ∈Rn 称为问题的 Pareto 最优解 ,当 且仅当不存在 x v ∈ Rn ,使得 F( x v ) 支配 F( xu) 。
定义 3 所有 Pareto 最优解的集合称为 Pareto 最优
集 ,相应的目标向量的图形称为 Pareto 最优前沿 。
2. 2 混合流水车间调度问题
52
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
优秀个体间的信息共享 ,优秀个体直接指导粒子下一代的 进化方向 , 而 GA 是基于种群所有个体间的信息共享 ,向 最优解的方向缓慢进化 ,所以 PSO 比 GA 具有更高的搜索 效率 。因此 , 研 究 基 于 多 目 标 PSO 算 法 ( Multi2o bjective PSO ,MO PSO) 的 H FSP 问题的调度方法具有重要的理论 意义和工程应用价值 。
3. 1 标准 PSO 算法
SPSO ( Standard PSO ,简称 SPSO) 将每个个体看作是 D 维搜索空间中一个没有体积质量的粒子 ,在搜索空间中 以一定的速度飞行 ,粒子通过跟踪两个极值来更新自己 :一 是粒子本身所找到的最优解 , 即个体极值 rbest ;另一个是 整个种群目前找到的最优解 , 即全局极值 gbest 。若用 vid 表示粒子 i 在第 d 维空间的速度 , xid 表示其在第 d 维空间 的位置 , w 表示惯性权重 , c1 和 c2 分别表示认知系数和社 会系数 , ran d1 () 、ran d2 () 为区间 [ 0 ,1 ]内均匀分布的随 机数 ,则粒子按式 (5) 和式 (6) 更新当前速度和位置 。
粒子群算法是一种新兴的基于群集智能的进化算法 , 已在神经网络训练 、模糊系统控制和多目标函数优化[6] 等 领域取得了广泛的应用 。与遗传算法相比 , PSO 和 GA 都 具有强大的隐并行搜索性能 。由于 PSO 基于单个粒子与
3 收稿日期 :2008204209 ;修订日期 :2008209212 基金项目 :国家自然科学基金资助项目 (60634020) 作者简介 :欧微 (19832) ,男 ,湖南邵阳人 ,硕士生 ,研究方向为粒子群算法与优化调度 ;邹逢兴 ,教授 ,研究方向为控制理论与控制工 程 、检测技术与自动化装置 、智能算法与优化调度等 ;高政 ,副教授 ,研究方向为图像处理与模式识别 、数据挖掘与智能算法等 ;徐晓 红 ,高级实验师 。 通讯地址 :410073 湖南省长沙市国防科技大学机电工程与自动化学院 ; Tel :13975849475 ; E2mail :ouweiwlmq @163. co m Address :School of Mechat ronics Engineering and Auto mation , National Universit y of Defense Technology , Changsha , Hunan 410073 ,P. R. China
based on t he fit ness crowd degree is p resented. Finally , t he effectiveness of MO PSO is demonst rated by numerous simula2
tio n experiment s.
关键词 :生产调度 ;混合流水车间 ;多目标优化 ;粒子群算法 ; Pareto 最优解 ;进化计算
摘 要 :混合流水车间调度问题 H FSP 是一种具有很强应用背景的生产调度问题 。本文给出了一种 H FSP 多目标调
度模型 ,提出了一种针对该类问题的多目标粒子群算法 。该算法采用基于 Pareto 支配关系的极值更新策略 ;采取对自适
应惯性权重递减和对种群变异的方法以保持种群多样性 ;设置 Pareto 解池保存计算中出现的 Pareto 最优解 ,并提出了一
机器进行加工是降低产品次品率的有效方法 :
S Mj
∑∑ Maxmize (
N kj E jk )
(4)
j =1 k =1
其中 , N kj 表示加工第 j 道工序的第 k 台机器加工工件的个
数 , Ejk 表示该机器的品质属性 。式 (4) 表示调度目标为最
大化品质较优机器的加工任务 。
2 问题描述
A multi2o bjective scheduling model of H FSP is p ut forward in t his paper , and a multi2o bjective particle swarm optimizatio n
(MO PSO) algo rit hm is p ropo sed. This algorit hm adopt s an updating st rategy based on t he Pareto dominance relatio nship ,
Key words :p roduction scheduling ; hybrid flow2shop scheduling ; multi2objective optimizatio n ; particle swarm optimiza2
tio n ; Pareto optimum solution ;evolutionary algo rit hm
vid ( t + 1) = wv id ( t) + c1 ran d1 () ( rbest id - x id ( t) ) +
c2 ran d2 () ( gbest d - x id ( t) )
(5)
x id ( t + 1) = xid ( t) + vid ( t + 1)
H FSP 问题可以描述为 : N 个工件在流水线上进行 S
道工序的加工 ,每个工序有 M j ( M j ≥1) 台并行机 ,每个工 件各道工序都可以在相应阶段上的任意一台机器上加工 , 要求确定并行机器的分配情况和同一机器上工件的加工顺
序 ,使得多个调度目标得以优化[4] 。 缩短生产周期 、优化资源配置和降低产品的次品率是
种基于适应度拥挤度的聚类算法优化解的分布特性 。实验结果表明 ,本文算法是求解 H FSP 问题的一种有效方法 。
Abstract :The hybrid flow2shop scheduling p roblem ( H FSP) is a scheduling p roblem wit h st ro ng application background.
生产系统的三个最重要的调度目标 。缩短生产周期可以提
高系统的生产能力 ,并能增加系统的柔性 ;减少设备空转时 间可以减少资源浪费 ,提高设备的使用寿命 ,降低单位产品 的生产成本和能源消耗 ;降低产品的次品率可以减少次品
返厂加工的人力 、原料和能源消耗 。因此 ,对调度目标描述 如下 :
(1) 缩短生产周期 。即最小化最大流程时间 :
N
Minmize ( Max ( CiS ) )
(2)
i =1
其中 , CiS 表示工件 i 的第 S 道工序 (最后一道工序) 的完工
时间 。式 (2) 表示调度目标为使得所有工件中的最大完工
时间最小化 。
(2) 减少设备空转时间 。一般情况下 ,考虑到开启和停 止设备带来的消耗 ,设备一旦开启 ,则在所有加工任务完成
文献[2 ]证明 ,即使是单目标两阶段中只有一个阶段有 并行机的 HFSP 问题也属于 NP2hard 问题 。鉴于问题的复
杂性 ,很难用一般的数学规划方法进行求解 。科学的调度方 法一直是研究的重点 ,近年来 ,启发式方法[3] 、遗传算法 ( Ge2 netic Algorithm ,简称 GA) [4] 和粒子群算法 ( Particle Swarm Optimization ,简称 PSO) [5] 等智能算法在求解单目标 HFSP 问题时表现出了较好的性能 。但是 ,对于实际问题 , HFSP 往往需要综合考虑生产成本 、资源能耗和产品周期等多个因 素 ,而且各因素之间往往会存在冲突 ,属于多目标优化问题 (Multi2Objective Optimization Problem ,简称 MOP) 。
and int roduces a self2adaptive inertia weight and mutation app roach to keep t he diversity of t he pop ulation , t he also designs
a Pareto optimal set pool to p reserve t he dominance solutio ns fo und in t he evolution p rocess. Then a clustering algo rit hm
基于多目标粒子群算法的混合流水车间调度方法研究3 A Hybrid Flow2Shop Scheduling Approach
计算机工程与科学
COMPU TER EN GIN EERIN G & SCIENCE
文章编号 :10072130X(2009) 0820052205
2009 年第 31 卷第 8 期 Vol1 31 ,No1 8 ,2009
(1)
x ∈Rn
其中 , Rn 称为决策向量可行空间 , RQ 称为目标向量空间 。
定义 1 一个向量 u = ( u1 , u2 , …, uQ) 支配向量 v = ( v1 , v2 , …, vQ) ,当且仅当对任意 i ∈{ 1 ,2 , …, Q} , ui ≥ vi , 且 ϖ i ∈{ 1 ,2 , …, Q} ,使得 ui > vi 。
定义 2 一个解 x u ∈Rn 称为问题的 Pareto 最优解 ,当 且仅当不存在 x v ∈ Rn ,使得 F( x v ) 支配 F( xu) 。
定义 3 所有 Pareto 最优解的集合称为 Pareto 最优
集 ,相应的目标向量的图形称为 Pareto 最优前沿 。
2. 2 混合流水车间调度问题
52
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
优秀个体间的信息共享 ,优秀个体直接指导粒子下一代的 进化方向 , 而 GA 是基于种群所有个体间的信息共享 ,向 最优解的方向缓慢进化 ,所以 PSO 比 GA 具有更高的搜索 效率 。因此 , 研 究 基 于 多 目 标 PSO 算 法 ( Multi2o bjective PSO ,MO PSO) 的 H FSP 问题的调度方法具有重要的理论 意义和工程应用价值 。
3. 1 标准 PSO 算法
SPSO ( Standard PSO ,简称 SPSO) 将每个个体看作是 D 维搜索空间中一个没有体积质量的粒子 ,在搜索空间中 以一定的速度飞行 ,粒子通过跟踪两个极值来更新自己 :一 是粒子本身所找到的最优解 , 即个体极值 rbest ;另一个是 整个种群目前找到的最优解 , 即全局极值 gbest 。若用 vid 表示粒子 i 在第 d 维空间的速度 , xid 表示其在第 d 维空间 的位置 , w 表示惯性权重 , c1 和 c2 分别表示认知系数和社 会系数 , ran d1 () 、ran d2 () 为区间 [ 0 ,1 ]内均匀分布的随 机数 ,则粒子按式 (5) 和式 (6) 更新当前速度和位置 。
粒子群算法是一种新兴的基于群集智能的进化算法 , 已在神经网络训练 、模糊系统控制和多目标函数优化[6] 等 领域取得了广泛的应用 。与遗传算法相比 , PSO 和 GA 都 具有强大的隐并行搜索性能 。由于 PSO 基于单个粒子与
3 收稿日期 :2008204209 ;修订日期 :2008209212 基金项目 :国家自然科学基金资助项目 (60634020) 作者简介 :欧微 (19832) ,男 ,湖南邵阳人 ,硕士生 ,研究方向为粒子群算法与优化调度 ;邹逢兴 ,教授 ,研究方向为控制理论与控制工 程 、检测技术与自动化装置 、智能算法与优化调度等 ;高政 ,副教授 ,研究方向为图像处理与模式识别 、数据挖掘与智能算法等 ;徐晓 红 ,高级实验师 。 通讯地址 :410073 湖南省长沙市国防科技大学机电工程与自动化学院 ; Tel :13975849475 ; E2mail :ouweiwlmq @163. co m Address :School of Mechat ronics Engineering and Auto mation , National Universit y of Defense Technology , Changsha , Hunan 410073 ,P. R. China
based on t he fit ness crowd degree is p resented. Finally , t he effectiveness of MO PSO is demonst rated by numerous simula2
tio n experiment s.
关键词 :生产调度 ;混合流水车间 ;多目标优化 ;粒子群算法 ; Pareto 最优解 ;进化计算
摘 要 :混合流水车间调度问题 H FSP 是一种具有很强应用背景的生产调度问题 。本文给出了一种 H FSP 多目标调
度模型 ,提出了一种针对该类问题的多目标粒子群算法 。该算法采用基于 Pareto 支配关系的极值更新策略 ;采取对自适
应惯性权重递减和对种群变异的方法以保持种群多样性 ;设置 Pareto 解池保存计算中出现的 Pareto 最优解 ,并提出了一
机器进行加工是降低产品次品率的有效方法 :
S Mj
∑∑ Maxmize (
N kj E jk )
(4)
j =1 k =1
其中 , N kj 表示加工第 j 道工序的第 k 台机器加工工件的个
数 , Ejk 表示该机器的品质属性 。式 (4) 表示调度目标为最
大化品质较优机器的加工任务 。
2 问题描述
A multi2o bjective scheduling model of H FSP is p ut forward in t his paper , and a multi2o bjective particle swarm optimizatio n
(MO PSO) algo rit hm is p ropo sed. This algorit hm adopt s an updating st rategy based on t he Pareto dominance relatio nship ,
Key words :p roduction scheduling ; hybrid flow2shop scheduling ; multi2objective optimizatio n ; particle swarm optimiza2
tio n ; Pareto optimum solution ;evolutionary algo rit hm
vid ( t + 1) = wv id ( t) + c1 ran d1 () ( rbest id - x id ( t) ) +
c2 ran d2 () ( gbest d - x id ( t) )
(5)
x id ( t + 1) = xid ( t) + vid ( t + 1)
H FSP 问题可以描述为 : N 个工件在流水线上进行 S
道工序的加工 ,每个工序有 M j ( M j ≥1) 台并行机 ,每个工 件各道工序都可以在相应阶段上的任意一台机器上加工 , 要求确定并行机器的分配情况和同一机器上工件的加工顺
序 ,使得多个调度目标得以优化[4] 。 缩短生产周期 、优化资源配置和降低产品的次品率是
种基于适应度拥挤度的聚类算法优化解的分布特性 。实验结果表明 ,本文算法是求解 H FSP 问题的一种有效方法 。
Abstract :The hybrid flow2shop scheduling p roblem ( H FSP) is a scheduling p roblem wit h st ro ng application background.
生产系统的三个最重要的调度目标 。缩短生产周期可以提
高系统的生产能力 ,并能增加系统的柔性 ;减少设备空转时 间可以减少资源浪费 ,提高设备的使用寿命 ,降低单位产品 的生产成本和能源消耗 ;降低产品的次品率可以减少次品
返厂加工的人力 、原料和能源消耗 。因此 ,对调度目标描述 如下 :
(1) 缩短生产周期 。即最小化最大流程时间 :
N
Minmize ( Max ( CiS ) )
(2)
i =1
其中 , CiS 表示工件 i 的第 S 道工序 (最后一道工序) 的完工
时间 。式 (2) 表示调度目标为使得所有工件中的最大完工
时间最小化 。
(2) 减少设备空转时间 。一般情况下 ,考虑到开启和停 止设备带来的消耗 ,设备一旦开启 ,则在所有加工任务完成
文献[2 ]证明 ,即使是单目标两阶段中只有一个阶段有 并行机的 HFSP 问题也属于 NP2hard 问题 。鉴于问题的复
杂性 ,很难用一般的数学规划方法进行求解 。科学的调度方 法一直是研究的重点 ,近年来 ,启发式方法[3] 、遗传算法 ( Ge2 netic Algorithm ,简称 GA) [4] 和粒子群算法 ( Particle Swarm Optimization ,简称 PSO) [5] 等智能算法在求解单目标 HFSP 问题时表现出了较好的性能 。但是 ,对于实际问题 , HFSP 往往需要综合考虑生产成本 、资源能耗和产品周期等多个因 素 ,而且各因素之间往往会存在冲突 ,属于多目标优化问题 (Multi2Objective Optimization Problem ,简称 MOP) 。
and int roduces a self2adaptive inertia weight and mutation app roach to keep t he diversity of t he pop ulation , t he also designs
a Pareto optimal set pool to p reserve t he dominance solutio ns fo und in t he evolution p rocess. Then a clustering algo rit hm
基于多目标粒子群算法的混合流水车间调度方法研究3 A Hybrid Flow2Shop Scheduling Approach
![基于遗传算法与粒子群算法相结合的流水车间调度方法[发明专利]](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/973e9b3415791711cc7931b765ce05087632751f.webp)
