Methods & Algorithms in Manufacturing and Assembly Industry Scheduling for Flexible Manufacturing System

Abstract:

Flexible Manufacturing Systems-FMS is a term with various types of definitions, each of them trying to describe the complexity and the generalized features. One of these features is their complexity, along with difficulties in building models that capture the system in all its important aspects. In a heterogeneous flexible system, the scheduling events or actions could be a combinatorial problem which claims a particular solution. Manufacturing scheduling process, in special for FMS, is a very difficult scheduling problem, because involves all the aspects of the processes: order, resources, transportation system i.e. automated vehicle guided, perturbation factors such as breakdowns of machine, etc. Typically, the scheduling problem is a NP-hard problem modeled in mathematical form. If we simulate n jobs or orders which have to be assigned to the m machines or resources, we will observe that the mathematical solution is a huge number that means (n!)m possibilities of solutions. The challenge of researchers is to solve this equation in a reasonable time with an optimal solution, and of course with minimal resources. Those scientists applied many solutions which became Operational Research-OR or Combinatorial Optimization-CO areas using a various methods: Local Search-LS, Artificial Intelligence-AI, heuristic method, priority rules, memetic or hybrid techniques which combine this techniques.

• Periodical: Advanced Materials Research (Volume 664)
• Pages: 1098-1106
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.664.1098
• Online since: February 2013
• Authors: Mircea Gorgoi
• Keywords: Evolution Strategy, Evolutionary Programming, Flexible Manufacturing Systems, Genetic Algorithm (GA), Genetic Programming, Hill Climbing, Simulated Annealing (SA), Taboo Search

References

[1] L. Davis, Job shop scheduling with genetic algorithms, Proceedings of the International Conference on Genetic Algorithms and their Applications, San Mateo, Morgan Kaufmann, pp.136-149, (1985).

[2] J.H. Holland, Adaptive algorithms for discovering and using general patterns in growing knowledge bases, International Journal of Policy Analysis and Information systems, 4(3), pp.245-268, (1980).

[3] R. Nakano, T. Yamada, Conventional genetic algorithm for job shop problem, Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, California, pp.477-479, (1991).

[4] H. Fang, P. Ross, D. Corne, A promising genetic algorithm approach to job shop scheduling, rescheduling, and open-shop scheduling problems, Proceedings of the 5th International Conference on Genetic Algorithms, Urbana-Champaign, Illinois, pp.375-382, (1993).

DOI: 10.1049/cp:19951040

[5] R.W. Cheng, M. Gen, Y. Tsujimura, "A tutorial survey of job shop scheduling problems using genetic algorithms: Part I: Representation, International Journal of Computers and Industrial Engineering 30(4), pp.983-997, (1996).

DOI: 10.1016/0360-8352(96)00047-2

[6] R.W. Cheng, M. Gen, Y. Tsujimura, A tutorial survey of job shop scheduling problems using genetic algorithms : Part II: Hybrid genetic search strategies, International Journal of Computers and Industrial Engineering 36, pp.343-364, (1999).

DOI: 10.1016/s0360-8352(99)00136-9

[7] C.D. Mattfield, C. Bierwirth, An efficient genetic algorithm for job shops scheduling with tardiness objectives, European Journal of Operational Research 155, pp.616-630, (2004).

DOI: 10.1016/s0377-2217(03)00016-x

[8] Y.M. Wang, N.F. Xiao, H.L. Yin, E.L. Hu, C.G. Zhao, Y.R. Jiang, A two stage genetic algorithm for large size job shop scheduling problem, The international Journal of Advanced Manufacturing Technology 39, pp.813-820, (2008).

DOI: 10.1007/s00170-007-1260-0

[9] L. Asadzadeh, K. Zamanifar", An agent-based parallel approach for job shop scheduling problem with genetic algorithms", Mathematical and Computer Modelling 52(11-12), pp.1957-1965, (2010).

DOI: 10.1016/j.mcm.2010.04.019

[10] A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian, Ant system for job-shop scheduling, JORBEL-Belgian Journal of Operations Research, Statistics and Computer Science 34, pp.39-53, (1994).

[11] C. Bierwirth, A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spectrum, 17, pp.87-92, (1995).

DOI: 10.1007/bf01719250

[12] S.C. Esquirel, S.W. Ferrero, R.H. Gallard, Parameter Settings and Representations" In Pareto-Based Optimization for Job Shop Scheduling, Cybernetics and Systems 33, Taylor & Francis, pp.559-578, (2002).

DOI: 10.1080/01969720290040759

[13] M.L. Pinedo, Scheduling, Theory, Algorithms, and Systems, 3rd ed., Springer Science-Business Media, LLC, New York, (2008).

[14] A.S. Jain, S. Meeran, Deterministic job shop scheduling: past, present, future, European Journal of Operational research, 113(2), (1998).

DOI: 10.1016/s0377-2217(98)00113-1

[15] K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, A fast and elitist multiojective genetic algorithm for multi-objective optimization: NSGA-II, Proceedings of the VIth Parallel Problem Solving from Nature Conference, Paris, pp.849-859, (2000).

DOI: 10.1007/3-540-45356-3_83

[16] C. Bierwirth, C.D. Mattfield, H. Kopfer, On permutation representations for scheduling problems, Proceedings of the 4th Conference on Parallel Problem Solving from Nature (PPSN IV), pp.310-318, (1996).

DOI: 10.1007/3-540-61723-x_995

[17] T. Yamada, R. Nakano, Scheduling by genetic local search with multi-step crossover, Proceedings of the 4th Conference on Parallel Problem Solving from Nature (PPSN IV), H.M. Voigt, W. Ebeling, I. Rechenberg and H.P. Schwefel (Eds. ), pp.960-969, (1996).

DOI: 10.1007/3-540-61723-x_1059

[18] D.E. Godberg, Genetic algorithms in Search, Optimization and Machine learning, Addison-Wesley Reading, MA, (1989).

[19] G. Zhang, X. Shao, P. Li, L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job shop scheduling problem, Computers & Industrial Engineering 56(4), pp.1309-1318, (2009).

DOI: 10.1016/j.cie.2008.07.021

[20] M. Mastrolilli, L.M. Gambardella, Effective neighborhood functions for the flexible job shop problem, Journal of Scheduling 3(1), pp.3-20, (2000).

DOI: 10.1002/(sici)1099-1425(200001/02)3:1<3::aid-jos32>3.0.co;2-y

[21] I. Kacem, Scheduling flexible job-shops: a worst case analysis and evolutionary algorithm, International Journal of Computational Intelligence and Applications 3(4), Imperial College Press, pp.437-452, (2003).

DOI: 10.1142/s1469026803001117

[22] F.T.S. Chan, T.C. Wong, L.Y. Chang, Flexible job-shop scheduling problem under resource constraints, International Journal of Production Research 44(11), pp.2071-2089, (2006).

DOI: 10.1080/00207540500386012

[23] S.W. Mahfood, D.E. Goldberg, Parallel recombinative simulated annealing a genetic algorithm, Parallel Computing 21, pp.1-28, (1995).

DOI: 10.1016/0167-8191(94)00071-h

[24] J.D. L. Silva, E.K. Burke, S. Petrovici, An introduction to multi-objective metaheuristics for scheduling and timetable, Automated Scheduling, Optimization and Planning Research Group, ISN Workshop, School of Computer Science and IT, University of Nottingham, UK, (2004).

[25] M. Affenzeller, S. Wagner, SASEGASA: A new genetic parallel evolutionary algorithm for achieving highest quality results, Journal of Heuristics 10, Kluver Academic Publisher, pp.234-267, (2004).

DOI: 10.1023/b:heur.0000026895.72657.a2

[26] J. Heitko Her and D. Beasley (Eds. ), Hitch-Hiker's Guide to Evolutionary Computation, A list of Frequently Asked Question (FAG). ENCORE (The Evolutionary Computation Repository Network), (1998).

[27] J.R. Koza, Hierarchical genetic algorithms operating on population of computer programs,. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, pp.768-774, (1989).

[28] J.R. Koza, Genetic evolution and co-evolution by computers program,. In Artificial Life II, pp.603-629, (1990).

[29] J.R. Koza, Genetic Programming Computers by Means of Natural Selection, Bradford Book, MIT Press, Cambrige, Massachusetts, USA, (1992).

[30] A.S. Bickel and R.W. Bickel, Tree structured rules in genetic algorithms,. Proceeding of the Second International Conference on Genetic algorithms and their application, pp.77-81, (1987).

[31] W. Banzhof, P. Nordin, R.E. Keller and F.D. Francine, Genetic Programming: An Introduction-on the Automatic Evolution of Computer Programs and its applications,. Morgan Kaufmann Publisher, San Francisco, CA, USA/Heidelberg, Germany, (1997).

[32] R. Poli, Evolution of graph-like programs with parallel distributed genetic programming,. In Genetic Algorithms; Proceedings of the Seventh International Conference, pp.346-353, (1997).

[33] H.J. Antonisse, A grammar-Based genetic algorithm,. In Proceedings of Fundations of Genetic Algorithms FOGA-90, pp.193-204, (1990).

[34] M.L. Wong, K.S. Leung, An adaptive inductive logic programming system using genetic programming,. In Evolutionary Programming IV Proceedings of the Fourth Annual Conference on Evolutionary Programming, pp.737-752, (1995).

DOI: 10.7551/mitpress/2887.003.0062

[35] A.G. Schultz, Fuzzy Rule Based Expert Systems and Genetic Machine Learning, Studies in Fuzziness and Soft Computing Vol. 3, Physica-Verlag, 2nd rev. ed, (1997).

[36] C. Ryan, M. O'Neill, J.J. Collins", Grammatical evolution: Solving trigonometric industries", Proceedings of Mendel 1998: 4th International Mendel Conference on Genetic Algorithms Optimization Problems, FUZZY Logic, Neural Networks, Rough Sets, pp.111-119, (1998).

[37] C. Ryan, M. O'Neill, Grammatical evolution: A study approach,. In Late Breaking Papers at the Genetic Programming 1998 Conference, (1998).

[38] M. O'Neill, F. Leahy, A. Brabazon, Grammatical swarm: Available-length particle swarm algorithm, In Swarm Intelligent Systems, Springer, (2006).

DOI: 10.1007/978-3-540-33869-7_3

[39] M. O'Neill, A. Brabazon, Grammatical differential evolution, In R. Arabnia (Eds. ) Proceedings of the 2006 International Conference on Artificial Intelligence, ICAI 2006, vol1, pp.231-236, CSREA Press, Las Vegas, Nevada, USA, (2006).

[40] M. O'Neill, Automatic Programming in an Arbitrary Language: Evolving Programs with Grammatical Evolution, PhD Thesis, University of Limerick, (2001).

[41] I. Rechenberg, Cybernetic Solution Path of an Experimental Problem, Royal Air-Craft Establishment, Library Translation 1122, Farnborough, (2005).

[42] H.D. Huang, J.T. Yang, S.F. Shen, J.T. Horng, An evolution strategy to solve sports scheduling problems, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, vol. 1, pg. 943, (1999).

[43] R. Storm and K. Price, Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces,. Technical Report T-95-012, International Computer Science Institute, Berkeley, CA 94704, Berkeley, CA, (1995).

[44] B. Apolloni, R.J. Howlett, L.C. Jain (Eds. ), "Proceedings of 11th International Conference on the Knowledge-Based Intelligent Information and Engineering Systems, KES 2007, and the XVII Italian Workshop on Neural Networks, Part III, vol. 4694 of lecture Notes in Computer Science (LNCS), 2007, Springer, Italy.

DOI: 10.1007/978-3-540-74829-8

[45] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, Equation on state calculations by fast computing machines, The Journal of Chemical Physics, 21(6), pp.1087-1092, (1953).

DOI: 10.1063/1.1699114

[46] S. Kirkpatrick, C.D. Jr. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science 220, pp.671-680, (1983).

DOI: 10.1126/science.220.4598.671

[47] E.H.L. Aarts, R. Varssens, J.K. Lenstra, Job-shop scheduling by simulated annealing, Operation Research 40, pp.113-125, (1988).

DOI: 10.1287/opre.40.1.113

[48] P.V. Laarhoven, E. Aarts, J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40(1), pp.113-125, (1992).

DOI: 10.1287/opre.40.1.113

[49] M.E. Aydin, T.C. Fogarty, A simulated annealing algorithm for multi-agent systems: a job-shop scheduling application, Journal of Intelligent manufacturing 15(6), pp.805-814, (2004).

DOI: 10.1023/b:jims.0000042665.10086.cf

[50] S.J. Russel, P. Norving, Artificial Intelligence: A Modern Approach, Prentice Hall, second edition, (2002).

[51] B.P. Gerkey, S. Thrum, G. Gordon, Parallel Stochastic hill-climbing with small teams,. In L.E. Parker, F.E. Schneider, A.C. Schultz (Eds. ). Proceeding from 2005 International Workshop on Multi-Robots Systems, vol. III of Multi-Robots Systems: from Swarm to Intelligent Automata, pp.65-77, Springer (2005).

DOI: 10.1007/1-4020-3389-3_6

[52] R. M. Arex, S. Binato, M. G. C. Resende, Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing 29(4), pp.393-430, (2002).

DOI: 10.1016/s0167-8191(03)00014-0

[53] C. Fleurent, F. Glover, Improved constructive multistrat strategies for the quadratic assignment problem using adaptive memory,. INFORMS Journal on Computing 11, pp.198-204, (1999).

DOI: 10.1287/ijoc.11.2.198

[54] F. Glover, E.D. Taillard, D. de Werra, An user's quid to taboo search, annals of Operations Research, 41(3), pp.3-28, (1993).

[55] M. Dell'Amico, M. Trubian, Applying Taoo-search to the Job Shop Scheduling Problem, Annals of Operations Research 41, pp.231-252, (1991).

DOI: 10.1007/bf02023076

[56] E. Nowichi, C. Smutnick, A Fast Taboo Search algorithm for the Job Shop Problem, Management Science 42, pp.797-813, (1996).

DOI: 10.1287/mnsc.42.6.797

[57] P. Brucker, T. Kampmeyer, Taboo search algorithms for cycle machine scheduling problem, Journal of Scheduling 8(4), pp.303-322, (2005).

DOI: 10.1007/s10951-005-1639-4

[58] M. Dorigo, V. Maniezzo, a. Colorni, The Ant system: Optimization by a colony of cooperating agents,. IEEE transactions on Systems, man, and Cybernetics Part B: Cybernetics, 26(1): pp.29-41, (1996).

DOI: 10.1109/3477.484436