Improved TLBO and JAYA algorithms to solve new fuzzy flexible job-shop scheduling problems

Subject Areas : Metaheuristics

Raviteja Buddala ¹ , Siba Sankar Mahapatra ² , Manas Ranjan Singh ³ , Bhanu Chandar Balusa ⁴ , Purusotham Singamsetty ⁵ , Venkata Phanikrishna Balam ⁶

1 - School of Mechanical Engineering, Vellore Institute of Technology, Vellore.
2 - Department of Mechanical Engineering, National Institute of Technology Rourkela
3 - Department of Basic Sciences and Humanities, Silicon Institute of Technology
4 - School of Computer Science and Engineering, Vellore Institute of Technology, Chennai
5 - Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore.
6 - School of Computer Science and Engineering, Vellore Institute of Technology, Vellore,

Received: 2021-07-08 Accepted : 2023-03-06 Published : 2022-12-01

Keywords: Triangular Fuzzy Numbers, Teaching-learning-based optimization, Flexible job-shop scheduling problem, processing times uncertainty,

Abstract :

Flexible job-shop scheduling problem (FJSP) finds significant interest in the field of scheduling in dealing with complexity, solution methodology and, industrial applications. However, most of the studies on FJSP, consider the processing time of operations to be deterministic and known at priori while solving the problem. Since uncertainty is bound to occur in industries, deterministic approaches for solving FJSP may not yield good solutions. Schedules generated considering uncertainties may help the manufacturing firms to handle the uncertainties efficiently. The present work aims at solving FJSP in a realistic manner, considering uncertainty in the processing times. A modified version of optimization algorithms without tuning parameters such as teaching-learning-based optimization (TLBO) and JAYA is proposed to solve fuzzy FJSP (FFJSP) with less computational burden. Although there are enough challenging benchmark problems for deterministic FJSP problems, only limited benchmarks are available for a fuzzy variant of FJSP. The currently available FFJSP problems in the literature are small in size as compared to Brandimate data instances which are widely accepted for a deterministic variant of FJSP. Therefore, an attempt has been made in this paper to solve the instances of Kacem’s and Brandimarte’s by converting them into fuzzy FJSP. The present work also provides new challenging problems compared to the existing benchmark problems to study FFJSP.

References:

[1] Apornak, A., Raissi, S., & Pourhassan, M. R. (2021). Solving flexible flow-shop problem using a hybrid multi criteria Taguchi based computer simulation model and DEA approach. Journal of Industrial and Systems Engineering, 13(2), 264-276.

[2] Balin, S. (2011). Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation. Information Sciences, 181(17), 3551-3569. doi: https://doi.org/10.1016/j.ins.2011.04.010

[3] BORTOLAN, G., & DEGANI, R. (1993). A review of some methods for ranking fuzzy subsets Readings in Fuzzy Sets for Intelligent Systems (pp. 149-158): Elsevier.

[4] Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183. doi:https://doi.org/10.1007/BF02023073

[5] Bruni, M. E., Beraldi, P., Guerriero, F., & Pinto, E. (2011). A heuristic approach for resource constrained project scheduling with uncertain activity durations. Computers & Operations Research, 38(9), 1305-1318. doi: https://doi.org/10.1016/j.cor.2010.12.004

[6] Buddala, R., & Mahapatra, S. S. (2016). An effective teaching learning based optimization for flexible job shop scheduling. Paper presented at the International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT).

[7] Buddala, R., & Mahapatra, S. S. (2018). Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems. Journal of Industrial Engineering International, 14(3), 555-570. doi: 10.1007/s40092-017-0244-4
[8] Buddala, R., Mahapatra, S. S., & Singh, M. R. (2021). Solving multi-objective flexible flow-shop scheduling problem using teaching-learning-based optimisation embedded with maximum deviation theory. International Journal of Industrial and Systems Engineering. doi: 10.1504/IJISE.2021.10037222
[9] Celano, G., Costa, A., & Fichera, S. (2003). An evolutionary algorithm for pure fuzzy flowshop scheduling problems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 11(06), 655-669. doi: https://doi.org/10.1142/S0218488503002466
[10] Chaari, T., Chaabane, S., Aissani, N., & Trentesaux, D. (2014). Scheduling under uncertainty: Survey and research directions. Paper presented at the Advanced Logistics and Transport (ICALT), 2014 International Conference on.
[11] Chanas, S., & Kasperski, A. (2003). On two single machine scheduling problems with fuzzy processing times and fuzzy due dates. European Journal of Operational Research, 147(2), 281-296. doi: https://doi.org/10.1016/S0377-2217(02)00561-1
[12] Dubois, D., Fargier, H., & Fortemps, P. (2003). Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge. European Journal of Operational Research, 147(2), 231-252. doi: https://doi.org/10.1016/S0377-2217(02)00558-1
[13] Dunke, F., & Nickel, S. (2022). A multi-method approach to scheduling and efficiency analysis in dual-resource constrained job shops with processing time uncertainty. Computers & Industrial Engineering, 168, 108067.
[14] Fortemps, P. (1997). Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Transactions on Fuzzy Systems, 5(4), 557-569. doi: https://doi.org/10.1109/91.649907
[15] Gao, K.-Z., Suganthan, P. N., Pan, Q.-K., Chua, T. J., Cai, T. X., & Chong, C.-S. (2016). Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. Journal of Intelligent Manufacturing, 27(2), 363-374. doi: https://doi.org/10.1007/s10845-014-0869-8
[16] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129. doi: https://doi.org/10.1287/moor.1.2.117
[17] 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. doi: https://doi.org/10.1016/S1568-4946(02)00069-8

[18] Gonzalez-Rodriguez, I., Puente, J., Vela, C. R., & Varela, R. (2008). Semantics of schedules for the fuzzy job-shop problem. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 38(3), 655-666. doi: https://doi.org/10.1109/TSMCA.2008.918603
[19] Gonzalez-Rodriguez, I., Vela, C. R., & Puente, J. (2007). A memetic approach to fuzzy job shop based on expectation model. Paper presented at the Fuzzy Systems Conference, 2007. FUZZ-IEEE 2007. IEEE International.
[20] González-Rodríguez, I., Vela, C. R., & Puente, J. (2006). Study of objective functions in fuzzy job-shop problem. Paper presented at the InternationalConference on Artificial Intelligence and Soft Computing.
[21] Rodrıguez, I., Vela, C. R., Puente, J., & Varela, R. (2008). A new local search for the job shop problem with uncertain durations. Paper presented at the Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling.
[22] He, W., Sun, D., & Liao, X. (2013). Applying novel clone immune algorithm to solve flexible job shop problem with machine breakdown. JOURNAL OF INFORMATION &COMPUTATIONAL SCIENCE, 10(9), 2783-2797. doi: https://doi.org/10.12733/jics20101851
[23] Ishibuchi, H., & Murata, T. (1998). A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 28(3), 392-403. doi: https://doi.org/10.1109/5326.704576
[24] Jin, L., Zhang, C., Wen, X., Sun, C., & Fei, X. (2021). A neutrosophic set-based TLBO algorithm for the flexible job-shop scheduling problem with routing flexibility and uncertain processing times. Complex & Intelligent Systems, 7(6), 2833-2853.
[25] Kacem, I., Hammadi, S., & Borne, P. (2002a). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 32(1), 1-13. doi: https://doi.org/10.1109/TSMCC.2002.1009117
[26] Kacem, I., Hammadi, S., & Borne, P. (2002b). Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Mathematics and computers in simulation, 60(3-5), 245-276. doi: https://doi.org/10.1016/S0378-4754(02)00019-8
[27] Kasperski, A. (2007). Some general properties of a fuzzy single machine scheduling problem. International Journal of Uncertainty, Fuzziness andKnowledge-Based Systems, 15(01), 43-56. doi: https://doi.org/10.1142/S0218488507004364
[28] 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. doi: https://doi.org/10.1007/s00170-007-0945-8
[29] Lei, D. (2010a). A genetic algorithm for flexible job shop scheduling with fuzzy processing time. International Journal of Production Research, 48(10), 2995-3013. doi: https://doi.org/10.1080/00207540902814348
[30] 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. doi: https://doi.org/10.1007/s00170-009-2379-y
[31] Lei, D. (2011). Scheduling fuzzy job shop with preventive maintenance through swarm-based neighborhood search. The International Journal of Advanced Manufacturing Technology, 54(9-12), 1121-1128. doi: https://doi.org/10.1007/s00170-010-2989-4
[32] Lei, D. (2012). Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing, 12(8), 2237-2245. doi: https://doi.org/10.1016/j.asoc.2012.03.025
[33] Li, R., Gong, W., & Lu, C. (2022a). A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling. Expert Systems with Applications, 203, 117380.
[34] Li, R., Gong, W., & Lu, C. (2022b). Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time. Computers & Industrial Engineering, 168, 108099.
[35] Lin, F.-T. (2002). Fuzzy job-shop scheduling based on ranking level (/spl lambda/, 1) interval-valued fuzzy numbers. IEEE Transactions on Fuzzy Systems, 10(4), 510-522. doi: https://doi.org/10.1109/TFUZZ.2002.800659
[36] Ludwig, A., Möhring, R. H., & Stork, F. (2001). A computational study on bounding the makespan distribution in stochastic project networks. Annals of Operations Research, 102(1-4), 49-64. doi:  https://doi.org/10.1023/A:1010945830113
[37] 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. doi: https://doi.org/10.1016/j.amc.2008.05.086
[38] Ourari, S., Berrandjia, L., Boulakhras, R., Boukciat, A., & Hentous, H. (2015). Robust approach for centralized job shop scheduling: Sequential flexibility. IFAC-PapersOnLine, 48(3), 1960-1965. doi: https://doi.org/10.1016/j.ifacol.2015.06.375
[39] Palacios, J. J., González-Rodríguez, I., Vela, C. R., & Puente, J. (2014). Robust swarm optimisation for fuzzy open shop scheduling. Natural Computing, 13(2), 145-156. doi: https://doi.org/10.1007/s11047-014-9413-1
[40] Palacios, J. J., González, M. A., Vela, C. R., González-Rodríguez, I., & Puente, J. (2015). Genetic tabu search for the fuzzy flexible job shop problem. Computers & Operations Research, 54, 74-89. doi: https://doi.org/10.1016/j.cor.2014.08.023
[41] Palacios, J. J., Puente, J., Vela, C. R., & González-Rodríguez, I. (2016). Benchmarks for fuzzy job shop problems. Information Sciences, 329, 736-752. doi: https://doi.org/10.1016/j.ins.2015.09.042
[42] Peng, J., & Liu, B. (2004). Parallel machine scheduling models with fuzzy processing times. Information Sciences, 166(1-4), 49-66. doi: https://doi.org/10.1016/j.ins.2003.05.012
[43] Petrovic, S., Fayad, C., Petrovic, D., Burke, E., & Kendall, G. (2008). Fuzzy job shop scheduling with lot-sizing. Annals of Operations Research, 159(1), 275-292. doi: https://doi.org/10.1007/s10479-007-0287-9
[44] Puente Peinador, J., Rodríguez Vela, M. d. C., & González Rodríguez, I. (2010). Fast local search for fuzzy job shop scheduling. Frontiers in Artificial Intelligence and Applications. doi: http://dx.doi.org/10.3233/978-1-60750-606-5-739
[45] Raissi, S., Rooeinfar, R., & Ghezavati, V. R. (2019). Three Hybrid Metaheuristic Algorithms for Stochastic Flexible Flow Shop Scheduling Problem with Preventive Maintenance and Budget Constraint. Journal of Optimization in Industrial Engineering, 12(2), 131-147.
[46] Rao, R. (2016). Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 7(1), 19-34. doi: http://dx.doi.org/10.5267/j.ijiec.2015.8.004
[47] Rao, R. V., Savsani, V. J., & Vakharia, D. (2011). Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-Aided Design, 43(3), 303-315. doi: https://doi.org/10.1016/j.cad.2010.12.015
[48] Rooeinfar, R., Raissi, S., & Ghezavati, V. (2019). Stochastic flexible flow shop scheduling problem with limited buffers and fixed interval preventive maintenance: a hybrid approach of simulation and metaheuristic algorithms. Simulation, 95(6), 509-528.
[49] Sakawa, M., & Kubota, R. (2000). Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate throughgenetic algorithms. European Journal of Operational Research, 120(2), 393-407. doi: https://doi.org/10.1016/S0377-2217(99)00094-6

[50] Sakawa, M., & Mori, T. (1999). An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate. Computers & Industrial Engineering, 36(2), 325-341. doi: https://doi.org/10.1016/S0360-8352(99)00135-7
[51] Singh, M. R., & Mahapatra, S. S. (2016). A quantum behaved particle swarm optimization for flexible job shop scheduling. Computers & Industrial Engineering, 93, 36-44. doi: https://doi.org/10.1016/j.cie.2015.12.004
[52] Sowinski, R., & Hapke, M. (2000). Scheduling under fuzziness: Physica-Verlag.
[53] Subramaniam, V., & Raheja, A. S. (2003). mAOR: A heuristic-based reactive repair mechanism for job shop schedules. The International Journal of Advanced Manufacturing Technology, 22(9-10), 669-680. doi: https://doi.org/10.1007/s00170-003-1601-6
[54] 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, 59(4), 431-442. doi: https://doi.org/10.1057/palgrave.jors.2602351
[55] Vieira, G. E., Herrmann, J. W., & Lin, E. (2003). Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 6(1), 39-62. doi: https://doi.org/10.1023/A:1022235519958
[56] Wang, C., Tian, N., Ji, Z., & Wang, Y. (2017). Multi-objective fuzzy flexible job shop scheduling using memetic algorithm. Journal of Statistical Computation and Simulation, 87(14), 2828-2846. doi: https://doi.org/10.1080/00949655.2017.1344846
[57] Wang, K., & Choi, S. (2012). A decomposition-based approach to flexible flow shop scheduling under machine breakdown. International Journal of Production Research, 50(1), 215-234. doi: https://doi.org/10.1080/00207543.2011.571456
[58] Wang, L., Zhou, G., Xu, Y., & Liu, M. (2013). A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem. International Journal of Production Research, 51(12), 3593-3608. doi: https://doi.org/10.1080/00207543.2012.754549
[59] Wang, L., Zhou, G., Xu, Y., Wang, S., & Liu, M. (2012). An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 60(1-4), 303-315. doi: https://doi.org/10.1007/s00170-011-3610-1
[60] Wang, S., Wang, L., Xu, Y., & Liu, M. (2013). An effective estimation of distribution algorithm for the flexible job-shop scheduling problem withfuzzy processing time. International Journal of Production Research, 51(12), 3778-3793. doi: https://doi.org/10.1080/00207543.2013.765077
[61] Wang, X., Gao, L., Zhang, C., & Li, X. (2012). A multi–objective genetic algorithm for fuzzy flexible job–shop scheduling problem. International Journal of Computer Applications in Technology, 45(2-3), 115-125. doi: https://doi.org/10.1504/IJCAT.2012.050700
[62] Wang, X., Li, W., & Zhang, Y. (2013). An improved multi–objective genetic algorithm for fuzzy flexible job–shop scheduling problem. International Journal of Computer Applications in Technology, 47(2-3), 280-288. doi: https://doi.org/10.1504/IJCAT.2013.054360
[63] Xu, Y., Wang, L., Wang, S.-y., & Liu, M. (2015). An effective teaching–learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time. Neurocomputing, 148, 260-268. doi: https://doi.org/10.1016/j.neucom.2013.10.042
[64] Yuan, Y., Xu, H., & Yang, J. (2013). A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, 13(7),3259-3272. doi: https://doi.org/10.1016/j.asoc.2013.02.013
[65] 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. doi: https://doi.org/10.1504/IJCAT.2012.048682