| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 709775 | IFAC Proceedings Volumes | 2012 | 6 Pages |
Abstract
In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve large-scale instances and instances, where the parameters are not integer. For some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of a DPA.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
