首页 | 本学科首页   官方微博 | 高级检索  
     


A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles
Authors:Tatsushi Nishi  Yuichiro Hiranaka  Ignacio E. Grossmann
Affiliation:1. Division of Mathematical Science for Social Systems, Department of Systems Innovation, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka City, Osaka 560-8531, Japan;2. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Abstract:We address a bilevel decomposition algorithm for solving the simultaneous scheduling and conflict-free routing problems for automated guided vehicles. The overall objective is to minimize the total weighted tardiness of the set of jobs related to these tasks. A mixed integer formulation is decomposed into two levels: the upper level master problem of task assignment and scheduling; and the lower level routing subproblem. The master problem is solved by using Lagrangian relaxation and a lower bound is obtained. Either the solution turns out to be feasible for the lower level or a feasible solution for the problem is constructed, and an upper bound is obtained. If the convergence is not satisfied, cuts are generated to exclude previous feasible solutions before solving the master problem again. Two types of cuts are proposed to reduce the duality gap. The effectiveness of the proposed method is investigated from computational experiments.
Keywords:Bilevel decomposition   Lagrangian relaxation   Scheduling   Routing   Automated guided vehicle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号