Solving the Fm|block|Cmax problem using Bounded Dynamic Programming

被引：20
作者：
Bautista, Joaquin [1 ]
Cano, Alberto [1 ]
Companys, Ramon [2 ]
Ribas, Imma [2 ]
机构：
[1] Univ Politecn Cataluna, Escola Tecn Super Engn Barcelona, Nissan Chair, E-08028 Barcelona, Spain
[2] Univ Politecn Cataluna, Escola Tecn Super Engn Barcelona, Dept Org Empreses, E-08028 Barcelona, Spain
来源：
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE | 2012年 / 25卷 / 06期
关键词：
Blocking flow shop; Scheduling; Production; Logistics; Dynamic programming; Meta-heuristics; FLOW-SHOP PROBLEM; LIMITED BUFFERS; SCHEDULING PROBLEMS; SEQUENCING PROBLEM; ASSEMBLY-LINE; CYCLE TIME; NO-WAIT; ALGORITHM; MACHINE; STORAGE;
D O I：
10.1016/j.engappai.2011.09.001
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present some results attained with two variants of Bounded Dynamic Programming algorithm to solve the Fm vertical bar block vertical bar C-max problem using as an experimental data the well-known Taillard instances. We have improved the best known solutions for 17 of Taillard's instances, including the 10 instances from set 12. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1235 / 1245
页数：11
相关论文
共 31 条
[1]   Minimizing cycle time in a blocking flowshop [J].
Abadi, INK ;
Hall, NG ;
Sriskandarajah, C .
OPERATIONS RESEARCH, 2000, 48 (01) :177-180
[2]   Heuristics and exact algorithms for solving the Monden problem [J].
Bautista, J ;
Companys, R ;
Corominas, A .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (01) :101-113
[3]   Solving mixed model sequencing problem in assembly lines with serial workstations with work overload minimisation and interruption rules [J].
Bautista, Joaquin ;
Cano, Alberto .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 210 (03) :495-513
[4]   A dynamic programming based heuristic for the assembly line balancing problem [J].
Bautista, Joaquin ;
Pereira, Jordi .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 194 (03) :787-794
[5]   Minimizing makespan in a blocking flowshop using genetic algorithms [J].
Caraffa, V ;
Ianes, S ;
Bagchi, TP ;
Sriskandarajah, C .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2001, 70 (02) :101-115
[6]   AN IMPROVED DISCRETE DYNAMIC-PROGRAMMING ALGORITHM FOR ALLOCATING RESOURCES AMONG INTERDEPENDENT PROJECTS [J].
CARRAWAY, RL ;
SCHMIDT, RL .
MANAGEMENT SCIENCE, 1991, 37 (09) :1195-1200
[7]   Different behaviour of a double branch-and-bound algorithm on Fm|prmu|Cmax,, and Fm|block|Cmax problems [J].
Companys, Ramon ;
Mateo, Manel .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (04) :938-953
[8]  
Gilmore P.C., 1991, TRAVELING SALESMAN P, P87
[9]   SEQUENCING 1 STATE-VARIABLE MACHINE - SOLVABLE CASE OF TRAVELING SALESMAN PROBLEM [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1964, 12 (05) :655-&
[10]   The permutation flow shop problem with blocking. A tabu search approach [J].
Grabowski, Jozef ;
Pempera, Jaroslaw .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2007, 35 (03) :302-311
1234