An integrated approach for scheduling flexible job-shop using teaching–learning-based optimization method

Subject Areas : Mathematical Optimization

Raviteja Buddala ¹ , Siba Sankar Mahapatra ²

1 - Department of Mechanical Engineering, National Institute of Technology Rourkela, Rourkela, Odisha, 769008, India
2 - Department of Mechanical Engineering, National Institute of Technology Rourkela, Rourkela, Odisha, 769008, India

Received: 2020-10-08 Accepted : 2020-10-08 Published : 2020-03-01

Keywords: learning-based optimization, Flexible job shop scheduling . Local search . Makespan . Meta-heuristics . Teaching,

Abstract :

In this paper, teaching–learning-based optimization (TLBO) is proposed to solve flexible job shop scheduling problem (FJSP) based on the integrated approach with an objective to minimize makespan. An FJSP is an extension of basic job-shop scheduling problem. There are two sub problems in FJSP. They are routing problem and sequencing problem. If both the sub problems are solved simultaneously, then the FJSP comes under integrated approach. Otherwise, it becomes a hierarchical approach. Very less research has been done in the past on FJSP problem as it is an NP-hard (non-deterministic polynomial time hard) problem and very difficult to solve till date. Further, very less focus has been given to solve the FJSP using an integrated approach. So an attempt has been made to solve FJSP based on integrated approach using TLBO. Teaching–learning-based optimization is a meta-heuristic algorithm which does not have any algorithm-specific parameters that are to be tuned in comparison to other meta-heuristics. Therefore, it can be considered as an efficient algorithm. As best student of the class is considered as teacher, after few iterations all the students learn and reach the same knowledge level, due to which there is a loss in diversity in the population. So, like many meta-heuristics, TLBO also has a tendency to get trapped at the local optimum. To avoid this limitation, a new local search technique followed by a mutation strategy (from genetic algorithm) is incorporated to TLBO to improve the quality of the solution and to maintain diversity, respectively, in the population. Tests have been carried out on all Kacem’s instances and Brandimarte's data instances to calculate makespan. Results show that TLBO outperformed many other algorithms and can be a competitive method for solving the FJSP.

References:

Artigues C, Feillet D (2008) A branch and bound method for the jobshop problem with sequence-dependent setup times. Ann Oper Res 159:135–159
Bagheri A, Zandieh M, Mahdavi I, Yazdani M (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Future Gener. Comput. Syst. 26:533–541

Baykasoglu A, Hamzadayi A, Kose SY (2014) Testing the performance of teaching–learning based optimization (TLBO) algorithm on combinatorial problems: flow shop and job shop scheduling cases. Inf Sci 276:204–218
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157–183
Brucker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45:369–375
Brucker P, Jurisch B, Sievers B (1994) A branch and bound algorithm for the job-shop scheduling problem. Discrete Appl. Math. 49:107–127
Buddala R, Mahapatra SS (2016) An effective teaching learning based optimization for flexible job shop scheduling. In: International conference on electrical, electronics, and optimization techniques (ICEEOT). IEEE, pp 3087–3092. https://doi.org/10.1109/ICEEOT.2016.7755269
Buddala R, Mahapatra SS (2017) Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems. J Ind Eng Int. https://doi.org/10.1007/s40092-017-0244-4
Chang HC, Chen YP, Liu TK, Chou JH (2015) Solving the flexible job shop scheduling problem with makespan optimization by using a hybrid taguchi-genetic algorithm. IEEE Access 3:1740–1754
Chen H, Ihlow J, Lehmann C (1999) A genetic algorithm for flexible job-shop scheduling. In: 1999 IEEE international conference on robotics and automation, 1999. Proceedings, vol 2. IEEE, pp 1120–1125
Fattahi P, Mehrabad MS, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18:331–342
Gambardella LM, Mastrolilli M (1996) Effective neighborhood functions for the flexible job shop problem. J Sched 3:3–20
Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907
Gao KZ, Suganthan PN, Pan QK, Chua TJ, Cai TX, Chong CS (2016) Discrete harmony search algorithm for flexible job shop
scheduling problem with multiple objectives. J Intell Manuf 27:363–374
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129
Garmdare HS, Lotfi MM, Honarvar M (2017) Integrated model for pricing, delivery time setting, and scheduling in make-to-order environments. J Ind Eng Int. https://doi.org/10.1007/s40092-017-0205-y
Garmsiri M, Abassi MR (2012) Resource leveling scheduling by an ant colony-based model. J Ind Eng Int 8(1):7
Kacem I, Hammadi S, Borne P (2002a) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60:245–276
Kacem I, Hammadi S, Borne P (2002b) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Syst Man Cybern Part C Appl Rev 32:1–3
Karthikeyan S, Asokan P, Nickolas S, Page T (2015) A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int J Bio Inspired Comput 7:386–401
Keesari HS, Rao RV (2014) Optimization of job shop scheduling problems using teaching–learning-based optimization algorithm. Opsearch 51:545–561
Kia H, Ghodsypour SH, Davoudpour H (2017) New scheduling rules for a dynamic flexible flow line problem with sequencedependent setup times. J Ind Eng Int. https://doi.org/10.1007/s40092-017-0185-y
Lenstra JK, Kan AR, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343–362
Li JQ, Pan QK, Liang YC (2010) An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 59:647–662
Li JQ, Pan QK, Tasgetiren MF (2014) A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Modell 38:1111–1132
Liouane N, Saad I, Hammadi S, Borne P (2007) Ant systems and local search optimization for flexible job shop scheduling production. Int J Comput Commun Control 2:174–184
Maleki-Darounkolaei A, Modiri M, Tavakkoli-Moghaddam R, Seyyedi I (2012) A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. J Ind Eng Int 8(1):26
Manne AS (1960) On the job-shop scheduling problem. Oper Res 8:219–223
Mirabi M, Ghomi SF, Jolai F (2014) A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem. J Ind Eng Int. https://doi.org/10.1007/s40092-014-0057-7
Niu Q, Zhou T, Ma S (2009) A quantum-inspired immune algorithm for hybrid flow shop with makespan criterion. J UCS
15(4):765–785
Noori-Darvish S, Tavakkoli-Moghaddam R (2012) Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times. J Ind Eng Int 8(1):25
Nouri HE, Driss OB, Ghe´dira K (2017) Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model. J Ind Eng Int. https://doi.org/10.1007/s40092-017-0204-z
Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35:3202–3212
Pinedo M (2008) Scheduling: theory, algorithms and systems, 3rd edn. Springer, Berlin
Potts CN, Van Wassenhove LN (1987) Dynamic programming and decomposition approaches for the single machine total tardiness problem. Eur J Oper Res 32:405–414
Rahmati SH, Zandieh M (2012) A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. Int J Adv Manuf Technol 58:1115–1129
Rao R, Patel V (2012) An elitist teaching–learning-based optimization algorithm for solving complex constrained optimization problems. Int J Ind Eng Comput 3:535–560
Rao R, Patel V (2013) Comparative performance of an elitist teaching–learning-based optimization algorithm for solving
unconstrained optimization problems. Int J Ind Eng Comput 4:29–50
Rao RV, Savsani VJ, Vakharia DP (2011) Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems. Comput Aided Des 43:303–315
Shen JN, Wang L, Zheng HY (2016) A modified teaching–learningbased optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling. Int J Prod Res 54:3622–3639
Singh MR, Mahapatra SS (2012) A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. Int J Adv Manuf Technol 62:267–277
Singh MR, Mahapatra SS (2016) A quantum behaved particle swarm optimization for flexible job shop scheduling. Comput Ind Eng 93:36–44
Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60:303–315

Xia W, Wu Z (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48:409–425
Xie Z, Zhang C, Shao X, Lin W, Zhu H (2014) An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem. Adv Eng Softw 77:35–47
Xing LN, Chen YW, Yang KW (2009a) An efficient search method for multi-objective flexible job shop scheduling problems. J Intell Manuf 20:283–293
Xing LN, Chen YW, Yang KW (2009b) Multi-objective flexible job shop schedule: design and evaluation by simulation modeling. Appl Soft Comput 9:362–376
Xing LN, Chen YW, Wang P, Zhao QS, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop
scheduling problems. Appl Soft Comput 10:888–896
Xu Y, Wang L, Wang SY, 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
Yazdani M, Amiri M, Zandieh M (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Syst Appl 37:678–687
Yuan Y, Xu H, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13:3259–3272
Zhang C, Li P, Guan Z, Rao Y (2007) A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res 34:3229–3242
Zhang G, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 38:3563–3573