کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10346202 | 698774 | 2013 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An optimal method for the preemptive job shop scheduling problem
ترجمه فارسی عنوان
یک روش بهینه برای برنامه زمانبندی فروشگاه پیشگیرانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، شعبه و مرز، پیش پرداخت، فروشگاه شغلی، گراف جداسازی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this study, a powerful solution methodology is developed for minimizing makespan in the preemptive Job Shop Scheduling Problem (pJSSP). Some new properties of the problem are stated and proved via theorems on the basis of which a new dominant set is introduced for the problem. These properties give rise to a dramatic decrease in the search space and provide the potential for exact methods to be successfully used in the solution of this notoriously NP-hard problem. The exact method presented here is a branch and bound algorithm developed on the basis of a new disjunctive graph. Its efficiency is enhanced by the effective use of such techniques as dominance rules or lower bounds. The capability of the approach is investigated by using it to solve the well-known benchmark problems and comparing the results obtained with those from the best methods in common use. The results indicate that the proposed method is capable of optimally solving 24 open benchmark problems including the famous 10Ã10 problems. Additionally, it is the first optimal method ever developed to find optimal solutions to some large-scale problems of the size 30Ã10 and 50Ã10.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1314-1327
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1314-1327
نویسندگان
Abbas Ebadi, Ghasem Moslehi,