Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search

被引：6
作者：
Pedersen, Christian R.
Rasmussen, Rasmus V.
Andersen, Kim A.
机构：
[1] Aarhus Univ, Dept Operat Res, DK-8000 Aarhus C, Denmark
[2] Aarhus Sch Business, Dept Accounting Finance & Logist, DK-8210 Aarhus V, Denmark
来源：
COMPUTERS & OPERATIONS RESEARCH | 2007年 / 34卷 / 07期
关键词：
large-scale scheduling; elastic jobs; precedence constraints; practical application; tabu search; ALGORITHM; MAKESPAN;
D O I：
10.1016/j.cor.2005.08.001
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
This paper presents a solution method for minimizing makespan of a practical large-scale scheduling problem with elastic jobs. The jobs are processed on three servers and restricted by precedence constraints, time windows and capacity limitations. We derive a new method for approximating the server exploitation of the elastic jobs and solve the problem using a tabu search procedure. Finding an initial feasible solution is in general NP-complete, but the tabu search procedure includes a specialized heuristic for solving this problem. The solution method has proven to be very efficient and leads to a significant decrease in makespan compared to the strategy currently implemented. (c) 2005 Elsevier Ltd. All rights reserved.
引用
收藏
页码：2025 / 2042
页数：18
相关论文
共 15 条
  • [1] Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems
    Baptiste P.
    Le Pape C.
    [J]. Constraints, 2000, 5 (1-2) : 119 - 139
  • [2] Baptiste P., 2001, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems
  • [3] An efficient approximation algorithm for minimizing makespan on uniformly related machines
    Chekuri, C
    Bender, M
    [J]. JOURNAL OF ALGORITHMS, 2001, 41 (02) : 212 - 224
  • [4] CHIANG WC, 1997, INFORMS J COMP, V9, P417
  • [5] Scheduling using tabu search methods with intensification and diversification
    Ferland, JA
    Ichoua, S
    Lavoie, A
    Gagné, E
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2001, 28 (11) : 1075 - 1092
  • [6] Garey M. R., 1979, COMPUTERS INTRACTABI
  • [7] Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]
  • [8] Glover F., 1997, Tabu Search
  • [9] A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion
    Grabowski, J
    Wodecki, M
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (11) : 1891 - 1909
  • [10] Logic-based Benders decomposition
    Hooker, JN
    Ottosson, G
    [J]. MATHEMATICAL PROGRAMMING, 2003, 96 (01) : 33 - 60
12