Memetic algorithms for solving job-shop scheduling problems

被引：0
|
作者：
Hasan S.M.K. [1 ]
Sarker R. [1 ]
Essam D. [1 ]
Cornforth D. [1 ]
机构：
[1] School of Information Technology and Electrical Engineering, University of New South Wales, Australian Defence Force Academy, Canberra, ACT 2600, Nortchcott Drive
来源：
Memetic Computing | 2009年 / 1卷 / 1期
关键词：
Genetic algorithm; Job-shop scheduling; Local search; Memetic algorithm; Priority rules;
D O I：
10.1007/s12293-008-0004-5
中图分类号：
学科分类号：
摘要：
The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA. We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time. © 2008 Springer-Verlag.
引用
收藏
页码：69 / 83
页数：14
相关论文
共 50 条
  • [41] A Multi-objective Memetic Algorithm for the Job-Shop Scheduling Problem
    Mariano Frutos
    Fernando Tohmé
    Operational Research, 2013, 13 : 233 - 250
  • [42] JOB-SHOP SCHEDULING
    NEW, C
    DATA PROCESSING, 1974, 16 (02): : 100 - 102
  • [43] A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems
    Tamssaouet, Karim
    Dauzere-Peres, Stephane
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 311 (02) : 455 - 471
  • [44] Comparative evaluation of genetic algorithms for job-shop scheduling
    Ponnambalam, SG
    Aravindan, P
    Rao, PS
    PRODUCTION PLANNING & CONTROL, 2001, 12 (06) : 560 - 574
  • [45] DISTRIBUTED SIMULATED ANNEALING ALGORITHMS FOR JOB-SHOP SCHEDULING
    KRISHNA, K
    GANESHAN, K
    RAM, DJ
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1995, 25 (07): : 1102 - 1109
  • [46] An efficient memetic algorithm for solving the job shop scheduling problem
    Gao, Liang
    Zhang, Guohui
    Zhang, Liping
    Li, Xinyu
    COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (04) : 699 - 705
  • [47] Production job-shop scheduling using genetic algorithms
    Mesghouni, K
    Hammadi, S
    Borne, P
    INFORMATION INTELLIGENCE AND SYSTEMS, VOLS 1-4, 1996, : 1519 - 1524
  • [48] Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms
    Yuan, Yuan
    Xu, Hua
    IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2015, 12 (01) : 336 - 353
  • [49] New scheduling type applied to solving job-shop scheduling problem
    Zhang, Chaoyong
    Guan, Zailin
    Liu, Qiong
    Shao, Xinyu
    Li, Peigen
    Jixie Gongcheng Xuebao/Chinese Journal of Mechanical Engineering, 2008, 44 (10): : 24 - 31
  • [50] Solving nonstandard job-shop scheduling problem by efficient scheduling algorithm
    Wang, Feng-Ru
    Xu, Wei-Wen
    Xu, Hong-Fu
    Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2001, 7 (07): : 12 - 15
12345