An estimation of distribution algorithm for combinatorial optimization problems
DOI:
https://doi.org/10.12928/ijio.v3i1.5862Keywords:
Estimation of distribution algorithm, Mallows model, Moth-flame algorithm, Job shop scheduling problem, Vehicle routing problem with time windowsAbstract
This paper considers solving more than one combinatorial problem considered some of the most difficult to solve in the combinatorial optimization field, such as the job shop scheduling problem (JSSP), the vehicle routing problem with time windows (VRPTW), and the quay crane scheduling problem (QCSP). A hybrid metaheuristic algorithm that integrates the Mallows model and the Moth-flame algorithm solves these problems. Through an exponential function, the Mallows model emulates the solution space distribution for the problems; meanwhile, the Moth-flame algorithm is in charge of determining how to produce the offspring by a geometric function that helps identify the new solutions. The proposed metaheuristic, called HEDAMMF (Hybrid Estimation of Distribution Algorithm with Mallows model and Moth-Flame algorithm), improves the performance of recent algorithms. Although knowing the algebra of permutations is required to understand the proposed metaheuristic, utilizing the HEDAMMF is justified because certain problems are fixed differently under different circumstances. These problems do not share the same objective function (fitness) and/or the same constraints. Therefore, it is not possible to use a single model problem. The aforementioned approach is able to outperform recent algorithms under different metrics for these three combinatorial problems. Finally, it is possible to conclude that the hybrid metaheuristics have a better performance, or equal in effectiveness than recent algorithms.
References
Kim, Y., Park, K., & Ko, J. (2003). A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Computers & Operations Research, 30, 1151-1171.
Rossi, A., & Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robotics and Computer-Integrated Manufacturing, 23, 503-516.
Dauod, H., Li, D., Yoon, S., & Srihari, K. (2016). Multi-objective optimization of the order scheduling problem in mail-order pharmacy automation systems. International Journal of Advanced Manufacturing Technology. 99, 73–83
Yue, L., Guan, Z., Saif, U., Zhang, F., & Wang, H. (2016). Hybrid Pareto artificial bee colony algorithm for multi objective single machine group scheduling problem with sequence dependent setup times and learning effects. Springerplus, 5(1593). doi:10.1186/s40064 016 3265 3
Huang, S., Tian, N., Wang, Y., & Ji, Z. (2016). Multi objective flexible job shop scheduling problem using modified discrete particle swarm optimization. Springerplus, 5(1432). doi:10.1186/s40064 016 3054 z
Xu, H., Bao, Z., & Zhang, T. (2017). Solving dual flexible job‐shop scheduling problem using a Bat Algorithm. Advances in Production Engineering & Management, 12(1), 5-16.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31, 1985-2002.
Gao, J., Sun, L., & Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35, 2892-2907.
Zeng, Q., & Yang, Z. (2009). Integrating simulation and optimization to schedule loading operations in container terminals. Computers & Operations Research, 36, 1935-1944.
Lee, L., Chew, E., Tan, K., & Wang, Y. (2010). Vehicle dispatching algorithms for container transshipment hubs. OR Spectrum, 32, 663-685.
Schittekat, P., Kinable, J., Sörensen, K., Sevaux, M., & Spieksma, F. (2013). A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research, 229, 518-528.
Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible jobshop scheduling problem. International Journal of Production Economics, 174, 93-110.
Raden, A.C.L., Mohd, N.A.R., Wan, M.F.W.M., & Chairul, S. (2019). Integrated Vendor–Buyer Lot-Sizing Model with Transportation and Quality Improvement Consideration under Just-in-Time Problem. Mathematics, 7(10), 944.
Raden, A.C.L., Fairul, A.B.J., Chairul, S., Mohd, R.B.M., & Mohd, N.A.R. (2014). Incorporating Transportation Cost into Joint Economic Lot Size For Single Vendor-Buyer. Journal of Software, 9(5), 1313-1323.
Leuveano, A.C., Bin Jafar, F.A., & Bin Muhamad, M.R. (2012). Development of genetic algorithm on multi-vendor integrated procurement-production system under shared transportation and just-in-time delivery system. 2nd International Conference on Uncertainty Reasoning and Knowledge Engineering, 2012, pp. 78-81.
Jarboui, B., Eddaly, M., & Siarry, P. (2009). An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Computers & Operations Research, 36, 2638-2646.
Chen, S., Chen, M., Chang, P., Zhang, Q., & Chen, Y. (2010). Guidelines for developing effective Estimation of Distribution Algorithms in solving simple machine scheduling problems. Expert Systems with Applications, 37, 6441-6451.
Pan, Q., & Ruiz, R. (2012). An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega, 40, 166-180.
Wang, L., Wang, S., Xu, Y., Zhou, G., & Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62, 917-926.
Chen, Y., Chen , M., Chang, P., & Chen, S. (2012). Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems. Computers & Industrial Engineering, 62, 536-545.
González, T., & Sahni, S. (1978). Flowshop and jobshop schedules: complexity, and approximation. Operations Research, 26, 36–52.
Mühlenbein, H. (1997). The equation for response to selection and its use for prediction. Evolutionary Computation, 5(3), 303-346.
De Bonet, J., Isbell, C., & Viola, P. (1997). MIMIC: Finding Optima by Estimation Probability Densities. In Advances in Neural Information Processing Systems, (pp. 424–430).
Baluja, S., & Davies, S. (1997). Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space. In D. Fisher (Ed.), Proceedings of the Fourteenth International Conference on Machine Learning, (pp. 30–38).
Pelikan, M., Goldberg, D., & Cantú-Paz, E. (1998). Linkage problem, distribution estimation, and Bayesian networks. The University of Illinois, Genetic Algorithm Laboratory, Urbana-Champaign., Illinois.
Pérez-Rodríguez, R., S, Jöns., Hernández-Aguirre, A., & Ochoa, C. (2014). Simulation optimization for a flexible jobshop scheduling problem using an estimation of distribution algorithm. International Journal of Advanced Manufacturing Technology, 73, 3-21.
Ceberio, J., Irurozki, E., Mendiburu, A., & Lozano, J. (2012). A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progress in Artificial Intelligence, 1, 103-117.
Wang, Y., Chen, Y., & Wang, k. (2009). A case study of genetic algorithms for quay crane scheduling. In B. Chien, & T. Hong (Ed.), Opportunities and challenges for next-generation applied intelligence. 214. Berlin, Heidelberg: Studies in Computational Intelligence, Springer.
Figliozzi, M. (2010). An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transportation Research Part C: Emerging Technologies, 18(5), 668-679.
Kamkar, I., Poostchi, M., and Totonchi, M.R.A. (2010). A cellular genetic algorithm for solving the vehicle routing problem with time windows. In: Gao, X-Z., Gaspar, A., Köppen, M., Schaefer, G., and Wang, J. (eds.) Soft Computing in Industrial Applications, Advances in Intelligent and Soft Computing 75, Springer-Verlag, Berlin Heidelberg, pp. 263-270.
Kaveshgar, N., Huynh, N., & Rahimian, S.-K. (2012). An efficient genetic algorithm for solving the quay crane scheduling problem. Expert Systems with Applications, 39(18), 13108-13117.
Chung, S.-H., & Choy, K.-L. (2012). A modified genetic algorithm for quay crane scheduling operations. Expert Systems with Applications, 39(4), 4213-4221.
Tas, D., Dellaert, N., van Woensel, T., and Kok, T. (2013). Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers & Operations Research, 40(1), 214-224.
Chung, S.-H., & Chan, T.-S. (2013). A workload balancing genetic algorithm for the quay crane scheduling problem. International Journal of Production Research, 51(16), 4820-4834.
Vidal, T., Crainic, T., Gendreau, M., & Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research, 40(1), 475-489.
Garg, H. (2014). A hybrid GA-GSA algorithm for optimizing the performance of an industrial system by utilizing uncertain data. In P. Vasant, Handbook of Research on Artificial Intelligence Techniques and Algorithms. IGI Global.
Phanden R.K., & Jain, A. (2015). Assessment of makespan performance for flexible process plans in job shop scheduling. IFAC-PapersOnLine. 48(3):1948-1953.
Garg, H. (2016). A hybrid PSO-GA algorithm for constrained optimization problems. Applied Mathematics and Computation, 274, 292-305.
Garg, H. (2019). A hybrid GSA-GA algorithm for constrained optimization problems. Information Sciences, 478, 499-523.
Peña, J., Robles, V., Larrañaga, P., Herves, V., Rosales, F., & Pérez, M. (2004). GA-EDA: Hybrid Evolutionary Algorithm Using Genetic and Estimation of Distribution Algorithms. In R. Orchard, C. Yang, & M. Ali (Ed.), IEA/AIE 2004, LNAI 3029, (pp. 361-371). Ottawa: Springer-Verlag Berlin Heidelberg.
Zhang, Q., Sun, J., Tsang, E., & Ford, J. (2006). Estimation of distribution algorithm with 2-opt local search for the quadratic assignment problem. Stud. Fuzziness Soft Computing, 192, 281-292.
Liu, H., Gao, L., & Pan, Q. (2011). A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Expert Systems with Applications, 38, 4348-4360.
Fang, C., Kolisch, R., Wang, L., & Mu, C. (2015). An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem. Flexible Services and Manufacturing Journal, 27, 585–605
Wang, K., Huang, Y., & Qin, H. (2016). A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown. Journal of the Operational Research Society, 67, 68-82.
Ceberio, J., Irurozki, E., Mendiburu, A., & Lozano, J. (2014). A Distance-Based Ranking Model Estimation of Distribution Algorithm for the Flowshop Scheduling Problem. IEEE Transactions on Evolutionary Computation, 18(2), 286-300.
Pérez-Rodríguez, R., Hernández-Aguirre, A., & Cruz, I. (2017). An estimation of distribution algorithm coupled with the generalized Mallows distribution for a school bus routing problem with bus stop selection. RIAI Revista Iberoamericana de Automática e Informática industrial, 14, 288-298.
Pérez-Rodríguez, R., & Hernández-Aguirre, A. (2018). A hybrid estimation of distribution algorithm for flexible job-shop scheduling problems with process plan flexibility. Applied Intelligence, 48, 3707–3734
Pérez-Rodríguez, R., & Hernández-Aguirre, A. (2019). A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. Computers & Industrial Engineering, 130, 75-96.
Mirjalili, S. (2015). Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm. Knowledge-Based Systems, 89, 228-249.
Mallows, C. (1957). Nonnull ranking models. Biometrika, 44(1-2), 114-130.
Fligner, M., & Verducci, J. (1986). Distance based ranking models. Journal of the Royal Statistical Society, 48(3), 359–369.
Fligner, M., & Verducci, J. (1988). Multistage ranking models. Journal of the American Statistical Association, 83(403), 892–901.
Yan, Y., & Wang, G. (2007). A job shop scheduling approach based on simulation optimization. Proceedings of the 2007 I.E. IEEM [54] Toth, P., & Vigo, D. (2001). The vehicle routing problem. Monographs on discrete mathematics, and applications. Philadelphia: SIAM.
Sun, D., Tang, L., & Baldacci, R., (2019). A Benders decomposition based framework for solving quay crane scheduling problems. European Journal of Operational Research, 273(2), 504–515.
Borda, J. (1784). Memoire sur les elections au scrutin. Histoire de l'Academie Royale des Science.
Meilă, M., Phadnis, K., Patterson, A., & Bilmes, J. (2007). Consensus ranking under the exponential model. UAI 2007, pp. 285-294.
Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391–401.
Fisher, H., & Thompson, G. (1963). Probabilistic learning combinations of local job-shop scheduling rules. In J. Muth, & G. Thompson (Ed.), Industrial Scheduling (pp. 225–251). Prentice Hall, Englewood Cliffs.
Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement). Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh.
Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3(2), 149–156.
Storer, R., Wu S, S., & Vaccari , R. (1992). New search spaces for sequencing problems with application to job shop scheduling. Management Science, 38(10), 1495–1509.
Yamada, T., & Nakano, R. (1992). A genetic algorithm applicable to large-scale job-shop problems. PPSN, 2, pp. 281–290.
Homberger, J., & Gehring, H. (2005). A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research, 162(1), 220–238.
Kim, K., & Park, Y. (2004). A crane scheduling method for port container terminals. European Journal of Operational Research, 156(3).
Li, X., Xing, K., Wu, Y., Wang, X., Luo, J. (2017). Total energy consumption optimization via genetic algorithm in flexible manufacturing systems. Computers & Industrial Engineering,104, 188-200.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 RICARDO PEREZ-RODRIGUEZ
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
- That it is not under consideration for publication elsewhere,
- That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Copyright
Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
1.png)
