پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,652 |
| تعداد مقالات | 13,408 |
| تعداد مشاهده مقاله | 30,253,135 |
| تعداد دریافت فایل اصل مقاله | 12,089,753 |
مدل‌سازی مسئلۀ زمان‌بندی تک‌ماشین با تولید دسته‌ای و خرابی تصادفی و حل آن به‌وسیلۀ روش شاخه و کران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| پژوهش در مدیریت تولید و عملیات | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مقاله 7، دوره 13، شماره 2 - شماره پیاپی 29، تیر 1401، صفحه 121-136 اصل مقاله (962.78 K) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نوع مقاله: مقاله پژوهشی | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/jpom.2022.126335.1315 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| احسان ملائی1؛ رامین صادقیان* 1؛ پرویز فتاحی2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه پیام نور، تهران، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه الزهرا، تهران، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| در این مقاله مسئلۀ زمان‌بندی تک‌ماشین با تولید دسته‌ای و خرابی تصادفی ماشین بررسی می‌شود. در این مسئله هر کار متعلق به یک خانوادۀ کار است و هر خانوادۀ کار زمان آماده‌سازی معلوم و مستقل از توالی دارد. همچنین فرض می‌شود یک خرابی ماشین در طول افق برنامه‌ریزی اتفاق می‌افتد و زمان شروع و طول تصادفی با توزیع احتمال دلخواه و از قبل مشخص دارد. تابع هدف مسئله حداقل‌سازی مجموع حداکثر زودکرد و حداکثر دیرکرد موردانتظار کارهاست. تاکنون در پژوهش‌های گذشته مطالعه‌ای بر این مسئله مشاهده نشده است. برای این مسئله یک مدل جدید برنامه‌ریزی عدد صحیح خطی مختلط توسعه داده شده است. با توجه به NP-hard بودن مسئله برای حل بهینۀ آن، یک الگوریتم شاخه و کران جدید با اصول غلبه و یک حد پایین کارا ارائه شده است که از یک الگوریتم ابتکاری جدید برای به دست آوردن حد بالا استفاده می‌کند. به‌منظور ارزیابی عملکرد الگوریتم‌های معرفی‌شده، تعداد 2520 عدد مسئلۀ نمونه طراحی و با الگوریتم‌های ارائهشده، حل شده است. نتایج محاسباتی نشان می‌دهد 98% مسائل نمونه در محدودۀ زمانی مشخص‌شده با الگوریتم شاخه و کران به‌صورت بهینه حل شده‌اند و میانگین درصد انحراف از جواب بهینه در الگوریتم ابتکاری ارائهشده کمتر از 30% است. این موارد کارایی الگوریتم‌های ارائهشده را تأیید می‌کند. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| کلیدواژه‌ها | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| زمان‌بندی؛ تک‌ماشین؛ تولید دسته‌ای؛ خرابی؛ زودکرد؛ دیرکرد | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
1- مقدمه امروزه در بسیاری از صنایع مدرن تولیدی مانند تولید فولاد، تولید نیمه‌رسانا و صنعت تولید هواپیما، فرآیندهای تولید دسته‌ای به‌طور گسترده‌ای درخور توجه قرار گرفته است (چنگ[i] و همکاران، 2017). همچنین خرابی غیرمنتظرۀ ماشین‌آلات یک چالش مهم در سیستم‌های تولیدی و پردازنده‌های رایانه‌ای است. در بسیاری از سیستم‌های تولیدی و خدماتی، به دلایلی نظیر خرابی ماشین‌آلات، نوسانات و خرابی‌های برق، کمبود مواد اولیه، نیروی انسانی و ابزارآلات و غیره، دوره‌های عدم‌دسترسی با شروع و مدت‌زمان تصادفی اتفاق می‌افتد (شونگ[ii] و همکاران، 2017). از سوی دیگر براساس نظام تولید بهنگام، هم زودکرد و هم دیرکرد کارها در محیط‌های تولیدی هزینه‌بر است. دیرکرد کارها به هزینه‌های کمبود منجر می‌شود و زودکرد کارها نیز باعث بروز هزینه‌های موجودی می‌شود. در این مقاله مسئلۀ زمان‌بندی تک‌ماشین با تولید دسته‌ای، خرابی تصادفی و تابع هدف مجموع حداکثر زودکرد و دیرکرد بررسی می‌شود. در این مسئله کارها براساس مشابهت با یکدیگر به خانواده‌هایی تقسیم‌بندی می‌شوند و کارهای متعلق به یک خانواده به آماده‌سازی نیاز ندارند؛ اما اگر پس از تکمیل کاری از یک خانوادۀ خاص، کاری از خانوادۀ دیگری بخواهد پردازش یابد، آماده‌سازی ضرورت می‌یابد. فرض می‌شود یک خرابی در طول افق برنامه‌ریزی وجود دارد و زمان شروع و مدت‌زمان آن متغیرهای تصادفی با توزیع‌های احتمال مشخص و دلخواه است. در این مسئله هر کار، زمان پردازش و موعد تحویل معلوم دارد و کلیۀ کارها از سر گرفتنی است؛ یعنی اگر هنگام پردازش، یک کار بر ماشین خرابی اتفاق بیفتد، پس از اتمام خرابی کل عملیات پردازش آن کار مجدداً انجام می‌شود. هدف زمان‌بندی کارها به‌گونه‌ای است که مجموع قابل‌انتظار حداکثر زودکرد و حداکثر دیرکرد کارها حداقل شود. تاکنون هیچ‌گونه مطالعه‌ای بر این مسئله مشاهده نشده است. تاکنون مطالعات بسیاری بر مسائل زمان‌بندی با پردازش دسته‌ای انجام شده است. برخی از پژوهشگران مسائل زمان‌بندی تک‌ماشین را با دسته‌بندی سری کارها و انواع معیارهای منظم بررسی کرده‌اند (پی[iii] و همکاران، 2017 الف و ب؛ فن[iv] و همکاران، 2017؛ پی و همکاران، 2019). برخی دیگر مسائل زمان‌بندی تک‌ماشین را با دسته‌بندی موازی کارها، با فرضیات مختلف تجزیه‌وتحلیل کرده‌اند (چنگ و همکاران، 2017؛ تانگ[v] و همکاران، 2017؛ مونچ[vi] و روب[vii]، 2017؛ لی[viii] و همکاران، 2019؛ کونگ[ix] و همکاران، 2020؛ امده[x] و همکاران، 2020؛ هاشمی و کاشان، 2020) و برخی دیگر مسائل زمان‌بندی تک‌ماشین را با زمان‌های آماده‌سازی خانوادۀ کار بررسی کرده‌اند (هیندر[xi] و میسون[xii]، 2017؛ عبداله[xiii] و جنگ[xiv]، 2017). برای هریک از مسائل معیارهای منظمی بررسی شده و براساس فرضیات داده‌شده الگوریتم‌های دقیق (مدل‌سازی ریاضی، برنامه‌ریزی پویا، شاخه و کران)، الگوریتم‌های ابتکاری و یا فراابتکاری ارائه شده است. برخی از پژوهشگران مسائل زمان‌بندی را در شرایط خرابی بررسی کرده و با استفاده از روش‌های دقیق، ابتکاری یا فراابتکاری آنها را حل کرده‌اند (شونگ و همکاران، 2017؛ هاله و همکاران، 2017؛ امیرخانی و همکاران، 2017). شن[xv] و ژو[xvi] (2018) برای مسئلۀ تک‌ماشین با نت دوره‌ای، زمان‌های پردازش و تعمیر غیرقطعی و تابع هدف حداکثر زمان تکمیل الگوریتم‌های ابتکاری را ارائه دادند. دتی[xvii] و همکاران (2019) برای مسئلۀ تک‌ماشین با نت انعطاف‌پذیر و توابع هدف، حداکثر زمان تکمیل و زمان تکمیل کل یک مدل استوار و رویه‌های ابتکاری را برای حل آن توسعه دادند. تاکنون بر مسائل زمان‌بندی با پردازش دسته‌ای و محدودیت دسترسی، مطالعات کمی مشاهده شده است. پی و همکاران (2017 ج) برای مسئلۀ تک‌ماشین دسته‌ای سریالی با یک محدودیت دسترسی، زمان‌های پردازش وابسته به موقعیت، زمان‌های آماده‌سازی وابسته به زمان و تابع هدف حداکثر زمان تکمیل، یک الگوریتم دقیق ارائه کردند. لو[xviii] و همکاران (2018) برای مسئلۀ زمان‌بندی ماشین‌های موازی غیرمرتبط دسته‌ای، با کارها و فعالیت‌های نت زوال‌یافتنی و تابع هدف حداکثر زمان تکمیل، یک الگوریتم فراابتکاری ترکیبی را ارائه دادند. همان‌گونه که بررسی پژوهش‌های گذشته نشان می‌دهد، تاکنون مطالعه‌ای بر مسائل زمان‌بندی تک‌ماشین با تولید دسته‌ای، خرابی تصادفی و تابع هدف مجموع حداکثر زودکرد و دیرکرد مشاهده نشده است. در این مقاله برای این مسئله، یک مدل برنامه‌ریزی عدد صحیح خطی جدید ارائه شده است. همچنین با توجه به سخت‌بودن مسئله، یک الگوریتم شاخه و کران جدید برای حل بهینۀ آن طراحی شده است که حد بالای آن با یک الگوریتم ابتکاری جدید مبتنی بر تپه‌نوردی به دست می‌آید. ترتیب بخش‌های بعدی مقاله به‌صورت زیر است: در بخش دوم، مسئله و ویژگی‌های آن تعریف می‌شود؛ در بخش سوم یک مدل برنامه‌ریزی ریاضی برای مسئله ارائه و همچنین یک الگوریتم حل بهینۀ شاخه و کران برای مسئله تعریف می‌شود؛ در بخش چهارم نتایج محاسباتی ارائه می‌شود؛ در بخش پنجم نتایج به‌دست‌آمده تجزیه‌وتحلیل می‌شود و در بخش ششم، نتیجه‌گیری و پیشنهادهایی برای پژوهش‌های آتی ارائه می‌شود.
2- مبانی نظری پژوهش مسئله عبارت است از زمان‌بندی F خانوادۀ کار بر یک ماشین، به‌طوری که هر خانواده f ( ) دارای کار و است. هر کار زمان پردازش معلوم و موعد تحویل معلوم دارد. هر خانوادۀ f یک آماده‌سازی با زمان معلوم دارد. اگر در یک توالی، کار اولین کار توالی باشد یا کار قبل از عضو خانوادۀ f نباشد یا کار اولین کار بعد از اتمام خرابی باشد، آنگاه آماده‌سازی ضرورت می‌یابد. کلیۀ کارها از سر گرفتنی‌اند؛ یعنی اگر هنگام وقوع خرابی پردازش کاری ناتمام بماند، بعد از اتمام خرابی، پردازش آن کار مجدداً شروع می‌شود. شروع و طول دورۀ خرابی به‌ترتیب با دو متغیر تصادفی و D نشان داده و فرض می‌شود براساس اطلاعات گذشته، توزیع احتمال این دو متغیر تصادفی از قبل معلوم است. همچنین فرض می‌شود زمان شروع و طول دورۀ خرابی می‌توانند هر توزیع احتمال دلخواهی داشته باشند. با الهام از گورن[xix] و سبوکیوقلو[xx] (2009)، تابع هدف استوار مجموع موردانتظار حداکثر زودکرد و حداکثر دیرکرد برای این مسئله در نظر گرفته شده است که به‌صورت زیر تعریف می‌شود:
که در آن و مقادیر موردانتظار حداکثر زودکرد و حداکثر دیرکردند و به‌صورت زیر محاسبه می‌شوند:
در این روابط، نشان‌دهندۀ زمان تکمیل کار i ( ) در توالی است و با توجه به تصادفی‌بودن زمان شروع و طول خرابی، مقدار آن نیز تصادفی است. این مسئله به‌صورت نشان داده می‌شود. در این مسئله با توجه به هزینه‌های بالای بیکار نگه داشتن عمدی ماشین، فرض می‌شود بیکاری عمدی مجاز نیست. مسئلۀ بررسی‌شده کاملاً جدید است و تاکنون در پژوهش‌های گذشته مطالعه‌ای بر آن مشاهده نشده است. با توجه به اینکه مسئلۀ تک‌ماشین با یک دورۀ عدم‌دسترسی و تابع هدف حداکثر مغایرت ( )، NP-hard است (لی[xxi]، 1996)، همچنین مسئلۀ تک‌ماشین با خانوادۀ آماده‌سازی و تابع هدف حداکثر مغایرت ( ) نیز NP-hard است (برونو[xxii] و دونی[xxiii]، 1978)، بنابراین می‌توان گفت مسئله به‌شدت NP-hard است. 3- روش‌شناسی پژوهش با توجه به جدیدبودن مسئله ، کلیۀ روش‌های حل ارائهشده برای این مسئله در این مقاله نیز کاملاً جدید و نوآورانه است. در این بخش رویکردهای حل این مسئله بررسی می‌شود. در ابتدا با توجه به مبانی نظری و مفروضات مطرح‌شده در بخش دوم، مدل ریاضی مسئله توسعه داده می‌شود، سپس برای حل بهینۀ مسئله در ابعاد گسترده‌تر، یک الگوریتم بهینۀ شاخه و کران و یک الگوریتم ابتکاری ارائه می‌شود. 3-1- مدل ریاضی مسئله به‌منظور توسعۀ مدل برنامۀ ریاضی مسئله، مقدار متغیر تصمیم ، یک تعریف می‌شود اگر کار در موقعیت k ام ( ) توالی پردازش یابد و در غیر این صورت مقدار آن صفر تعریف می‌شود. همچنین اگر کار زمان‌بندی‌شده در موقعیت k ام توالی به آماده‌سازی نیاز داشته باشد، مقدار متغیر تصمیم یک تعریف و در غیر این صورت صفر تعریف می‌شود. درنهایت اگر کار زمان‌بندی‌شده در موقعیت k ام قبل از شروع خرابی موردانتظار زمان‌بندی شود، مقدار متغیر تصمیم برابر صفر تعریف می‌شود و اگر کار مربوط بعد از پایان خرابی پیش‌بینی‌شده زمان‌بندی شود، مقدار این متغیر یک تعریف می‌شود. مدل برنامه‌ریزی ریاضی مسئله به‌صورت زیر است:
با توجه به جدیدبودن ماهیت مسئلۀ بررسی‌شده و در نظر گرفتن هم‌زمان مفروضات تولید دسته‌ای و خرابی تصادفی در آن، مدل ارائهشده برای مسئلۀ مدنظر نیز جدید است. در این مدل روابط (10) تا (13) محدودیت‌های جدیدی‌اند که خاص مسئلۀ بررسی‌شده‌اند و دیگر روابط توسعه‌یافته، برخی روابط ارائهشده در پژوهش‌های قبلی‌اند. در ادامه روابط ارائهشده در این مدل تشریح می‌شود. رابطۀ (4) نشان‌دهندۀ تابع هدف استوار مسئله است که به‌دنبال حداقل‌کردن حداکثر مجموع زودکرد و دیرکرد موردانتظار است. روابط (5) تا (8) توسعه‌یافتۀ محدودیت‌های مدل ارائهشده توسط گوپتا[xxiv] و چانتراواراپان[xxv] (2008) برای زمان‌بندی با خانوادۀ آماده‌سازی‌اند. محدودیت‌های (5) و (6) بیان می‌کنند که هر موقعیت تنها می‌تواند توسط یک کار اشغال شود و هر کار تنها می‌تواند یک‌بار پردازش یابد. محدودیت (7) برای کار در اولین موقعیت توالی، زمان آماده‌سازی خانوادۀ کار را در نظر می‌گیرد. محدودیت (8) برای کارهایی که قبل از آنها کاری از یک خانواده متفاوت است، زمان آماده‌سازی خانوادۀ کار را در نظر می‌گیرد. محدودیت (9) توسعه‌یافتۀ محدودیت مربوط به محاسبۀ زمان تکمیل در مدل ارائهشده توسط دتی و همکاران (2019) است و زمان تکمیل موردانتظار کلیۀ کارها به‌جز اولین کار، بعد از زمان پایان موردانتظار خرابی را محاسبه می‌کند. محدودیت (10) زمان تکمیل اولین کار بعد از پایان موردانتظار خرابی را محاسبه می‌کند. محدودیت (11) تضمین می‌کند زمان تکمیل کارهایی که قبل از زمان شروع موردانتظار خرابی برنامه‌ریزی می‌شوند، نباید از زمان شروع موردانتظار خرابی بزرگ‌تر باشد. محدودیت (12) وجودنداشتن بیکاری عمدی را قبل از شروع خرابی موردانتظار بررسی می‌کند. محدودیت (13) تضمین می‌کند که فقط یک خرابی در طول افق برنامه‌ریزی اتفاق می‌افتد. محدودیت‌های (14) و (15) مقادیر حداکثر زودکرد و حداکثر دیرکرد موردانتظار کارها را محاسبه می‌کنند. محدودیت‌های (16) تا (20) مقادیر مرزی موردنیاز، نوع و علامت متغیرهای تصمیم مسئله را توصیف می‌کنند. با توجه به متغیرهای صفر و یک ، و ، مدل فوق یک مدل برنامه‌ریزی عدد صحیح خطی مختلط[xxvi] (MILP) است. برای صحت‌سنجی نهایی، این مدل با استفاده از نرم‌افزار گمز بر مسائل نمونه با ابعاد کوچک آزمایش و نتایج حل آن در مقایسه با نتایج شمارش کامل، تأیید شد. با توجه به سخت‌بودن مسئله و ناکارآمدبودن فرآیند مدل‌سازی ریاضی، ضرورت استفاده از روش‌های دیگر در حل این مسئله احساس می‌شود. برای محاسبۀ زمان تکمیل موردانتظار کارها، باید از مقادیر قطعی زمان‌های پردازش و آماده‌سازی و مقادیر موردانتظار شروع و طول خرابی، یعنی به‌ترتیب مقادیر و استفاده شود. 3-2- روش شاخه و کران در این بخش یک الگوریتم شاخه و کران[xxvii] (BB) جدید برای حل بهینۀ مسئله ارائه می‌شود. در این الگوریتم کارها از ابتدای توالی چیده می‌شوند و در هر توالی جزئی، هریک از کارهای باقی‌مانده به‌عنوان شاخۀ جدید به انتهای توالی افزوده می‌شود. ترتیب ورود کارها به درخت جست‌وجو براساس ترتیب غیرنزولی موعدهای تحویل[xxviii] (EDD) است و استراتژی جست‌وجو به‌صورت اولین عمق[xxix] است. در شکل 1 فرآیند شاخه‌زنی الگوریتم BB برای یک مسئله با چهار کار نشان داده شده است. در این شکل گره‌ها به‌ترتیب پیمایش درخت جست‌وجو شماره‌گذاری شده‌اند. در ادامه، فرآیند اجرای الگوریتم شاخه و کران و نحوۀ قطع شاخه‌ها تشریح می‌شود.
شکل 1- فرآیند شاخه‌زنی در الگوریتم BB Fig 1- Branching process in the BB algorithm قبل از شروع الگوریتم BB، یک حد بالا برای مسئله محاسبه و در هر شاخه، مقدار حد پایین توالی جزئی متناظر با آن شاخه محاسبه می‌شود. اگر در شاخه‌ای مقدار حد پایین بزرگ‌تر یا مساوی حد بالا بود، آن شاخه قطع می‌شود. همچنین در صورت رسیدن به یک توالی پذیرفتنی کامل، مقدار تابع هدف موردانتظار این توالی با حد بالای جاری مقایسه و در صورت نیاز، حد بالا به‌روزرسانی می‌شود. در ادامه حدود بالا و پایین و برخی اصول غلبه برای الگوریتم BB ارائه می‌شود. 3-2-1- حد بالا در این مقاله از یک الگوریتم ابتکاری جدید به نام تعویض جفتی مبتنی بر تپه‌نوردی[xxx] (PHC) به‌منظور به دست آوردن حد بالای رویۀ BB برای مسئلۀ استفاده می‌شود. این الگوریتم دارای دو فاز ساخت و بهبود است. در فاز ساخت براساس یک ویژگی مسئله، یک توالی اولیه ایجاد می‌شود و در فاز بهبود، براساس یک رویکرد حریصانه، توالی ایجادشده بهبود می‌یابد. در مرحلۀ ساخت توالی اولیه، کارهای با موعد تحویل کوچک‌تر در ابتدای توالی و براساس ترتیب EDD مرتب می‌شوند. این کار باعث کاهش میزان دیرکرد کارهای دیرکرددار می‌شود. همچنین کارهای با موعد تحویل بزرگ‌تر در انتهای توالی و براساس ترتیب غیرنزولی زمان‌های شناوری[xxxi] (MST) مرتب می‌شوند که زمان شناوری کار به‌صورت تعریف می‌شود؛ این کار نیز باعث کاهش میزان زودکرد کارهای زودکرددار می‌شود. در مرحلۀ بهبود توالی اولیه، با استفاده از یک رویۀ تعویض جفتی براساس الگوریتم تپه‌نوردی با تیزترین شیب، در جهت بهبود مقدار تابع هدف تلاش می‌شود. با توجه به اینکه رویۀ تپه‌نوردی یک رویکرد حریصانه است، در مرحلۀ بهبود ضمن تلاش در جهت کاهش مقدار موردانتظار تابع هدف، ساختار کلی توالی اولیه حفظ می‌شود. گام‌های الگوریتم PHC به‌صورت زیر است: الگوریتم PHC: شروع فاز ایجاد: توالی current را به‌صورت زیر ایجاد کنید: میانگین موعدهای تحویل کارها را محاسبه کنید و آن را بنامید؛ کارهای با موعد تحویل کوچک‌تر مساوی را در ابتدای توالی و براساس ترتیب EDD بچینید؛ کارهای با موعد تحویل بزرگ‌تر از را در انتهای توالی و براساس ترتیب MST بچینید. فاز بهبود: قرار دهید (M یک مقدار بزرگ است)؛ تا زمانی که تکرار کنید؛ قرار دهید ؛ به‌ازای 1 =i تا 1-n i= تکرار کنید؛ به‌ازای 1 +i j= تا j= n تکرار کنید؛ در توالی current دو کار i و j را جابه‌جا کنید و توالی حاصل را next بنامید؛ اگر ، آنگاه:
پایان اگر پایان تکرار پایان تکرار اگر آنگاه پایان تکرار توالی current را به‌عنوان جواب نهایی در نظر بگیرید. پایان 3-2-2- حد پایین در هر شاخه از درخت BB، توالی جزئی نشان‌دهندۀ توالی کارهای زمان‌بندی‌شده و مجموعۀ نشان‌دهندۀ مجموعۀ کارهای زمان‌بندی‌نشده در این شاخه است. توالی نشان‌دهندۀ ترتیب MST کارهای برنامه‌ریزی نشده است که زمان آماده‌سازی خانوادۀ کار برای هریک از آنها در نظر گرفته شده است. همچنین اگر زمان تکمیل موردانتظار آخرین کار توالی کوچک‌تر مساوی باشد، کارهای توالی بلافاصله بعد از زمان پایان موردانتظار خرابی چیده می‌شود؛ در غیر این صورت، کارهای این توالی بلافاصله بعد از توالی چیده می‌شوند. درنهایت هنگام چیدن کارها براساس ترتیب MST، برای محاسبۀ مقادیر شناوری، زمان آماده‌سازی خانوادۀ هر کار به زمان پردازش آن اضافه می‌شود. توالی ترتیب EDD کارهای باقی‌مانده با فرض انقطاع کار تعریف می‌شود. در این توالی فقط برای اولین کار مربوط به هریک از این خانواده‌ها که در توالی ظاهر می‌شود، زمان آماده‌سازی در نظر گرفته می‌شود. ذکر این نکته مهم است که اگر آخرین کار توالی کار ( و ) باشد، در صورتی که در مجموعۀ کارهای زمان‌بندی‌نشده کاری عضو خانوادۀ h وجود داشته باشد، در ترتیب برای هیچ‌یک از کارهای عضو خانوادۀ h زمان آماده‌سازی در نظر گرفته نمی‌شود. قضیۀ زیر نحوۀ محاسبۀ حد پایین در هر شاخه از درخت BB را بیان می‌کند. قضیۀ 1: در مسئلۀ حد پایین توالی جزئی به‌صورت زیر محاسبه می‌شود:
اثبات: اگر تابع هدف موردانتظار به‌تنهایی در نظر گرفته شود، واضح است با افزایش زمان‌های تکمیل موردانتظار، مقدار موردانتظار این معیار افزایش نمی‌یابد. همچنین اگر در مجموعۀ هر کار یک دستۀ مجزا در نظر گرفته شود که زمان آماده‌سازی خانوادۀ کار مربوط به خود را دارد، بیشترین حالت زمان تکمیل موردانتظار برای کارها در نظر گرفته شده است و ترتیب MST برای این کارها با لحاظ‌کردن زمان آماده‌سازی خانوادۀ هر کار در زمان پردازش کار، معیار را برای آنها کمینه می‌کند. از سوی دیگر اگر تنها معیار موردانتظار در نظر گرفته شود، با کاهش زمان‌های تکمیل موردانتظار کارها، مقدار موردانتظار تابع هدف افزایش نمی‌یابد. حال با توجه به اینکه آخرین کار توالی عضو خانوادۀ h است، با چیدن هریک از کارهای عضو مجموعۀ که عضو خانوادۀ h نباشند، حداقل یک‌بار زمان آماده‌سازی مربوط به خانوادۀ کار آنها باید در نظر گرفته شود؛ بنابراین در نظر گرفتن زمان آماده‌سازی برای اولین کاری که در ترتیب EDD کارهای زمان‌بندی‌نشده ظاهر می‌شود، معیار را برای آنها حداقل می‌کند. 3-2-3- اصول غلبه در این زیربخش دو اصل غلبه بیان می‌شود که می‌توانند فضای جست‌وجوی الگوریتم BB را کاهش دهند. در هر شاخه از الگوریتم BB، دو اصل غلبۀ 1 و 2 به‌ترتیب اجرا و به قطع برخی از شاخه‌ها منجر می‌شوند. زمان تکمیل موردانتظار توالی جزئی با نشان داده می‌شود و بیان‌کنندۀ زمان تکمیل موردانتظار آخرین کار در توالی جزئی است. اگر در فرآیند BB ابتدا کار ( و ) و سپس کار به انتهای توالی جزئی اضافه شوند، توالی حاصل به‌صورت نشان داده می‌شود. همچنین عبارت به این صورت تعریف می‌شود: اگر بعد از اتمام توالی خرابی موردانتظار ماشین شروع شود، یعنی کارهای و اولین کارهایی باشند که بعد از پایان خرابی موردانتظار ماشین پردازش می‌یابند یا اگر آخرین کار توالی عضو خانوادۀ k نباشد، آنگاه است. اما اگر آخرین کار توالی عضو خانوادۀ k باشد و کارهای و اولین کارهای زمان‌بندی‌شده بعد از دسترسی مجدد ماشین نباشند، آنگاه است. لم 1: اگر کارهای و در صورت اضافه‌شدن به انتهای توالی جزئی ، هر دو قبل از شروع خرابی موردانتظار ماشین و یا هر دو بعد از پایان خرابی موردانتظار ماشین پردازش یابند و روابط زیر برقرار باشد:
آنگاه رابطۀ زیر برقرار است:
اثبات: با توجه به رابطۀ (22) انتظار داریم هر دو کار و در توالی‌های و زودکرددار شوند، درنتیجه مقدار حداکثر دیرکرد موردانتظار این دو کار برابر صفر می‌شود و در مقدار موردانتظار توالی‌های جزئی مربوط اثرگذار نخواهند بود. از سوی دیگر با توجه به اینکه ترتیب MST معیار را حداقل می‌کند، با توجه به رابطۀ (23) چون در توالی دو کار و براساس ترتیب MST مرتب شده‌اند، مقدار حداکثر زودکرد موردانتظار مربوط به این دو کار در توالی از مقدار حداکثر زودکرد موردانتظار آنها در بیشتر نیست. نتیجۀ 1 (اصل غلبۀ 1): با توجه به لم 1، اگر در فرآیند جست‌وجوی BB در شاخۀ شرایط لم 1 برقرار باشد، می‌توان این شاخه را قطع کرد. لم 2: اگر کارهای و در صورت اضافه‌شدن به انتهای توالی جزئی ، هر دو قبل از شروع خرابی موردانتظار ماشین و یا هر دو بعد از پایان خرابی موردانتظار ماشین پردازش یابند و روابط زیر برقرار باشد:
آنگاه رابطۀ زیر برقرار است:
اثبات: با توجه به رابطۀ (25) انتظار داریم هر دو کار و در توالی‌های و دیرکرددار شوند، درنتیجه مقدار حداکثر زودکرد موردانتظار این دو کار برابر صفر می‌شود و در مقدار موردانتظار توالی‌های جزئی مربوط اثرگذار نخواهند بود. از سوی دیگر با توجه به اینکه ترتیب EDD معیار را حداقل می‌کند، با توجه به رابطۀ (26) چون در توالی دو کار و براساس ترتیب EDD مرتب شده‌اند، مقدار حداکثر دیرکرد موردانتظار مربوط به این دو کار در توالی از مقدار حداکثر دیرکرد موردانتظار آنها در بیشتر نیست. نتیجۀ 2 (اصل غلبۀ 2): با توجه به لم 2، اگر در فرآیند جست‌وجوی BB در شاخۀ شرایط لم 2 برقرار باشد، می‌توان این شاخه را قطع کرد.
4- مطالعۀ کاربردی به‌منظور ارزیابی عملکرد الگوریتم‌های ارائهشده، مجموعۀ گسترده‌ای از مسائل نمونه طراحی و با الگوریتم‌های ارائهشده حل شده‌اند. براساس نظر اسکالر[xxxii] (2007) برای طراحی مسائل نمونه، تعداد خانواده‌های کار و تعداد کارهای هر خانواده از مجموعه‌های و ، و ، و ، و ، و ، و و همچنین و انتخاب شده‌اند. زمان‌های پردازش به‌طور تصادفی از توزیع یکنواخت گسسته در بازۀ ایجاد شده‌اند. همچنین زمان‌های آماده‌سازی هر خانوادۀ کار به‌طور تصادفی از دو توزیع یکنواخت گسسته در بازه‌های [1,20] و [1,10] ایجاد شده‌اند. موعدهای تحویل نیز به‌طور تصادفی از توزیع یکنواخت گسسته در بازۀ ایجاد شده‌اند. در این روابط، ، R نشان‌دهندۀ پارامتر موعد تحویل و r عامل دیرکرد تعریف می‌شود. برای پارامترهای ، سه زوج مقداری (0.5,0.5)، (0.5,1) و (0.25,1) در نظر گرفته شده است. براساس اودونوان[xxxiii] و همکاران (1999)، فرض می‌شود زمان شروع خرابی دارای توزیع نمایی با میانگین است که در آن و است. پارامتر می‌تواند یکی از مقادیر 10، 5 و 3 را داشته باشد. همچنین فرض می‌شود طول خرابی دارای توزیع یکنواخت گسسته در بازۀ است. مقادیر از زوج مقادیر و انتخاب می‌شوند. براساس هر ترکیب از مقادیر مختلف پارامترها، سری‌های برای مسائل نمونۀ تولیدشده تعریف می‌شود که در آنها i ( ) نشان‌دهندۀ نوع خانوادۀ آماده‌سازی کارها، j ( ) نشان‌دهندۀ نوع موعد تحویل کارها، k ( ) نشان‌دهندۀ نوع زمان شروع خرابی و l ( ) مشخص‌کنندۀ نوع طول دورۀ خرابی است. در جدول 1 مقادیر اندیس‌های سری‌های تعریف شده است. به‌ازای هر ترکیب F و ، در هر سری 10 مسئلۀ نمونه تولید شده است. به این ترتیب تعداد کل مسائل نمونۀ تولیدی 2520 عدد است.
جدول 1- اندیس‌های سری Table 1- Series Sijkl indeces
برای حل هریک از مسائل توسط الگوریتم BB محدودیت زمانی 4000 ثانیه لحاظ شده است و نمونه‌هایی که الگوریتم BB در محدودۀ زمانی مدنظر قادر به حل آنها نبوده است، به‌عنوان مسائل حل‌نشده توسط BB در نظر گرفته می‌شوند. به‌منظور ارزیابی الگوریتم PHC از شاخص درصد انحراف Dev به‌صورت زیر استفاده شده است:
در این رابطه نشان‌دهندۀ مقدار تابع هدف توالی به‌دست‌آمده از اجرای الگوریتم PHC بر نمونۀ بررسی‌شده و نشان‌دهندۀ مقدار تابع هدف جواب بهینۀ نمونۀ بررسی‌شده است. 4-1- یافته‌ها الگوریتم‌های PHC و BB در زبان برنامه‌نویسی VC++ کدنویسی شدند و توسط یک پردازنده با مشخصات Intel CORE i7 2.7 GHz CPU 8 GB RAM بر مسائل نمونه اجرا شدند. در جدول 2 نتایج حل مسائل نمونه توسط الگوریتم‌های داده‌شده آمده است. در این جدول ستون «تعداد BB» نشان‌دهندۀ تعداد نمونه‌هایی است که در محدودۀ زمانی مشخص‌شده توسط الگوریتم BB به‌صورت بهینه حل شده‌اند. شایان ذکر است که تعداد کل مسائل نمونه در هر سری 70 عدد است. نتایج محاسباتی نشان می‌دهد الگوریتم BB توانسته است کلیۀ مسائل نمونه تا سقف 25 کار را در محدودۀ زمانی مشخص‌شده به‌صورت بهینه حل کند و مسائل حل‌نشده تنها مربوط به نمونه‌های با تعداد 30 کار است. ستون «زمان حل BB» در جدول 2 نشان‌دهندۀ میانگین زمان‌های حل مسائل نمونه توسط الگوریتم BB برحسب ثانیه است. به‌دلیل ناچیزبودن زمان‌های حل مسائل توسط الگوریتم PHC، مقادیر مربوط به آن در این جداول ذکر نشده است. ستون‌های «درصد قطع‌شده» در جدول 2 نیز میانگین درصد گره‌های قطع‌شده را به‌ترتیب توسط حد پایین، اصل غلبۀ 1 و اصل غلبۀ 2 نسبت‌به کل گره‌های طی‌شده در هر نمونه، در الگوریتم شاخه و کران نشان می‌دهد. ستون «انحراف PHC» در جدول 2 نشان‌دهندۀ میانگین درصد انحراف از جواب بهینه در الگوریتم ابتکاری PHC در هر نمونه است. جدول 2- نتایج حل مسئله Table 2- Result for the problem 1|Sf, brkdown| E[Emax+Tmax]
5- بحث از بررسی جدول 2 مشاهده می‌شود که سخت‌ترین مسائل ازنظر متوسط زمان حل BB و تعداد نمونۀ بهینۀ حل‌شده توسط BB مربوط به سری‌های با j= 1 است. این امر می‌تواند به این دلیل باشد که در این سری‌ها بازۀ موعد تحویل کوچک‌تر است و درنتیجه پراکندگی موعدهای تحویل کارها کمتر است. این خاصیت باعث می‌شود که در توالی‌های مختلف مقادیر دیرکرد و زودکرد کارها نزدیک به یکدیگر شود و بنابراین برای پیداکردن جواب بهینه، لازم است که فضای بیشتری از درخت جست‌وجو پیمایش شود. همچنین ساده‌ترین مسائل مربوط به سری‌های با j= 2 است. این امر می‌تواند به این دلیل باشد که در این سری‌ها، علاوه بر پراکندگی بیشتر موعدهای تحویل، تأثیر بیشتر عامل دیرکرد به دیرکرددارشدن کارها منجر می‌شود و بنابراین با تأثیرگذارتربودن یکی از معیارهای تابع هدف، مسائل ساده‌تر حل می‌شود. بررسی‌ها نشان می‌دهد با کاهش زمان آماده‌سازی خانوادۀ کارها، مسائل کمی سخت‌تر می‌شود. ممکن است این خاصیت به این دلیل باشد که با کاهش زمان‌های آماده‌سازی خانوادۀ کارها، احتمال دارد که با افزایش تعداد دسته‌های کاری تابع هدف موردانتظار مسئله بهبود یابد و این امر به پیچیده‌ترشدن فرآیند حل مسائل منجر می‌شود. همچنین افزایش یا کاهش زمان شروع و طول موردانتظار دورۀ خرابی، تأثیر معناداری را بر پیچیدگی محاسباتی مسائل نمونه نشان نمی‌دهد و این امر استواربودن رویه‌های حل ارائهشده را نسبت‌به مقادیر مختلف زمان شروع و طول خرابی نشان می‌دهد. نتایج جدول 2 نشان می‌دهد حد پایین رویۀ BB کارآیی بالایی را در قطع گره‌های پیموده‌شده داشته است و در بیشتر مسائل نمونه به قطع بیش از 80درصد گره‌های پیموده‌شده منجر شده است. همچنین در سری‌های مسائل، اصل غلبۀ 2 نسبت‌به اصل غلبۀ 1 عملکرد مناسب‌تری در قطع گره‌های طی‌شده در درخت BB داشته است. همچنین میانگین درصد انحراف الگوریتم ابتکاری PHC نسبت‌به جواب بهینه، در بیشتر مجموعه داده‌ها کمتر از 30درصد بوده است. در شکل‌های 2 تا 5، نمودار مقایسه‌ای میانگین زمان حل و تعداد مسائل بهینۀ حل‌شده توسط الگوریتم BB به تفکیک هریک از اندیس‌های i، j، k و l در سری نشان داده شده است.
شکل 2- نمودار میانگین زمان و تعداد نمونۀ حل‌شده توسط BB به‌ازای مقادیر مختلف i Fig 2- Average number and average computation time diagrams of instances solved by BB for values i
شکل 3- نمودار میانگین زمان و تعداد نمونۀ حل‌شده توسط BB به‌ازای مقادیر مختلف j Fig 3- Average number and average computation time diagrams of instances solved by BB for values j
شکل 4- نمودار میانگین زمان و تعداد نمونۀ حل‌شده توسط BB به‌ازای مقادیر مختلف k Fig 4- Average number and average computation time diagrams of instances solved by BB for values k
شکل 5- نمودار میانگین زمان و تعداد نمونۀ حل‌شده توسط BB به‌ازای مقادیر مختلف l Fig 5- Average number and average computation time diagrams of instances solved by BB for values l
6- نتیجه‌گیری در این مقاله با توجه به نیاز صنایع تولیدی، مسئلۀ زمان‌بندی تک‌ماشین با زمان‌های آماده‌سازی خانوادۀ کارها، خرابی تصادفی و تابع هدف مجموع حداکثر زودکرد و حداکثر دیرکرد موردانتظار بررسی شد. تاکنون مطالعه‌ای بر این مسئله مشاهده نشده است. برای مسئلۀ بررسی‌شده در این مقاله، یک مدل برنامه‌ریزی ریاضی توسعه داده و نشان داده شد به‌دلیل سخت‌بودن مسئله، مدل مربوطه در حل مسائل با ابعاد متوسط و بزرگ کارایی مناسبی ندارد. به همین دلیل برای حل بهینۀ مسئلۀ مدنظر، یک الگوریتم حل بهینۀ BB توسعه داده شد که اصول غلبه و یک حد پایین کارا دارد و از جواب به‌دست‌آمده از یک الگوریتم ابتکاری جدید به نام PHC به‌عنوان حد بالا استفاده می‌کند. به‌منظور ارزیابی الگوریتم‌های حل ارائهشده، مجموعۀ گسترده‌ای از مسائل نمونه شامل 36سری داده طراحی و با الگوریتم‌های معرفی‌شده حل شدند. نتایج حل مسائل نمونه نشان داد در نمونه‌های با اندازۀ کوچک و متوسط، الگوریتم BB قادر به حل 98% مسائل نمونه در محدودۀ زمانی مدنظر شده و حد پایین آن توانسته است در بیشتر مسائل نمونه بیش از 80درصد گره‌های پیموده‌شده را در درخت BB قطع کند. همچنین در بیشتر نمونه‌های حل‌شده به‌ازای هر زوج تعداد خانواده و تعداد کارهای هر خانواده، میانگین درصد انحراف از جواب بهینۀ الگوریتم PHC کمتر از 30% بوده است. با توجه به اینکه مسئلۀ بررسی‌شده در این مقاله کاملاً جدید است، در پژوهش‌های بعدی بر این مسئله، مسائل نمونه و الگوریتم‌های دقیق و ابتکاری ارائهشده در این مقاله می‌تواند مبنایی برای ارزیابی دیگر روش‌های حل ارائهشده برای این مسئله در نظر گرفته شود. برای انجام پژوهش‌های آتی، در نظر گرفتن دیگر حالت‌های مواجهه با خرابی ماشین مانند خرابی‌های مبتنی بر سناریو یا زمان‌بندی مجدد کارها با هدف حداقل‌سازی انحرافات برنامۀ واقعی از برنامۀ زمان‌بندی‌شده، حالت‌های با بیش از یک ماشین مانند ماشین‌های موازی، فلوشاپ و سیستم کارگاهی، دیگر توابع هدف مربوط به زمان‌بندی مانند حداکثر زمان تکمیل یا زمان تکمیل کل، همچنین توسعۀ دیگر الگوریتم‌های دقیق، ابتکاری یا فراابتکاری پیشنهاد می‌شود.
[i] Cheng [ii] Xiong [iii] Pei [iv] Fan [v] Tang [vi] Mönch [vii] Roob [viii] Li [ix] Kong [x] Emde [xi] Hinder [xii] Mason [xiii] Abdallah [xiv] Jang [xv] Shen [xvi] Zhu [xvii] Detti [xviii] Lu [xix] Goren [xx] Sabuncuoglu [xxi] Lee [xxii] Bruno [xxiii] Downey [xxiv] Gupta [xxv] Chantaravarapan [xxvi] Mixed Integer Linear Programming [xxvii] Branch and Bound [xxviii] Earliest Due Date [xxix] Back Tracking [xxx] Pairwise Hill Climbing [xxxi] Minimum Slack Time [xxxii] Schaller [xxxiii] O'Donovan | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Abdallah, K.S., Jang, J. (2017). Scheduling a single machine with job family setup times to minimize total tardiness. IEEE International Conference on Engineering, Technology and Innovation (ICE/ITMC), Funchal, Portugal, 665-672. 10.1109/ICE.2017.8279948
Amirkhani, F., Amiri, A., Sahraeian, R. (2017). A New Method Based on Simulation-Optimization Approach to Find Optimal Solution in Dynamic Job-shop Scheduling Problem with Breakdown and Rework. Journal of Production and Operations Management, 7th year, Vol. 13, 157-174.
Bruno, J., Downey, P. (1978). Complexity of task sequencing with deadlines, set-up times and changeover costs. SIAM Journal on Computing, Vol. 7, Iss. 4. https://doi.org/10.1137/0207031
Cheng, B.Y., Leung, J. Y.T., Li, k. (2017). Integrated scheduling on a batch machine to minimize production, inventory and distribution costs. European Journal of Operational Research, 258(1), 104-112. https://doi.org/10.1016/j.ejor.2016.09.009
Detti, P., Nicosia, G., Pacifici, A., Manrique, G.Z. (2019). Robust single machine scheduling with a flexible maintenance activity. Computers and Operations Research, 107, 19-31. https://doi.org/10.1016/j.cor.2019.03.001
Emde, S., Polten, L., Gendreau, M. (2020). Logic-based benders decomposition for scheduling a batching machine. Computers & Operations Research, 113, 1-12. https://doi.org/10.1016/j.cor.2019.104777
Fan, W., Pei, J.,Liu, X., Pardalos, P.M.,Kong, M. (2017). Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning. Journal of Global Optimization, 71, 147–163. https://doi.org/10.1007/s10898-017-0536-7
Goren, S., Sabuncuoglu, I. (2009). Optimization of schedule robustness and stability under random machine breakdowns and processing time variability. IIE Transactions, 42(3), 203-220. https://doi.org/10.1080/07408170903171035
Gupta, J. N.d., Chantaravarapan, S. (2008). Single machine group scheduling with family setups to minimize total tardiness. International Journal of Production Research, Volume 46, Issue 6, 1707-1722. 10.1080/00207540601009976
Haleh, H., Maghsoudlou, H., Hadipour, H., Nabovati, H. (2017). Scheduling single machine with random breakdown and preemptive jobs. Journal of Industrial and Production Engineering, 34(4), 1-11. https://doi.org/10.1080/21681015.2017.1292961
Hashemi, S.N., Kashan, A.H. (2020). A branch and bound algorithm equipped with tighter lower bound values for makespan minimization on a batch processing machine. Production and Operations Management, Vol. 10, Issue 2, No. 19, 181-201.
Hinder, O., Mason, A. G. (2017). A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness. European Journal of Operational Research, 262(2), 411-423. https://doi.org/10.1016/j.ejor.2017.03.003
Kong, M., Liu, X., Pei, J., Zhou, Z., Pardalos, P.M. (2020). Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine. Optimization Letters, 14, 857–871. https://doi.org/10.1007/s11590-019-01389-x
Lee, C.Y. (1996). Machine scheduling with an availability constraint. J Glob Optim, 9, 395–416. https://doi.org/10.1007/BF00121681
Li, X., Li, Y., Huang, Y. (2019). Heuristics and lower bound for minimizing maximum lateness on a batch processing machine with incompatible job families. Computers and Operations Research, (106), 91–101. https://doi.org/10.1016/j.cor.2019.02.012
Lu, S., Liu, X., Pei, J., My T.T., My, M.Pardalos, P. (2018). A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Applied Soft Computing, 66, 168-182. https://doi.org/10.1016/j.asoc.2018.02.018
Mönch, L., Roob, S. (2017). A matheuristic framework for batch machine scheduling problems with incompatible job families and regular sum objective. Applied Soft Computing, 68, 835-846. https://doi.org/10.1016/j.asoc.2017.10.028
O'Donovan, R., Uzsoy, R., Mckay, K. N. (1999). Predictable scheduling of a single machine with breakdowns and sensitive jobs. International Journal of Production Research, 37(18), 4217-4233. https://doi.org/10.1080/002075499189745
Pei, J., Cheng, B., X Liu, X., Pardalos, P.M., Kong, M. (2019). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, 272, 217–241. https://doi.org/10.1007/s10479-017-2481-8
Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S. (2017a). Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, 249, 175–195. https://doi.org/10.1007/s10479-015-1824-6
Pei, J., Liu, X., Pardalos, P.M., Li, K., Fan, W., Migdalas, A. (2017c). Single-machine serial-batching scheduling with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. Optimization Letters, 11, 1257–1271. https://doi.org/10.1007/s11590-016-1074-9
Pei, J., Liu, X., Pardalos, P.M., Migdalas, A., Yang, S. (2017b). Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine. Journal of Global Optimization, 67, 251–262. 10.1007/s10898-015-0320-5
Schaller, J. (2007). Scheduling on a single machine with family setups to minimize total tardiness. International Journal of Production Economics, 105(2), 329-344.
Shen, J., Zhu, K. (2018). An uncertain single machine scheduling problem with periodic maintenance. Knowledge-Based Systems, 144, 32-41. https://doi.org/10.1016/j.knosys.2017.12.021
Tang, L., Zhao, X., Liu, J., Leung, J.Y.T (2017). Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 63(2), 401-411. https://doi.org/10.1016/j.ejor.2017.05.019
Xiong, X., Wang, D., Cheng, T.C. E., Wu, C., Yi, Y. (2017). Single-machine scheduling and common due date assignment with potential machine disruption. International Journal of Production Research, 56(3), 1345-1360. https://doi.org/10.1080/00207543.2017.1346317 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
آمار تعداد مشاهده مقاله: 642 تعداد دریافت فایل اصل مقاله: 318 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||