Comparison between Three Metaheuristic Algorithms for Minimizing Cycle Time in Cyclic Hybrid Flow Shop Scheduling with Learning Effect

Document Type : Research Paper

Abstract

Jobs scheduling in industries with cyclic procedure on machines, such as perishable products (food industries) or products with a limited lifetime (chemicals, radio actives, etc), is very important. Due to time limitation or competition with other companies, these industries try to minimize thecycle time of jobs processing. Since most productive environments of the industries are cyclic hybrid flow shop and operator’s learning effect is obvious in speed of productions, the aim of this study is to minimize cycle time of each machine with learning effect by consequence of jobs. After proposing a mathematical model and since the cyclic hybrid flow shop environment is NP-hard, three metaheuristics, i.e., genetic algorithm, simulated annealing algorithm and population based simulated annealing algorithm, have been proposed for solving this problem. Results show that on average, population based simulated annealing algorithm due to its population-based structure has a better performance in comparison to other algorithms.

Keywords

Main Subjects

References

[1] Elmaghraby, S.E., Kanoub, R.E. (1997). “Production control in hybrid flowshops: an example from textile manufacturing”, A. Artiba and S.E. Elmaghraby, eds. The planning and scheduling of production systems, Chapman and Hall, 163-198.
[2] Salvador, M.S. (1973). “A solution to a special class of flow shop scheduling problems”, S.E. Elmaghraby, ed. Symposium on the theory of scheduling and its applications, Berlin, Springer, 83-91.
[3] Adler, L., et al. (1993). “A scheduling support system for the packaging industry”, Operations Research, 41(4): 641-648.
[4] Guinet, A.G.P., Solomon, M. (1996). “Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time”, International Journal of Production Research, 34(6): 1643-1654.
[5] Agnetis, A. (1997). “Scheduling of flexible flow lines in an automobile assembly plant”, European Journal of Operational Research, 97(2): 348-362.
[6] Paul, R.J. (1979). “A production scheduling problem in the glass-container industry”, Operation Research, 22: 290-302.
[7] Leon, V.J., Ramamoorthy, B. (1997). “An adaptable problem-space based search method for flexible flow line scheduling”, IIE Transactions, 29(22): 115–126.
[8] Riane, F. (1998). “Scheduling hybrid flowshops: algorithms and applications”, Thesis (PhD), Faculty’s Universities Catholiques de Mons, Wallonia, Belgium.
[9] Moursli, O., Pochet, Y. (2000). “A branch-and-bound algorithm for the hybrid flow shop”, International Journal of Production Economics, 64(1–3): 113-125.
[10] Quadt, D., Kuhn, H. (2005). “A conceptual framework for lot-sizing and scheduling of flexible flow lines”, International Journal of Production Research, 43(11): 2291-2308.
[11] Herrmann J.W., Lee, C.-Y. (1992). “Three-machine look-ahead scheduling problems”, Research Report, Dept. of Industrial and Systems Engineering, University of Florida, 92-23.
[12] Lee, C.-Y., Herrmann, J.W. (1993). “A three-machine scheduling problem with look-behind characteristics”, Research Report, Dept. of Industrial and Systems Engineering, University of Florida, 93-11.
[13] Narasimhan S.L., Panwalker. S.S. (1984). “Scheduling in a two-stage manufacturing process”, International Journal of Production Research, 22: 555-564.
[14] Soltani, S. Abolfazl, Karimi, B. (2014). “Cyclic hybrid flow shop scheduling problem with limited buffers and machine eligibility constraints”, International Journal of Advanced Manufacturing, Springer, DOI 10.1007/s00170-014-6343-0.
[15] Karabati S., Kouvelis P. (1996). “Cyclic scheduling in flow lines: modeling observations, effective heuristics and a cycle time minimization procedure”, Naval Res Logist (NRL), 43(2): 211-231.
[16] Song JS, Lee TE. (1998). “Petri net modeling and scheduling for cyclic job shops with blocking”. Computers & Industrial Engineering, 34(2): 281-295.
[17] Levner E., Kats V., López A., De Pablo, D., Cheng TCE. (2010), “Complexity of cyclic scheduling problems: a state-of-the-art survey”, Computers & Industrial Engineering, 59(2): 352-361.
[18] Cuninghame-Green, RA. (1960). “Process synchronisation in a steelworks- a problem of feasibility”, Proceedings of the 2nd international conference on operational research, 323-328.
[19] Cuninghame-Green, RA. (1962). “Describing industrial processes with interference and approximating their steady-state behavior”, Operational Research Society, 13(1): 95-100.
[20] Wittrock, RJ. (1985). “Scheduling algorithms for flexible flow lines”, IBM Journal of Research and Development, 29(4): 401-412.
[21] Hall, NG. (1999). “Operations research techniques for robotic system planning, design, control and analysis”, Handbook of Industrial Robotics, John Wiley, 543-577.
[22] Pinedo, M. (2008). “Scheduling: theory, algorithms and systems”, Springer.
[23] Hanen, C., Munier, A. (1995). “A Study of Cyclic Scheduling Problem on Parallel Processors”, Discrete Applied Mathematics, 57(2): 167-192.
[24] Hanen, C., Munier, A. (1995). “Cyclic scheduling on parallel processors: an overview, Scheduling Theory and its Applications”, IEEE Computer Science Press, 194-226.
[25] Kats, V., Levner, E. (2003). “Polynomial algorithms for periodic scheduling of tasks on parallel processors”, Pract Appl Parallel Comput: Adv Comput Theory Pract, 12: 363-370.
[26] Dawande, M., Geismar, HN., Sethi, SP., Sriskandarajah, C. (2005). “Sequencing and scheduling in robotic cells: recent developments”, Journal of Scheduling, 8(5): 387-426.
[27] Dawande, MW., Geismar, HN., Sethi, SP. (2007). “Throughput optimization in robotic cells”, Springer.
[28] McCormick, ST., Rao, US. (1994). “Some complexity results in cyclic scheduling”, Math Comput Model, 20(2):107–122.
[29] Levner, E., Katz, V., De Pablo, DAL. (2007). “Cyclic scheduling in robotic cells: an extension of basic models in machine scheduling theory”, Multiprocessor Scheduling 1.
[30] Grave's, SC., Meal, HC., Stefek, D., Zeghmi, AH. (1983). “Scheduling of reentrant flow shops”, Journal of Operations Management, 3(4):197-207.
[31] McCormick, ST., Pinedo, ML., Wolf, B. (1986). “Sequencing in a flexible assembly line with blocking to minimize cycle time”, Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems, 15(1): 227–267.
[32] McCormick, ST., Pinedo, ML., Shenker, S., Wolf, B. (1989). “Sequencing in an assembly line with blocking to minimize cycle time”, Operational Research ,37(6): 925–935.
[33] Hanen, C. (1994). “Study of a NP-hard cyclic scheduling problem: the recurrent job-shop”, European Journal of Operational Research, 72(1): 82–101.
[34] Kampmeyer, T. (2006). “Cyclic scheduling problems, PhD thesis, University of Osnabrueck”, Germany.
[35] Nambiar, AN. (2007). “Mathematical formulation and scheduling heuristics for cyclic permutation flow-shops”, PhD dissertation, Ohio University.
[36] Baker, K. R. (1974). “Introduction to sequencing and scheduling”, John Wiley & Sons.
[37] فخرزاد، محمدباقر، علی­نژاد، اسماعیل (1392). برنامه‌ریزی و زمانبندی پیشرفته با در نظر گرفتن اثر یادگیری در سیستم‌های ساخت کارگاهی انعطاف‌پذیر، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 1(1): 13-24.
[38] Okolowski, D., Gawiejnowicz, S. (2010). “Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect”, Computers & Industrial Engineering 59: 272–279.
[39] ذگردی، سید حسام‌الدین، بهلولی، احسان (1388). زمانبندی گروهی با در نظر گرفتن اثر یادگیری در سیستم تولید سلولی، نشریه بین‌المللی مهندسی صنایع و مدیریت تولید، 20(2): 45-56.
 [40] Biskup, D. A. (2008). “State-of-the-art review on scheduling with learning effects”, European Journal of Operational Research, 188: 315–329.
[41] Wright, T.P. (1936). “Factors affecting the cost of airplanes”, Journal of Aeronautical Sciences, 3: 122–128.
[42] Biskup, D. (1999). “Single-machine scheduling with learning considerations, European Journal of Operational Research”, 115: 173-178.
[43] Janiak, A., Rudek, R. (2008). “A new approach to the learning effect: Beyond the learning curve restrictions”, Computers & Operations Research, 35: 3727-3736.
[44] Mosheiov, Gur. (2000). “Scheduling problem with a learning effect”, European Journal of Operational Research, 132: 687-693.
[45] Wang, Ji-Bo, Huang, Xue., Wang, Xiao-Yuan., Yin, Na., Wang, Li-Yan. (2009). “Learning effect and deteriorating jobs in the single machine scheduling problems”, Applied Mathematical Modelling. 33: 3848-3853.
[46] Toksari, M., Duran, Güner Ertan. (2008). “Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach”, International Journal of Advanced Manufacturing Technology, 38:801–808. DOI 10.1007/s00170-007-1128-3.
[47] Eren, Tamer. (2008). “A bicriteria parallel machine scheduling with a learning effect of setup and removal times”, Applied Mathematical Modelling. 33: 1141–1150.
[48] Xu, Dehua., Yin, Yunqiang. (2011). “Comments on A bicriteria parallel machine scheduling with a learning effect of setup and removal times”, Applied Mathematical Modelling, 35: 3648-3650.
[49] Behnamian, J., Zandieh, M. (2012). “Earliness and Tardiness Minimizing on a Realistic Hybrid Flow shop Scheduling with Learning Effect by Advanced Metaheuristic”, Arabian Journal for Science and Engineering, 38:1229-1242.
[50] Behnamian, J. (2014). “Scheduling and worker assignment problems on hybrid flow shop with cost-related objective function”, International Journal of Advanced Manufacturing Technology, DOI 1 0.1007/s00170-014-5960-y.
[51] Johnson, SM. (1954). “Optimal two and three stage production schedules with setup times included”, Naval Res Logist Q, 1(1): 61–68.
[52] Ríos-Mercado, R.Z., Bard, J.F. (1998). “Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups”, Computers & Operations Research, 25(5): 351-366.
 [53] Gupta, J.N.D., Tunc, E.A. (1991). “Schedules for a two stage hybrid flow shop with parallel machines at the second stage”, International Journal of Production Research, 29(7): 1489-1502.
[54] Ruiz, R., Maroto, C. (2006). “A genetic algorithm for hybrid flow shops with sequence dependent setup times and machine eligibility”, European Journal of Operational Research, 169(3): 781–800.
[55] Yaurima, V., Burtseva, L., Tchernykh, A. (2009). “Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers”, Computers & Industrial Engineering Journal, 56(4): 1452–146
Journal of Industrial Engineering Research in Production Systems
Volume 4, Issue 8
February 2017
Pages 105-117

Files

Share

How to cite

Statistics