Content Type: Статьи

Для NP-трудной в обычном смысле задачи теории расписаний минимизация суммарного запаздывания для одного прибора построен Гибридный алгоритм, использующий идею известного метаэвристического алгоритма «Муравьиные колонии» и комбинаторные свойства Правил исключения 1-4. Приводится сравнительный анализ эффективности Гибридного алгоритма и алгоритма «Муравьиные колонии».

E.R. Gafarov (2007), Hybrid Algorithm of Solution of the Minimization Problem of Total Delay for One Device. Journal of Information Technology (in Russian), 1, 30-37.

this paper we show that the special case B-1 of the single machine
total tardiness problem 1||\sum T_j is NP-hard in ordinary sense. For the
case there exist pseudo-polynomial algorithm O(n \sum p_j) time.

A.A. Lazarev, E.R. Gafarov (2006), Special Case of the Single-Machine Total Tardiness Problem is NP-hard. Journal of Computer and Systems Sciences International, 45 (3), 450-458. (journal impact factor 2018: 0.513). Q3

A.A. Lazarev, A.G. Kvaratskheliya, E.R. Gafarov (2007), Algorithms for Solving the NP-Hard Problem of Minimizing Total Tardiness for a Single Machine. Doklady Mathematics, 75 (1), 130-134 (journal impact factor 2018: 0.625). Q2

Consideration was given to the resource-constrained project scheduling problem and its special cases. The existing lower estimates of the objective function—minimization of the project time—were compared. It was hypothesized that the optimal value of the objective
function of the nonpreemptive resource-constrained project scheduling problem is at most twice as great as that of the objective function with preemption. The hypothesis was proved for the cases of parallel machines and no precedence relation.

A.A. Lazarev and E.R. Gafarov (2008), On Project Scheduling Problem. Automation and Remote Control, 69 (12), 2070-2087 (journal impact factor 2018: 0.589). Q2

We propose a hybrid algorithm based on the ant colony optimization (ACO) meta-heuristic, in conjunction with four well-known
elimination rules, to tackle the NP-hard single-machine scheduling problem to minimize the total job tardiness. The hybrid algorithm
has the same running time as that of ACO. We conducted extensive computational experiments to test the performance of the hybrid
algorithm and ACO. The computational results showthat the hybrid algorithm can produce optimal or near-optimal solutions quickly,
and its performance compares favourably with that of ACO for handling standard instances of the problem.

T. C. E. Cheng, A. A. Lazarev, E. R. Gafarov (2009), A Hybrid Algorithm for the Single Machine Total Tardiness Problem. Computers & Operations Research, 36 (2), 308-315. (journal impact factor 2018: 3.002). Q1

A.A. Lazarev and E.R. Gafarov (2009), Transformation of the Network Graph of Scheduling Problems with Precedence Constraints to a Planar Graph. Doklady Mathematics, 79 (1), 1-3. (journal impact factor 2018: 0.625). Q2

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.

E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Single machine total tardiness maximization problems: complexity and algorithms.Annals of Operation Research, doi:10.1007/s10479-012-1288-x, Volume 207, Issue 1, pp 121-136 (journal impact factor 2018: 2.284). Q1

E.R. Gafarov, A.A. Lazarev and F. Werner (2010), Algorithms for Some Maximization Scheduling Problems on a Single Machine. Automation and Remote Control, 10, 2070-2084 (journal impact factor 2018: 0.589). Q2

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), we  present 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.

E.R. Gafarov, A.A. Lazarev, and F. Werner (2011), Single Machine Scheduling Problems with Financial Resource Constraints: Some Complexity Results and Properties. Mathematical Social Sciences, 62, 7-13. (among the 25 most downloaded papers of this journal in Science Direct from July to September 2011 and also from October to December 2011)  (journal impact factor 2018: 0.540). Q1.

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive  problems have a ratio of $O(\log n)$, where $n$ is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi has a bad relative error of $O(\log n)$, and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$, and known lower bounds have a relative error of at least equal to $O(\log n)$. This type of instances corresponds to the single machine parallel-batch scheduling problem $1|p-batch, b=\infty|C_{max}$

E.R. Gafarov, A.A. Lazarev and F. Werner (2012), Approximability Results for the Resource-Constrained Project Scheduling Problem with a Single Type of Resources. Annals of Operations Research, doi:10.1007/s10479-012-1106-5 (accepted, in print) (journal impact factor 2018: 2.284). Q1