نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه پیام نور، تهران، ایران
2 گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه الزهرا، تهران، ایران
چکیده
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
نویسندگان [English]
Purpose: Scheduling of batch production and machine disruption are the two main challenges in manufacturing organizations. Due to the complexity of production processes, many industries try to group jobs according to family criteria and use a common setup time to process every family. Also, machine breakdown is an influential factor in the planning of production systems. In this paper, the problem of scheduling a single machine with family setup times and breakdowns is studied. It is assumed that there is a breakdown with an uncertain start time and duration based on the specified probability distribution functions during the planning horizon. The objective function of this problem is the sum of the expected maximum earliness and maximum tardiness.
Design/methodology/approach: For the problem under study, a new mixed integer linear programming model has been developed. Due to the NP-hardness of the problem, a new branch and bound algorithm with the dominance rules and an efficient lower bound is presented for its optimal solving, which uses a new heuristic approach to achieve the upper bound.
Findings: To evaluate the performance of the introduced algorithms, 2520 instances were designed and solved with the presented algorithms. The computational results indicated that 98% of the instances were optimally solved in the specified time limitation by the branch and bound algorithm, and the average percentage of deviation from the optimal solution in the proposed heuristic approach was less than 30%. The results demonstrated the efficiency of the proposed algorithms.
Research limitations/implications: Considering the newness of the problem investigated in this paper, the proposed instances and algorithms can be used as a basis for evaluating other solution methodologies in future research studies. Also, considering other modes of machine failures such as scenario-based failures or re-scheduling the jobs to minimize the deviations of the actual schedule from the planned program, situations with more than one machine such as parallel machines, flow shops, and job shops, other objective functions related to scheduling such as maximum completion time or total completion time, as well as the development of other exact, heuristic or meta-heuristic algorithms are suggested as subjects for future study.
Practical implications: The problem studied in this paper can be attractive and practical for manufacturing organizations. Industries such as automotive, ship and aircraft manufacturing, steel, telecommunication power supply manufacturing, electronic, computer processors, and all industries and systems that somehow deal with the batch production process and unexpected machine breakdowns, can benefit from the results of this research.
Social implications: Because in this study, the starting and finishing times of machine breakdowns were predicted, by applying the results of this research, the production of defective products will be prevented when the machine breaks down, and this leads to the reduction of waste in the environment. Also, according to the objective function defined in the problem investigated in this article, the implication of the results of this research in production environments leads to the reduction of earliness and tardiness costs, which in turn increases the work efficiency of human resources and as a result, increases the job satisfaction.
Originality/value: It seems no study has been conducted on the single machine scheduling problem with batch production, random breakdown, and the objective function of minimizing the sum of the expected maximum earliness and maximum tardiness of the jobs. Particularly, innovations of this paper are threefold: i) a new mixed integer linear programming model was developed for the problem; ii) a novel heuristic approach was proposed to solve the problem, based on hill climbing (PHC); and iii) a new branch and bound algorithm with the dominance rules and an efficient lower bound was presented to solve the problem optimally, which used the PHC heuristic approach to achieve the upper bound.
کلیدواژه‌ها [English]
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)، تابع هدف استوار مجموع موردانتظار حداکثر زودکرد و حداکثر دیرکرد برای این مسئله در نظر گرفته شده است که به‌صورت زیر تعریف می‌شود:
|
(1) |
|
که در آن و مقادیر موردانتظار حداکثر زودکرد و حداکثر دیرکردند و به‌صورت زیر محاسبه می‌شوند:
|
(2) |
|
|
(3) |
|
در این روابط، نشان‌دهندۀ زمان تکمیل کار i ( ) در توالی است و با توجه به تصادفی‌بودن زمان شروع و طول خرابی، مقدار آن نیز تصادفی است. این مسئله به‌صورت نشان داده می‌شود. در این مسئله با توجه به هزینه‌های بالای بیکار نگه داشتن عمدی ماشین، فرض می‌شود بیکاری عمدی مجاز نیست. مسئلۀ بررسی‌شده کاملاً جدید است و تاکنون در پژوهش‌های گذشته مطالعه‌ای بر آن مشاهده نشده است.
با توجه به اینکه مسئلۀ تک‌ماشین با یک دورۀ عدم‌دسترسی و تابع هدف حداکثر مغایرت ( )، NP-hard است (لی[xxi]، 1996)، همچنین مسئلۀ تک‌ماشین با خانوادۀ آماده‌سازی و تابع هدف حداکثر مغایرت ( ) نیز NP-hard است (برونو[xxii] و دونی[xxiii]، 1978)، بنابراین می‌توان گفت مسئله به‌شدت NP-hard است.
3- روش‌شناسی پژوهش
با توجه به جدیدبودن مسئله ، کلیۀ روش‌های حل ارائهشده برای این مسئله در این مقاله نیز کاملاً جدید و نوآورانه است. در این بخش رویکردهای حل این مسئله بررسی می‌شود. در ابتدا با توجه به مبانی نظری و مفروضات مطرح‌شده در بخش دوم، مدل ریاضی مسئله توسعه داده می‌شود، سپس برای حل بهینۀ مسئله در ابعاد گسترده‌تر، یک الگوریتم بهینۀ شاخه و کران و یک الگوریتم ابتکاری ارائه می‌شود.
3-1- مدل ریاضی مسئله
به‌منظور توسعۀ مدل برنامۀ ریاضی مسئله، مقدار متغیر تصمیم ، یک تعریف می‌شود اگر کار در موقعیت k ام ( ) توالی پردازش یابد و در غیر این صورت مقدار آن صفر تعریف می‌شود. همچنین اگر کار زمان‌بندی‌شده در موقعیت k ام توالی به آماده‌سازی نیاز داشته باشد، مقدار متغیر تصمیم یک تعریف و در غیر این صورت صفر تعریف می‌شود. درنهایت اگر کار زمان‌بندی‌شده در موقعیت k ام قبل از شروع خرابی موردانتظار زمان‌بندی شود، مقدار متغیر تصمیم برابر صفر تعریف می‌شود و اگر کار مربوط بعد از پایان خرابی پیش‌بینی‌شده زمان‌بندی شود، مقدار این متغیر یک تعریف می‌شود. مدل برنامه‌ریزی ریاضی مسئله به‌صورت زیر است:
|
(4) |
s. t. |
|
(5) |
، |
|
(6) |
، ، |
|
(7) |
، |
|
(8) |
، ، |
|
(9) |
، |
|
(10) |
، |
|
(11) |
، |
|
(12) |
، |
|
(13) |
|
|
(14) |
، |
|
(15) |
، |
|
(16) |
|
|
(17) |
|
|
(18) |
، ، ، |
|
(19) |
|
|
(20) |
|
با توجه به جدیدبودن ماهیت مسئلۀ بررسی‌شده و در نظر گرفتن هم‌زمان مفروضات تولید دسته‌ای و خرابی تصادفی در آن، مدل ارائهشده برای مسئلۀ مدنظر نیز جدید است. در این مدل روابط (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: در مسئلۀ حد پایین توالی جزئی به‌صورت زیر محاسبه می‌شود:
|
(21) |
|
اثبات: اگر تابع هدف موردانتظار به‌تنهایی در نظر گرفته شود، واضح است با افزایش زمان‌های تکمیل موردانتظار، مقدار موردانتظار این معیار افزایش نمی‌یابد. همچنین اگر در مجموعۀ هر کار یک دستۀ مجزا در نظر گرفته شود که زمان آماده‌سازی خانوادۀ کار مربوط به خود را دارد، بیشترین حالت زمان تکمیل موردانتظار برای کارها در نظر گرفته شده است و ترتیب MST برای این کارها با لحاظ‌کردن زمان آماده‌سازی خانوادۀ هر کار در زمان پردازش کار، معیار را برای آنها کمینه می‌کند.
از سوی دیگر اگر تنها معیار موردانتظار در نظر گرفته شود، با کاهش زمان‌های تکمیل موردانتظار کارها، مقدار موردانتظار تابع هدف افزایش نمی‌یابد. حال با توجه به اینکه آخرین کار توالی عضو خانوادۀ h است، با چیدن هریک از کارهای عضو مجموعۀ که عضو خانوادۀ h نباشند، حداقل یک‌بار زمان آماده‌سازی مربوط به خانوادۀ کار آنها باید در نظر گرفته شود؛ بنابراین در نظر گرفتن زمان آماده‌سازی برای اولین کاری که در ترتیب EDD کارهای زمان‌بندی‌نشده ظاهر می‌شود، معیار را برای آنها حداقل می‌کند.
3-2-3- اصول غلبه
در این زیربخش دو اصل غلبه بیان می‌شود که می‌توانند فضای جست‌وجوی الگوریتم BB را کاهش دهند. در هر شاخه از الگوریتم BB، دو اصل غلبۀ 1 و 2 به‌ترتیب اجرا و به قطع برخی از شاخه‌ها منجر می‌شوند.
زمان تکمیل موردانتظار توالی جزئی با نشان داده می‌شود و بیان‌کنندۀ زمان تکمیل موردانتظار آخرین کار در توالی جزئی است. اگر در فرآیند BB ابتدا کار ( و ) و سپس کار به انتهای توالی جزئی اضافه شوند، توالی حاصل به‌صورت نشان داده می‌شود. همچنین عبارت به این صورت تعریف می‌شود: اگر بعد از اتمام توالی خرابی موردانتظار ماشین شروع شود، یعنی کارهای و اولین کارهایی باشند که بعد از پایان خرابی موردانتظار ماشین پردازش می‌یابند یا اگر آخرین کار توالی عضو خانوادۀ k نباشد، آنگاه است. اما اگر آخرین کار توالی عضو خانوادۀ k باشد و کارهای و اولین کارهای زمان‌بندی‌شده بعد از دسترسی مجدد ماشین نباشند، آنگاه است.
لم 1: اگر کارهای و در صورت اضافه‌شدن به انتهای توالی جزئی ، هر دو قبل از شروع خرابی موردانتظار ماشین و یا هر دو بعد از پایان خرابی موردانتظار ماشین پردازش یابند و روابط زیر برقرار باشد:
|
(22) |
|
|
(23) |
|
آنگاه رابطۀ زیر برقرار است:
|
(24) |
|
اثبات: با توجه به رابطۀ (22) انتظار داریم هر دو کار و در توالی‌های و زودکرددار شوند، درنتیجه مقدار حداکثر دیرکرد موردانتظار این دو کار برابر صفر می‌شود و در مقدار موردانتظار توالی‌های جزئی مربوط اثرگذار نخواهند بود. از سوی دیگر با توجه به اینکه ترتیب MST معیار را حداقل می‌کند، با توجه به رابطۀ (23) چون در توالی دو کار و براساس ترتیب MST مرتب شده‌اند، مقدار حداکثر زودکرد موردانتظار مربوط به این دو کار در توالی از مقدار حداکثر زودکرد موردانتظار آنها در بیشتر نیست.
نتیجۀ 1 (اصل غلبۀ 1): با توجه به لم 1، اگر در فرآیند جست‌وجوی BB در شاخۀ شرایط لم 1 برقرار باشد، می‌توان این شاخه را قطع کرد.
لم 2: اگر کارهای و در صورت اضافه‌شدن به انتهای توالی جزئی ، هر دو قبل از شروع خرابی موردانتظار ماشین و یا هر دو بعد از پایان خرابی موردانتظار ماشین پردازش یابند و روابط زیر برقرار باشد:
|
(25) |
|
|
(26) |
|
آنگاه رابطۀ زیر برقرار است:
|
(27) |
|
اثبات: با توجه به رابطۀ (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
|
اندیس |
i |
j |
k |
l |
|
مقدار 1 |
|
|
|
|
|
مقدار 2 |
|
|
|
|
|
مقدار 3 |
-- |
|
|
-- |
برای حل هریک از مسائل توسط الگوریتم BB محدودیت زمانی 4000 ثانیه لحاظ شده است و نمونه‌هایی که الگوریتم BB در محدودۀ زمانی مدنظر قادر به حل آنها نبوده است، به‌عنوان مسائل حل‌نشده توسط BB در نظر گرفته می‌شوند. به‌منظور ارزیابی الگوریتم PHC از شاخص درصد انحراف Dev به‌صورت زیر استفاده شده است:
|
(28) |
|
در این رابطه نشان‌دهندۀ مقدار تابع هدف توالی به‌دست‌آمده از اجرای الگوریتم 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]
|
انحراف |
|
درصد قطع‌شده |
|
زمان |
|
تعداد |
|
سری |
|
انحراف |
|
درصد قطع‌شده |
|
زمان |
|
تعداد |
|
سری |
||||
|
PHC |
|
D2 |
D1 |
LB |
|
BB |
|
BB |
|
|
|
PHC |
|
D2 |
D1 |
LB |
|
BB |
|
BB |
|
|
|
23/15 |
|
11/3 |
02/0 |
48/83 |
|
15/170 |
|
67 |
|
S2111 |
|
75/21 |
|
98/3 |
01/0 |
93/82 |
|
47/122 |
|
66 |
|
S1111 |
|
22/13 |
|
23/3 |
02/0 |
49/83 |
|
89/125 |
|
65 |
|
S2112 |
|
08/20 |
|
09/4 |
02/0 |
95/82 |
|
90/60 |
|
66 |
|
S1112 |
|
88/14 |
|
26/3 |
02/0 |
05/83 |
|
45/195 |
|
67 |
|
S2121 |
|
30/22 |
|
68/3 |
01/0 |
92/83 |
|
21/124 |
|
67 |
|
S1121 |
|
79/15 |
|
71/3 |
02/0 |
73/82 |
|
59/148 |
|
66 |
|
S2122 |
|
59/20 |
|
17/4 |
01/0 |
77/83 |
|
20/93 |
|
65 |
|
S1122 |
|
21/15 |
|
11/3 |
01/0 |
36/84 |
|
45/235 |
|
68 |
|
S2131 |
|
85/19 |
|
82/3 |
01/0 |
56/83 |
|
21/109 |
|
67 |
|
S1131 |
|
03/13 |
|
00/4 |
01/0 |
89/83 |
|
18/198 |
|
67 |
|
S2132 |
|
84/17 |
|
77/3 |
01/0 |
93/83 |
|
04/135 |
|
70 |
|
S1132 |
|
66/11 |
|
17/1 |
01/0 |
10/89 |
|
00/3 |
|
70 |
|
S2211 |
|
34/16 |
|
61/1 |
01/0 |
64/87 |
|
63/2 |
|
70 |
|
S1211 |
|
81/11 |
|
29/1 |
01/0 |
15/89 |
|
77/5 |
|
70 |
|
S2212 |
|
14/15 |
|
91/1 |
01/0 |
57/87 |
|
03/4 |
|
70 |
|
S1212 |
|
89/10 |
|
09/1 |
01/0 |
18/88 |
|
55/1 |
|
70 |
|
S2221 |
|
41/14 |
|
62/1 |
01/0 |
05/88 |
|
42/1 |
|
70 |
|
S1221 |
|
13/10 |
|
31/1 |
01/0 |
56/88 |
|
44/1 |
|
70 |
|
S2222 |
|
54/14 |
|
99/1 |
01/0 |
67/87 |
|
02/2 |
|
70 |
|
S1222 |
|
51/9 |
|
15/1 |
01/0 |
98/88 |
|
03/2 |
|
70 |
|
S2231 |
|
79/14 |
|
63/1 |
01/0 |
75/87 |
|
90/0 |
|
70 |
|
S1231 |
|
90/9 |
|
45/1 |
01/0 |
64/88 |
|
18/5 |
|
70 |
|
S2232 |
|
52/15 |
|
03/2 |
01/0 |
56/87 |
|
07/2 |
|
70 |
|
S1232 |
|
47/9 |
|
70/0 |
01/0 |
62/89 |
|
66/1 |
|
70 |
|
S2311 |
|
85/15 |
|
14/1 |
01/0 |
72/87 |
|
01/2 |
|
70 |
|
S1311 |
|
47/9 |
|
92/0 |
01/0 |
92/88 |
|
71/2 |
|
70 |
|
S2312 |
|
10/15 |
|
35/1 |
01/0 |
37/87 |
|
36/3 |
|
70 |
|
S1312 |
|
95/9 |
|
77/0 |
01/0 |
53/88 |
|
61/1 |
|
70 |
|
S2321 |
|
07/16 |
|
29/1 |
01/0 |
38/87 |
|
47/9 |
|
70 |
|
S1321 |
|
11/10 |
|
90/0 |
01/0 |
27/88 |
|
30/1 |
|
70 |
|
S2322 |
|
54/17 |
|
46/1 |
01/0 |
08/87 |
|
20/2 |
|
70 |
|
S1322 |
|
75/9 |
|
69/0 |
01/0 |
63/89 |
|
94/3 |
|
70 |
|
S2331 |
|
75/16 |
|
32/1 |
01/0 |
61/87 |
|
44/9 |
|
70 |
|
S1331 |
|
17/12 |
|
75/0 |
01/0 |
90/88 |
|
77/26 |
|
70 |
|
S2332 |
|
84/16 |
|
52/1 |
01/0 |
15/87 |
|
69/9 |
|
70 |
|
S1332 |
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
)