مشکل زمانبندی فروشگاه کار سخت: مدل های ریاضی، الگوریتم های دقیق و اکتشافی

Elsevier
سال انتشار :
2016
تعداد صفحات مقاله انگلیسی :
10
نشریه :
الزویر
تعداد رفرنس ها :
21
نوع مقاله :
مقاله ISI
کراس مارک :
Crossmark
keywords :
Job shop scheduling Robustness index Disruption Branch and Bound Particle swarm optimization
کلمات کلیدی :
برنامه زمانبندی کار، شاخص قابلیت اطمینان، اخلال انشعابی و کراندار ، بهینه سازی ذرات
عنوان فارسی :

مشکل زمانبندی فروشگاه کار سخت: مدل های ریاضی، الگوریتم های دقیق و اکتشافی

عنوان انگلیسی :

Robust job shop scheduling problem: Mathematical models, exact and heuristic algorithms

ژورنال :
Expert Systems with Applications
لینک مقاله :
http://www.sciencedirect.com/science/article/pii/S0957417416300185
آدرس DOI :
https://doi.org/10.1016/j.eswa.2016.01.054
وضعیت ترجمه :
انجام نشده.

سال انتشار : 2016

تعداد صفحات مقاله انگلیسی : 9

نشریه : الزویر

تعداد رفرنس ها : 21

نوع مقاله : مقاله ISI

کلمات کلیدی انگلیسی : Job shop scheduling Robustness index Disruption Branch and Bound Particle swarm optimization

کلمات کلیدی : برنامه زمانبندی کار، شاخص قابلیت اطمینان، اخلال انشعابی و کراندار ، بهینه سازی ذرات

عنوان فارسی : مشکل زمانبندی فروشگاه کار سخت: مدل های ریاضی، الگوریتم های دقیق و اکتشافی

عنوان انگلیسی : Robust job shop scheduling problem: Mathematical models, exact and heuristic algorithms

لینک مقاله : http://www.sciencedirect.com/science/article/pii/S0957417416300185



چکیده انگلیسی
Job shop scheduling problem is very important one in real application of many kind of industries. In the real world applications, there exist many different kinds of disruptions with different sizes. In this situation, beyond the optimality of the final solution, its ability to absorb disruptions is vital, so that the final solution remains feasible in the case of occurring predicted disruptions. In this paper a robust job shop scheduling problem under disruptions is considered. It is intended to generate robust schedules which are able to absorb a predefined range of disruptions. For this reason, two robustness indices are proposed and the related formulas for computing the required buffer times to reach the desired robustness level are proposed. For this purpose, four methods are proposed to solve the variant defined robust job shop scheduling problem, including (1) a mathematical model, (2) a Branch and Bound algorithm, (3) a beam search algorithm, and (4) a meta-heuristic algorithm based on the particle swarm optimization (PSO) method. The first and second methods result in optimum solution. As the size of the problem increases, the required time to find the optimum solutions raises, so that no solutions can be achieved in rational amount of time, e.g. one hour. Therefore, the third and fourth methods are proposed to find good solutions even for large-scale problem in a limited amount of time. Finally, the algorithms are compared using some randomly generated instances. The results show that each algorithm can outperform the others in different conditions.

چکیده فارسی
مسائل مربوط به برنامه زمانبندی کار در بسیاری از صنایع بسیار مهم است. در برنامه های دنیای واقعی، انواع مختلف اختلالات با اندازه های مختلف وجود دارد. در این وضعیت، فراتر از بهینه بودن راه حل نهایی، توانایی آن در جذب اختلالات حیاتی است، به طوری که راه حل نهایی در صورت وقوع اختلالات پیش بینی شده امکان پذیر است. در این مقاله یک مسئله برنامه ریزی شغلی در معرض اختلال در نظر گرفته شده است. این در نظر گرفته شده برای تولید برنامه های قوی است که قادر به جذب طیف از تعریف از اختلالات از پیش تعریف شده است. به همين دليل، دو شاخص اطمينان پيشنهاد شده و فرمول هاي مربوطه براي محاسبه بارهاي مورد نياز براي رسيدن به سطح مقاومتي مورد نظر پيشنهاد مي شود. برای این منظور، چهار روش برای حل مسئله برنامه ریزی دقیق کار فروشگاه، عبارتند از (1) یک مدل ریاضی، (2) یک الگوریتم انشعابی و کراندار و (3) یک الگوریتم جستجوی شعاع ، و (4) یک الگوریتم متا اکتشافی بر اساس روش بهینه سازی ذرات (PSO). روش های اول و دوم باعث بهینه سازی می شوند. با افزایش اندازه مشکل، زمان لازم برای یافتن راه حل های بهینه، افزایش می یابد، به طوری که در زمان منطقی هیچ وقت راه حلی به دست نمی آید، مثلا یک ساعت. بنابراین، روش های سوم و چهارم برای یافتن راه حل های خوب حتی برای مشکل بزرگ در یک زمان محدود پیشنهاد می شود. در نهایت، الگوریتم ها با استفاده از برخی از نمونه های تصادفی تولید شده مقایسه می شوند. نتایج نشان می دهد که هر الگوریتم می تواند دیگران را در شرایط مختلف بهتر کند.

موضوعات مقاله