A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

Bülbül, Kerem (2011) A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem. Computers & Operations Research, 38 (6). pp. 967-983. ISSN 0305-0548

This is the latest version of this item.

[thumbnail of This is a RoMEO green publisher -- author can archive post-print (ie final draft post-refereeing)] PDF (This is a RoMEO green publisher -- author can archive post-print (ie final draft post-refereeing))
jobshop_WT.pdf

Download (377kB)

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.
Item Type: Article
Uncontrolled Keywords: job shop; weighted tardiness; shifting bottleneck; tabu search; preemption; transportation problem.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 06 Dec 2010 15:49
Last Modified: 29 Jul 2019 12:09
URI: https://research.sabanciuniv.edu/id/eprint/15624

Available Versions of this Item

Actions (login required)

View Item
View Item