Математическая формализация задач проектного планирования в расширенной постановке

Аничкин А.С.; Семенов Виталий Адольфович

doi:10.15514/ISPRAS-2017-29(2)-9

Publications

Article

Математическая формализация задач проектного планирования в расширенной постановке

Труды Института системного программирования РАН. 2017. Т. 29. № 2. С. 231-256.

Аничкин А., Семенов В. А.

Language: Russian

DOI

Keywords: теория расписаний проектное планирование

Теория расписаний. Задачи и алгоритмы

Лазарев А. А., Гафаров Е. Р. М.: Физический факультет МГУ, 2011.

Added: Dec 10, 2012

Graphical Algorithm for the Knapsack Problem

Lazarev A. A., Salnikov A. M., Baranov A. V. In bk.: Parallel Computing Technologies. 11th International Conference, Pact 2011, Kazan, Russia, September 19-23, 2011. Proceedings. Iss. 6873. NY: Springer, 2011. P. 469-466.

Added: Dec 1, 2012

Графический подход к решению задач комбинаторной оптимизации

Лазарев А. А. Автоматика и телемеханика. 2007. № 4. С. 13-23.

Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems.

Added: Nov 23, 2012

Classical Combinatorial and Single Machine Scheduling Problems With Opposite Optimality Criteria

Gafarov E., Lazarev A. A., Werner F. Otto-von-Guericke Universitaet, 2010. No. 11.

Added: Mar 4, 2013

A Polynomial Time Graphical Algorithm for Maximizing Total Tardiness on a Single Machine

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.

Added: Mar 4, 2013

Scheduling Problems with Financial Resource Constraints

Gafarov E., Lazarev A. A., Werner F. In bk.: II International Conference Optimization and Application (OPTIMA-2011). M.: 2011. P. 82-85.

Added: Mar 4, 2013

Теория расписаний. Задачи управления транспортными системами

Лазарев А. А., Мусатова Е. Г., Кварацхелия А. Г. и др. М.: Физический факультет МГУ, 2012.

Added: Dec 10, 2012

Теория расписаний. Задачи суммарного запаздывания для одного прибора

Лазарев А. А., Гафаров Е. Р. Саарбрюкен: LAP LAMBERT Academic Publishing, 2011.

Added: Dec 17, 2012

К решению задачи построения расписания выполнения проекта

Лазарев А. А., Гафаров Е. Р. Автоматика и телемеханика. 2008. № 12. С. 86-104.

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

Added: Nov 23, 2012

A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Complexity

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.

Added: Mar 4, 2013

Polynomial algorithm for the scheduling problem $1|pmtn, p=2, r_j=j-1, w_j \leq w_{j+1}| \sum{w_j c_j}$

Lazarev A. A., Arkhipov D. I. In bk.: Методы оптимизации и их приложения - 2011. Труды XV Байкальской международной школы-семинара. Vol. Дискретная оптимизация. Irkutsk: 2011. P. 25-28.

In this paper, we consider the following scheduling problem. On the single machine need to process $n$ jobs. Job $j, j=1,\dots, n,$ characterized: release times $r_j = j - 1$; processing time $p_j = 2$; weight of jobs are non-decreasing $w_j \leq w_{j+1}$. The objective function is $\min{\sum\limits_{j=1}^n (w_j \cdot C_j)}$, where $C_i$ -- completion time.

Added: Mar 4, 2013

Свойства оптимальных расписаний задачи теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора

Лазарев А. А., Кварацхелия А. Г. Автоматика и телемеханика. 2010. № 10. С. 80-89.

In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases.

Added: Nov 24, 2012