| 引用本文: | 周炳海,钟臻怡.可重入混合流水车间调度的拉格朗日松弛算法[J].控制理论与应用,2015,32(7):881~886.[点击复制] |
| ZHOU Bing-hai,ZHONG Zhen-yi.Lagrangian relaxation algorithm for scheduling problems of reentrant hybrid flow shops[J].Control Theory and Technology,2015,32(7):881~886.[点击复制] |
|
| 可重入混合流水车间调度的拉格朗日松弛算法 |
| Lagrangian relaxation algorithm for scheduling problems of reentrant hybrid flow shops |
| 摘要点击 3928 全文点击 1837 投稿时间：2014-07-01 修订日期：2015-04-24 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2015.40616 |
| 2015,32(7):881-886 |
| 中文关键词 可重入混合流水车间 调度 拉格朗日松弛 动态规划 |
| 英文关键词 reentrant hybrid flow shop scheduling Lagrangian relaxation dynamic programming |
| 基金项目 国家自然科学基金项目(61273035, 71471135), 国家高技术研究发展计划(“863”计划)项目(2009AA043000)资助. |
|
| 中文摘要 |
| 为了有效提升多重入车间的生产效率, 考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性, 提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法. 首先进行了问题域的描述, 并在此基础上以最小化加权完成时间为调度目标, 建立数学规划模型. 针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法, 使松弛问题分解成工件级子问题, 并使用动态规划方法建立递归公式, 求解工件级子问题. 随后, 使用次梯度算法求解拉格朗日对偶问题. 最后, 对各种不同问题规模进行了仿真实验, 结果表明, 所提出的调度算法能够在合理的时间内获得满意的近优解. |
| 英文摘要 |
| To effectively enhance the productivity of multi-reentrant workshops, we consider the importance of inspection and repair processes to reentrant production systems where products are manufactured layer by layer; and then, propose a scheduling method of reentrant hybrid flow shops based on Lagrangian relaxation algorithm. Firstly, a scheduling problem domain of reentrant hybrid flow shops is described and then a mathematical programming model is built with an objective of minimizing the total weighted completion time. A Lagrangian relaxation algorithm with relaxing machine capacity constraints is developed, which decomposes the relaxed problem into job-level sub-problems. Each sub-problem is solved by a dynamic programming method with dynamic programming recursive formulas. After that, the sub-gradient algorithm is used to solve the Lagrangian dual problem. Finally, simulation experiments in different problem scales are carried out to analyze the proposed algorithm. Results indicate that the proposed algorithm can obtain satisfactory near-optimal solutions within a reasonable time period. |
|
|
|
|
|