没有合适的资源?快使用搜索试试~ 我知道了~
混合离散教与学算法求解复杂并行机调度问题.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 18 浏览量
2023-02-23
16:51:01
上传
评论
收藏 326KB DOCX 举报
温馨提示
试读
25页
混合离散教与学算法求解复杂并行机调度问题.docx
资源推荐
资源详情
资源评论
智能制造是解决我国制造业由大变强的根本路径, 有效地生产调度优化算法是提高企
业效率和竞争力的重要途径, 属于智能制造的重要研究领域.并行机调度问题(Parallel
machine scheduling problem, PMSP)是制造行业中的一类典型生产调度问题.该类问题不仅需
要确定每个工件的加工机器, 还需要确定每台机器上相应工件的加工顺序
[1]
. Allahverdi
[2]
将
并行机分为三个类别:相同并行机, 均匀平行机和不相关并行机.在实际生产制造或加工过程
中, 许多问题可抽象为带不同约束的上述三类并行机调度问题.其中, 带到达时间、多工
序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with
arrival time, multiple operations, process restraints and sequence-dependent setup times,
PMSP_AMPS), 是模具制造
[3]
、半导体芯片终端测试阶段
[4]
、塑料加工
[5]
等行业中广泛存在
的一类复杂并行机调度问题, 属于带不同约束的不相关并行机调度问题.显然, 在计算复杂
度上, 并行机问题已被证明为 NP-Complete 问题
[6]
, 而该问题又归约为 PMSP_AMPS, 故
PMSP_AMPS 属于 NP-Complete 问题. PMSP_AMPS 是不相关并行机中非常复杂的一类, 很
多其他并行机调度问题均可归约为该类问题.因此, 研究求解 PMSP_AMPS 的有效算法具有
较大的工程意义和理论价值.
并行机调度问题可建立两类问题模型.一类是 0-1 数学规划模型, 由目标函数和多条显
式约束组成, 其对应的求解算法主要为分支定界、列生成
[7-10]
等运筹学算法.该算法可在几分
钟至几十分钟内求解较小规模问题(工件数小于等于 30), 同时经过合适设计, 也可用于求解
较大规模问题(工件数大于等于 100), 但往往求解时间较长.由于问题具有非凸特性, 目前尚
无通用的最优解多项式时间求解算法, 故求解质量取决于具体问题的复杂度以及算法设计
者对该问题结构的理解程度, 算法要在较短时间获取满意解的难度较大.另一类是排序模型,
该类模型相对数学规划模型来说则较为简单, 由几个计算各工件在不同机器上的开始加工
时间的式子组成, 约束隐式包含在问题解的排序编码中, 其对应的求解算法主要为基于动态
规划的近似算法
[11-13]
和各种智能优化算法.基于动态规划的近似算法需要所求解的问题能提
出可构造状态递推方程的、确保最优解不丢失的规则方可使用.这使其应用主要集中在可行
状态较少、能提出相应规则的单机、并行机等调度问题上, 优点在于可确保算法获得问题
的最优解, 具有较大理论意义.但由于该算法本质上仍属于穷举法, 其计算时间复杂度大多
为指数型, 难以实际应用.智能优化算法利用某种拟人、拟物的机制来引导算法执行搜索,
往往在几秒或十几秒就能获得各类调度问题的满意解.正是由于智能算法具有性能好、求解
时间短、适用面广的优点, 使其近年得到广泛研究和应用.
目前, 各种智能优化算法已被设计用于求解包括并行机在内的大量生产调度问题, 并
取得良好效果.但是, 各类文献对所提算法使用少量个体(一般种群规模为 20 ∼∼ 100)运行少
量代数(一般进化代数为 100 ∼∼ 500 代)后, 为何都可获得问题的满意解, 基本都只从各自
算法本身的机制、特点进行解释, 而忽略了该类算法所采用的排序模型对求解质量的重要
影响.这导致了很多后续研究者过于追求方法和技巧上的创新.实际上, 智能优化算法为何有
效, 是由所采用排序模型的解空间和解的特点, 以及智能优化算法自身机制共同决定的.
在排序模型的解空间方面, 调度问题的目标值变化范围远远小于排序模型解空间的规
模.譬如, 对于智能优化算法求解最多的优化目标为最小化最大完工时间的置换流水线调度
问题, 假如有 50 个工件, 5 台机器, 每个工件在每台机器上的加工时间为在间均匀分布的随
机数, 则其目标值变化范围在之内(25 000 为各工件在各机器上的加工时间之和, 实际的最
大目标值小于此值), 而解空间规模为 50!50!, 平均每一个具体目标值对应约
1.2×10601.2×1060 个不同排列或解, 这表明数量巨大的不同解具有相同的目标值.对于其他
类型的调度问题(包括本文研究的并行机问题)同样存在上述情况.因此, 调度问题的排序模
型解空间是一个"巨大"和"极为扁平"的空间.该空间规模"巨大", 内部遍布各种不同的山峰
(峰顶为局部极大解)和低谷(谷底为局部极小解), 而最高峰顶(全局极大解)和最低谷底(全局
极小解)之间的差值相对于整个空间的规模来说又非常小, 这使得整个空间呈现出"极为扁平
"的形态, 即空间中大量不同的位置(对应不同的解)会具有相同的目标值.另外, 就排序模型
的解(即排列或个体)而言, 解与解之间没有梯度, 两个相似解的目标值也可能差别较大.排序
模型解空间的"极为扁平"性, 以及解与解之间"无梯度"性, 使得任何带保优的随机搜索只需
用较短时间搜索解空间中极小的区域(类似足球场中 1 根针面积甚至更小的区域), 却可能到
达较广的目标值区域.各种智能优化算法均是在带保优的随机搜索基础上, 增加了自身的寻
优机制.这使此类算法不仅可短时间内搜索较广的目标值区域, 而且其内在的寻优机制可推
动算法到达目标值较小的不同区域搜索, 从而获得问题的满意解.智能优化算法这种通过对
排序模型解空间极小区域的搜索来实现对目标值较大、较优区域的搜索, 是其有效地本质
原因, 也是现有运筹学算法和基于动态规划的近似算法这些偏遍历或部分遍历解空间的算
法难以做到的.因此, 采用智能优化算法求解复杂调度问题是合理且必要的.
对于基于排序模型的复杂并行机调度问题, 智能优化算法在过去几年中已有较多的研
究. Woo 等
[14]
针对在处理时间不断恶化下带多个机器维护阶段的并行机调度问题, 提出一种
融合了改进启发式操作的基于规则的遗传算法(Genetic algorithm, GA)来求解, 以此增强解
的高效性. Avalos-Rosales 等
[15]
针对带序相关设置时间的不相关并行机调度问题, 提出了一
种基于多启动和变邻域下降的元启发式算法.张嘉琦等
[16]
针对并行机动态调度问题, 引入问
题分解思想和评价策略, 提出了一种基于差分进化算法与代理模型相结合的快速求解方法.
Chen
[17]
针对带不相等准备时间和序相关设置时间的不相关并行机问题, 提出了几种迭代混
合元启发式算法进行求解. Damodaran 等
[18]
提出一种微粒群优化算法(Particle swarm
optimization, PSO)求解不相关并行批处理机问题, 测试结果表明该算法在求解大规模问题
时, 能在较短时间内找到优质解. Diana
[19]
提出了一种基于变邻域下降的混合免疫算法求解
带序相关设置时间的不相关并行机调度问题. Sels 等
[20]
针对不相关并行机调度问题, 提出了
融合禁忌搜索、遗传算法和截断分支定界法的混合算法, 通过标准测试问题表明了所提算
法的有效性. Bitar 等
[21]
针对半导体制造中的不相关并行机调度问题, 提出了一种文化基因算
法, 在合理的测试时间内求得了较好的解. Joo 等
[22]
提出了三种分配规则的混合遗传算法,
求解带序相关设置时间和产品约束的不相关并行机调度问题, 通过对比实验验证了算法的
高效性和鲁棒性.罗家祥等
[23]
提出一种基于变深度环交邻域结构的迭代搜索算法, 用于求解
不相关并行机调度问题, 仿真实验验证了算法计算结果十分接近问题的下界. Lin 等
[24]
提出
了一种混合人工蜂群算法求解带序相关设置时间的不相关并行机调度问题.由文献调研可知,
尚无智能优化算法求解 PMSP_AMPS 的相关研究.
对于 PMSP_AMPS 这一类复杂并行机调度问题, 无论是运筹学方法还是基于动态规划
的近似算法均难以在较短时间内有效求解, 故有必要设计相应的智能优化算法.教与学算法
(Teaching-learning-based optimization, TLBO)是一种基于群体智能的连续随机优化算法, 最
早由 Rao 等
[25]
于 2011 年提出.它模拟了教师给学员的教学过程和学员的学习过程, 目的是
通过教师的"教"和学员之间的相互"学"来提高学员的学习成绩. TLBO 参数少、算法简单、
易理解、搜索能力较强
[26]
.对于制造过程调度问题(即一类典型的离散优化问题), 现有的
TLBO 求解算法分为两类: 1)以标准的连续 TLBO 为基础, 通过一定的编码和解码方式实现
离散问题解空间到连续空间的映射, 在"教"、"学"阶段, 对个体的更新仍采用传统的连续运
算准则; 2)利用 TLBO 的基本思想, 重新定义"教"、"学"阶段中个体的离散更新方式, 使算
法可直接用于离散解空间的搜索, 这类算法称为离散 TLBO (Discrete TLBO, DTLBO).近年
TLBO 和 DTLBO 在生产调度领域均已有初步研究, 在 TLBO 方面, Shao 等
[27]
针对零等待流
水车间调度问题, 提出了一种基于高斯分布的扩展教与学算法, 建立反向学习机制和高斯概
率模型实现对个体的更新, 并加入基于模拟退火和插入操作的局部搜索, 通过对标准测试问
题的仿真实验验证了所提算法的有效性. Xu 等
[28]
针对带模糊加工时间的柔性作业车间调度
问题, 提出了一种有效地 TLBO 算法, 通过加入交叉操作和局部搜索以增强算法的性能.在
DTLBO 方面, Shao 等
[29]
提出了一种混合离散优化算法求解零等待流水车间调度问题, 采用
前向、后向插入操作模拟教学阶段, 同时将学习阶段用 2 维分布估计算法替换, 并使用基于
3 种邻域结构的局部搜索来增强算法的搜索能力, 仿真实验验证了其算法的鲁棒性和有效
性. Li 等
[30]
针对流水线重调度问题, 提出离散教与学算法进行求解, 在"教"、"学"阶段分别
定义了 2 种较复杂的离散操作, 并在每个阶段都采用同一种迭代贪心局部搜索来提高算法
性能, 所提算法在与 5 有效算法的对比中优势明显.文献调研表明, DTLBO 求解并行机调度
问题的研究处于空白状态.
已有的 TLBO 和 DTLBO 与大多数文献中的连续域智能调度算法一样(包括前一段中
求解并行机问题的连续域智能算法), 均过于强调原有机制的完整保留, 要么采用一定的编
码和解码方式实现原算法从连续空间搜索到离散空间搜索的映射(譬如文献[27-28]), 要么在
离散化时不够彻底和直接(譬如文献[27-28]), 从而导致全局搜索的实际效率并不高.因此, 本
文设计一种离散化更为彻底的 DTLBO, 直接用大部分智能调度算法实际执行搜索的排序操
作(即交叉、插入、交换等)来对 TLBO 进行离散化, 以实现对解空间更有效率的搜索.具体
来说, 本文提出一种混合离散教与学优化算法(Hybrid discrete teaching-learning-based
optimization, HDTLBO), 求解以最小化最大完工时间为目标的 PMSP_AMPS. HDTLBO 设计
了针对问题解的多种排序操作, 在保持标准教与学算法更新机理的前提下实现算法的离散
化.首先, 在算法初始化阶段, 将工件排序(即问题的解)作为种群中的个体, 随机初始化种群,
这样有利于确保算法初期搜索的分散性; 其次, 设计了不同的排序操作以实现对标准 TLBO
两阶段更新公式的离散化, 使算法能直接在离散解空间中进行基于 TLBO 机理的有效全局
搜索, 明显增强了算法的全局搜索效率; 最后, 采用 Interchange 和 Insert 邻域操作设计了一
种有效地变邻域局部搜索, 进一步增强了算法的局部搜索能力.通过对不同测试问题的仿真
实验和算法比较验证了 HDTLBO 的有效性和鲁棒性.
1. 问题描述
第 1.1 节建立 PMSP_AMPS 的排序模型, 第 1.2 节给出该模型的一个示例.
1.1 问题模型
PMSP_AMPS 可描述如下: nn 个产品或工件在 mm 台设备上进行加工.每种产品需要
sjsj, j∈(1,2j∈(1,2, ⋯,l)⋯,l)道加工工序, , ⋯,sl]⋯,sl]表示所有产品的工序数所构成的集合, 同
种产品的不同工序需要按先后顺序加工; 所有工序只能由满足加工约束的设备进行加工;
产品的加工时间与加工设备有关, 任何设备同一时刻只能加工一种产品; 不同产品间带序相
关设置时间, 其依赖于加工顺序, 同种产品间的设置时间为 0.
令 TSTS 为所有产品的总工序数, π=[π1,π2π=[π1,π2, ,πj∈(1,2,⋯,n),πj∈(1,2,⋯,n)为待加
工的 nn 个工件基于工序的排列(该排列中的工件从左往右根据一定的规则及并行加工约束
分配到相应的机器上加工), 也是问题的决策变量, TiTi 为第 ii 台设备上加工的工序总数, 为
第 ii 台设备上所加工工件基于工序的排列; P(πT(i)k)P(πkT(i))为 πT(i)kπkT(i)的加工时
间; St(πT(i)k)St(πkT(i))为 πT(i)kπkT(i)的开始加工时间
(St(πT(i)0)=0)(St(π0T(i))=0); S(πT(i)k−1,πT(i)k)S(πk−1T(i),πkT(i))为 πT(i)k−1πk−1T(i)与
πT(i)kπkT(i)之间的序相关设置时间, 当 k>1k>1 且 πT(i)k−1=πT(i)kπk−1T(i)=πkT(i)时
S(πT(i)k−1,πT(i)k)=0)S(πk−1T(i),πkT(i))=0); pre_m(πT(i)k)pre_m(πkT(i))为 πT(i)kπkT(i)前一
次加工所用的设备号, pre_k(πT(i)k)pre_k(πkT(i))为 πT(i)kπkT(i)在前一次加工设备上的排列
πT(pre_m(πT(i)k))πT(pre_m(πkT(i)))中从左往右的位置, (当 πT(i)kπkT(i)是首次加工
时, pre_m(πT(i)k)=0,pre_k(πT(i)k)=0pre_m(πkT(i))=0,pre_k(πkT(i))=0); R(πT(i)k)R(πkT(i))是
工件 kk 首次到达第 ii 台设备的时间.
根据上述定义, 建立如下排序模型, 优化目标为在所有产品排序的集合中找到一个最
优排序 π∗π∗, 使得最早完工时间最小, 即
Cmax(π)=max{St(πT(1)T1)+P(πT(1)T1),St(πT(2)T2)+P(πT(2)T2),⋯,St(πT(m)Tm)+P(πT(m)Tm)}Cmax(π)=max{St(πT1T(1))+P(πT1T(1)),St(πT2T(2))+P(πT2T(2)),⋯,St(πTmT(m))+P(πTmT(m))}
(1)
St(πT(i)k)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪max{St(πT(i)k−1)+P(πT(i)k−1)+S(πT(i)k−1,πT(i)k),R(πT(i)k)},若
pre_k(πT(i)k)=0max{St(πT(i)k−1)+P(πT(i)k−1)+S(πT(i)k−1,πT(i)k),St(πT(pre_m(πT(i)k))pre_k(πT(i)k))+P(πT(pre_m(πT(i)k))pre_k(πT(i)k))},其他
St(πkT(i))={max{St(πk−1T(i))+P(πk−1T(i))+S(πk−1T(i),πkT(i)),R(πkT(i))},若
pre_k(πkT(i))=0max{St(πk−1T(i))+P(πk−1T(i))+S(πk−1T(i),πkT(i)),St(πpre_k(πkT(i))T(pre_m(πkT(i))))+P(πpre_k(πkT(i))T(pre_m(πkT(i))))},其他
(2)
Cmax(π∗)=minm⊂ΠCmax(π)Cmax(π∗)=minm⊂ΠCmax(π)
(3)
π∗=arg{Cmax(π)}→min,∀π∈Ππ∗=arg{Cmax(π)}→min,∀π∈Π
(4)
其中, 式(1)和式(2)为最大完工时间 Cmax(π)Cmax(π)的计算公式, 式(3)和式(4)表示在
所有产品集合 ΠΠ 中找到最优排序, 使得 Cmax(π)Cmax(π)最小.
1.2 甘特图示例
由于 PMSP_AMPS 中部分产品需多工序加工, 故 HDTLBO 采用基于操作的编码方式
来表示个体或解.例如, 对于 n=5n=5, m=3m=3, 工序集合 St=[3,1,3,2,1]St=[3,1,3,2,1]的问
题, 可以表示该问题采用基于操作的编码方式的一个编码排列, 即第一个加工的工件为工件
1, 共有 3 个加工工序, 第二个加工的工件是工件 3, 共有 3 个加工工序, 以此类推.本文采用
最早完工时间(Early completion time, ECT)规则进行解码.现对
π=[1325413134]π=[1325413134]的解码操作举例说明, 排列 ππ 中各工件的工序加工约
束、序相关设置时间(s)和工件到达时间(s)如表 1 所示, 其中每个工件的不同操作可在 0 台
或多台机器上加工, 工序加工时间如表 2 所示.根据表 1、表 2 中所给数据, 结合 ECT 规
则可得 T1=4T1=4, T2=4T2=4, T3=3T3=3, 3 台机器分别对应的工件排序
为: ; ; [πT(3)1,πT(3)2]=[3,5][π1T(3),π2T(3)]=[3,5], 对应的甘特图如图 1 所示.
表 1 工序加工约束、序相关设置时间和工件到达时间表(ππ = [1 3 2 5 4 1 3 1 3 4])
Table 1 The schedule of process constraint, sequence setup time and arrival time (ππ =
[1 3 2 5 4 1 3 1 3 4])
可执行操作的设备
序相关设置时间
首次到达设备的时间
操作 1
操作 2
操作 3
工件 1
工件 2
工件 3
工件 4
工件 5
m1
m2
m3
工件 1
m1/m2
m1/m2/m3
m1/m3
—
83
38
39
47
35
34
23
工件 2
m1
—
—
53
—
66
45
25
38
78
98
工件 3
m3
m2/m3
m2
64
57
—
72
46
52
23
32
工件 4
m1/m3
m1
—
46
67
83
—
55
132
131
98
工件 5
m1/m3
—
—
40
66
83
77
—
114
99
112
下载: 导出 CSV
| 显示表格
表 2 工件加工时间表(ππ = [1 3 2 5 4 1 3 1 3 4]) (tt/s)
Table 2 The processing time table (ππ = [1 3 2 5 4 1 3 1 3 4]) (tt/s)
操作 1
操作 2
操作 3
m1
m2
m3
m1
m2
m3
m1
m2
m3
工件 1
62
44
—
78
86
26
48
—
87
工件 2
41
—
—
—
—
—
—
—
—
工件 3
—
—
31
—
58
65
—
42
—
工件 4
32
—
31
27
—
—
—
—
—
剩余24页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3649
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功