fa الگوریتم ممتیک برای حل مسئله زمانبندی کار کارگاهی منعطف با امکان ایجاد وقفه در انجام فعالیت‌ها سایر موضوعاتی که به مرزهای دانش در مهندسی صنایع و تولید کمک می کند Other related Industrial and production reserach subjects in which has direct relation to the state-of-the art of the IE پژوهشي Research <p align="right"><span style="FONT-FAMILY: Nazanin FONT-SIZE: 11pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA">مسئله زمانبندی کارِ کارگاهی منعطف </span><span style="FONT-FAMILY: "Times New Roman","serif" FONT-SIZE: 10pt mso-bidi-font-family: Nazanin mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA">Flexible Job Shop)</span><span dir="rtl"></span><span dir="rtl"></span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 10pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span>) </span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 11pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA">، حالت توسعه یافته زمانبندی کارِ کارگاهی </span><span style="FONT-FAMILY: "Times New Roman","serif" FONT-SIZE: 10pt mso-bidi-font-family: Nazanin mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA">Job Shop)</span><span dir="rtl"></span><span dir="rtl"></span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 10pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span>) </span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 11pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA">‌است که در آن هر عملیات می‌تواند توسط بیش از یک ماشین از میان مجموعه ماشین‌های‌ موجود انجام شود. این مسئله در زمره مسائل </span><span style="FONT-FAMILY: "Times New Roman","serif" FONT-SIZE: 10pt mso-bidi-font-family: Nazanin mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA">NP-hard</span><span dir="rtl"></span><span dir="rtl"></span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 10pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl"><span dir="rtl"></span><span dir="rtl"></span> </span><span style="FONT-FAMILY: Nazanin FONT-SIZE: 11pt mso-ascii-font-family: 'Times New Roman' mso-hansi-font-family: 'Times New Roman' mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA" dir="rtl" lang="FA">طبقه بندی می‌شود و برای حل آن با دو زیر مساله مواجه هستیم. نخست اینکه، نحوه تخصیص هر فعالیت به ماشینی از میان ماشین‌های‌ موجود که قادر به پردازش فعالیت مورد نظر است تعیین شود و سپس توالی فعالیت‌های‌ تخصیص یافته مشخص گردد. واضح است که دستیابی به پاسخ بهینه، حتی در ابعاد کوچک دشوار و بسیار زمان‌بر است در این مقاله یک الگوریتم ممتیک جهت کمینه کردن حداکثر زمان تکمیل و بدست آوردن جواب بهینه<font face="Nazanin"><span style="mso-spacerun: yes"><font size="3">  </font></span>مسائل کوچک و بهترین جواب مسایل متوسط و بزرگ ارائه می شود.در این مقاله<span style="mso-spacerun: yes"><font size="3">  </font></span>همچنین به منظور بهبود جواب های حاصل از الگوریتم ممتیک<span style="mso-spacerun: yes"><font size="3">  </font></span>و کاهش حداکثر زمان تکمیل فرض ایجاد وقفه در انجام کارها را نیز در نظر می­گیریم.</font></span></p> <span style="FONT-FAMILY: "Times New Roman","serif" FONT-SIZE: 11pt mso-fareast-language: EN-US mso-ansi-language: EN-US mso-fareast-font-family: 'Times New Roman' mso-bidi-language: FA"><em>Flexible job shop scheduling problem <span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">)</font></span>FJSP<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">(</font></span><span dir="ltr"></span><span dir="ltr"></span><span dir="ltr"></span><span dir="ltr"></span> is an extension of the classical job shop scheduling problem which allows an operation to be processed by any machine from a given set<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">. </font></span>FJSP is NP<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">-</font></span>hard and mainly presents two difficulties<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">. </font></span>The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">. </font></span>However, it is quite difficult to achieve an optimal solution to this problem in medium and large size problems with traditional optimization approaches<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">. </font></span>In this paper a memetic algorithm (MA)<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman"> </font></span>or flexible job shop scheduling with overlapping in operation is proposed that solves the FJSP to minimize makespan time and obtain the optimum solution for small problem and best solution for medium and large scale problems<span dir="rtl"></span><span dir="rtl"></span><span dir="rtl" lang="FA"><span dir="rtl"></span><span dir="rtl"></span><font size="3" face="Times New Roman">. </font></span>In this paper we also used preemption to improve the results of memetic algorithm and reduce the makespan.</em></span> الگوریتم ممتیک، زمانبندی کار کارگاهی منعطف، اشتراک زمانی فعالیت‌ها، وقفه Memetic algorithm, Flexible job shop scheduling, Overlapping, Preemption 331 340 http://ijiepm.iust.ac.ir/browse.php?a_code=A-10-416-3&slc_lang=fa&sid=1 بابک یوسفی یگانه bys.yegane@gmail.com 180031947532846003544 180031947532846003544 Yes ،دانشگاه آزاد اسلامی، واحد ملایر، گروه مهندسی صنایع، ملایر، ایران، نرگس خانلرزاده، nkh.khanlarzade@gmail.com 180031947532846003545 180031947532846003545 No دانشجوی کارشناسی ارشد مهندسی صنایع، دانشگاه تربیت مدرس، علی رحیمی فرد، alirahimifard59@gmail.com 180031947532846003546 180031947532846003546 No دانشگاه آزاد اسلامی، واحد ملایر، گروه مهندسی صنایع، ملایر، ایران