Interval-indexed formulation based heuristics for single machine total weighted tardiness problem

被引：6
|
作者：
Altunc, Arife Burcu Colak [1 ]
Keha, Ahmet Burak [1 ]
机构：
[1] Arizona State Univ, Dept Ind Engn, Tempe, AZ 85287 USA
来源：
COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 06期
关键词：
Single machine scheduling; Interval-indexed formulation; Mixed integer programming; Linear programming based heuristics; AVERAGE COMPLETION-TIME; SCHEDULING PROBLEMS; ALGORITHM; MINIMIZE; COSTS; OPTIMIZATION;
D O I：
10.1016/j.cor.2008.08.004
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
in this paper, we solve the single machine total weighted tardiness problem by using integer programming and linear programming based heuristic algorithms. Interval-indexed formulation is used to formulate the problem. We discuss several methods to form the intervals and different post-processing methods. Then, we show how our algorithm can be used to improve a population of a genetic algorithm. We also provide some computational results that show the effectiveness of our algorithm. Many aspects of our heuristic algorithm are quite general and can be applied to other scheduling and combinatorial optimization problems. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码：2122 / 2131
页数：10
相关论文
共 50 条
  • [1] Meta-heuristics for the single-machine scheduling total weighted tardiness problem
    Madureira, Ana Maria
    Proceedings of the IEEE International Symposium on Assembly and Task Planning, 1999, : 405 - 410
  • [2] Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem
    Valente, Jorge M. S.
    Schaller, Jeffrey E.
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (09) : 2223 - 2231
  • [3] Performance comparison of heuristics for the total weighted tardiness problem
    Huegler, Peter A.
    Vasko, Francis J.
    Computers and Industrial Engineering, 1997, 32 (04): : 753 - 767
  • [4] A genetic algorithm for the single machine total weighted tardiness problem
    Liu, N
    Abdelrahman, MA
    Ramaswamy, S
    PROCEEDINGS OF THE 35TH SOUTHEASTERN SYMPOSIUM ON SYSTEM THEORY, 2003, : 34 - 38
  • [5] New constructive heuristics for the total weighted tardiness problem
    Yoon, S. H.
    Lee, I. S.
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2011, 62 (01) : 232 - 237
  • [6] A performance comparison of heuristics for the total weighted tardiness problem
    Huegler, PA
    Vasko, FJ
    COMPUTERS & INDUSTRIAL ENGINEERING, 1997, 32 (04) : 753 - 767
  • [7] Genetic algorithm for the single machine total weighted tardiness problem
    Ferrolho, Antonio
    Crisostomo, Manuel
    2006 1ST IEEE INTERNATIONAL CONFERENCE ON E-LEARNING IN INDUSTRIAL ELECTRONICS, 2006, : 17 - +
  • [8] Single machine total weighted tardiness problem with genetic algorithms
    Ferrolho, Antonio
    Crisostomo, Manuel
    2007 IEEE/ACS INTERNATIONAL CONFERENCE ON COMPUTER SYSTEMS AND APPLICATIONS, VOLS 1 AND 2, 2007, : 1 - +
  • [9] Time-indexed formulations and the total weighted tardiness problem
    Bigras, Louis-Philippe
    Gamache, Michel
    Savard, Gilles
    INFORMS JOURNAL ON COMPUTING, 2008, 20 (01) : 133 - 142
  • [10] Improved heuristics for the n-job single-machine weighted tardiness problem
    Volgenant, A.
    Teerhuis, E.
    Computers and Operations Research, 1999, 26 (01): : 35 - 44
12345