Abstract
Flexible job-shop scheduling problem (FJSP), which is proved to be NP-hard, is an extension of the classical job-shop scheduling problem. In this paper, we propose a new genetic algorithm (NGA) to solve FJSP to minimize makespan. This new algorithm uses a new chromosome representation and adopts different strategies for crossover and mutation. The proposed algorithm is validated on a series of benchmark data sets and tested on data from a drug manufacturing company. Experimental results prove that the NGA is more efficient and competitive than some other existing algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
M. R. Garey, D. S. Johmson and R. Sethi, The complexity of flow shop and job shop scheduling, Mathematics of Operational Research, 1 (1976) 117–129.
I. Kacem, S. Hammadi and P. Borne, Pareto-optimality approach for flexible job shop scheduling problems, Hybridization of evolutionary algorithms and fuzzy logic, Matimatic and Computers in Simulation, 60 (2002) 245–276.
P. Brucker and R. Schile, Job-shop scheduling with multipurpose machines, Computing, 45 (4) (1990) 369–375.
P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, 41 (1993) 157–183.
J. A. Paulli, Hierarchical approach for the FMS scheduling problem, European Journal of Operational Research, 86 (1) (1995) 32–42.
K. Mesghani, S. Hammadi and P. Borne, On modeling genetic algorithms for flexible job shop scheduling problems (1998).
H. Chen, J. Ihlow and C. A. Lehmann, Genetic algorithm for flexible Job shop scheduling, IEEE International Conferenceon Robotics and Automation, Detroit, 2 (1999) 1120–1128.
I. Kacem, S. Hammadi and P. Borne, Approche by localization and multiobjective evolutionary and optimization for flexible job shop scheduling problems, IEEE Transations Man and Cybernetrics, 32 (1) (2002) 1–13.
N. B. Ho and J. C. Tay, GENACE: An efficient cultural algorithm for solving the flexible job shop problem, Proceeding of IEEE Congress on Evolutionary Computation, 1 (2004) 1759–1766.
H. P. Zhang and M. Gen, Multistage-based genetic algorithm for flexible job shop scheduling problem, Journal of Complexity International, 48 (2005) 409–425.
P. Fattahi, M. S. Mehrabad and F. Joli, Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, Journal of Inteligent Manufacturing, 18 (2007) 331–342.
N. B. Ho, J. C Tay, M. Edmund and K. Lai, An effective architecture for learning and evolving flexible job shop schedules, European journal of Operational Research, 179 (2007) 316–333.
J. Gao, M. Gen and L. Sun, A hybrid of genetic algorithm and bottleneck shifting for multi objective flexible job shop scheduling problems, Computers and Industrial Engineering, 53 (2007) 149–162.
J. C. Tay and N. B. Ho, Evolving dispatching rules using genetic programming for solving multi- objective flexible jobshop problems, Computers and Industrial Engineering, 54 (2008) 453–473.
B. S. Girish and N. Jawahar, Scheduling job shops associated with multiple routings with genetic and ant colony heuristics (2008).
S. G. Pannanbalam, N. Jawahar and B. S. Girish, Giffler and Thampson Procedure based genetic algorithms for scheduling job shops, Springer-Verbag Berlin Heidelberg (2009) 229–259.
F. Pezzela, G. Margenti and G. Ciaschetti, A genetic algorithm for flexible job shop scheduling problem, Computers and Operations Research, 35 (10) (2007) 3202–3212.
W. Sun, Y. Pan, X. Lu and Q. Ma, Research on flexible job shop scheduling problem based on a modified genetic algorithm, Journal of Mechanical Science And Technology, 24 (10) (2010) 2115–2119.
A. Motaghedi, K. Sabri-Laghare and M. Heydari, solving flexible job shop scheduling problem with multi objectives, International Journal of Industrial Engineering and Production Research, 21 (2010) 197–209.
G. Zhang, L. Gao and Y. Shi, An effective genetic algorithm for the flexible job shop scheduling problem, Expert System with Application, 38 (2011) 3563–3573.
Q. Zhang, H. Manier and A. Manier, A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constants and bounded proceding times, Computers and operations Research, 39 (2012) 1713–1723.
J. C. Chen, C. C. Wu and C. W. Chen, Flexible job shop with parallel machines using genetic algorithm and grouping genetic algorithm, Expert Systems with Application, 39 (2012) 10016–10021.
N. Kim, H. Kim and J. Lee, Damage detection of truss structures using two stage optimization based on micro genetic algorithm, Journal Of Mechanical Science And Technology, 28 (9) (2014) 3687–3695.
R. N. Yadar, V. Yadar and G. H. Singh, Application of non dominated sorting genetic algorithm for multi objective optimization of electrical discharge diamond face grinding process, Journal of Mechanical Science And Technology, 28 (6) (2014) 2299–2306.
L. N. Xing, Y. U. Chen and K. W. Yang, Multi population interactive coevolutionnary algorithm for flexible job shop scheduling problems, Comput. Optim. Appl. (2009), DOI 10.1007//S10589-009-9244-7.
F. N. Defersha and M. Chen, A coase-grain parallel genetic algorithm for flexible job shop scheduling with lot streaming, In IEEE International Conference on Computational Science and Engineering (2009).
Y. K. Park and J. M. Yang, Optimization of mixed casting processes considering discrete ingot sizes, Journal Of Mechanical Science and Technology, 23 (2009) 1899–1910.
S. F. Hwang, Y. Hsu and Y. Chen, A genetic algorithm for the optimization of fiber angles in composite laminates, Journal of Mechanical Science and Technology, 28 (8) (2014) 3163–3169.
J. J. Palacios, A. González and C. R. González, Genetic tabu search for the fuzzy flexible job shop problem, Computers & Operations Research (2014) 5474–89.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Editor Haedo Jeong
Imen Driss received her Master’s degree from the Department of Industrial Engineering, University of Batna, Algeria, in 2010. She is currently a doctoral student at the Department of Industrial Engineering, University of Batna, Algeria. Her research interests include producti degree on scheduling, production engineering, ma nufacturing, and others. E-mail: idrissamina@hotmail.fr.
Kinza Nadia Mouss was born in Batna, Algeria, in 1960. She received the B.Sc. degree in Electrical Engineering in 1983 from the National Polytechnic School of Algiers, Algeria; the M.Sc. degree in Electrical and Computer Engineering in 1984 from the ENSERB, France; and the Ph.D. also in Electrical and Computer Engineering in 1986 from Bordeaux University, France. After graduation, she joined the University of Batna, Algeria, where she is a Professor of Electrical and Computer Engineering. Dr. Mouss is the head of the Computer Integrated Manufacturing and Supply Chain Management Group. Her current research interests include industrial supply chain management, production systems, and computer integrated manufacturing. E-mail: kinzmouss@yahoo.fr.
Rights and permissions
About this article
Cite this article
Driss, I., Mouss, K.N. & Laggoun, A. A new genetic algorithm for flexible job-shop scheduling problems. J Mech Sci Technol 29, 1273–1281 (2015). https://doi.org/10.1007/s12206-015-0242-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12206-015-0242-7