خلاصة:
این مقاله به زمانبندی کارها در سیستم جریان کارگاهی با معیار عملکرد مجموع دیرکردهای مرحلهای میپردازد. این معیار بیانگر شرایطی است که کارها علاوه بر موعد نهایی، دارای موعدهای تحویل میانی برای فعالیتها هستند. در برخی از امور، مانند پروژههای تحقیقاتی، کارهای خدماتی، طراحی و مهندسی، خروجی گامهای مختلف تعیین شده و زمان تحویل آنها مشخص میشود. با توجه به طی نمودن یک مسیر توسط این پروژهها، استفاده از منابع مشترک و همچنین تعهد به انجام بهموقع مراحل کاری و عدم تأخیر آنها، برنامهریزی صحیح برای تخصیص منابع و زمانبندی مناسب جهت حداقل کردن مجموع دیرکردها ضروری مینماید. تاکنون، این هدف کمتر مدنظر قرار گرفته و استفاده از روشهای فراابتکاری برای حل آن مشاهده نشده است. با توجه به NP-hard بودن چنین مسئلهای، در این مقاله نسبت به حل آن با روشهای فراابتکاری، الگوریتم ژنتیک، شبیهسازی تبرید و ازدحام ذرات اقدام شد. 96 مسئله در ابعاد مختلف و سه مقدار عامل فشردگی برای زمانهای تحویل ایجاد و حل شدند. الگوریتمهای شبیهسازی تبرید و الگوریتم ژنتیک در رابطه با دستیابی به هدف مسئله، یعنی حداقل مجموع دیرکرد، نتایج بهتری را نشان دادند. روش ازدحام ذرات زمان حل کمتری داشت. در کل با در نظر گرفتن هر دو شاخص، نتایج نشان از برتری الگوریتم ژنتیک در این مسئله دارد.
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.
ملخص الجهاز:
پژوهش هاي نوين در تصميم گيري دوره ٢، شماره ٣، پاييز ١٣٩٦ حداقل ديرکرد در زمانبندي مسائل جريان کارگاهي با موعد تحويل مياني 1) لعيا الفت * استاد، گروه مديريت صنعتي، دانشکده مديريت و حسابداري، دانشگاه علامه طباطبائي، تهران، ايران دريافت : ١٣٩٥/٩/١٨ پذيرش: ١٣٩٦/٥/٣٠ چکيده ايـن مقالـه بـه زمـانبنـدي کارهـا در سيسـتم جريـان کارگـاهي بـا معيـار عملکـرد مجمـوع ديرکردهاي مرحله اي ميپردازد.
اين مقاله به اين مهم ميپردازد و حداقل کردن مجمـوع ديرکرد٣ در يک سيستم جريان کارگـاهي را بـا فـرض اينکـه هـر کـار متشـکل از چندين عمليات يا مراحلي با موعد تحويل است ، مدنظر قـرار مـيدهـد؛ بـه عبـارتي موعدهاي مياني در محاسبه ديرکرد هر کار لحاظ ميشود.
_______________________________________ لعيا الفت [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.
[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.
[9] Karimi N and Davoudpour H, "A high Performing meta heuristic for multi- objective Flow shop Scheduling Problem," Computers & Operations Research, vol.
[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.
-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.