Abstract
This article focuses on the evaluation of moves for the local search of the job-shop problem with the makespan criterion. We reason that the omnipresent ranking of moves according to their resulting value of a criterion function makes the local search unnecessarily myopic. Consequently, we introduce an alternative evaluation that relies on a surrogate quantity of the move’s potential, which is related to, but not strongly coupled with, the bare criterion. The approach is confirmed by empirical tests, where the proposed evaluator delivers a new upper bound on the well-known benchmark test yn2. The line of the argumentation also shows that by sacrificing accuracy the established makespan estimators unintentionally improve on the move evaluation in comparison to the exact makespan calculation, in contrast to the belief that the reliance on estimation degrades the optimization results
چکیده
تمرکز این مقاله بر ارزشیابی حرکتها برای جستجوی محلی مسئله job shop با مقیاس بازه میباشد. استدلال ما اینست که ارزشیابی حاضر حرکتها با توجه به نتیجه ای که از توابع بدست امده است، جستجوی محلی را بی ارزش ساخته است. در نتیجه یک ارزیابی تقریبا مرتبط دیگر را که متکی بر مقدار جایگزین حرکت های بالقوه است را معرفی میکنیم. این رویکرد بر طبق آزمون های تجربی شکل گرفته است که در آن ارزیاب پیشنهادی یک محدوده ی بالا در تست بنچمارک yn2 ارائه می دهد.همچنین این بحث نشان می دهد که عدم دقت بازه ی تخمین ارائه شده ، بطور ناخواسته ارزیابی حرکت را در مقایسه با محاسبه ی دقیق بازه افزایش داده است. در مقابل این باور که تکیه بر تخمین زدن،نتایج بهینه سازی را تنزل داده است.