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

Warning The system is temporarily closed to updates for reporting purpose.

Ş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

[thumbnail of TWT_nested_PMS2012_MainFile.pdf] PDF
TWT_nested_PMS2012_MainFile.pdf

Download (163kB)

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
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: 16 Oct 2012 12:44
Last Modified: 26 Apr 2022 09:06
URI: https://research.sabanciuniv.edu/id/eprint/19371

Actions (login required)

View Item
View Item