• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site
Of all publications in the section: 9
Sort:
by name
by year
Working paper
Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2008. No. 15.
In this paper we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with $n \le 10$ numbers. For almost all instances, the new algorithm considers on average substantially less "stages" than the dynamic programming algorithm.
Working paper
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2009. No. 38.
We consider single machine problems with opposite criteria, namely we consider the maximization of total tardiness, the maximization of the number of tardy jobs and the maximization of total completion time (in contrast to usual minimization problems)and a minimization version of the Knapsack problem.
Working paper
Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2008. No. 12.
The scheduling problem of minimizing total tardiness on a single machine is knownto be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times $p_j$ and the due dates $d_j$ of the jobs $j, \, j \in N = \{ 1, 2, \ldots, n \}$, are oppositely ordered: $p_1\ge p_2\ge\dots\ge p_n$ and $d_1\le d_2\le\dots\le d_n$. It is shown that already this special case is $NP$-hard in the ordinary sense, too. The set of jobs $N$ is partitioned into $\Bbbk, 1 \le \Bbbk \le n$, subsets$\mathcal{M}_1,\mathcal{M}_2,\dots,\mathcal{M}_\Bbbk$,$\mathcal{M}_\nu \bigcap \mathcal{M}_\mu=\emptyset$ for $\nu\ne \mu,$$N=\mathcal{M}_1\bigcup\mathcal{M}_2\bigcup\dots\bigcup\mathcal{M}_\Bbbk$,such that$\max_{i,j\in\mathcal{M}_\nu}|d_i-d_j|\le\min_{j\in\mathcal{M}_\nu}p_j$for each $\nu=1,2,\dots,\Bbbk$. We propose algorithms which solve the problem: in $O(\Bbbk n\sum p_j)$ time if $1\le \Bbbk< n$ in $O(n^2)$ time if $\Bbbk= n$ and in $O(n^2)$ time if $\max_{i,j\in N}|d_i-d_j|\le 1$. The polynomial algorithms do neitherrequire the conditions $p_1\ge p_2\ge\dots\ge p_n$ mentioned above nor integer processing times to construct an optimal schedule. Finally, we apply the idea of the presented algorithm for the case $\Bbbk = 1$ to the even-odd partition problem
Working paper
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 20.
In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For the knapsack problem and some single machine scheduling problems, it is shown that the time complexity of the GrA is less that the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve largescale instances and instances, where the parameters are not integer. In addition, for some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of DPA.
Working paper
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 12.
In this paper, we consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time.
Working paper
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 11.