Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation

Exact move evaluation in local search-based job shop scheduling is known to be time consuming, especially for medium and large size instances. Therefore, approximation functions providing quick estimates for the cost induced by a move are often used in order to accelerate the search process. This paper describes the generalization of an existing cost estimation function for insertion moves towards min-sum objectives, such as total weighted tardiness, total weighted completion time and total weighted number of late jobs. Besides the transfer of the concept itself, shortcomings of the original approach are identified and eliminated and an enhanced approximation scheme is presented. The final estimation function is able to provide a considerably increased accuracy for the considered min-sum objectives compared to the existing approach. The advantage of the new function emerges most clearly when it is embedded into a tabu search algorithm, as verified based on benchmark instances from literature involving up to 100 jobs and 20 machines.