A Graphical Approach to Solve Combinatorial Problems: Algorithms and Some Computational Results
Information Control Problems in Manufacturing, Volume # 14 | Part# 1
Gafarov, Evgeny R.; Lazarev, Alexander; Werner, Frank
Digital Object Identifier (DOI)
Mathematical Approaches for Scheduling; Dynamic Programming; Discrete Applied Mathematics
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.
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.