Population Initialisation Methods for Fuzzy Job-Shop Scheduling Problems: Issues and Future Trends

Iman Mousa Shaheed, Syaimak Abdul Shukor, Salwani Abdullah

Abstract


Scheduling job shops in the real-world manufacturing environment is a multifarious task that involved various and multiple components, solutions and approach. Fuzzy Job-Shop Scheduling Problems (Fuzzy JSSPs) are most commonly addressed by the population-based Meta-heuristic algorithms. These algorithms usually derive near-optimum solutions within reasonable computational times, almost by two main steps; the initialisation and then improvement step. Numerous theoretical studies pointed out that a Meta-heuristic performance is mainly affected by the performance of its initialisation method. The main purpose of this paper is to understand the existing trend and concerns of issues in population initialisation for Fuzzy JSSPs research by examining the published articles and furthermore to provide comprehension insight and future direction on these methods. Therefore, this paper determined to review and classify the existing literature on Fuzzy JSSPs and analyse the performance of the initialisation methods used to identify their possible limitations. In consequence, previous works outlined three potential methods for initial solutions generation, which are Random-based, priority rules-based, and heuristic methods. However, the current analysis showed that Heuristic-based initialisation approach remains lacking in the Fuzzy JSSPs domain in spite of its successful performance in the crisp JSSP domain, especially, its capability to generate high-quality initial population that consists of optimal or near optimal solutions. Furthermore, this paper identifies probable gaps and reveals several performance limitations in the existing methods, which demands for an urgent solution to develop alternatives. Promising suggestions for future studies are also provided that may lead to new Heuristic Initialisation methods to be proposed in order to overcome the existing shortcomings.

Keywords


Fuzzy job shop scheduling, population initialisation

Full Text:

PDF

References


Roshanaei, V. (2012). Mathematical Modelling and Optimization of Flexible Job Shops Scheduling Problem. (M.A.Sc.), University of Windsor.

Zalmiyah Zakaria, Safaai Deris, Muhamad Razib Othman, Shahreen Kasim (2017). Non-Reshuffle-Based Approach for Reshceduling of Flexible Manufacturing System. International Journal on Advanced Science Engineering, Information Technology, 4(2), 1543-1552.

Kuroda, M., & Wang, Z. (1996). Fuzzy job shop scheduling. International Journal of Production Economics, 44(1–2), 45-51

Maroosi, A., Muniyandi, R.C., Sundararajan, E., Md Zain, A., (2016). A Parallel Membrane Inspired Harmony Search for Optimization Problems: A Case Study based on a Flexible Job Shop Scheduling Problem. Applied Soft Computing, 49 120-136.

Behnamian, J. (2015). Survey on fuzzy shop scheduling. Fuzzy Optimization and Decision Making, 1-36.

Rahnamayan, S., Tizhoosh, H. R., & Salama, M. M. A. (2007, 25-28 Sept. 2007). Quasi-oppositional Differential Evolution. Evolutionary Computation, 2007.

Victer Paul, P., Ramalingam, A., Baskaran, R., Dhavachelvan, P., Vivekanandan, K., & Subramanian, R. (2014). A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach. Journal of Computational Science, 5(2), 277-297.

Abdolrazzagh-Nezhad, M., & Abdullah, S. (2014). A Robust Intelligent Construction Procedure for Job-Shop Scheduling. Information Technology and Control, 43(3), 217-229.

Chen, Y., Fan, Z.-P., Ma, J., & Zeng, S. (2011). A hybrid grouping genetic algorithm for reviewer group construction problem. Expert Systems with Applications, 38(3), 2401-2411.

Yugay, O., Kim, I., Kim, B., & Ko, F. I. S. (2008, 11-13 Nov. 2008). Hybrid Genetic Algorithm for Solving Traveling Salesman Problem with Sorted Population. Paper presented at the Convergence and Hybrid Information Technology, 2008. ICCIT '08.

Abdolrazzagh-Nezhad, M., & Abdullah, S. (2017), Job Shop Scheduling: Classification, Constraints and Objective Functions. International Journal of Computer and Information Engineering. 11(4), 429-434.

Maaranen, H., Miettinen, K., & Mäkelä, M. M. (2004). Quasi-random initial population for genetic algorithms. Computers & Mathematics with Applications, 47(12), 1885-1895.

Ge, H.-W., Sun, L., Liang, Y.-C., & Qian, F. (2008). An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 38(2), 358-368.

Park, B. J., Choi, H. R., & Kim, H. S. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering, 45(4), 597-613.

Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38(4), 3563-3573.

Moaath Shatnawi, Mohammad Faidzul Nasrudin, Shahnorbanun Sahran, (2017). A New Initialization Technique in Polar Coordinates for Particle Swarm Optimization and Polar PSO. International Journal on Advanced Science Engineering, Information Technology, 7(1), 242-249.

Fortemps, P. (1997). Job shop scheduling with imprecise durations: a fuzzy approach. Fuzzy Systems, IEEE Transactions on, 5(4), 557-569.

Lin, F.-T. (2001). A job-shop scheduling problem with fuzzy processing times. In Computational Science-ICCS 2001 (pp. 409-418): Springer.

Tavakkoli-Moghaddam, R., Safaei, N., & Kah, M. (2008). Accessing feasible space in a generalized job shop scheduling problem with the fuzzy processing times: a fuzzy-neural approach. Journal of the Operational Research Society, 431-442.

García-Ãlvarez, J., González-Rodríguez, I., Vela, C. R., González, M. A., & Afsar, S. (2018). Genetic fuzzy schedules for charging electric vehicles. Computers & Industrial Engineering, 121, 51-61.

González Rodrıguez, I., Vela, C. R., Hernández-Arauzo, A., & Puente, J. (2009). Improved local search for job shop scheduling with uncertain durations. Paper presented at the Proc. of ICAPS.

Gonzalez-Rodriguez, I., Puente, J., Vela, C. R., & Varela, R. (2008). Semantics of Schedules for the Fuzzy Job-Shop Problem. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 38(3), 655-666.

Hu, Y., Yin, M., & Li, X. (2011). A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. The International Journal of Advanced Manufacturing Technology, 56(9-12), 1125-1138.

Lei, D. (2009a). A genetic algorithm for flexible job shop scheduling with fuzzy processing time. International Journal of Production Research, 48(10), 2995-3013.

Lei, D. (2009b). Genetic Algorithm for Job Shop Scheduling under Uncertainty. In U. Chakraborty (Ed.), Computational Intelligence in Flow Shop and Job Shop Scheduling (Vol. 230, pp. 191-228): Springer Berlin Heidelberg.

Lei, D. (2010a). Fuzzy job shop scheduling problem with availability constraints. Computers & Industrial Engineering, 58(4), 610-617.

Lei, D. (2010b). Solving fuzzy job shop scheduling problems using random key genetic algorithm. The International Journal of Advanced Manufacturing Technology, 49(1-4), 253-262.

Lei, D. (2011). Scheduling fuzzy job shop with preventive maintenance through swarm-based neighbourhood search. The International Journal of Advanced Manufacturing Technology, 54(9-12), 1121-1128.

Lei, D. (2012). Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing, 12(8), 2237-2245.

Lei, D., & Guo, X. (2011). Swarm-based neighbourhood search algorithm for fuzzy flexible job shop scheduling. International Journal of Production Research, 50(6), 1639-1649.

Li, J., Pan, Q.-K., Suganthan, P. N., & Tasgetiren, M. F. (2012). Solving fuzzy job-shop scheduling problem by a hybrid PSO algorithm. In Swarm and Evolutionary Computation (pp. 275-282): Springer.

Niu, Q., Jiao, B., & Gu, X. (2008). Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time. Applied Mathematics and Computation, 205(1), 148-158.

Puente, J., Vela, C. R., Hernández-Arauzo, A., & González-Rodríguez, I. (2010). Improving local search for the fuzzy job shop using a lower bound. In Current Topics in Artificial Intelligence (pp. 222-232): Springer.

Thammano, A., & Teekeng, W. (2015). A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems. International Journal of General Systems, 44(4), 499-518.

Wang, S., Wang, L., Xu, Y., & Liu, M. (2013). An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time. International Journal of Production Research, 51(12), 3778-3793.

Xu, Z., Gu, X., Jiao, B., & Gu, J. (2009). Research on job shop scheduling under uncertainty. Paper presented at the Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation.

Zheng, Y.-l., Li, Y.-x., & Lei, D.-m. (2011). Multi-objective swarm-based neighborhood search for fuzzy flexible job shop scheduling. The International Journal of Advanced Manufacturing Technology, 60(9), 1063-1069.

Fayad, C., & Petrovic, S. (2005). A Fuzzy Genetic Algorithm for Real-World Job Shop Scheduling. In M. Ali & F. Esposito (Eds.), Innovations in Applied Artificial Intelligence (Vol. 3533, pp. 524-533): Springer Berlin Heidelberg.

Ghrayeb, O. A. (2000). Solving job-shop scheduling problems with fuzzy durations using genetic algorithms. New Mexico State University,

Ghrayeb, O. A. (2003). A bi-criteria optimization: minimizing the integral value and spread of the fuzzy makespan of job shop scheduling problems. Applied Soft Computing, 2(3), 197-210.

Liu, J.-j. (2009). Application of optimization genetic algorithm in fuzzy job shop scheduling problem. Paper presented at the Intelligent Systems, 2009. GCIS'09. WRI Global Congress.

González Rodrıguez, I., Vela, C. R., Puente, J., & Varela, R. (2008). A new local search for the job shop problem with uncertain durations. International conference on automated planning and scheduling (ICAPS 2008), Sydney.

González-Rodríguez, I., Vela, C., & Puente, J. (2005). An Evolutionary Approach to Designing and Solving Fuzzy Job-Shop Problems. In J. Mira & J. Ãlvarez (Eds.), Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach (Vol. 3562, pp. 74-83): Springer Berlin Heidelberg.

González-Rodríguez, I., Vela, C., & Puente, J. (2006). Study of Objective Functions in Fuzzy Job-Shop Problem. In L. Rutkowski, R. Tadeusiewicz, L. Zadeh, & J. Żurada (Eds.), Artificial Intelligence and Soft Computing – ICAISC 2006 (Vol. 4029, pp. 360-369): Springer Berlin Heidelberg.

Li, F.-m., Zhu, Y.-l., Yin, C.-w., & Song, X.-y. (2005). Fuzzy Programming for Multiobjective Fuzzy Job Shop Scheduling with Alternative Machines Through Genetic Algorithms. In L. Wang, K. Chen, & Y. Ong (Eds.), Advances in Natural Computation (Vol. 3611, pp. 992-1004): Springer Berlin Heidelberg.

Sakawa, M., & Kubota, R. (2000). Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms. European Journal of Operational Research, 120(2), 393-407.

Sakawa, M., & Mori, T. (1999). An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy due date. Computers & Industrial Engineering, 36(2), 325-341.

Xie, Y., Xie, J., & Li, J. (2005). Fuzzy due dates job shop scheduling problem based on neural network. In Advances in Neural Networks–ISNN 2005 (pp. 782-787): Springer.

Song, X., Zhu, Y., Yin, C., & Li, F. (2006). A hybrid strategy based on ant colony and taboo search algorithms for fuzzy job shop scheduling. Paper presented at the Intelligent Control and Automation, 2006. WCICA 2006. The Sixth World Congress.

Palacios, J. J., González-Rodríguez, I., Vela, C. R., & Puente, J. (2015). Coevolutionary makespan optimisation through different ranking methods for the fuzzy flexible job shop. Fuzzy Sets and Systems, 278, 81-97.

Gao, K. Z., Suganthan, P. N., Pan, Q. K., & Tasgetiren, M. F. (2015). An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time. International Journal of Production Research, 53(19), 5896-5911.

Itoh, T., & Ishii, H. (1999). Fuzzy dueâ€date scheduling problem with fuzzy processing time. International Transactions in Operational Research, 6(6), 639-647.

Kuroda, M., & Wang, Z. (1996). Fuzzy job shop scheduling. International Journal of Production Economics, 44(1–2), 45-51.

Petrovic, S., & Fayad, C. (2004). A fuzzy shifting bottleneck hybridised with genetic algorithm for real-world job shop scheduling. Paper presented at the Proceedings of Mini-EURO Conference, Managing Uncertainty in Decision Support Models, Coimbra, Portugal.

Lei, D. (2008). Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 37(1-2), 157-165.

Li, J., & Pan, Y.-x. (2013). A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 66(1-4), 583-596.

Li, X., & Yin, M. (2013). An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure. Advances in Engineering Software, 55(0), 10-31.

Nalepa, J., Cwiek, M., & Zak, L. (2017). Behind the Scenes of Deadline24: A Memetic Algorithm for the Modified Job Shop Scheduling Problem. Paper presented at the International Conference on Man–Machine Interactions.

Shaheed, I.M., Shukor, S.A., Nababan, E.B. (2016). An empirical analysis of the relationship between the initialization method performance and the convergence speed of a meta-heuristic for Fuzzy Job-Shop scheduling problems. Journal of Theoretical and Applied Information Technology. 93(2), 297-311.

Kuczapski, A. M., Micea, M. V., Maniu, L. A., & Cretu, V. I. (2010). Efficient generation of near optimal initial populations to enhance genetic algorithms for job-shop scheduling. Information Technology and Control, 39(1), 32-37.

Abdullah, S., & Abdolrazzagh-Nezhad, M. (2014). Fuzzy job-shop scheduling problems: A review. Information Sciences, 278(0), 380-407.

Nguyen, S. (2013). Automatic Design of Dispatching Rules for Job Shop Scheduling with Genetic Programming. Victoria University of Wellington.

Michalewicz, Z., & Fogel, D. B. (2004). How to solve it: modern heuristics: Springer Science & Business Media.

Lin, F.-T. (2002). Fuzzy job-shop scheduling based on ranking level (λ, 1) interval-valued fuzzy numbers. Fuzzy Systems, IEEE Transactions on, 10(4), 510-522.

Shahzad, A., Mebarki, N., & IRCCyN, I. (2010). Discovering dispatching rules for job shop scheduling problem through data mining. Paper presented at the 8th International Conference of Modeling and Simulation-MOSIM.

Zheng, Y. L., & Li, Y. X. (2012). Artificial bee colony algorithm for fuzzy job shop scheduling. International Journal of Computer Applications in Technology, 44(2), 124-129.

Yahyaoui, A., Fnaiech, N., & Fnaiech, F. (2011). A Suitable Initialization Procedure for Speeding a Neural Network Job-Shop Scheduling. Industrial Electronics, IEEE Transactions on, 58(3), 1052-1060.

Kaur, D., & Murugappan, M. M. (2008). Performance enhancement in solving traveling salesman problem using hybrid genetic algorithm. Paper presented at the Fuzzy Information Processing Society, 2008. NAFIPS 2008. Annual Meeting of the North American.

Victer Paul, P., Moganarangan, N., Kumar, S. S., Raju, R., Vengattaraman, T., & Dhavachelvan, P. (2015). Performance analyses over population seeding techniques of the permutation-coded genetic algorithm: An empirical study based on traveling salesman problems. Applied Soft Computing, 32(0), 383-402

Brizuela, C. A., & Sannomiya, N. (1999, 17/08/19999). A Diversity Study in Genetic Algorithms for Job Shop Scheduling Problems. Paper presented at the Proceedings of Genetic and Evolutionary Computation Conference (GECCO-99), Morgan Kaufmann, San Francisco, CA.

Bahameish, H. A. (2014). Finding a Cost Effective LNG Annual Delivery Program (ADP) Using Genetic Algorithms.

Dalfard, V. M., & Mohammadi, G. (2012). Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints. Computers & Mathematics with Applications, 64(6), 2111-2117.




DOI: http://dx.doi.org/10.18517/ijaseit.8.4-2.6808

Refbacks

  • There are currently no refbacks.



Published by INSIGHT - Indonesian Society for Knowledge and Human Development