• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта
Меню
Найдено 10 публикаций
Сортировка:
по названию
по году
Препринт
Lazarev A. A., Lemtuzhnikova D., Werner F. Otto-von-Guericke Universitaet, 2019
We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest instance for which a polynomial or pseudo-polynomial algorithm is known. For this determined instance, we construct a schedule which is then applied to the original instance. It is shown how this approach is applied to di_erent scheduling problems.
Добавлено: 26 апреля 2020
Препринт
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.
Добавлено: 4 марта 2013
Препринт
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.
Добавлено: 4 марта 2013
Препринт
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
Добавлено: 4 марта 2013
Препринт
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.
Добавлено: 4 марта 2013
Препринт
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.
Добавлено: 4 марта 2013
Препринт
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 11.
In this paper, we consider some scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. We present some complexity results for such maximization problems with classical objective functions (e.g. total tardiness, number of tardy jobs and total completion time) and various additional constraints (e.g. deadlines, weights and/or release dates of jobs may be given). As a generalization, we consider a classical combinatorial problem with an opposite optimization criterion, namely a minimization version of the knapsack problem, for which we give an NP-hardness proof and an exact pseudo-polynomial algorithm.
Добавлено: 4 марта 2013
Препринт
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 8.
Problem RCPSP may be formulated as follows. Given a set $N=\{1,\dots,n\}$ of jobs. A constant amount (quantity) of $Q_k>0$ units of resource $k, k=1,\dots,K,$ is available at any time. Job $j\in N$has to be processed for $p_j\geq 0$ time units without preemption. During this period, a constant amount (quantity) of $q_{jk} \geq 0$ units of resource $k$ is occupied. Fur the rmore, finish-start precedence relations $i \rightarrow j$ are defined between the jobs according to an acyclic directed graph $G.$ The objective is to determine the starting times $S_j$ for each job $j=1,\dots,n,$ in such a way that: at each time $t$, the total resource demand is less than or equal to the resource availability for each resource type the given precedence constraints arefulfilled the makespan $C_{max} = \max_{j=1}^n C_j$, where $C_j=S_j+p_j,$ is minimized.
Добавлено: 4 марта 2013
Препринт
Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 10.
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler.
Добавлено: 4 марта 2013
Препринт
Гафаров Е. Р., Лазарев А. А., Вернер Ф. Otto-von-Guericke Universitaet, 2010. № 7.
In this paper, we consider single machine scheduling problems with a non-renewable resource. This type of problems has not been intensively investigated in the literature so far. For several problems of this type with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), wepresent some complexity results. Particular attention is given to the problem of minimizing total tardiness. In addition, for the so-called budget scheduling problem with minimizing the makespan, we present some properties of feasible schedules.
Добавлено: 4 марта 2013