» Download Article

Authors
Gafarov, Evgeny R.; Lazarev, Alexander; Werner, Frank

Digital Object Identifier (DOI)
10.3182/20120523-3-RO-2023.00119

Page Numbers:
127-132

Index Terms
Mathematical Approaches for Scheduling; Dynamic Programming; Discrete Applied Mathematics

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.

References

R. Bellman. Dynamic Programming. Princeton: Princeton
Univ. Press, 1957.
S.K. Sahni. Algorithms for scheduling independent jobs.
J. Assoc. Comput. Mach., vol. 23, 116–127, 1976.
E.L. Lawler, J.M. Moore. A functional equation and
its application to resource allocation and sequencing
problems. Management Sci., vol. 16, No. 1, 77–84, 1969.
H. Hoogeveen, V. T’Kindt. Minimizing the number of
late jobs when the start time of the machine is variable.
Proceedings PMS 2010, 235–238, 2010.
E.R. Gafarov, A.A. Lazarev and F. Werner. A note on a
single machine scheduling problem with generalized total
tardiness objective function. Information Processing
Letters, vol. 112, No. 3, 72 – 76, 2012.
E.R. Gafarov, A.A. Lazarev and F. Werner. Transforming
a pseudo-polynomial algorithm for the single
machine total tardiness maximization problem into a
polynomial one. Annals of Operations Research, DOI
10.1007/s10479-011-1055-4, 2012, in print.
A.A. Lazarev, F. Werner. Algorithms for special cases
of the single machine total tardiness problem and an
application to the even-odd partition problem. Math.
Comp. Modelling, vol. 49, No. 9-10, 2061–2072, 2009.