article

An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems

Authors:

Zhiming WuAuthors Info & Claims

Computers and Industrial Engineering, Volume 48, Issue 2

Pages 409 - 425

Published: 01 March 2005 Publication History

Abstract

Scheduling for the flexible job-shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. The combining of several optimization criteria induces additional complexity and new problems. Particle swarm optimization is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) as a local search algorithm employs certain probability to avoid becoming trapped in a local optimum and has been proved to be effective for a variety of situations, including scheduling and sequencing. By reasonably hybridizing these two methodologies, we develop an easily implemented hybrid approach for the multi-objective flexible job-shop scheduling problem (FJSP). The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the multi-objective FJSP, especially for problems on a large scale.

References

[1]

Routing and scheduling in a flexible job shop by taboo search. Annals of Operations Research. v41. 157-183.

[2]

Job-shop scheduling with multi-purpose machines. Computing. v45. 369-375.

[3]

An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research. v70. 281-306.

[4]

Eberhart, R.,&Kennedy, J. (1995). A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science (pp. 39-43).

[5]

Eberhart, R.,&Shi, Y. (2001). Particle swarm optimization: Developments, applications and resources. In: Proceedings of the 2001 IEEE international conference on evolutionary computation (pp. 81-86).

[6]

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

[7]

Hsu, T., Dupas, R.,&Jolly, D., Goncalves, G. (2002). Evalution of mutation heuristics for the solving of multiobjective flexible job shop by an evolutionary algorithm. In: Proceedings of the 2002 IEEE international conference on systems, man and cybernetics (pp. 6-9).

[8]

Tabu search for the job shop scheduling problem with multi-purpose machines. Operations Research Spektrum. v15. 205-215.

[9]

Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C. v32 i1. 1-13.

[10]

Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation. v60. 245-276.

[11]

Kennedy, J. (1997). The particle swarm: social adaptation of knowledge. In: Proceeding of the 1997 IEEE international conference on evolutionary computation (pp. 303-308).

[12]

Kennedy, J.,&Eberhart, R. (1995). Particle swarm optimization. In: Proceeding of the 1995 IEEE international conference on neural network, IV (pp. 1942-1948).

[13]

Optimization by simulated annealing. Science. v220. 671-680.

[14]

Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling. v3 i1. 3-20.

[15]

Shi, Y.,&Eberhart, R. (1999). Empirical study of particle swarm optimization. In: Proceedings of congress on evolutionary computation (pp. 1945-1950).

[16]

Multi-objective scheduling for the hierarchical control of flexible manufacturing systems. The International Journal of Flexible Manufacturing Systems. v11. 379-409.

[17]

Job shop scheduling by simulated annealing. Operations Research. v40. 113-125.

Cited By

Lee DAu T(2022)Scheduling of Mobile Workstations for Overlapping Production Time and Delivery Time2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS40897.2019.8968181(4147-4152)Online publication date: 28-Dec-2022
https://dl.acm.org/doi/10.1109/IROS40897.2019.8968181
Yu WZhang LGe N(2022)An adaptive multiobjective evolutionary algorithm for dynamic multiobjective flexible scheduling problemInternational Journal of Intelligent Systems10.1002/int.2309037:12(12335-12366)Online publication date: 29-Dec-2022
https://dl.acm.org/doi/10.1002/int.23090
Luo MLin JXu L(2020)Solving Flexible Job-shop Problem with Sequence-dependent Setup Times by Using Selection Hyper-heuristicsProceedings of the 2nd International Conference on Artificial Intelligence and Advanced Manufacture10.1145/3421766.3421780(428-433)Online publication date: 15-Oct-2020
https://dl.acm.org/doi/10.1145/3421766.3421780
Show More Cited By

Index Terms

Recommendations

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very ...
A multi-objective PSO for job-shop scheduling problems

Most previous research into the job-shop scheduling problem has concentrated on finding a single optimal solution (e.g., makespan), even though the actual requirement of most production systems requires multi-objective optimization. The aim of this ...
A Multi-swarm Approach to Multi-objective Flexible Job-shop Scheduling Problems
Swarm Intelligence

Swarm Intelligence (SI) is an innovative distributed intelligent paradigm whereby the collective behaviors of unsophisticated individuals interacting locally with their environment cause coherent functional global patterns to emerge. In this paper, we ...

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 48, Issue 2

March 2005

299 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2005.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 March 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lee DAu T(2022)Scheduling of Mobile Workstations for Overlapping Production Time and Delivery Time2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS40897.2019.8968181(4147-4152)Online publication date: 28-Dec-2022
https://dl.acm.org/doi/10.1109/IROS40897.2019.8968181
Yu WZhang LGe N(2022)An adaptive multiobjective evolutionary algorithm for dynamic multiobjective flexible scheduling problemInternational Journal of Intelligent Systems10.1002/int.2309037:12(12335-12366)Online publication date: 29-Dec-2022
https://dl.acm.org/doi/10.1002/int.23090
Luo MLin JXu L(2020)Solving Flexible Job-shop Problem with Sequence-dependent Setup Times by Using Selection Hyper-heuristicsProceedings of the 2nd International Conference on Artificial Intelligence and Advanced Manufacture10.1145/3421766.3421780(428-433)Online publication date: 15-Oct-2020
https://dl.acm.org/doi/10.1145/3421766.3421780
Jiang TZhang C(2019)Adaptive discrete cat swarm optimisation algorithm for the flexible job shop problemInternational Journal of Bio-Inspired Computation10.1504/ijbic.2019.09918613:3(199-208)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1504/ijbic.2019.099186
Zhang JDing GZou YQin SFu J(2019)Review of job shop scheduling research and its new perspectives under Industry 4.0Journal of Intelligent Manufacturing10.1007/s10845-017-1350-230:4(1809-1830)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10845-017-1350-2
Zhang BPan QGao LZhang XPeng K(2019)A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3447-823:17(8101-8129)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s00500-018-3447-8
Grobler J(2019)A Diversity Based Multi-objective Hyper-heuristic for the FJSP with Sequence-Dependent Set-Up Times, Auxiliary Resources and Machine Down TimeProgress in Artificial Intelligence10.1007/978-3-030-30244-3_13(145-156)Online publication date: 3-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-30244-3_13
(2018)Performance improvement of the particle swarm optimisation algorithm for the flexible job shop problem under machines breakdownInternational Journal of Intelligent Engineering Informatics10.5555/3271870.32718806:3-4(396-416)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3271870.3271880
Meziane MTaghezout N(2018)A hybrid genetic algorithm with a neighborhood function for flexible job shop schedulingMultiagent and Grid Systems10.3233/MGS-18028614:2(161-175)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/MGS-180286
Lunardi WVoos HHaddad HWainwright RChbeir R(2018)Comparative study of genetic and discrete firefly algorithm for combinatorial optimizationProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167160(300-308)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167160
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents