A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles

A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles

0.00 Avg rating0 Votes
Article ID: iaor20108504
Volume: 38
Issue: 5
Start Page Number: 876
End Page Number: 888
Publication Date: May 2011
Journal: Computers and Operations Research
Authors: , ,
Keywords: production
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.

Reviews

Required fields are marked *. Your email address will not be published.