دانلود مقاله ISI انگلیسی شماره 81063 + ترجمه فارسی
ترجمه فارسی عنوان مقاله

مدل های برنامه نویسی عدد صحیح مختلط برای زمانبندی فروشگاه کار: یک تجزیه و تحلیل محاسباتی

عنوان انگلیسی
Mixed Integer Programming models for job shop scheduling: A computational analysis
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی ترجمه فارسی
81063 2016 9 صفحه PDF 18 صفحه WORD
دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
تولید محتوا برای سایت شما
پایگاه ISIArticles آمادگی دارد با همکاری مجموعه «شهر محتوا» با بهره گیری از منابع معتبر علمی، برای کتاب، سایت، وبلاگ، نشریه و سایر رسانه های شما، به زبان فارسی «تولید محتوا» نماید.
  • تولید محتوا با مقالات ISI برای سایت یا وبلاگ شما
  • تولید محتوا با مقالات ISI برای کتاب شما
  • تولید محتوا با مقالات ISI برای نشریه یا رسانه شما
  • و...

پیشنهاد می کنیم کیفیت محتوای سایت خود را با استفاده از منابع علمی، افزایش دهید.

سفارش تولید محتوا کد تخفیف 10 درصدی: isiArticles
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Operations Research, Volume 73, September 2016, Pages 165–173

فهرست مطالب ترجمه فارسی
چکیده 

لغات کلیدی

1. مقدمه 

2. سابقه 

2.1. تعریف مسئله 

شکل 1. مسئله ی زمانبندی فروشگاه کار. سه کار J1، J2، J3 در سه ماشین M1، M2 و M3 زمانبندی شده اند

2.2. مرور نوشته ها

3. مدل های MIP

3.1. مدل گسسته 

شکل 2. مدل گسسته

3.2. مدل گسسته ی لیائو

3.3. مدل شاخص زمانی 

شکل 3. مدل شاخص زمانی.

3.4. مدل مبتنی بر ترتیب بندی 

4. آزمایش ها و مباحث 

شکل 4. مدل مبتنی بر رتبه

جدول 1. مقایسه ی مدل های MIP برای JSP .  و  به ترتیب نشان دهنده ی تعداد ماشین ها، تعداد کار ها و تعداد کل نقطه های زمانی می باشند. 

4.1. نمونه های مسئله 

4.2. مقایسه ی مدل های MIP 

جدول 2. مقایسه ی مدل های MIP برای سه حل کننده ی مورد استفاده. اعداد برجسته بهترین

شکل 5. عملکرد MRE با گذشت زمان برای مدل های گسسته ی MIP با استفاده از CPLEX. 

(a) مسائل 15 x 15، (b) ta01 – ta10

 شکل 6. عملکرد MRE با گذشت زمان برای مدل های گسسته ی MIP با استفاده از SCIP

(a) مسائل 15 x 15، (b) ta01 – ta10

4.3. مقایسه ی نرم افزارهای مختلف بهینه سازی MIP 

4.4. مقایسه ی محدودیت های گسسته 

4.5. چند ریسگی و تنظیم پارامتر 

جدول 3. مقایسه ی فرمول های گسسته با استفاده از محدودیت های شاخص (با استفاده از CPLEX). اعداد برجسته بهترین فرمول را برای هر حل کننده ی مربوط به اندازه ی مسئله ی داده شده نشان می دهند. علامت – بدین معنی است که هیچ یک از 10 نمونه مسئله در کمتر از 3600 s به بهینگی حل نشدند. 

 جدول 4. مقایسه ی بهترین مدل MIP با چندریسگی و تنظیم پارامتر (با استفاده از CPLEX) و مدل CP. اعداد برجسته بهترین فرمول را برای هر حل کننده ی مربوط به اندازه ی مسئله ی داده شده نشان می دهند. علامت – بدین معنی است که هیچ یک از 10 نمونه مسئله در کمتر از 3600 s به بهینگی حل نشدند. 

4.6. مقایسه ی MIP و CP

4.7. مقایسه با آخرین تکنولوژی ها 

شکل 7. عملکرد MRE مدل های MIP، CP و iSTS-SGS با گذشت زمان. توجه داشته باشید که برای مسائل ta11-ta20، ابزار تنظیم تنظیمات پارامتری متفاوت تر از پیش فرض پیدا نکرده است. در نتیجه ما منحنی را برای تنظیم چندگانه طرح ریزی نکرده ایم، (a) مسائل 20 x 20، (b) ta11-ta20. 

5. نتیجه گیری 

ضمیمه ی A. مدل CP
ترجمه کلمات کلیدی
برنامه ریزی فروشگاه کار؛ برنامه ریزی عدد صحیح مختلط؛ برنامه نویسی محدودیت
کلمات کلیدی انگلیسی
Job shop scheduling; Mixed Integer Programming; Constraint programming
ترجمه چکیده
در نوشته های صنعتی و هم در نوشته های تحقیقاتی، برنامه نویسی عدد صحیح مختلف (MIP) اغلب رویکرد پیش فرض برای حل مسائل زمانبندی می باشد. در این مقاله چهار فرمول MIP را برای مسئله ی سنتی زمانبندی فروشگاه کار (JSP) ارائه داده و ارزیابی می کنیم. در حالی که فرمول های MIP برای JSP از دهه ی 1960 پدید آمده اند، به نظر می رسد که مطالعات محاسباتی جامع از آن زمان اجرا نشده اند. به خاطر بهبود های چشمگیر در تکنولوژی MIP در سال های اخیر، مقایسه ی مدل های استاندارد JSP با استفاده از نرم افزار بهینه سازی مدرن مطلوب می باشد. ما با استفاده از CPLEX، GUROBI و SCIP یک مطالعه ی کاملا تجربی روی چهار مدل MIP انجام داده و بر روی تعداد نمونه هایی که می توانند ثابت شوند که بهینه هستند و کیفیت راه حل با گذشت زمان، تمرکز می کنیم. نتایج ما حاکی از این می باشند که حل کننده های مدرن MIP می توانند بهینگی را به سرعت برای مسائل اندازه-متوسط اثبات کنند. در مقایسه ی چهار مدل MIP، فرمول گسسته ی مطرح شده توسط مانه بهترین عملکرد را در هر دو مقیاس عملکردی ارائه می دهد. ما همچنین عملکرد MIP با تنظیم پارامتر و چند ریسگی با استفاده از CPLEX بررسی می کنیم. هنگام مقایسه ی نتایج با استفاده از تنها یک دنباله و مقداردهی های پیش فرض پارامتری، گین عملکردی چشمگیری مشاهده می شود. نتایج ما بعنوان تصویر لحظه ای عملکرد حل کننده های مدرن MIP برای مسئله ی زمانبندی مهم و به خوبی مطالعه شده، عمل می کنند. در نهایت نتایج MIP با برنامه نویسی محدود (CP)، که یک روش متداول دیگر برای زمانبندی بوده و معروف ترین الگوریتم کامل برای ارائه ی یک نگرش وسیع میان رویکردهای مختلف می باشد، مقایسه می شوند.
ترجمه مقدمه
برنامه نویسی عدد صحیح مختلط (MIP) بطور گسترده ای به مسائل زمانبندی اعمال شده و این اغلب رویکرد اولیه برای حمله به مسئله ی جدید زمانبندی می باشد. برای مثال، از بین 40 تحقیق منتشر شده در مجله ی زمانبندی سال 2014، 14 مورد از MIP استفاده کرده اند، که بیش از هر تکنولوژی دیگری می باشد. با توجه به این محبوبیت، همراه با بهبودهای انجام پذیرفته در تکنولوژی MIP تجاری، درک اینکه مدل های مختلف MIP برای زمانبندی در بافت حل کننده های مدرن چگونه با همدیگر مقایسه می شوند، ارزشمند می باشد. سه فرمول پرکاربرد MIP برای مسائل زمانبندی عبارتند از: فرمول شاخص زمانی، فرمول مبتنی بر رتبه بندی، و فرمول گسسته. یک مقایسه ی نظری میان این فرمول ها حاکی از این است که فرمول گسسته بعنوان بهترین فرمول بوده و فرمول شاخص زمانی بدترین آن ها می باشد. با این حال، برخلاف تاریخچه ی طولانی این فرمول ها، به نظر تابه حال یک مطالعه ی کامل محاسباتی برای مقایسه ی عملکرد فرمول های مختلف با استفاده از حل کننده های MIP انجام نپذیرفته است. در جدیدترین مطالعه ما پی بردیم که اپل گیت و همکارانش یک الگوریتم شاخه و مرز براساس فرمول گسسته ارائه دادند و به این نتیجه رسیدند که JSP حتی برای مسائل دارای اندازه متوسط نیز از لحاظ محاسباتی چالش برانگیز می باشد. در این مقاله، ما عملکرد چهار مدل MIP خود را برای JSP سنتی مقایسه می کنیم. علاوه بر سه فرمول JSP استاندارد، ما یک فرمول گسسته ی دیگر ارائه می دهیم که لیائو ادعا کرده است بر فرمول اصلی برتری دارد. ما آزمایش های مربوط به سه حل کننده ی مختلف را انجام می دهیم: ، و . CPLEX و GUROBI هر دو بعنوان حل کننده های جدید تجاری MIP در نظر گرفته می شوند، در حالی که SCIP سریعترین حل کننده ی غیرتجاری می باشد. هدف ما ارائه ی مقایسه ی کامل تجربی مدل های MIP برای JSP با استفاده از حل کننده های مختلف MIP و شناسایی موثرترین مدل می باشد. نتایج تجربی ما با استفاده از CPLEX و GUROBI برخلاف Pan نشان می دهند که مدل شاخص زمانی می تواند بهتر از مدل مبتنی بر رتبه بندی برای مسائل کوچک عمل کند، اما در مقیاس بندی مسائل بزرگتر به خاطر اندازه مدل ناکام می ماند. بعلاوه، برخلاف یافته ی لیائو، نتایج ما نشان مید هند که مدل گسسته ی اصلی نسبت به مدل گسسته ی لیائو برای CPLEX و GUROBI موثرتر می باشد. با این حال، آزمایش های انجام پذیرفته با استفاده از SCIP، نتایج متفاوتی ارائه داده اند: اولا، مدل مبتنی بر رتبه بندی برای مسائل کوچک بر مدل شاخص زمانی برتری دارد، دوما، با این که در نگاه اول فرمول گسسته ی لیائو به نظر نسبت به فرمول گسسته ی اصلی موثرتر می باشد، اما بررسی دقیق مشخص می کند که این تفاوت ها به خاطر تکنیک های مختلف پیش پردازش به کار رفته توسط SCIP و پدیده ی گسستگی در فرآیند جستجوی حل کننده های MIP می باشند. برخلاف این تفاوت ها، در بین تمامی حل کننده های تست شده، مدل گسسته بر مدل های شاخص زمانی و مبتنی بر رتبه بندی برتری دارد. ما سپس دو جنبه ی حیاتی مدل های شاخص زمانی را بررسی می کنیم: چند ریسگی و تنظیم پارامتر. چندریسگی اجازه می دهد جستجو بصورت موازی انجام پذیرد و در نتیجه می تواند بطور چشمگیری عملکرد را بهبود بخشد. هدف تنظیم پارامتر یافتن بهترین مجموعه ی پارامترها برای دسته ی خاصی از مسائل می باشد. ما آزمایش ها را با بهترین مدل MIP یعنی مدل گسسته با استفاده از CPLEX انجام می دهیم. نتایج نشان می دهند که اجرای هشت دنباله بصورت موازی باعث بهبود 1.5 برابری عملکرد برای مسائلی که می توانند بهینه باشند می شود، که 4.5 برابر سریع تر از جستجوی پیش فرض تک دنباله ای می باشد. برای مسائلی قبلی که برای آن ها راه حل بهینه پیدا نشد و در عرض یک ساعت اثبات شد، کیفیت راه حل با گذشت زمان 30 درصد بهبود یافت. ما همچنین یک مقایسه از بهترین نتایج MIP با دو رویکرد کامل ارائه می دهیم: برنامه نویسی گسسته (CP) و iSTS-SGS، که دومی الگوریتم دقیق نوین می باشد. انگیزه های ما از مقایسه ی CP و MIP دوگانه می باشند. اولا، از آنجایی که MIP و CP بطور گسترده ای توسط متخصصین بعنوان تکنولوژی خارج از محدوده برای زمانبندی استفاده شده اند، درک تفاوت های بین عملکردهای آن ها ارزشمند می باشد. ثانیا، به خاطر بهبودهای چشمگیر حل کننده های MIP و CP در یک دهه ی گذشته، بررCPLEXشرفت های MIP و CP مطلوب می باشد. ما یک مطالعه ی تجربی با استفاده از CPLEX برای مدل گسسته ی MIP با تنظیم پارامتر و چند ریسگی و بهینه ساز برای مدل CP انجام داده ایم. نتایج تجربی ما نشان می دهند که MIP برای مسائل دارای اندازه ی متوسط و دارای هدف اثبات بهینگی، همانند CP عمل می کند. با این حال برای نمونه های بزرگتر JSP نسبت MIP برتری داشته و با iTST-SGS قابل مقایسه می باشد. بطور خلاصه نوآوری این مقاله در تجزیه و تحلیل تجربی مدل های MIP برای مسئله ی زمانبندی فروشگاه کار می باشد.
پیش نمایش مقاله
پیش نمایش مقاله  مدل های برنامه نویسی عدد صحیح مختلط برای زمانبندی فروشگاه کار: یک تجزیه و تحلیل محاسباتی

چکیده انگلیسی

In both industry and the research literature, Mixed Integer Programming (MIP) is often the default approach for solving scheduling problems. In this paper we present and evaluate four MIP formulations for the classical job shop scheduling problem (JSP). While MIP formulations for the JSP have existed since the 1960s, it appears that comprehensive computational studies have not been performed since then. Due to substantial improvements in MIP technology in recent years, it is of interest to compare the standard JSP models using modern optimization software. We perform a fully crossed empirical study of four MIP models using CPLEX, GUROBI and SCIP, focusing on both the number of instances that can be proved optimal and the solution quality over time. Our results demonstrate that modern MIP solvers are able to prove optimality for moderate-sized problems very quickly. Comparing the four MIP models, the disjunctive formulation proposed by Manne performs best on both performance measures. We also investigate the performance of MIP with multi-threading and parameter tuning using CPLEX. Noticeable performance gain is observed when compared to the results using only single thread and default parameter settings. Our results serve as a snapshot of the performance of modern MIP solvers for an important, well-studied scheduling problem. Finally, the results of MIP is compared to constraint programming (CP), another common approach for scheduling, and the best known complete algorithm to provide a broad view among different approaches.

دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.