IFAC Proceedings Volumes 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucharest, 23-25 May 2012
In this paper, we consider the NP-hard minimizing total tardiness on a single machine scheduling problem. We propose a metric for that problem and present a polynomial approximation scheme based on search for the polynomially solvable instance which has a minimal distance from an initial instance.
We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented.
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.