装配线物料搬运的拉格朗日松弛算法

Lagrangian relaxation algorithm for material handling problems of assembly lines

中文关键词  物料搬运  看板  调度  拉格朗日松弛

英文关键词  material handling  kanban  scheduling  Lagrangian relaxation

中文摘要

      为提高汽车制造企业混流装配线的运行效益, 提出了基于看板模型的多封闭循环路径多载量小车物料配送调度方法—–装配线物料配送调度的拉格朗日松弛算法. 首先对问题域进行了描述并做出了具体假设, 以最小化 配送系统总成本为目标, 建立了混合整数规划模型.在此基础上, 针对该模型提出了两种算法—–次梯度和随机步长拉格朗日松弛算法, 将松弛问题分解为两个决策子问题分别进行求解. 仿真实验表明提出的两种调度算法均适用于该研究问题域, 并在求解时间及稳定性上表现出良好的性能.

英文摘要

      To effectively enhance the performance of the mixed-model assembly line in automobile manufacture enterprises, a kanban model-based scheduling method of multi-close-loops dolly train material delivery, Lagrangian relaxation algorithm for material delivery problems of assembly lines, is proposed in this paper. First of all, a problem domain of multiple-close-loops dolly train material delivery is presented and a few assumptions of the problem are depicted in detail in the paper. Then, a mixed integer programming model is constructed, which aims to minimize the total expected cost of material delivery system. On that basis, two algorithms –- Lagrangian relaxation based on subgradient and Lagrangian relaxation based on random step –- are proposed for the mixed integer programming model, which both decompose the relaxed problem into two decision sub-problems both of which are solved respectively. Simulation experiments show that the two scheduling methods are fit to solving the problem and have a better performance in calculating time and stability.