A Multi-swarm Approach to Multi-objective Flexible Job-shop Scheduling Problems

• Autorzy: Liu H. , Abraham A. , Wang Z.
• Języki publikacji: EN

Abstrakty

EN

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 model the scheduling problem for the multi-objective Flexible Job-shop Scheduling Problems (FJSP) and attempt to formulate and solve the problem using a Multi Particle Swarm Optimization (MPSO) approach. MPSO consists of multi-swarms of particles, which searches for the operation order update and machine selection. All the swarms search the optima synergistically and maintain the balance between diversity of particles and search space. We theoretically prove that the multi-swarm synergetic optimization algorithm converges with a probability of 1 towards the global optima. The details of the implementation for the multi-objective FJSP and the corresponding computational experiments are reported. The results indicate that the proposed algorithm is an efficient approach for the multi-objective FJSP, especially for large scale problems.

Słowa kluczowe

EN

swarm intelligence; emergence; multi-objective optimization; flexible job shop scheduling; particle swarm optimization (PSO); multi-swarm; probability; convergence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 95, nr 4
• Strony: 465--489
• Opis fizyczny: Bibliogr. 77 poz., tab., wykr.

Twórcy

autor

Liu H.

autor

Abraham A.

autor

Wang Z.

• School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China,

Bibliografia

• [1] Kennedy, J., Eberhart, R.: Swarm Intelligence, Morgan Kaufmann Publishers, San Francisco, CA, 2001.
• [2] Clerc, M.: Particle Swarm Optimization, ISTE Publishing Company, London, 2006.
• [3] Schute, J. F., Groenwold, A. A.: A study of global optimization using particle swarms, Journal of Global Optimization, 31, 2005, 93-108.
• [4] Grosan, C., Abraham, A., Nicoara,M.: Search optimization using hybrid particle sub-swarms and evolutionary algorithms, International Journal of Simulation Systems, Science & Technology, 6(10-11), 2005, 60-79.
• [5] Abraham, A., Guo, H., Liu, H.: Swarm intelligence: foundations, perspectives and applications, in: Swarm Intelligent Systems, (N. Nedjah and L.Mourelle, Eds.), Studies in Computational Intelligence, Springer Verlag Germany, 2006, 3-25.
• [6] Abraham, A., Liu, H., Clerc, M.: Chaotic dynamic characteristics in swarm intelligence, Applied Soft Computing Journal, 7, 2007, 1019-1026.
• [7] Paquet, U., Engelbrecht, A. P.: Particle swarms for linearly constrained optimisation, Fundamenta Informaticae, 76(1-2), 2007, 147-170.
• [8] Das, S., Abraham, A., Konar, A.: Automatic kernel clustering with a multi-elitist particle swarm optimization algorithm, Pattern Recognition Letters, 29, 2008, 688-699.
• [9] Liu, H., Abraham, A., Hassanien, A.E.: Scheduling job on computational Grids using fuzzy particle swarm algorithm, Future Generation Computer Systems, http://dx.doi.org/10.1016/j.future.2009.05. 022, 2009.
• [10] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
• [11] Brucker, P.: Scheduling Algorithms (2nd edition), Springer, Heidelberg, 1998.
• [12] Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems (3rd edition), Springer, Heidelberg, 2008.
• [13] Brucker, P., Schlie, R.: Job-shop scheduling with multi-purpose machines, Computing, 45(4), 1990, 369-375.
• [14] Jansen, K., Mastrolilli, M., Solis-Oba, R.: Approximation algorithms for flexible job shop problems. Lecture Notes in Computer Science, 1776, 2000, 68-77.
• [15] Mastrolilli, M., Gambardella, L. M.: Effective neighborhood functions for the flexible job shop problem, Journal of Scheduling, 3(1), 2002, 3-20.
• [16] Pezzellaa, F., Morganti, G., Ciaschetti, G.: A genetic algorithm for the flexible job-shop scheduling problem, Computers and Operations Research, 35(10), 2008, 3202-3212.
• [17] Stecke, K. S.: Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems, Management Science, 29(3), 1983, 273-288.
• [18] Akella, R., Choong, Y.: Performance of a hierarchical production scheduling policy, IEEE Transactions on Components, Hybrids and Manufacturing Technology, 7(3), 1984, 225-248.
• [19] Bona, B., Brandimarte, P.: Hybrid hierarchical scheduling and control systems inmanufacturing, IEEE Transactions on Robotics and Automation, 6(6), 1990, 673-686.
• [20] Brandimarte, P.: Routing and scheduling in a flexible job-shop by tabu search, Annals of Operations Research, 2, 1993, 158-183.
• [21] Paulli, J.: A hierarchical approach for the FMS scheduling problem, European Journal of Operational Research, 86(1), 1995, 32-42.
• [22] Barnes, J. W., Chambers, J. B.: Flexible job shop scheduling by tabu search, Graduate program in operations research and industrial engineering, Technical Report, ORP 9609, University of Texas, Austin, 1996, http://www.cs.utexas.edu/users/jbc/
• [23] Hurink, J., Jurish, B., Thole, M.: Tabu search for the job shop scheduling problem with multi-purpose machines, OR-Spektrum, 15, 1994, 205-215.
• [24] Dauzére-Pérés S., Paulli, J.: An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Annals of Operations Research, 70, 1997, 281-306.
• [25] Mastrolilli, M., Gambardella, L. M.: Effective neighborhood functions for the flexible job shop problem, Journal of Scheduling, 3, 1996, 3-20.
• [26] Saidi-Mehrabad, M., Fattahi, P.: Flexible job shop scheduling with tabu search algorithms, International Journal of Advanced Manufacturing Technology, 32, 2007, 563-570.
• [27] Cheng, R., Gen, M., Tsujimura, Y.: A tutorial survey of job-shop scheduling problems using genetic algorithms, part I: representation, International Journal of Computers and Industrial Engineering, 30, 1996, 983-997.
• [28] Cheng, R., Gen M., Tsujimura, Y.: 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, 1996, 343-364.
• [29] Gao, J., Sun, L., Gen, M.: A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers and Operations Research, 35(9), 2008, 2892-2907.
• [30] Zhang, H., Gen, M.: Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of Complexity International, 11, 2005, 223-232.
• [31] Chen, H., Ihlow, J., Lehmann, C.: Agenetic algorithm for flexible job-shop scheduling, IEEE International Conference on Robotics and Automation, Detroit, 1999, 1120-1125.
• [32] Jia, H. Z., Nee, A., Fuh, J., Zhang, Y.: A modified genetic algorithm for distributed scheduling problems, International Journal of Intelligent Manufacturing, 14, 2003, 351-362.
• [33] Ho, N. B., Tay, J. C.: GENACE: an efficient cultural algorithm for solving the flexible job-Shop problem, IEEE International Conference on Robotics and Automation, 2004, 1759-1766.
• [34] Ho, N. B., Tay, J. C., Lai, E.: An effective architecture for learning and evolving flexible job-shop schedules, European Journal of Operational Research, 179, 2007, 316-333.
• [35] Ong, Z. X., Tay, J. C., Kwoh, C. K.: Applying the clonal selection principle to find flexible job-shop schedules. Lecture Notes in Computer Science, 3627, 2005, 442-455.
• [36] Kleeman, M. P., Lamont, G. B.: Scheduling of flow-shop, job-shop, and combined scheduling problems using MOEAs with fixed and variable length chromosomes, Studies in Computational Intelligence, 49, 2007, 49-99.
• [37] Kacem, I., Hammadi, S., Borne, P.: Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man, and Cybernetics, Part C, 32(1), 2002, 1-13.
• [38] Kacem, I., Hammadi, S., Borne, P.: Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic,Mathematics and Computers in Simulation, 60, 2002, 245-276.
• [39] Tanev, I. T., Uozumi, T., Morotome, Y.: Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: application service provider approach, Applied Soft Computing, 5, 2004, 87-100.
• [40] Liouane, N., Saad, I., Hammadi, S., Borne, P.: Ant systems & local search optimization for flexible job shop scheduling production, International Journal of Computers, Communications& Control, 2(2), 2007, 174-184.
• [41] Blum C., Samples, M.: An Ant Colony Optimization Algorithm for Shop Scheduling Problems, Journal of Mathematical Modeling and Algorithms, 3, 2004, 285-308.
• [42] Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job-shop problem, Management Science, 42(2), 1996, 797-813.
• [43] Wu, Z., Weng, M. X.: Multiagent scheduling method with earliness and tardiness objectives in flexible job shops, IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 35(2), 2005, 293-301.
• [44] Xia, W., Z. Wu, Z.: An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers and Industrial Engineering, 48, 2005, 409-425.
• [45] Sha, D. Y., Hsu, C. Y.: A hybrid particle swarm optimization for job shop scheduling problem, Computers & Industrial Engineering, 51(4), 2006, 791-808.
• [46] Giffler, J. and Thompson, G. L.: Algorithms for solving production scheduling problems, Operations Research, 8, 1960, 487-503.
• [47] Baykasoglu, A., Özbkir, L., Sőnmez, A.: Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems, Journal of Intelligent Manufacturing, 15, 2004, 777-785.
• [48] Parsopoulos, K. E., Vrahatis, M. N.: Recent approaches to global optimization problems through particle swarm optimization, Natural Computing, 1, 2002, 235-306.
• [49] Ripon, K., C. Tsang, C., Kwong, S. An evolutionary approach for solving the multi-objective job-shop scheduling problem, Studies in Computational Intelligence, 49, 2007, 165-195.
• [50] Salman, A., Ahmad, I., Al-Madani, S.: Particle swarm optimization for task assignment problem, Microprocessors and Microsystems, 26, 2002, 363-371.
• [51] van den Bergh, F., Engelbrecht, A. P.: A study of particle swarm optimization particle trajectories, Information Sciences, 176, 2006, 937-971.
• [52] Liu, H., Abraham, A.: Chaos and swarm intelligence, in: Intelligent Computing Based on Chaos (L. Kocarev, Z. Galias, S. Lian, Eds.), Studies in Computational Intelligence, Springer Verlag, Germany, 184, 2009, 197-212.
• [53] Clerc M., Kennedy, J.: The particle swarm-explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 2002, 58-73.
• [54] Cristian, T. I.: The particle swarm optimization algorithm: convergence analysis and parameter selection, Information Processing Letters, 85(6), 2003, 317-325.
• [55] Liu, H., Li, B., Ji, Y., Sun, T.: Particle swarm optimisation from lbest to gbest, in: Applied Soft Computing Technologies: The Challenge of Complexity (A. Abraham, B. D. Baets, M. Kőppen, B. Nickolay Eds.), Springer, 2006, 537-545.
• [56] Liu, H., Abraham, A.: An hybrid fuzzy variable neighborhood particle swarm optimization algorithm for solving quadratic assignment problems, Journal of Universal Computer Science, 13(7), 2007, 1032-1054.
• [57] Gen, M., Tsujimura, Y., Kubota, E.: Solving job-shop scheduling problem using genetic algorithms, in: Proceedings of the 16th International Conference on Computer and Industrial Engineering, 1994, 576-579.
• [58] Liu, B., Wang, L., Jin, Y.: An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers, Computers and Operations Research, 33(10), 2006, 2960-2971.
• [59] Tasgetiren, M. F., Sevkli, M., Liang, Y. C., Gencyilmaz, G.: Particle swarm optimization algorithm for permutation flow shop sequencing problem, Lecture Notes in Computer Science, 3172, 2004, 382-389.
• [60] van den Bergh, F., Engelbrecht, A. P.: A cooperative approach to particle swarm optimization, IEEE Transactions on Evolutionary Computation, 8(3), 2004, 225-239.
• [61] Settles, M., Rylander, B.: Neural network learning using particle swarm optimizers, Advances in Information Science and Soft Computing, 2002, 224-226.
• [62] Blackwell, T., Branke, J.: Multi-swarm optimization in dynamic environments, Lecture Notes in Computer Science, 3005, 2004, 489-500.
• [63] Settles, M., Soule, T.: Breeding swarms: a GA/PSO hybrid, in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 2005, 161-168.
• [64] Elshamy, W., Emara, H. M., Bahgat, A.: Clubs-based particle swarm optimization, in: Proceedings of the IEEE International Conference on Swarm Intelligence Symposium, 1, 2007, 289-296.
• [65] Guo, C., Tang, H.: Global convergence properties of evolution stragtegies, Mathematica Numerica Sinica, 23(1), 2001, 105-110.
• [66] He, R., Wang, Y., Wang, Q., Zhou, J., Hu, C.: An improved particle swarm optimization based on selfadaptive escape velocity, Chinese Journal of Software, 16(12), 2005, 2036-2044.
• [67] Weisstein, E. W.: Borel-Cantelli Lemma. From Math World - A Wolfram Web Resource, http://mathworld.wolfram.com/Borel-CantelliLemma.html, 2007.
• [68] Xu, Z., Cheng, G., Liang, Y.: Search capability for an algebraic crossover, Journal of Xi'an Jiaotong University, 33(10), 1999, 88-99.
• [69] Whitley, L. D.: Fundamental principles of deception in genetic search, in: Foundation of Genetic Algorithms, (J. E. Gregory, Ed.), California: Morgan Kaufmann Publishers, 1991, 221-241.
• [70] Holland, J. H.: Adaptation in natural and artificial systems, Ann Arbor: University of Michigan Press, 1975.
• [71] Goldberg, D. E.: Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA: Addison-Wesley, 1989.
• [72] Taillard, E. D.: Benchmarks for basic scheduling problems, European Journal of Operational Research, 64(2), 1993, 278-285.
• [73] Tay, J. C., Wibowo, D.: An effective chromosome representation for evolving flexible job shop schedules, Lecture Notes in Computer Science, 3103, 2004, 210-221.
• [74] Fisher, H., Thompson, L.: Probabilistic learning combinations of local job shop scheduling rules, in: Industrial Scheduling (J. F. Muth, G. L. Thompson, Eds.), NJ: Prentice-Hall, 1968, 225-251.
• [75] Lawrence, S.: Supplement To Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Techniques, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1984.
• [76] Abraham, A., Nedjah, N., Mourelle, L.: Evolutionary computation: from genetic algorithms to genetic programming, in: Studies in Computational Intelligence (N. Nedjah, et al. Eds.), Germany: Springer Verlag, 2006, 1-20.
• [77] Cantu-Paz, E.: Efficient and Accurate ParallelGenetic Algorithms, Kluwer Academic publishers, Netherland, 2000.