Breakout dynasearch for the single-machine total weighted tardiness problem

Junwen Ding, Zhipeng Lü, Edwin Tai Chiu Cheng, Liping Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

We present a breakout dynasearch algorithm (BDS) for solving the single-machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of the weighted tardiness of all the jobs. BDS explores the search space by combining the dynasearch procedure and the adaptive perturbation strategy. Experimental results show that BDS virtually solves all the standard benchmark problem instances with 40, 50, and 100 jobs from the literature within 0.1 s. For 500 larger instances with 150, 200, 250, and 300 jobs, BDS obtains all the upper bounds with the same objective function of the optimal solutions within an average of 252 s, demonstrating the efficacy of BDS in terms of both solution quality and computational efficiency. We also analyze some key features of BDS to identify its success factors.
Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalComputers and Industrial Engineering
Volume98
DOIs
Publication statusPublished - 1 Aug 2016

Keywords

  • Adaptive perturbation strategy
  • Breakout local search
  • Dynasearch
  • Heuristic
  • Single-machine scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this