A genetic algorithm for the single machine total weighted tardiness problem

被引：2
作者：
Liu, N [1 ]
Abdelrahman, MA [1 ]
Ramaswamy, S [1 ]
机构：
[1] Tennessee Technol Univ, Dept Elect & Comp Engn, Cookeville, TN 38505 USA
来源：
PROCEEDINGS OF THE 35TH SOUTHEASTERN SYMPOSIUM ON SYSTEM THEORY | 2003年
关键词：
D O I：
10.1109/SSST.2003.1194525
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Scheduling problems are important NP-hard problems. Genetic algorithms can provide good solutions for such optimization problems. In this paper, we present a genetic algorithm to solve the single machine total weighted tardiness scheduling problem, which is a strong NP-hard problem. The algorithm uses the natural permutation representation of a chromosome, heuristic dispatching rules combined with random method to create the initial population, position-based crossover and order-based mutation operators, and the best members of the population during generations. The computational results of problem examples with 10 and 25 jobs and general problems with 50, 100, 200 and 500 jobs show the good performance and the efficiency of the developed algorithm.
引用
收藏
页码：34 / 38
页数：5
相关论文
共 21 条
  • [1] ALEXANDRE F, 1997, PLANNING SCHEDULING, P300
  • [2] [Anonymous], 1989, GENETIC ALGORITHM SE
  • [3] [Anonymous], 1991, Handbook of genetic algorithms
  • [4] Crauwels H. A. J., 1998, INFORMS Journal on Computing, V10, P341, DOI 10.1287/ijoc.10.3.341
  • [5] DUAL ALGORITHM FOR ONE-MACHINE SCHEDULING PROBLEM
    FISHER, ML
    [J]. MATHEMATICAL PROGRAMMING, 1976, 11 (03) : 229 - 251
  • [6] HOLLAND JH, 1975, ADAPTATION NATURAL A
  • [7] A performance comparison of heuristics for the total weighted tardiness problem
    Huegler, PA
    Vasko, FJ
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 1997, 32 (04) : 753 - 767
  • [8] KAN AHG, 1975, OPER RES, V23, P908
  • [9] Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X
  • [10] A GA based scheduling system for dynamic single machine problem
    Madureira, A
    Ramos, C
    Silva, SD
    [J]. PROCEEDINGS OF THE 2001 IEEE INTERNATIONAL SYMPOSIUM ON ASSEMBLY AND TASK PLANNING (ISATP2001): ASSEMBLY AND DISASSEMBLY IN THE TWENTY-FIRST CENTURY, 2001, : 262 - 267
123