More Web Proxy on the site http://driver.im/

article

An efficient memetic algorithm for solving the job shop scheduling problem

Authors:

Xinyu LiAuthors Info & Claims

Computers and Industrial Engineering, Volume 60, Issue 4

Pages 699 - 705

https://doi.org/10.1016/j.cie.2011.01.003

Published: 01 May 2011 Publication History

Abstract

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.

References

[1]

The shifting bottleneck procedure for job-shop scheduling. Management. v34. 391-401.

Digital Library

[2]

The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm. European Journal of Operational Research. v159 i2. 420-429.

[3]

Machine sequencing via disjunctive graph: An implicit numeration algorithm. Operations Research. v17. 941-957.

[4]

OR-library: Distributing test problems by electronic mail. Journal of Operational Research Society. v41 i11. 1069-1072.

[5]

A GRASP for job shop scheduling. In: Ribiero, C., Hansen, P. (Eds.), Essays and surveys on meta-heuristics, Kluwer. pp. 59-80.

[6]

The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research. v93. 1-33.

[7]

A new memetic algorithm for the asymmetric traveling sales man problem. Journal of Heuristics. v10. 483-506.

Digital Library

[8]

Fuzzy priority rule for job shop scheduling. Journal of Intelligent Manufacturing. v15 i4. 527-533.

[9]

A memetic algorithm for the job-shop with time-lags. Computers & Operations Research. v35. 2331-2356.

Digital Library

[10]

An alternative framework to Lagrangian relaxation approach for job shop scheduling. European Journal of Operational Research. v149 i3. 499-512.

[11]

A genetic algorithm for the job shop problem. Computer and Operations Research. v22 i1. 15-24.

Digital Library

[12]

A new memtic algorithm for optimizing the partitioning problem of tandem AGV systems. International Journal of Production Economics. v118. 508-520.

[13]

A memetic algorithm for the total tardiness single machine scheduling problem. European Journal of Operational Research. v132. 224-242.

[14]

The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. v1. 117-129.

[15]

A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research. v167. 77-95.

[16]

Memetic algorithm for solving job-shop scheduling problems. Memetic Computing. v1. 69-83.

[17]

Adaption in natural and artificial systems. 1975. The University of Michigan Press, Ann Arbor.

[18]

An improved shifting bottleneck procedure for the job shop scheduling problem. Computers & Operations Research. v31 i12. 2093-2110.

[19]

Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research. v113 i1. 123-136.

[20]

A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint. Journal of the Operational Research Society. v53 i11. 1239-1246.

[21]

A multi-model immune algorithm for the job shop scheduling problem. Information Sciences. v179. 1516-1532.

Digital Library

[22]

Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transaction on Evolutionary Computation. v4 i4. 337-352.

Digital Library

[23]

A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems. Parallel Computing and Transputer Applications. v1. 177-186.

[24]

A fast taboo search algorithm for the job shop problem. Management Science. v42 i6. 797-813.

Digital Library

[25]

Meta-Lamarckian learning in memetic algorithms. IEEE Transactions on Evolutionary Computation. v8. 99-110.

Digital Library

[26]

A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering. v45 i4. 597-613.

Digital Library

[27]

Scheduling theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs, NJ.

[28]

Radcliffe, N. J., Surry, P. D. (1994). Formal memetic algorithms. In T. Fogarty (Ed.), AISB workshop, evolutionary computing, lecture notes in computer science, selected papers (pp. 1-16).

Digital Library

[29]

A filter-and-fan approach to the job shop scheduling problem. European Journal of Operational Research. v194. 650-662.

[30]

A hybrid particle swarm optimization for job shop scheduling problem. Computers & Industrial Engineering. v51. 791-808.

Digital Library

[31]

An improved genetic algorithm for job-shop scheduling problems using Taguchi-based crossover. International Journal of Advanced Manufacture Technology. v38. 987-994.

[32]

Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research. v46 i15. 4155-4175.

[33]

Clonal selection based memetic algorithm for job shop scheduling problems. Journal of Bionic Engineering. v5. 111-119.

[34]

A new adaptive neural network and heuristics hybrid approach for job-shop scheduling. Computers & Operations Research. v28. 955-971.

Digital Library

[35]

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Computers & Operations Research. v34. 3229-3242.

Digital Library

Cited By

Li JLi XGao L(2024)An operator-inspired framework for metaheuristics and its applications on job-shop scheduling problemsApplied Soft Computing10.1016/j.asoc.2024.111522157:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111522
Castello Rosa APereira F(2024)An intensification approach based on fitness landscape characteristics for job shop scheduling problemJournal of Combinatorial Optimization10.1007/s10878-024-01176-047:5Online publication date: 18-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01176-0
Farahani AVan Elzakker MGenga LTroubil PDijkman R(2023)Relational Graph Attention-Based Deep Reinforcement Learning: An Application to Flexible Job Shop Scheduling with Sequence-Dependent Setup TimesLearning and Intelligent Optimization10.1007/978-3-031-44505-7_24(347-362)Online publication date: 4-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-44505-7_24
Show More Cited By

An efficient memetic algorithm for solving the job shop scheduling problem

Recommendations

Investigating Memetic Algorithm for Solving the Job Shop Scheduling Problems
AICI '10: Proceedings of the 2010 International Conference on Artificial Intelligence and Computational Intelligence - Volume 02

The job shop scheduling problem (JSP) is well known as one of the most complex optimization problems due to its very large search space and many constraint between machines and jobs. Memetic algorithm (MA) is a hybrid evolutionary algorithm that ...
A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations

The flexible job shop scheduling problem (FJSP) is an extension of the classical job shop scheduling problem (JSP) which allows an operation to be processed by any machine from a given set of machines. FJSP is NP-hard and presents two major ...
Job Shop Scheduling by Local Search

<P>We survey solution methods for the job shop scheduling problem with an emphasis on local search. Both deterministic and randomized local search methods as well as the proposed neighborhoods are discussed. We compare the computational performance of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Industrial Engineering

Computers and Industrial Engineering Volume 60, Issue 4

May, 2011

410 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2011.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 May 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JLi XGao L(2024)An operator-inspired framework for metaheuristics and its applications on job-shop scheduling problemsApplied Soft Computing10.1016/j.asoc.2024.111522157:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111522
Castello Rosa APereira F(2024)An intensification approach based on fitness landscape characteristics for job shop scheduling problemJournal of Combinatorial Optimization10.1007/s10878-024-01176-047:5Online publication date: 18-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01176-0
Farahani AVan Elzakker MGenga LTroubil PDijkman R(2023)Relational Graph Attention-Based Deep Reinforcement Learning: An Application to Flexible Job Shop Scheduling with Sequence-Dependent Setup TimesLearning and Intelligent Optimization10.1007/978-3-031-44505-7_24(347-362)Online publication date: 4-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-44505-7_24
Zhu ZZhou XCao DLi M(2022)A shuffled cellular evolutionary grey wolf optimizer for flexible job shop scheduling problem with tree-structure job precedence constraintsApplied Soft Computing10.1016/j.asoc.2022.109235125:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.asoc.2022.109235
Mahmud SChakrabortty RAbbasi ARyan M(2022)Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problemsJournal of Intelligent Manufacturing10.1007/s10845-022-01940-133:7(1939-1966)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10845-022-01940-1
He LLi WChiong RAbedi MCao YZhang Y(2021)Optimising the job-shop scheduling problem using a multi-objective Jaya algorithmApplied Soft Computing10.1016/j.asoc.2021.107654111:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.asoc.2021.107654
Luo YLu CLi XWang LGao L(2019)Green Job Shop Scheduling Problem with Machine at Different Speeds using a multi-objective grey wolf optimization algorithm^*2019 IEEE 15th International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2019.8843132(573-578)Online publication date: 22-Aug-2019
https://dl.acm.org/doi/10.1109/COASE.2019.8843132
Chen JWang LHe XHuang D(2019)A Probability Model-based Memetic Algorithm for Distributed Heterogeneous Flow-Shop Scheduling2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790051(411-418)Online publication date: 10-Jun-2019
https://dl.acm.org/doi/10.1109/CEC.2019.8790051
Rahman HNielsen I(2019)Scheduling automated transport vehicles for material distribution systemsApplied Soft Computing10.1016/j.asoc.2019.10555282:COnline publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.105552
Kurdi M(2017)An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problemComputers and Industrial Engineering10.1016/j.cie.2017.07.021111:C(183-201)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.cie.2017.07.021
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents