مقایسه سه روش فراابتکاری برای کمینه نمودن زمان چرخه در مسئله زمانبندی جریان کارگاهی مختلط دوره‌ای با در نظر گرفتن اثر یادگیری

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار گروه صنایع دانشکده مهندسی دانشگاه بوعلی سینا

2 دانشجو دکتری مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران

چکیده

زمانبندی کار‌ها در صنایعی که روند حرکت کار‌ها بر روی ماشین‌ها به صورت دوره‌ای می‌باشد، همچون صنایعی که محصولات آنها فاسد شدنی نظیر صنایع غذایی و یا دارای طول عمر همانند مواد شیمیایی، رادیواکتیو و غیره هستند، از اهمیت زیادی برخوردار است، زیرا که این صنایع به دلیل محدودیت‌های زمانی و یا رقابت با سایر شرکت‌ها سعی در کمینه نمودن بازه زمانی انجام کار‌ها دارند. از آنجا که غالباً محیط تولیدی این صنایع به صورت تولید جریان کارگاهی مختلط دوره‌ای می‌باشد و اثر یادگیری اپراتور در سرعت تولید مشهود است، این پژوهش در نظر دارد که زمان چرخه بر روی هر ماشین را با وجود اثر یادگیری به ‌کمک چینش فعالیت‌ها کمینه نماید. برای این منظور در روند این پژوهش، ابتدا تحقیقات پیشین در این حوزه مورد مطالعه قرار گرفت. سپس مدل ریاضی این مسأله نوشته و به دلیل آنکه ماهیت کمینه نمودن زمان انجام کار‌ها در محیط تولید جریان کارگاهی مختلط دوره‌ای، جزء مسائل سخت (NP-Hard) می‌باشد، برای حل این مسأله از سه روش فراابتکاری الگوریتم ژنتیک، الگوریتم شبیه‌سازی تبرید و الگوریتم شبیه‌سازی تبرید مبتنی بر جمعیت استفاده شد. نتایج نشان می‌دهند که الگوریتم شبیه‌سازی تبرید مبتنی بر جمعیت به دلیل ساختار جمعیتی آن، به‌طور میانگین نسبت به دو الگوریتم دیگر کارایی بهتری دارد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

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

چکیده [English]

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.

کلیدواژه‌ها [English]

  • Scheduling
  • Hybrid flow shop
  • Learning effect
  • Metaheuristic algorithm
[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