Proceedings of ISP RAS

Effective Method For Scheduling Complex Industrial Programs Under Spatio-Temporal Constraints.

V. A. Semenov, A. S. Anichkin, S. V. Morozov, O. A. Tarlapan, V. A. Zolotov.


Effective project management assumes usage of advanced methods for scheduling that allow planners to determine time frames and job sequencing to complete the project for minimal time within available resources. Traditional critical path method and resource-constrained scheduling methods completely ignore spatial factors and cannot guarantee trustworthiness of prepared schedules for complex industrial programs. An alternative statement of the resource-constrained project scheduling problem generalizing the traditional statement and taking into account spatial factors that relate to congestion of workspaces and disturbance of workflows is discussed in the paper. For the generalized problem an effective scheduling method is proposed. The method tends to minimize the project makespan while satisfying timing constraints and precedence relations, not exceeding resource utilization limits, avoiding workspace congestion and keeping workflows continuous. The method reuses so-called serial scheduling scheme and provides for additional computational routines and heuristic priority rules to generate feasible schedules satisfying all the imposed requirements. In order to evaluate the method, benchmark sets are proposed and investigated. The performed computational experiments reveal quasi-linear complexity of the method, which allows its application to large scale projects. The method is effective enough to generate schedules closed to optimal, at least for the benchmarks.


scheduling theory, planning, project management, spatio-temporal modeling technologies


Proceedings of the Institute for System Programming, vol. 26, issue 1, 2014, pp. 457-482.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(1)-20

Full text of the paper in pdf Back to the contents of the volume