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

Roland Braune, Günther Zäpfel, Michael Affenzeller

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)495-518
Number of pages24
JournalJournal of Scheduling
Issue number5
Publication statusPublished - Oct 2013


  • Cost estimation
  • Job shop scheduling
  • Local search
  • Min-sum objective
  • Move evaluation


Dive into the research topics of 'Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation'. Together they form a unique fingerprint.

Cite this