حداقل دیرکرد در زمان‌بندی مسائل جریان کارگاهی با موعد تحویل میانی

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

نویسنده

استاد، گروه مدیریت صنعتی، دانشکده مدیریت و حسابداری، دانشگاه علامه طباطبائی، تهران، ایران

چکیده

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

کلیدواژه‌ها


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

Total Tardiness Minimization in Flow Shop with Intermediate Due Dates

نویسنده [English]

  • Laya Olfat
Professor, Faculty of Management & Accounting, Allameh Tabataba'i University, Tehran, Iran
چکیده [English]

In this paper minimization of total tardiness with intermediate due dates in flow shop scheduling is presented. There are some situations in which there is a due date for each intermediate operation of a job such as research and development and consulting projects. Usually each project (job) is carried out through different phases (machines) and there is an associated due date for each phase. Thus the tardiness of each phase should be considered. Due to the complex nature of the tardiness in flow shop problems and since this problem is a NP-hard, three Meta heuristic approaches; Simulated Annealing, Genetic Algorithm and Particle Swarm Optimization have been applied to reach near optimal solution. Extensive computational experiments are performed on 96 generated scenarios. Two indicators were used to evaluate the Meta heuristics. The results indicate that Simulated Annealing and Genetic Algorithm presented better solutions for the given scheduling problem. Moreover considering the CPU time, Genetic Algorithm provided the solution in less time.

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

  • Flow shop scheduling
  • Total Tardiness
  • Meta Heuristic
  • Intermediate due dates
[1]   Deming L and Ping GX, "Variable neighborhood search for minimizing tardiness objectives on flow shop with batch processing machines," Int J Prod Res.., vol. 49, pp. 519-529, 2011.
[2]    Baker K.R and Schrage L.E, "Sequencing with earliness and tardiness penalties: a review," Operations Research, vol. 38, pp. 22-36, 1990.
[3]    Kanet J, "Minimizing the average deviation of job completion times about a common due date," Naval Research Logistics Quart, vol. 28, pp. 643-651, 1981.
[4]    Yeh W and Allahverdi A, "A branch and bound algorithm for the three machine flow shop scheduling problem with bi-criteria of make-span and total flow time," International Transaction in Operations Research, vol. 11(30), pp. 323-327, 2004.
[5]    Anghinolfi D and Paolucci M, "Parallel machine total tardiness Scheduling With a new hybrid met heuristic approach," Computers & Operations Research, vol. 34, pp. 3471-3490, 2007.
[6]    Sari cicek i and Celik C, "Two meta-heuristics for Parallel machine Scheduling with job splitting to minimize total tardiness," Applied Mathematical Modelling, vol. 35, pp. 4117-4126, 2011.
[7]    Demirel T, Ozkir V, Demirel NC and Tasdelen B, "A genetic algorithm approach for minimizing total tardiness in parallel machine scheduling problems.," Proceedings of the World Congress on Engineering, July 6-8 2011.
[8]    Vallada E, Ruiz R and Minella G, "Minimizing total tardiness in the m-machine flow shop problem: a review and evaluation of heuristics and meta heuristics," Comput Oper Res, vol. 35, pp. 1350-1373, 2008.
[9]    Karimi N and Davoudpour H, "A high Performing meta heuristic for multi-objective Flow shop Scheduling Problem," Computers & Operations Research, vol. 52, pp. 149-156, 2014.
[10] Ghassemi Tari F and Olfat L, "Heuristic rules for tardiness Problem in Flow Shop With intermediate due. Int. J Adv manut Technology," J Adv manut Technology, vol. 71, pp. 381-393, 2014.
[11] Brucker P., S. Knust and G. and Wang, "Complexity result for flow-shop problems with a single server," European Journal of Operational Research, vol. 165, pp. 398-407, 2005.
[12] Elmi, A, Solimanpur, M and & Topaloglu, S, "A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts," Computers & Industrial Engineering, 2011.
[13] Gaafar, L and & Masoud, S, "Genetic algorithms and simulated annealing for scheduling in agile manufacturing.," International Journal of Production Research, vol. 43(14), pp. 3069-3085, 2005.
[14] Rabiee, M, Zandieh, M and & Jafarian, A, "Scheduling of a no-wait two-machine flow shop with sequence-dependent setup times and probable rework using robust meta-heuristics," 2012.
[15]  Ghafoori  S. and M. taghizadeh yazdi, "Proposing a Multi- Objective Mathematical Model for RCPSP and Solving it with Firefly and Simulated Annealing algorithms," Journal of Modern Researches in Decision Making, vol. vol 1 no4 (in Persian), pp.117-142,2017.
[16] Lian, Z, Gu, X and & Jiao, B, "A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan," Chaos, Solitons & Fractals, vol. 35(5), pp. 851-861, 2008.
[17] Tasgetiren, M.F, Liang, Y.-C, Sevkli, M and & Gency, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177(3), p. 1930, 2007.
[18] Chang, P.C, Chen, S.H and Fan, C.Y, "A hybrid electromagnetism-like algorithm for single machines scheduling problem," Expert Syst. Appl, vol. 36 (2), pp. 1259-1267, 2009.
[19] Holland, J.H, "Adaptation in natural and artificial systems, University of Michigan press," Ann Arbor, MI, vol. 1(97), p. 5, 1975.
[20] Yang, Y, Cui, Z and & Cheng, J, "An Improved Genetic Algorithm for Multiple-Depot Vehicle Routing Problem with Time Window," Journal of Soochow University (Engineering Science Edition), vol. 26(2), pp. 20-23, 2006.
[21] Chen, C.-L, Neppalli, R.V and & Aljaber, N, "Genetic algorithms applied to the continuous flow shop problem.," Computers & Industrial Engineering, vol. 30(4), pp. 919-929, 1996.
[22] Gen M., F. Altiparmak and L & Lin, "A genetic algorithm for two- stage transportation problem using priority- based encoding or spectrum,". vol 28 (3),. pp 337-354, 2006.
[23] Vahdani, B and & Zandieh, M, "Scheduling trucks in cross-docking systems: Robust meta-heuristics," Computers & Industrial Engineering, vol. 58(1), pp. 12-24, 2010.
[24] Sivanandam, S and & Deepa, S, "Introduction to genetic algorithms: Springer Science & Business Media.," 2007.
[25] Kirkpatrick, S, Gelatt, C.D and & Vecchi, M.P, "Optimization by simulated annealing," science, vol. 220(4598), p. 671, 1983.
[26] Golden, B.L and & Skiscim, C.C, "Using simulated annealing to solve routing and location problems," Naval Research Logistics Quarterly, vol. 33(2), pp. 261-279, 1986.
[27] Tarantilis, C and & Kiranoudis, C, "A meta-heuristic algorithm for the efficient distribution of perishable foods," Journal of food engineering, vol. 50(1), pp. 1-9, 2001.
[28] Kennedy, J and & Eberhart, R.C, "Particle swarm optimization. In: P.o.I.C.o.N. Networks," Perth, Australia,: IEEE., vol. 4, pp. 1942-1948, 1995.
[29] Eberhart, R.C, Shi, Y and & Kennedy, J, "Swarm intelligence. San Mateo," CA: Morgan Kaufmann division of Academic Press, 2011.
[30] Shi, Y and & Eberhart, R.C, "(1999). Empirical study of particle swarm optimization," In: (Vol. 3): IEEE..
[31] Govindan, K, Jafarian, A, Khodaverdi, R and & Marid, "Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food," International Journal of Production Economic, 2013.