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

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

Lagrangian relaxation algorithm for scheduling problems of reentrant hybrid flow shops

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.