推荐星级：
- 1
- 2
- 3
- 4
- 5
带等待时间约束并行机调度问题的Copula分布估计算法
资料介绍
本文针对一类带等待时间约束的不相关并行机调度问题,提出了一种基于Copula函数的分布估计算法.该算法以同类订单工件数与总工件数的比值为变量,对每台机器构造了一个Copula函数,进而建立了优势种群的概率模型.基于概率模型通过采样生成子代个体编码向量组,保留了父代种群的相对位置信息.从理论上分析了所提出算法的时间复杂度,其随工件个数的增加呈对数增长.通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.
部分文件列表
| 文件名 | 大小 |
| 带等待时间约束并行机调度问题的Copula分布估计算法.pdf | 1M |
部分页面预览
（完整内容请下载后查看）12
Vol． 45 No． 12
Dec． 2017
第
期
电
子
学
报
2017
12
ACTA ELECTRONICA SINICA
年
月
带等待时间约束并行机调度问题的
Copula
分布估计算法
， ，
曹政才 林诚然 黄 冉
(
，
北京化工大学信息科学与技术学院 北京
100029)
:
，
本文针对一类带等待时间约束的不相关并行机调度问题 提出了一种基于
Copula
函数的分布估计算
摘
要
． ，
法 该算法以同类订单工件数与总工件数的比值为变量 对每台机器构造了一个
Copula ，
函数 进而建立了优势种群的
． ， ．
概率模型 基于概率模型通过采样生成子代个体编码向量组 保留了父代种群的相对位置信息 从理论上分析了所提
， ．
出算法的时间复杂度 其随工件个数的增加呈对数增长 通过基于实例的数值仿真以及与已有算法的比较验证了所提
．
算法的有效性和鲁棒性
:
;
; Copula
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
并行机调度 等待时间约束
理论 分布估计算法 对数时间复杂度
0372-2112 ( 2017) 12-2949-08
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 12． 017
:
TP273
:
A
:
文章编号
文献标识码
电子学报
An Estimation of Distribution Algorithm Based on Copula for
Parallel Machine Scheduling with Constrained Waiting Time
CAO Zheng-cai，LIN Cheng-ran，HUANG Ran
( College of Information Science and Technology，Beijing University of Chemical Technology，Beijing 100029，China )
Abstract: This paper proposes an estimation of distribution algorithm based on Copula for solving parallel machine
scheduling problem with constrained waiting time． By considering the ratios of each class of orders to total lots as variables，
a Copula function is constructed for each machine，and then the probability model of the dominant population is established．
This algorithm generates individual coding vector group by sampling based on the probability model，and preserves the rela-
tive location information of the parent population． The time complexity of the proposed algorithm is analyzed，which increa-
ses logarithmically as the number of lots raises． Simulation results based on some instances and comparisons with some exist-
ing algorithms demonstrate the effectiveness and robustness of the proposed algorithm．
Key words: parallel machines scheduling; constrained waiting time; copula; estimation of distribution ( EDA)
， ，
和调度目标的依赖性较强 通用性差 且难以保证解的
1
引言
［5］
．
，
精确算法在理论上能得到最优解 但其计算时
质量
，
在工业生产过程中 每台机器可加工的工件种类
， ，
间过长 难以满足实际生产线的需求 通常只适用于小
［1，2］
，
常受工艺约束 各机器加工能力也不尽相同
．
特别
． ，
规模问题 近年来 智能计算方法被广泛应用于求解并
［6，7］
，
地 某些工件在机器缓冲区内还受等待加工时间的限
， ( GA) 、
如 遗 传 算 法 粒 子 群 算 法
行机 调 度 问 题
． ， ．
制 若等待时间过长 产品次品率将会大幅提高 因此
，
( PSO ) 、
模 拟 退 火 算 法
( SA ) 、
差 分 进 化 算 法
［8，9］
对带等待时间约束的不相关并行机调度问题进行研究
( DE)
．
等
［3，4］
．
具有重要的理论意义和经济价值
( EDA)
分布估计算法
是一种新颖的群体进化算
早期求解并行机调度问题的方法主要是启发式方
， ，
法 其利用统计学方法从全局建立解的概率模型 具有
． ，
法和精确算法 启发式方法可快速求解 但对调度环境
、 、 ，
全局收敛 适用于非线性 高维度问题求解的优点 近年
: 2016-11-03;
: 2017-01-13 ;
:
责任编辑 梅志强
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No． 51375038，61403018) ;
( No． 20130010110009) ;
北京市自
高等学校博士学科点专项科研基金博导类资助课题
( No． 4162046)
然科学基金
2950
2017
年
电
子
学
报
［10］
，
．
前的该机器所花费的整定时间之和 则所有工件的总
来已成为了国内外学者的研究热点
在神经网络设
［11，12］
、 、 、
计 特征选择 模式匹配 车间调度
:
超限等待时间为
等诸多领域得
GA ，
m
v
r－1
． ， ［13］ EDA
到了广泛应用 例如 文献 将
与
相结合
T
=
( ( T
∑ ∑ ∑ a( k，u)
) )
( 2)
t1
EDA
给出一种求解时间约束不相关并行机问题的混合
k = 1
r = 2
u = 1
k
设备 的完工时间为
:
;
算法 文献
［14］ Copula
EDA
，
将
函数应用于
． Copula EDA
算法解的质量 尽管
算法 有效
v
EDA
地改善了
等智能
T
=
t
∑
a( k，u)
( 3)
k
u = 1
，
算法凭借优异的寻优能力取得较好的效果 但该类算
:
最小完工周期为
，
法普遍存在时间消耗偏高的缺点 当问题规模变大后
，
T = max( T ) ，k = 1，2，…，m
k
( 4)
t2
．
难以满足实时调度的要求
本文针对一类具有等待时间约束的不相关并行
( 2)
( 4) ， :
本文优化目标为
结合式
和式
Z = min( T + W·T )
t2
( 5)
t1
，
机调度问题 以最小化完工周期和超限等待时间为
W
其中 为归一化系数
．
，
目标 研究一种基于
Copula
理论的多种群混合分布
( Multi Subpopulation with Hybrid Estimation
估计算法
of Distribution Algorithm based on Copula，MHEDAC) ．
3
MHEDAC
及时间复杂度分析
MHEDAC
本小节介绍
算法求解带等待时间约束的
，
该算法的优势在于不仅可以改善解的质量 同时可
． MHEDAC
Copu-
核心在于构建
不相关并行机调度问题
，
降低算法的时间复杂度 其随工件个数增长而对数
la
， Copula
函数 由
．
函数建立优势种群的概率模型 该算
．
增长
，
法优势在于不仅可改善解的质量 同时可降低时间复
2
问题描述
． 1
杂度 算法结构如图 所示
．
1
图
中粗框部分的主要作用在于在保证算法的收
I = { 1，2，…，i}
，M = { 1，
为待加工工件集合
设
．
敛速度的前提下避免陷入局部最优 但若选择个体数
2，…，m}
，
为并行机器集合 每个工件仅 需 经 一 道 工
．
量过多可能无法保证种群进化方向
3. 1
编码和解码
． 5
序即可完成加工 在加工过程中存在如下 类约束
:
( 1)
:
等待时间约 束 工 件 在 设 备 缓 冲 区 内 的 等 待 时
，
根据并行机调度问题特点 对机器分配和工件排
．
间不应超过一个预设的值 例如在半导体生产线中
，
．
序分别进行编码
，
多晶硅氮化层在淀积工序之前 若等待时间过长容
［15］
2 ， 1 ［16］
如图 所示 其中第 部分采用文献 提出的轮
，
易被氧化
因此在多晶硅氮化层生成后必须设置
， ，
盘赌方式的整数编码 保证编码自动满足工艺约束 避
，
一个有限的等待时间 否则会导致次品率增加
． ( 2 )
． 2
免产生不可行解 第 部分采用
0-1
，
的小数编码 数字
: ，
工艺约束 每台机器可加工的工件种类不确定 至少
，
越小 工件加工优先级越高
．
，
有一类工件可以在多台机器上进行加工 且同一工
1 ，
解码方式以表 的问题实例为例说明 该实例共有
．
件在不同的机器上加工所需的时间各不相同 一台
5
，10 82 ． 13
台机器与 个工件 第一类订单包含
类订单
，
机器同一时刻只能加工一件工件 加工一旦开始不
， 5 ， ．
个工件 第二类订单包含 个工件 类推 同类订单工
，
能中断 不同工件的加工没有先后约束
． ( 3)
设备故
． 1 5，
件属性相同 设某个体的编码第 位为 该编码位置
: ，
障约束 假定机器发生故障的概率服从泊松分布 且
1 ～ 13
， 1 ， 6
之间 对应第 类订单的工件 共有 台可行
在
． ( 4)
:
故障修复时间为一个预先确定的数
整定时间
在不同类的工艺菜单间进行切换时 机器需要一个
． ( 5)
，
机可加工该工件 分别是机器
3，4，5，6，8，9．
1
按照均
将
，
6 ，
等概率分成 份 每份
0. 167．
5
+
用编码值 除以机器数
( 0. 334 0. 501
之
:
到达时间 各类的工件进
预先确定的整定时间
1，
得到
5 /11 = 0. 455， 3
落在第 份
与
，
入并行机群进行加工的时间为到达时间 它是一个
) ， 1 5．
故将工件 分配给机器
间
，
预先给定的数 可能各不相同
．
3. 2
种群初始化
，
种群初始解对算法性能有一定影响 为保证解空
k
设机器 上共有
v( v i)
， r(
≤
≤
个工件进行加工 第
a( k，r) ，t a( k，r)
在机
v)
个加工的工件记为
，t a ，
是工件 的等待时间约束 则工
a
为工件
a( k，r)
，
间均匀性 本文使用均匀分布随机产生初始解
．
k
器
件
上的加工时间
3. 3 Copula
构建
函数
a( k，r)
T
:
为
的超限等待时间
a( k，r)
，
对于每一台机器 通过
Copula
函数获取其各类订
D
， D
＞ 0
a( k，r)
a( k，r)
a( k，r)
T
=
( 1)
a( k，r)
单工件数所占该机器加工的总工件数比例的概率模
Copula
{
0，
D
0
≤
．
型 再额外构建一个
，
函数 构建各机器加工的工
r－1
，D
=
t
+ T
－ t ，T
a
其中
为加工该工件
．
件数占所有工件数比例的概率模型
a( k，r)
∑
a( k，u)
setup
setup
u = 1
全部评论(0)