research-article

A tabu search-based memetic algorithm for the multi-objective flexible job shop scheduling problem

Authors:

Marios Kefalas,

Steffen Limmer,

Asteris Apostolidis,

Markus Olhofer,

Michael Emmerich,

Thomas BäckAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 1254 - 1262

https://doi.org/10.1145/3319619.3326817

Published: 13 July 2019 Publication History

Abstract

In this paper we propose a tabu search-based memetic algorithm (TSM) for the multi-objective flexible job shop scheduling problem (FJSSP), with the objectives to minimize the makespan, the total workload and the critical workload. The problem is addressed in a Pareto manner, which targets a set of Pareto optimal solutions. The novelty of our method lies in the use of tabu search (TS) as the local search method as well as a mutation operator and the use of the hypervolume indicator to avoid stagnation by increasing the flow of individuals in the local search. To the best of our knowledge, the use of TS in the context of multi-objective FJSSP has not been reported so far. We apply our algorithm on well known test instances and compare our results to state-of-the art algorithms. The results show that our approach yields competitive solutions in 6 of the 10 instances against two of their algorithms proving that the use of TS as a local search method can provide competitive results.

Supplementary Material

ZIP File (p1254-kefalas_suppl.zip)

Supplemental material.

Download
15.12 KB

References

[1]

Hasan Ali, Rashedul Haque, and Fashiar Rahman. 2017. Chronological Evolution Of Flexible Job Shop Scheduling: A Review. Wiley Encyclopedia of Electrical and Electronics Engineering (2017), 7.

[2]

Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. 2016. A Medium-Scale Distributed System for Computer Science Research: Infrastructure for the Long Term. Computer 49, 5 (May 2016), 54--63.

[3]

Egon Balas. 1969. Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm. Operations Research 17, 6 (Dec. 1969), 941--957.

Digital Library

[4]

Paolo Brandimarte. 1993. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research 41, 3 (Sept. 1993), 157--183.

Digital Library

[5]

Hao-Chin Chang, Yeh-Peng Chen, Tung-Kuan Liu, and Jyh-Horng Chou. 2015. Solving the Flexible Job Shop Scheduling Problem With Makespan Optimization by Using a Hybrid Taguchi-Genetic Algorithm. IEEE Access 3 (2015), 1740--1754.

[6]

Imran Ali Chaudhry and Abid Ali Khan. 2016. A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research 23, 3 (May 2016), 551--591.

[7]

Tsung-Che Chiang and Hsiao-Jou Lin. 2012. Flexible Job Shop Scheduling Using a Multiobjective Memetic Algorithm. In Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence, De-Shuang Huang, Yong Gan, Phalguni Gupta, and M. Michael Gromiha (Eds.). Vol. 6839. Springer Berlin Heidelberg, Berlin, Heidelberg, 49--56.

Digital Library

[8]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182--197.

Digital Library

[9]

Michael Emmerich, Nicola Beume, and Boris Naujoks. 2005. An EMO Algorithm Using the Hypervolume Measure as Selection Criterion. In Evolutionary Multi-Criterion Optimization, David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Dough Tygar, Moshe Y. Vardi, Gerhard Weikum, Carlos A. Coello Coello, Arturo HernÃąndez Aguirre, and Eckart Zitzler (Eds.). Vol. 3410. Springer Berlin Heidelberg, Berlin, Heidelberg, 62--76.

Digital Library

[10]

Michael T. M. Emmerich and Andrè H. Deutz. 2018. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Natural Computing 17, 3 (Sept. 2018), 585--609.

Digital Library

[11]

Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012. DEAP: Evolutionary Algorithms Made Easy. Journal of Machine Learning Research 13 (jul 2012), 2171--2175.

Digital Library

[12]

M. R. Garey, D. S. Johnson, and Ravi Sethi. 1976. The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research 1, 2 (May 1976). 117--129.

Digital Library

[13]

Fred Glover. 1986. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13, 5 (Jan. 1986), 533--549.

Digital Library

[14]

Alain Hertz, Eric Taillard, and Dominique de Werra. 1996. A Tutorial on Tabu Search. (1996), 13.

[15]

H. Ishibuchi, T. Yoshida, and T. Murata. 2003. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 7, 2 (April 2003), 204--223.

Digital Library

[16]

I. Kacem, S. Hammadi, and P. Borne. 2002. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 32, 1 (Feb. 2002), 1--13.

Digital Library

[17]

Grecia Lapizco-Encinas, Carl Kingsford, and James Reggia. 2009. A cooperative combinatorial Particle Swarm Optimization algorithm for side-chain packing. In 2009 IEEE Swarm Intelligence Symposium. IEEE, Nashville, 22--29.

[18]

Eugene L. Lawler, Jan Karel Lenstra, Alexander H.G. Rinnooy Kan, and David B. Shmoys. 1993. Chapter 9 Sequencing and scheduling: Algorithms and complexity. In Handbooks in Operations Research and Management Science. Vol. 4. Elsevier, 445--522.

[19]

Sanghyup Lee, Ilkyeong Moon, Hyerim Bae, and Jion Kim. 2012. Flexible job-shop scheduling problems with 'AND'/'OR' precedence constraints. International Journal of Production Research 50, 7 (April 2012), 1979--2001.

[20]

Pablo Moscato. 1989. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts Towards Memetic Algorithms. (1989), 68.

[21]

Pablo Moscato and Carlos Cotta. 2003. A Gentle Introduction to Memetic Algorithms. In Handbook of Metaheuristics, Fred Glover and Gary A. Kochenberger (Eds.). Vol. 57. Kluwer Academic Publishers, Boston, 105--144.

[22]

Ghasem Moslehi and Mehdi Mahnam. 2011. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics 129, 1 (Jan. 2011), 14--22.

[23]

B. Naujoks, N. Beume, and M. Emmerich. 2005. Multi-objective optimisation using S-metric selection: application to three-dimensional solution spaces. In 2005 IEEE Congress on Evolutionary Computation, Vol. 2. 1282--1289 Vol. 2.

[24]

Eugeniusz Nowicki and Czeslaw Smutnicki. 1996. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science 42, 6 (1996), 797--813. http://www.jstor.org/stable/2634595

Digital Library

[25]

E O Oyetunji. 2009. Some Common Performance Measures in Scheduling Problems: Review Article. (2009), 5.

[26]

F. Pezzella, G. Morganti, and G. Ciaschetti. 2008. A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research 35, 10 (Oct. 2008), 3202--3212.

Digital Library

[27]

Seyed Habib A. Rahmati, M. Zandieh, and M. Yazdani. 2013. Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology 64, 5--8 (Feb. 2013), 915--932.

[28]

Yves Tabourier. 1969. Probème d'ordonnancement è contraintes purement disjonctives. Revue française d'informatique et de recherche opérationnelle. Série verte 3, V3 (1969), 51--65.

[29]

Xiaojuan Wang, Liang Gao, Chaoyong Zhang, and Xinyu Shao. 2010. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology 51, 5--8 (Nov. 2010), 757--767.

[30]

Wenchao Yi, Xinyu Li, and Baolin Pan. 2016. Solving flexible job shop scheduling using an effective memetic algorithm. 53, 2 (2016).

Digital Library

[31]

Jian Xiong, Xu Tan, Ke-wei Yang, Li-ning Xing, and Ying-wu Chen. 2012. A Hybrid Multiobjective Evolutionary Approach for Flexible Job-Shop Scheduling Problems. Mathematical Problems in Engineering 2012 (2012), 1--27.

[32]

Wenchao Yi, Xinyu Li, and Baolin Pan. 2016. Solving flexible job shop scheduling using an effective memetic algorithm. International Journal of Computer Applications in Technology 53, 2 (2016), 157.

Digital Library

[33]

Yuan Yuan and Hua Xu. 2015. Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms. IEEE Transactions on Automation Science and Engineering 12, 1 (Jan. 2015), 336--353.

Cited By

Hazbei MRafati NKharma NEicker U(2024)Optimizing architectural multi-dimensional forms; a hybrid approach integrating approximate evolutionary search, clustering and local optimizationEnergy and Buildings10.1016/j.enbuild.2024.114460318(114460)Online publication date: Sep-2024
https://doi.org/10.1016/j.enbuild.2024.114460
Hajibabaei MBehnamian J(2024)Considering environmental impacts in flexible assembly job shop scheduling: non-dominated sorting memetic algorithmFlexible Services and Manufacturing Journal10.1007/s10696-024-09553-xOnline publication date: 21-Jun-2024
https://doi.org/10.1007/s10696-024-09553-x
Sassi JAlaya IBorne PTagina M(2021)A decomposition-based artificial bee colony algorithm for the multi-objective flexible jobshop scheduling problemEngineering Optimization10.1080/0305215X.2021.188424354:3(524-538)Online publication date: 9-Mar-2021
https://doi.org/10.1080/0305215X.2021.1884243

Index Terms

A tabu search-based memetic algorithm for the multi-objective flexible job shop scheduling problem
1. Applied computing
  1. Operations research
    1. Decision analysis
      1. Multi-criterion optimization and decision-making

Recommendations

Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood ...
A tabu search/path relinking algorithm to solve the job shop scheduling problem

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing ...
A hybrid pareto-based tabu search for multi-objective flexible job shop scheduling problem with e/t penalty
ICSI'10: Proceedings of the First international conference on Advances in Swarm Intelligence - Volume Part I

In this paper, we propose a Pareto-based tabu search algorithm for multi-objective FJSP with Earliness/Tardiness (E/T) penalty In the hybrid algorithm, several neighboring structure based approaches were proposed to improve the convergence capability of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2019

2161 pages

ISBN:9781450367486

DOI:10.1145/3319619

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
155
Total Downloads

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

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hazbei MRafati NKharma NEicker U(2024)Optimizing architectural multi-dimensional forms; a hybrid approach integrating approximate evolutionary search, clustering and local optimizationEnergy and Buildings10.1016/j.enbuild.2024.114460318(114460)Online publication date: Sep-2024
https://doi.org/10.1016/j.enbuild.2024.114460
Hajibabaei MBehnamian J(2024)Considering environmental impacts in flexible assembly job shop scheduling: non-dominated sorting memetic algorithmFlexible Services and Manufacturing Journal10.1007/s10696-024-09553-xOnline publication date: 21-Jun-2024
https://doi.org/10.1007/s10696-024-09553-x
Sassi JAlaya IBorne PTagina M(2021)A decomposition-based artificial bee colony algorithm for the multi-objective flexible jobshop scheduling problemEngineering Optimization10.1080/0305215X.2021.188424354:3(524-538)Online publication date: 9-Mar-2021
https://doi.org/10.1080/0305215X.2021.1884243

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents