Hybrid Metaheuristic for Just In Time Scheduling in a Flow Shop with Distinct Time Windows
Abstract
Scheduling to meet clients' order has been a challenge in recent times therefore researches in Just-in-Time (JIT) scheduling has evolved. JIT scheduling involves reducing waste, inventory costs and making goods available as at when needed. This work addresses the JIT scheduling problem on flow shop where jobs incur penalties if they are not completed within their specific due windows. The problem is to obtain an execution sequence that will minimize the bi-criteria earliness-tardiness objective. JIT scheduling problem is prevalent in real life manufacturing applications. An hybrid of Tabu-Search and Variable Neighborhood Search (HTVNS) algorithm is proposed for the problem. To justify this hybridization a benchmark of 12500 problem instances were solved and the result obtained is compared with an algorithm in the literature. The result shows that the proposed hybrid metahueristic algorithm performs considerable better.
References
Josefowska, J., Jurisch, B. & Kubiak, W. Scheduling shops to minimize the weighted number of late jobs. Operations Research Letters, 10, 27–33, (1994).
Ohno, T. Toyota production system: beyond large-scale production. Productivity Press, (1988).
Ohno, T. Just-In-Time for today & tomorrow. Productivity Press, (1988).
Murata, T., Ishibuchi, H. & Tanaka, H. Multi- objective genetic algorithm and its applications to flow shop scheduling. Computers & Industrial Engineering, 30(4), 957-967, (1996).
Monden, Y. Toyotal production system. Institute of Industrial Engineering Press, Norcross, G.A, (1983).
Kim, Y. & Kim, J. A coevolutionary algorithm for balancing & sequencing in mixed model assembly lines. Applied Inteligience, 13(3), 247–258, (2000).
Cheng, T. C. E., Gupta, J. N. D. & Wang, G. A review of flow shop scheduling research with setup times. Production and Operations Management, 9, 262–282, (2000).
French, S. Sequencing and scheduling: an introduction to the mathematics of the job shop. Ellis Harwood, England, (1982).
Pinedo, M. Scheduling: Theory, Algorithms & Systems. Fourth edition, Springer, (2015).
González, P., Torres J. F., González, P., León, J., & Usano, R. R. Flowshop scheduling problems with due date related objectives: A review of the literature. In XIII Congreso de Ingeniería de Organización, 1488–1497, (2009).
Kramer, F. J. & Lee, C. Y. Common due-window scheduling. Production & Operations Management, 2(4), 262–275, (1993).
Wan, G. & Yen, B. P. C. Tabu search for single machine scheduling with distinct due windows & weighted earliness/tardiness penalties. European Journal of Operational Research, 142, 271–281, (2002).
Wu, C. , Lee, W. & Wang, W. A two-machine flowshop maximum tardiness scheduling problem with a learning effect. The International Journal of Advanced Manufacturing Technology, 31(7-8), 743–750, (2007).
Lee, C. Earliness–tardiness scheduling problems with constant size of due date window. Research Report No. 91-17, Industrial & Systems Engineering Department, University of Florida, Gainesville, 4, 262–275, (1991).
Koulamas, C. On the complexity of two-machine flowshop problems with due date related objectives. European journal of operational research, 106(1), 95–100, (1998).
Yeung, W. K, Oğuz, C., & Cheng, T. C. E. Two-stage flowshop earliness & tardiness machine scheduling involving a common due window. International Journal of Production Economics, 90(3), 421–434, (2004).
Mosheiov, G. & Sarig, A. Scheduling with a common due-window: Polynomi-ally solvable cases. Information Sciences, 180(8), 1492–1505, (2010).
Zegordi, S. H., Itoh, K. & Enkawa T. A knowledgeable simulated annealing scheme for the early-tardy flow shop scheduling problem. International Journal of Production Research, 33, 1449–1466, (1995).
Schaller, J. & Valente, J. M. S. A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness & tardiness. International Journal of Production Research, 51, 772–779, (2013).
Janiak, A., Kozan, E., Lichtenstein, M. Oğuz, & C. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International journal of production economics, 105(2), 407–424, (2007).
Khalouli, S., Ghedjati, F, & Hamzaoui, A. A meta-heuristic approach to solve a jit scheduling problem in hybrid flow shop. Engineering Applications of Artificial Intelligence, 23(5), 765–771, (2010).
Moslehi, G., Mirzaee, M., Vasei, M., Modarres, M. & Azaron, A. Two-machine flow shop scheduling to minimize the sum of maximum earliness & tardiness. International Journal of Production Economics, 122(2), 763–773, (2009).
Huang, C., Huang, Y. & Lai, P. Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with cuda. Expert Systems with Applications, 39(5), 4999–5005, (2012).
M’Hallah, R. An iterated local search variable neighborhood descent hybrid heuristic for total earliness tardiness permutation flow shop. International Journal of Production Research, 52(13),3802–3819, (2014).
Liao, L. & Huang, C. Tabu search for non-permutation flowshop scheduling problem with minimizing total tardiness. Applied Mathematics & Computation, 217(2), 557–567, (2010).
Glover, F. & Laguna, M. Tabu search. In Handbook of combinatorial optimization. Springer, 2093–2229, (1998).
Mladenovic, N. & Hansen, P. Variable neighborhood search. Computers & Operations Research, 24, 1097–1100, (1997).
Hansen, P., Mladenovic, N. & Moreno-Perez, J. A. Variable neighbourhood search: Methods and applications. Annals of Operations Research, 175(4), 367–407, (2010).
Behnamian, J. & Ghomi, S. F. A survey of multi-factory scheduling. Journal of Intelligent Manufacturing, 27(1), 231–249, (2016).
Behnamian, J. & Zandieh, M. Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arabian Journal for Science and Engineering, 38(5), 1229–1242, (2013).
M’Hallah, R. Minimizing total earliness & tardiness on permutation flow shop using vns & mip. Computers & Industrial Engineering, 75, 142–156, (2016).
Graham, R. L., Lawler, E. L. , Lenstra, T. K., & Rinnooy-Kan, A. H. G. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326, (1979).
Adamu, M.O., Budlender, N., & Idowu, G. A . A note on just in time scheduling on flow shop machines. Journal of the Nigerian Mathematical Society, 33, 321–331, (2014).
Rosa, B. F., Souza, M. J. F., De Souza, S. R. , Filho, M. F., Ales, Z. & Michelon, P. Y. P. Algorithms for job scheduling problems with distinct time windows & general earliness/tardiness penalties. Computers & Operations Research, 81, 203–215, (2017).
Hansen, P., Mladenovic, N., & Prez J. A. M. Variable neighborhood search: methods and applications. European Journal of Operational Research, 6(4),319–316, (2008).
Bulfin, R. L. & M’Hallah, R. Minimizing the weighted number of tardy jobs on a two-machine flow shop. Computers and Operational Research, (30), 1887–1900, (2003).
Cochran, W. O. & Cox, G. M. Experimental designs. 2nd Edition. Wiley, (1992).
This is an Open Access article distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, adaptation, and reproduction in any medium, provided that the original work is properly cited.
