Title: Hybrid heuristic algorithms for single machine total weighted tardiness scheduling problems

Authors: R. Maheswaran, S.G. Ponnambalam, N. Jawahar

Addresses: Department of Computer Science and Engineering, MEPCO Schlenk Engineering College, Sivakasi – 626005, Virudunagar District, Tamilnadu, India. ' School of Engineering, Monash University, Sunway Campus, Petaling Jaya 46150, Selangor, Malaysia. ' Department of Mechanical Engineering, Thiagarajar College of Engineering, Madurai – 625 015, Tamilnadu, India

Abstract: This paper addresses on solving a well known Non Polynomial (NP) hard type problem, namely the single machine total weighted-tardiness problem. The performances of three hybrid heuristic algorithms to solve the single machine scheduling problems with the objective of minimising the total weighted tardiness are presented and compared. In the first hybrid algorithm, a dynamic dispatching rule, namely Modified Due Date (MDD), is hybridised with local search mechanism. In the second hybrid algorithm, a greedy heuristic, namely backward phase, is proposed and hybridised with local search mechanisms. The third hybrid algorithm hybridises the backward phase heuristics with an iterated local search (ILS) having an evolutionary perturbation tool. The algorithms are tested by solving all the 125 benchmark problem instances available in the OR-Library for different sizes and compared with the best known values. It is observed that the hybrid algorithm with evolutionary perturbation tool is performing better than the others.

Keywords: single machine scheduling; metaheuristics; evolutionary perturbation tool; total weighted tardiness; dispatching rules; due dates.

DOI: 10.1504/IJISTA.2008.016358

International Journal of Intelligent Systems Technologies and Applications, 2008 Vol.4 No.1/2, pp.34 - 56

Published online: 22 Dec 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article