| 引用本文: | 罗文冲,钱斌,胡蓉,张长胜,向凤红.超启发式交叉熵算法求解分布式装配柔性作业车间调度问题[J].控制理论与应用,2021,38(10):1551~1568.[点击复制] |
| LUO Wen-Chong,QIAN Bin,HU Rong,ZHANG Change-sheng,XIANG Feng-hong.Hyper-heuristic cross-entropy algorithm for distributed assembly flexible job-shop scheduling problem[J].Control Theory and Technology,2021,38(10):1551~1568.[点击复制] |
|
| 超启发式交叉熵算法求解分布式装配柔性作业车间调度问题 |
| Hyper-heuristic cross-entropy algorithm for distributed assembly flexible job-shop scheduling problem |
| 摘要点击 1704 全文点击 526 投稿时间：2021-01-06 修订日期：2021-08-31 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2021.10012 |
| 2021,38(10):1551-1568 |
| 中文关键词 分布式装配柔性作业车间调度 启发式方法 交叉熵算法 超启发式算法 |
| 英文关键词 distributed assembly flexible job-shop scheduling problem heuristics cross-entropy algorithm hyperheuristic algorithm |
| 基金项目 国家自然科学基金项目(62173169, 61963022, 51665025)资助. |
|
| 中文摘要 |
| 本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP), 建立问题模型, 以最小化最大完工
时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解. 首先, 设计基于工序序列、工厂分配和产品序
列的三维向量编码规则和结合贪婪策略的解码规则, 同时提出4种启发式方法以提高初始解的质量. 然后, 设计高低
分层结构的HHCEA, 高层为提高对搜索方向的引导性, 采用交叉熵算法(CEA)学习和积累优质排列的信息, 其中各
排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成; 低层为增加在解空间中的搜索深度, 将
高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制, 以此
作为一种新的启发式方法执行搜索. 最后, 通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP. |
| 英文摘要 |
| Aiming at a novel two-stage distributed assembly flexible job-shop scheduling problem (DAFJSP), this paper
establishes the problem model and proposes a hyper-heuristic cross-entropy algorithm (HHCEA) whose optimization
objective is to minimize the makespan. Firstly, a three-dimensional vector encoding rule based on process sequence, factory
assignment and product sequence and a decoding rule combined with greedy strategy are designed, meanwhile, four
heuristic methods are proposed to improve the quality of initial solutions. Then, a high and low stratified HHCEA is designed,
the upper layer for improving the guidance of the search direction, using the cross-entropy algorithm (CEA) to learn
and accumulate the information of the high-quality permutations which are composed of 11 heuristic operations (i.e., 11
effective neighborhood operations) and each heuristic operation is designed based on the characteristics of the problem;
and in order to increase the search depth in the solution space, the lower layer performs the search as a new heuristic
method by repeating the heuristic operation in each permutation which is identified by the upper layer for specified times
and adds a disturbance mechanism based on simulated annealing during the execution. Finally, simulations experiments
and comparisons demonstrate that HHCEA can effectively solve the DAFJSP. |
|
|
|
|
|