Optimization Online


A Hybrid Shifting Bottleneck-Tabu Search Heuristic for the Job Shop Total Weighted Tardiness Problem

Kerem Bulbul (bulbul***at***sabanciuniv.edu)

Abstract: In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck - tabu search (SB-TS) algorithm by replacing the reoptimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.

Keywords: job shop; weighted tardiness; shifting bottleneck; tabu search; preemption; transportation problem

Category 1: Applications -- OR and Management Sciences

Citation: Bulbul, K. (2011). A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem. Computers & Operations Research, 38(6):967-983. doi: 10.1016/j.cor.2010.09.015

Download: [PDF]

Entry Submitted: 03/24/2010
Entry Accepted: 03/24/2010
Entry Last Modified: 11/22/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society