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

被引：93

作者：

Nishi, Tatsushi ^{[1
]}

Hiranaka, Yuichiro ^{[1
]}

Grossmann, Ignacio E. ^{[2
]}

机构：

[1] Osaka Univ, Grad Sch Engn Sci, Dept Syst Innovat, Div Math Sci Social Syst, 1-3 Machikaneyama, Toyonaka, Osaka 5608531, Japan

[2] Carnegie Mellon Univ, Dept Chem Engn, Pittsburgh, PA 15213 USA

来源：

COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 05期

关键词：

Bilevel decomposition; Lagrangian relaxation; Scheduling; Routing; Automated guided vehicle; DESIGN; MACHINES; SYSTEM;

D O I：

10.1016/j.cor.2010.08.012

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：876 / 888

页数：13

共 26 条

[1]

BENDERS JF, 1962, NUMER MATH, V4, P238, DOI [DOI 10.1007/BF01386316, DOI 10.1007/S10287-004-0020-Y]

[2] A time window approach to simultaneous scheduling of machines and material handling system in an FMS [J].

Bilge, U ;

Ulusoy, G .

OPERATIONS RESEARCH, 1995, 43 (06) :1058-1070

[3] VEHICLE SCHEDULING IN 2-CYCLE FLEXIBLE MANUFACTURING SYSTEMS [J].

BLAZEWICZ, J ;

BURKHARD, RE ;

FINKE, G ;

WOEGINGER, GJ .

MATHEMATICAL AND COMPUTER MODELLING, 1994, 20 (02) :19-31

[4] Scheduling and routing of automated guided vehicles:: A hybrid approach [J].

Correa, Ayoub Insa ;

Langevin, Andre ;

Rousseau, Louis-Martin .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (06) :1688-1707

[5]

Dotoli M, 2004, INT J PROD RES, V42, P1787, DOI [10.1080/00207540410001661364, 10.1080/00207540310001661364]

[6] Integrated production and material handling scheduling using mathematical programming and constraint programming [J].

El Khayat, Ghada ;

Langevin, Andre ;

Riopel, Diane .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 175 (03) :1818-1832

[7] A decomposition method for the simultaneous planning and scheduling of single-stage continuous multiproduct plants [J].

Erdirik-Dogan, M ;

Grossmann, IE .

INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH, 2006, 45 (01) :299-315

[8] Design and operational issues in AGV-served manufacturing systems [J].

Ganesharajah, T ;

Hall, NG ;

Sriskandarajah, C .

ANNALS OF OPERATIONS RESEARCH, 1998, 76 (0) :109-154

[9] Conflict-free scheduling and routing of automated guided vehicles in mesh topologies [J].

Ghasemzadeh, Hamed ;

Behrangi, Ehsan ;

Azgomi, Mohammad Abdollahi .

ROBOTICS AND AUTONOMOUS SYSTEMS, 2009, 57 (6-7) :738-748

[10]

Hiranaka Yuichiro, 2007, Transactions of the Institute of Systems, Control and Information Engineers, V20, P465, DOI 10.5687/iscie.20.465

← 1 2 3 →