title   
  

A simple, fast, and effective heuristic for the single-machine total weighted tardiness problem

Şen, Halil and Bülbül, Kerem (2012) A simple, fast, and effective heuristic for the single-machine total weighted tardiness problem. In: 13th International Conference on Project Management and Scheduling (PMS 2012), Leuven, Belgium

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
159Kb

Official URL: http://www.econ.kuleuven.be/eng/tew/academic/prodbel/PMS2012/proceedings.pdf

Abstract

We consider the single-machine total weighted tardiness problem (TWT) where a set of n jobs with general weights w_1,…, w_n, integer processing times p_1,…, p_n, and integer due dates d_1,…, d_n has to be scheduled non-preemptively. If C_j is the completion time of job j then T_j = max(0, C_j - d_j) denotes the tardiness of this job. The objective is to find a schedule S^{*}_{WT} that minimizes the weighted sum of the tardiness costs of all jobs computed as \sum_{j=1}^{n} w_j T_j. This problem is known to be unary NP-hard. Our goal is to design a constructive heuristic for this problem that yields excellent feasible solutions in short computational times by exploiting the structural properties of a preemptive relaxation.

Item Type:Papers in Conference Proceedings
Additional Information:Halil received the 3rd place in the student paper competition.
Uncontrolled Keywords:Preemptive relaxation, transportation problem, nested schedule
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
ID Code:19371
Deposited By:Kerem Bülbül
Deposited On:16 Oct 2012 12:44
Last Modified:16 Oct 2012 12:44

Repository Staff Only: item control page