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

article

A hybrid particle swarm optimization for job shop scheduling problem

Authors:

Cheng-Yu HsuAuthors Info & Claims

Computers and Industrial Engineering, Volume 51, Issue 4

Pages 791 - 808

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

Published: 01 December 2006 Publication History

Abstract

A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the particle position representation, particle movement, and particle velocity to better suit PSO for the JSP. We modified the particle position based on preference list-based representation, particle movement based on swap operator, and particle velocity based on the tabu list concept in our algorithm. Giffler and Thompson's heuristic is used to decode a particle position into a schedule. Furthermore, we applied tabu search to improve the solution quality. The computational results show that the modified PSO performs better than the original design, and that the hybrid PSO is better than other traditional metaheuristics.

References

[1]

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

[2]

Guided local search with shifting bottleneck for job shop scheduling. Management Science. v44 i2. 262-275.

[3]

Genetic algorithms and random keys for sequencing and optimization. Operations Research Society of America (ORSA) Journal on Computing. v6. 154-160.

[4]

OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society. v14. 1069-1072.

[5]

Job shop scheduling with genetic algorithm. In: Grefenstette, J.J. (Ed.), Proceedings of the first international conference on genetic algorithms, Lawrence Erlbaum Associates, Hillsdale, NJ. pp. 140-163.

[6]

Industrial scheduling. Prentice-Hall, Englewood Cliffs, NJ.

[7]

Sequencing and scheduling: An introduction to the mathematics of the job-shop. Horwood, UK.

[8]

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

[9]

Genetic algorithms and engineering design. Wiley, New York.

[10]

Algorithms for solving production scheduling problems. Operations Research. v8. 487-503.

[11]

Future paths for integer programming and links to artificial intelligence. Computers & Operations Research. v13. 533-549.

[12]

Tabu search: Part I. ORSA Journal on Computing. v1. 190-206.

[13]

Tabu search: Part II. ORSA Journal on Computing. v2. 4-32.

[14]

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

[15]

New and "stronger" job-shop neighbourhoods: A focus on the method of Nowicki and Smutnicki (1996). Journal of Heuristics. v6. 457-480.

[16]

Particle swarm optimization. In: Proceedings of the 1995 IEEE international conference on neural networks, Vol. 4. IEEE Press, Piscataway, NJ. pp. 1942-1948.

[17]

An efficient genetic algorithm for job shop scheduling problems. In: Eshelman, L.J. (Ed.), Proceedings of the sixth international conference on genetic algorithms, Morgan Kaufman Publishers, San Francisco, CA. pp. 506-511.

[18]

Lawrence, S., (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration (GSIA), Carnegie Mellon University, Pittsburgh, PA.

[19]

Local optimization and the job-shop scheduling problem. European Journal of Operational Research. v83. 347-364.

[20]

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

[21]

A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research. v120 i2. 297-310.

[22]

Parameter selection in particle swarm optimization. In: Porto, V.W., Saravanan, N., Waagen, D., Eiben, A.E. (Eds.), Proceedings of the 7th international conference on evolutionary programming, Springer, New York. pp. 591-600.

[23]

A modified particle swarm optimizer. In: Fogel, D. (Ed.), Proceedings of the 1998 IEEE international conference on evolutionary computation, IEEE Press, Piscataway, NJ. pp. 69-73.

[24]

Effective job shop scheduling through active chain manipulation. Computers & Operations Research. v22 i2. 159-172.

[25]

Benchmarks for basic scheduling problems. European Journal of Operational Research. v64. 278-285.

[26]

An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research. v28. 585-596.

[27]

Particle swarm optimization-based schemes for resource-constrained project scheduling. Automation in Construction. v14. 393-404.

Cited By

Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Khurshid BMaqsood S(2024)A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108016133:PAOnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.108016
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
Show More Cited By

A hybrid particle swarm optimization for job shop scheduling problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Job Shop Scheduling Based on an Improved Cooperative Particle Swarm Optimization
ICMTMA '10: Proceedings of the 2010 International Conference on Measuring Technology and Mechatronics Automation - Volume 02

Aiming at the stagnation existing in the cooperative particle swarm optimization, this paper presents an improved cooperative particle swarm optimization algorithm. The algorithm uses an optimized sub-swarms cooperation mode with a disturbance mechanism ...
Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem

Research highlights This study generated schedules by both forward and backward scheduling particle swarms. This work applies justification technique to further shorten the makespan of the yield schedule. To synchronize the justified schedules, a ...
An improved cooperative quantum-behaved particle swarm optimization

Particle swarm optimization (PSO) is a population-based stochastic optimization. Its parameters are easy to control, and it operates easily. But, the particle swarm optimization is a local convergence algorithm. Quantum-behaved particle swarm ...

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 51, Issue 4

December, 2006

260 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2006.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 December 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Khurshid BMaqsood S(2024)A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108016133:PAOnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.108016
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
Huang BZhou MLu XAbusorrah A(2023)Scheduling of Resource Allocation Systems with Timed Petri Nets: A SurveyACM Computing Surveys10.1145/357032655:11(1-27)Online publication date: 9-Feb-2023
https://dl.acm.org/doi/10.1145/3570326
Zhang FMei YNguyen STan KZhang M(2023)Instance-Rotation-Based Surrogate in Genetic Programming With Brood Recombination for Dynamic Job-Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.318069327:5(1192-1206)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3180693
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
Gharehchopogh FAbdollahzadeh B(2022)An efficient harris hawk optimization algorithm for solving the travelling salesman problemCluster Computing10.1007/s10586-021-03304-525:3(1981-2005)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10586-021-03304-5
Kumar TKumar A(2021)Materialized View Selection Using Swap Operator Based Particle Swarm OptimizationInternational Journal of Distributed Artificial Intelligence10.4018/ijdai.202101010313:1(58-73)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.4018/ijdai.2021010103
Lara-Cárdenas ESánchez-Díaz XAmaya ICruz-Duarte JOrtiz-Bayliss J(2020)A Genetic Programming Framework for Heuristic Generation for the Job-Shop Scheduling ProblemAdvances in Soft Computing10.1007/978-3-030-60884-2_21(284-295)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-60884-2_21
Kawaguchi SFukuyama Y(2020)Improved parallel reactive hybrid particle swarm optimization using improved neighborhood schedule generation method for the integrated framework of optimal production scheduling and operational planning of an energy plant in a factoryElectronics and Communications in Japan10.1002/ecj.12237103:7(37-48)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1002/ecj.12237
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents