A tabu search algorithm for the single machine total weighted tardiness problem
European Journal of Operational Research, cilt.176, sa.3, ss.1423-1435, 2007 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 176 Sayı: 3
- Basım Tarihi: 2007
- Doi Numarası: 10.1016/j.ejor.2005.10.030
- Dergi Adı: European Journal of Operational Research
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.1423-1435
- Anahtar Kelimeler: Single machine scheduling, Tabu search, Total weighted tardiness minimization
- Boğaziçi Üniversitesi Adresli: Evet
Özet
In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature. © 2005 Elsevier B.V. All rights reserved.