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

سختی مشکل برای TS در برنامه ریزی تولید کارگاهی

عنوان انگلیسی
Problem difficulty for tabu search in job-shop scheduling
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
18912 2003 29 صفحه PDF
منبع

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

Journal : Artificial Intelligence, Volume 143, Issue 2, February 2003, Pages 189–217

ترجمه کلمات کلیدی
سختی مشکل - برنامه ریزی تولید کارگاهی - جستجوی محلی - جستجوی ممنوعه
کلمات کلیدی انگلیسی
Problem difficulty, Job-shop scheduling, Local search, Tabu search,
پیش نمایش مقاله
پیش نمایش مقاله  سختی مشکل برای TS در برنامه ریزی تولید کارگاهی

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

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.