A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Time Complexity Evgeny R. Gafarov, Alexander A. Lazarev Institute of Control Sciences of the Russian Academy of Sciences Moscow, Russia Frank Werner Otto-von-Guericke-University Magdeburg, Germany 1 Outline of the Talk 1. Dynamic Programming and Graphical Algorithms 2. A Polynomial Algorithm for Problem 1 (nd) | | max в€‘ Tj 3. A Numerical Example 4. An Overview of Graphical Algorithms for Single Machine Problems 2 1. Dynamic Programming and Graphical Algorithms Dynamic Programming (Bellman 1957) Idea of the graphical algorithm: Combine several states into a new state 3 Computations in a dynamic programming algorithm Computations in a graphical algorithm 4 2 . A Polynomial Algorithm for Problem 1 (nd) | | max в€‘ Tj single machine n jobs pj processing time j = 1,2,вЂ¦,n dj due date no idle times, a schedule starts at time 0 maximization of total tardiness в€‘ Tj 5 Lemma 1: There exists an optimal schedule ПЂ = (G, H), where all jobs in G are on-time and all jobs from H are tardy. All jobs from set G are processed in SPT order and all jobs from set H are processed in LPT order. Notations: ПЂl(t) вЂ“ best schedule of jobs 1,2,вЂ¦,l starting at time t Fl(t) вЂ“ corresponding total tardiness 6 7 8 9 10 11 12 Theorem 1: The graphical algorithm constructs an optimal schedule for problem 1 (nd) | | max в€‘ Tj in O(n2) time. 3. A Numerical Example n=4 13 14 15 16 17 18 4. An Overview of Graphical Algorithms for Single Machine Problems 19 Two Announcements 1. New Book is ready: Sotskov, Sotskova, Lai, Werner: Scheduling under Uncertainty: Theorems and Algorithms, Belarusian Science, Minsk, 326 p., July 2010 (ISBN 978-985-08-1173-8) - free download of a pdf from http://www.math.uni-magdeburg.de/~werner/sot-sot-lai-werner.pdf - paperback book at production cost available 2. LiSA вЂ“ Version 3.0 with documentation is ready: Andresen, BrГ¤sel, Engelhardt, Werner: LiSA вЂ“ A Library of Scheduling Algorithms, Handbook for Version 3.0, 107 pages, TR 10-05, August 2010.