Zurück zu den Preprints des Jahres 2010


2010-12

A Polynomial Time Graphical Algorithm for Maximizing Total Tardiness on a Single Machine

by E.R. Gafarov, A.A. Lazarev, F. Werner.


Series: 2010-12, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
In this paper, we consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time.

Keywords:
Scheduling, Single machine problems, Maximization problems, Total tardiness