New Task Domain Propagators with Polynomial Complexity for Resource-Constrained Project Scheduling Problem

Arkhipov D.; Battaia O.; Lazarev A.; Tarasov G.; Tarasov I.

doi:10.12783/dtcse/optim2018/27917

Publications

?

New Task Domain Propagators with Polynomial Complexity for Resource-Constrained Project Scheduling Problem

P. 3–13.

Arkhipov D., Battaia O., Lazarev A., Tarasov G., Tarasov I.

We consider a classic Resource-Constrained Project Scheduling Problem (RCPSP) which is known to be NP-hard. For defined project deadline T , each task of the project can be associated with its temporal domain – a time interval in which this task can be processed. In this research, we adopt existing resource-based methods of task domain propagation to generalized statement with time-dependent resource capacity and show how to improve its propagation efficiency. We also present new polynomial-time algorithms (propagators) to tighten such temporal task domains in order to make the optimization problem easier to solve. Moreover, we show how these propagators can be used to calculate lower bound on project makespan.

Keywords: project scheduling constraint programming Scheduling, RCPSP Task domain propagator

In book

DEStech Transactions on Computer Science and Engineering

Vol. 2018 IX International Conference on Optimization and Applications (OPTIMA 2018) (SUPPLEMENTARY VOLUME). , Lancaster: DEStech Publications,Inc., 2018.

Efficiency management of discrete production systems under the dynamics of project portfolio

Mylnikov L., Computers & Industrial Engineering 2022 Vol. 163 Article 107807

The problem investigated in the paper is very timely due to the necessity to increase planning and management efficiency of production systems as new innovation products come to the market on a regular basis. This task may be achieved if we upgrade the formalization level by the description of processes which a production system performs to create a ...

Added: October 5, 2022

Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints

Dmitry Arkhipov D. I., Battaia O. O., Cegarra J. et al., , in: 7th CIRP Conference on Assembly Technologies and Systems* 76.: Elsevier, 2018. Ch. 76 P. 63–66.

The assembly process is extremely complex for aircraft and its management requires to address numerous optimization problems related to the assignment of tasks to workstations, staffing problem for each workstation and finally the assignment of tasks to operators at each workstation. This paper treats the latter problem dealing with the assignment of tasks to operators ...

Added: October 29, 2018

7th CIRP Conference on Assembly Technologies and Systems

Elsevier, 2018.

Added: October 29, 2018

Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints

Alexander Lazarev, Cegarra J., Battaia O. O. et al., Procedia CIRP 2018 Vol. 76 P. 63–66

Added: October 1, 2018

CEUR Workshop Proceedings (CEUR-WS.org) of the VIII International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)

[б.и.], 2017.

Added: November 30, 2017

Математические модели управления проектами

Tsarkov I., М.: НИЦ Инфра-М, 2018.

Математические модели являются частью научного фундамента относительно новой области знаний — управлления проектами. Они обеспечивают менеджеров проекта практическими инструментами, позволяющими разрабатывать и оптимизировать расписания проекта, а также настраивать систему его управления таким образом, чтобы повысить эффективность управления. Изложены модели и методы, направленные на оптимизацию проекта через призму их практического использования. Особое внимание уделяется направлениям исследований в ...

Added: November 28, 2017

Сокращение продолжительности проекта в условиях неопределенности и ограниченных ресурсов

Tsarkov I., Научные исследования и разработки. Российский журнал управления проектами 2017 Т. 6 № 3 С. 26–36

Shortening project expected makespan in the case of resource constraints is the most popular problem in project scheduling. But in practice activity durations is not determined. So the problem is to find a policy which could define which activity should be started at decision points to minimize expected project makespan. This problem usually called SRCPSP. ...

Added: November 28, 2017

Heuristic Algorithm for Solving the Cosmonauts Training Planning Problem

Alexander Lazarev, Khusnullin N., Musatova E. et al., , in: CEUR Workshop Proceedings (CEUR-WS.org) of the VIII International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)Vol. 1987.: [б.и.], 2017. Ch. 1987 P. 364–369.

The cosmonauts training planning problem is a problem of construc- tion of cosmonauts training timetable. Each cosmonaut has his own set of tasks which should be performed with respect to resource and time con- straints. The problem is to determine start moments for all considered tasks. This problem is a generalization of the resource-constrained project ...

Added: October 20, 2017

Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem

Alexander Lazarev, Dmitry Arkhipov D. I., German Tarasov g., , in: CEUR Workshop Proceedings (CEUR-WS.org) of the VIII International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)Vol. 1987.: [б.и.], 2017. Ch. 1987 P. 356–363.

In Resource-Constrained Project Scheduling Problem (RCPSP), two kinds of constraints are considered: the precedence constraints, which can be eliminated by using critical path method, and the resource con- straints. This paper focuses on the latter, specifically, on estimating max- imum resource loads. We examine a variant of vector sum problem with fractions: considering preemptions allowed, ...

Added: October 20, 2017

Системный подход к управлению эффективностью проекта на основе генетических алгоритмов

Макеева О. Ю., Tsarkov I., Научные исследования и разработки. Российский журнал управления проектами 2012 № 1 С. 14–30

The discovery of Critical Path Method (CPM) made breakdown of project management possible. In the result, project management consists of some knowledge areas like project time management, project cost management etc. But there is a problem: CPM couldn’t take into account resource constrains and costs. So there are a lot of models which include different ...

Added: July 25, 2013