Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial oneстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 19 июля 2013 г.
Аннотация: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. This result settles the complexity
status of the problem under consideration which was open.