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
相关论文
共 28 条
  • [1] Aarts E.H.L., Van Laarhoven P.J.M., Lenstra J.K., Ulder N.L.J., A computational study of local search algorithms for job shop scheduling, ORSA J Comput, 6, pp. 118-125, (1994)
  • [2] Joseph A., Egon B., Daniel Z., SHIFTING BOTTLENECK PROCEDURE for JOB SHOP SCHEDULING., Management Science, 34, 3, pp. 391-401, (1988)
  • [3] Biegel J.E., Davern J.J., Genetic algorithms and job shop scheduling, Comput Ind Eng, 19, pp. 81-91, (1990)
  • [4] Binato S., Hery W.J., Loewenstern D.M., Resende M.G.C., A GRASP for Job Shop Scheduling. Essays and Surveys on Metaheuristics, pp. 58-79, (2001)
  • [5] Croce F.D., Tadei R., Volta G., A genetic algorithm for the job shop problem, Comput Oper Res, 22, pp. 15-24, (1995)
  • [6] Dorndorf U., Pesch E., Evolution based learning in a job shop scheduling environment, Comput Oper Res, 22, pp. 25-40, (1995)
  • [7] Garey M.R., Johnson D.S., Computers and Intractability : A Guide to the Theory of NP-completeness, (1979)
  • [8] Garey M.R., Johnson D.S., Sethi R., The complexity of flowshop and jobshop scheduling, Math Oper Res, 1, pp. 117-129, (1976)
  • [9] Goldberg D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, (1989)
  • [10] Hasan S.M.K., Sarker R., Cornforth D., GA with priority rules for solving job-shop scheduling problems, IEEE World Congress on Computational Intelligence, pp. 1913-1920, (2008)
123