2015 |
Murovec, Boštjan Job-shop local-search move evaluation without direct consideration of the criterion’s value Journal Article In: European Journal of Operational Research, vol. 241, no. 2, pp. 320 - 329, 2015, ISSN: 0377-2217. Abstract | Links | BibTeX | Tags: Job-shop, Local search, Makespan, Move evaluation, Scheduling @article{MUROVEC2015320, 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. |
2004 |
Murovec, Boštjan; Šuhel, Peter A repairing technique for the local search of the job-shop problem Journal Article In: European Journal of Operational Research, vol. 153, no. 1, pp. 220 - 238, 2004, ISSN: 0377-2217, (Timetabling and Rostering). Abstract | Links | BibTeX | Tags: Job-shop, Local search, Neighborhood function, Scheduling @article{MUROVEC2004220, The local search technique has become a widely used tool for solving many combinatorial optimization problems. In the case of the job-shop the implementation of such a technique is not straightforward at all due to the existence of the technological constraints among the operations that belong to the same job. Their presence renders a certain set of schedules infeasible. Consequently, special attention is required when defining optimization algorithms to prevent the possibility of reaching an infeasible schedule during execution. Traditionally, the problem is tackled on the neighborhood level by using only a limited set of moves for which feasibility inherently holds. This paper proposes an alternative way to avoid infeasibility by incorporating a repairing technique into the mechanism for applying moves to a schedule. Whenever an infeasible move is being applied, a repairing mechanism rearranges the underlying schedule in such a way that the feasibility of the move is restored. The possibility of reaching infeasible solutions is, therefore, eliminated on the lowest possible conceptual level. Consequently, neighborhood functions need not to be constrained to a limited set of feasible moves any more. |