可重入混合流水车间调度的拉格朗日松弛算法

摘要：

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.

关键词：可重入混合流水车间、调度、拉格朗日松弛、动态规划

所属期刊栏目：32

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目61273035,71471135;国家高技术研究发展计划“863”计划项目2009AA043000资助.Supported by National Natural Science Foundation of China61273035,71471135;National High Technology Research and Development Program of China "863" Program2009AA043000

在线出版日期：2015-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：881-886