Ş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

PDF

TWT_nested_PMS2012_MainFile.pdf

Download (163kB)

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 |