=Paper=
{{Paper
|id=Vol-1987/paper53
|storemode=property
|title=Heuristic Algorithm for Solving the Cosmonauts Training Planning Problem
|pdfUrl=https://ceur-ws.org/Vol-1987/paper53.pdf
|volume=Vol-1987
|authors=Alexander Lazarev,Nail Khusnullin,Elena Musatova,Denis Yadrentsev,Konstantin Ponomarev
}}
==Heuristic Algorithm for Solving the Cosmonauts Training Planning Problem==
https://ceur-ws.org/Vol-1987/paper53.pdf
Heuristic Algorithm for Solving
the Cosmonauts Training Planning Problem
Alexander A. Lazarev Nail Khusnullin
Institute of Control Sciences Institute of Control Sciences
65 Profsoyuznaya street, 65 Profsoyuznaya street,
117997 Moscow, Russia 117997 Moscow, Russia
jobmath@mail.ru nhusnullin@gmail.com
Elena Musatova Denis Yadrentsev Konstantin Ponomarev
Institute of Control Sciences YU.A. Gagarin Research YU.A. Gagarin Research
65 Profsoyuznaya street, and Test Cosmonaut and Test Cosmonaut
117997 Moscow, Russia Training Center Training Center
nekolyap@mail.ru Star City, 141160, Russia, Star City, 141160, Russia,
d.yadrentsev@gctc.ru K.Ponomarev@gctc.ru
Abstract
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 constraints. The problem is to determine start moments for all
considered tasks. This problem is a generalization of the resource-
constrained project scheduling problem with “time windows”. A new
heuristic method based on constraint programming is developed. The
effectiveness of the method is verified on real data.
1 Introduction
We consider a problem of planning the International Space Station (ISS) cosmonauts training. In order to main-
tain reliability of a space flight, the crew members are obligated to be trained for different types of situations and
operations, to obtain required skills and knowledge before the launch. Hence, the Yu.A. Gagarin Research & Test
Cosmonaut Training Center (CTC) must plan and schedule a list of trainings for every cosmonaut. The sequence
of the training program is based on the following training phases:
• general space training (GST) of candidates for cosmonauts;
• training in groups, separated by the type of manned spacecraft (MSC) or areas of specialization;
• training in approved crews for a specific space flight on MSC.
Passing the sequence of the stages of the training is mandatory for all Russian cosmonauts. The GST is performed
for every candidate only once. The other stages can be performed repeatedly. Usually, the phases last 2, 2 and
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
364
2.5 years, respectively. This article is devoted to the third stage. In general, three crew qualification levels are
defined; a user level, an operator level and a specialist level. For a given flight program, for every on-board system,
a pre-defined set of minimum qualifications is needed to safely operate and maintain the system (for example,
one specialist, one operator and one user). Each crew member, while being a specialist for one system, will be
an operator or only a user for another one system. Consequently, the training program for each crew member is
individually tailored to his set of tasks and pre-defined qualification levels. The development of training plans
for a crew is another problem. Some results for its solving can be found in [Lazarev et al., 2016]. In this article
we believe that an individual plan for each cosmonaut already exists, and the problem is to determine start
moments for all considered tasks for each cosmonaut.
Previously, for solving this problem we have proposed an approach based on methods of integer linear pro-
gramming [Musatova et al., 2016]. However, this approach turned out to be ineffective for high-dimensional
problems. In [Lazarev et al., 2016] comparison of two approaches for a medium dimension cosmonaut training
problem was presented. The first approach was based on integer linear programming and the second one was on
the basis of constraint programming (CP) [Dechter, 2003]. It has been shown an obvious advantage of CP. We
can explain the benefits of the CP by a large number of different constraints imposed by the training process.
The paper has the following structure. In section 2 a mathematical formulation of the considered problem is
given. Section 3 is devoted to properties of the problem. On the basis of these properties in Section 4 a heuristic
algorithm for solving the problem is proposed. Results of a computational experiment for different levels of a
crew experience are given.
2 Problem Statement
This section provides a formulation of the problem, that arises in cosmonauts training scheduling. Simultaneously
there are several crews on training in the Cosmonaut Training Center, but this article presents a model and a
method for its solving for one of them. We will assume that the planning of the cosmonauts training takes place
at a certain given time interval, which specifies a planning horizon. We take as a unit of time a half-hour interval.
Denote as W a set of all weeks and as D a set of all days on the planning horizon. Set H is a set of all half-hour
intervals in a day. Possible moments of the beginning of a task are in a set T = {0, 1, . . . , T }. Each time moment
t ∈ T is characterized by its number of the week w(t) ∈ W on the planning horizon, by its number of the day
d(t) ∈ D and by a number of the half-hour interval h(t) in the day d(t).
Let J be a set of all stages of cosmonauts training (set of tasks) and duration of task j ∈ J is equal to pj units
of time. We input a variable Sj , the value of which is equal to the moment of the beginning of the task j. Let
G = (J, Γ) be a graph of precedence relations between tasks. If (i, j) ∈ Γ, then the task i has to be completed
before the beginning of the task j:
Sj − Si ≥ pi ∀(i, j) ∈ Γ. (1)
We input a set of tasks which are active at the time moment t:
At = {j ∈ J | Sj ≤ t < Sj + pj }. (2)
Let R be a set of renewable resources (instructors, simulators, classrooms, special equipment). Each cosmonaut
is also a resource, available in a quantity of 1 during a working day (excluding holidays, business trips, etc.).
Denote by rart the amount of resource r ∈ R available at time t, and by rcjr — the amount of resource r ∈ R
required for the task j ∈ J. Then the resource constraints can be written in the following form:
∑
rcjr ≤ rart ∀r ∈ R, ∀t ∈ T. (3)
j∈At
Constraints (1), (3) are the standard constraints of the Resource-Constrained Project Scheduling Problem
(RCPSP). As a rule, the objective function in this problem is makespan (project duration). RCPSP is
strongly NP-hard [Artigues et al., 2008]. By this reason different heuristic methods are proposed for its solv-
ing: priority-rule based scheduling methods, truncated branch-and-bound, integer programming based heuris-
tics, disjunctive arc concepts, local constraint-based analysis, sampling techniques, evolutionary algorithms and
local search techniques (see, for example, [Brucker et al., 1999, Kolisch & Hartmann, 2006, Valls et al., 2003,
Debels & Vanhoucke, 2007, Homberger, 2007]. In [Kolisch & Hartmann, 2006] a large number of heuristics that
have been proposed in the literature for RCPSP solving are summarized and categorized. However, in the cos-
monauts training problem there are many other additional constraints that lead to additional difficulties for
365
solving process. In the case of existence of additional constraints, called “time windows” or “minimum and
maximum time lags” (which will be described below), the decision problem of a feasible solution existence is
strongly NP-complete [Bartusch et al., 1988]. Below we list the additional restrictions that arise in the problem
under consideration.
Any task has to be completed before the end of a working day:
h(Sj ) ≤ |H| − pj + 1 ∀j ∈ J. (4)
We divide the operations that take more than one day into one-day operations connected with special strict
precedence relations described below.
Denote as I a set of all cosmonauts of the crew under scrutiny. Each cosmonaut i ∈ I has his own set of tasks
J i , ∪i∈I J i = J. For some sets of tasks there are restrictions on total duration of tasks per day, or per week for
one cosmonaut: ∑
pj ≤ ak ∀i ∈ I, ∀d ∈ D, ∀k ∈ {1, 2, . . . , Kai }, (5)
j∈Aik ,d(Sj )=d
∑
pj ≤ bk ∀i ∈ I, ∀w ∈ W, ∀k ∈ {1, 2, . . . , Kbi }. (6)
j∈Bki ,w(Sj )=w
It means that any cosmonaut i can have no more that ak time units of tasks from the subset Aik per day and
no more bk time units of tasks from the subset Bki per week, where Kai and Kbi are numbers of such subsets.
Such restrictions may be caused by medical standards (for example, a cosmonaut can not be engaged in physical
activity more than a certain number of hours per day) or features of the educational processes.
Each instructor has a workload of no more than ck time units per day:
∑
pj ≤ ck ∀d ∈ D, ∀r ∈ RI , (7)
j∈J R (r),d(Sj )=d
where RI is a set of instructors and J R (r) is a set of tasks, for which resource r is required.
For all tasks j from a special set J t time boundaries [t1j ; t2j ] are established:
t1j ≤ Sj ≤ t2j ∀j ∈ J t . (8)
These boundaries can be both precise and rather extended. In the first case a task has an exact date of its
execution and in the second case — long period of time (for example, a winter forest landing training has to be
in winter).
Some tasks can be performed only in some period of a day (for example, exams have to be in the morning):
h(Sj ) ∈ H j ∀j ∈ J d , (9)
where J d is a set of tasks with day restrictions and H j is a set of possible beginning moments of the task j.
Sometimes it is more convenient to write down this restriction as “some tasks cannot be held during certain
parts of a day” (for example, physical training can not be performed immediately after lunch):
h(Sj ) ∈
/ H̄ j ∀j ∈ J d , (10)
where H̄ j is a set of impossible beginning moments of the task j.
Some tasks are performed by all crew members simultaneously:
Sj1 = Sj2 = Sj3 ∀(j1 , j2 , j3 ) ∈ J 123 , (11)
where J 123 is a set of triples of tasks that have to be simultaneously. Similarly, some tasks are conducted at the
same time for two crew members:
Sj1 = Sj2 ∀(j1 , j2 ) ∈ J 12 . (12)
In addition to the graph of precedence relations between tasks a graph of strict precedence relations G′ = (J, Γ′ )
is introduced. We have (j1 , j2 ) ∈ Γ′ if task j2 must be performed strictly after gj′ 1 ,j2 intervals after the task j1 :
Sj2 = Sj1 + pj1 + gj′ 1 ,j2 ∀(j1 , j2 ) ∈ Γ′ . (13)
366
In some cases a time distance between two tasks is given in weeks with help of another graph G′′ = (J, Γ′′ ):
w(Sj2 ) = w(Sj1 ) + gj′′1 ,j2 ∀(j1 , j2 ) ∈ Γ′′ . (14)
Every week a cosmonaut should remain f i time units for administrative duties (for example, self-preparation,
work with documentation, etc.):
∑
WL − pj ≥ f i ∀i ∈ I, ∀w ∈ W, (15)
j∈J i ,w(Sj )=w
where W L is a weekly workload for a cosmonaut.
Our problem is to find a feasible solution under constraints (1),(3)–(15). Note that we do not formulate the
optimization problem. Schedule of cosmonauts training for a large planning horizon is required for the staff of the
CTC for strategic planning. Solving a problem of optimizing a current weekly or monthly schedule (minimizing
training costs, maximizing the priorities of instructors or cosmonauts) is a tactical problem and the further
direction of our research.
3 Structure of the Input Data
As the planning horizon is very large, a solution of the problem (1),(3)–(15) cannot be obtained directly by modern
solvers. However, taking into account already existing schedules and researching the process of scheduling of the
Cosmonaut Training Center specialists have allowed us to obtain additional information about the structure of
the problem. Analysis of the existing schedules showed the following features.
9 1
2
3
4 10
5 11 12 13
6 7 14
8 18 15 16 17
19
20
21
22 23 24 27
26 28 29 30 31 32 33
25 34
36 37 38 39 35
40
41
42
47
48 49
43 50
44 51
45 52
46 53
54
Figure 1: Graph of precedence relations of on-board systems
• Most of the tasks are organized in the so-called on-board systems. An on-board system is a set of tasks
united by a theme.
• The graph G of the precedence relations at the macro level is given by a graph of the on-board systems
(see figure 1). Each vertex of the graph presented on the picture is, in its turn, also graph of tasks of an
on-board system.
• The graph G allows some decomposition, because at some key time points all tasks of some on-board systems
must be completed, and the remaining on-board systems must not start yet.
• Specialists of the Cosmonaut Training Center identify priority on-board systems, the schedule for which
must be constructed in the first place. These on-board systems are crucial because they require a lot of
resources.
• There is a some set of periodical tasks that are not connected by precedence relations and have to be in the
schedule every week. As a rule, these tasks do not require special equipment and resources which are used
for the study of on-board systems, but they require restrictions like (5), (6), (9).
367
4 Numerical Results
Taking into account the above observations, we propose to build a feasible schedule as follows. Denote as Jper a
set of all tasks that are isolated vertices of the graph G. We divide the set J\Jper into subsets J1 , J2 . . ., Jm−1 ,
Jm . For any Jk and Jl , where k < l, either all on-board systems from Jk are more prioritized than on-board
systems from Jl , or all tasks from the set Jk must be completed earlier than any of the tasks of the set Jl .
Let S be a set of start time moments of tasks from some set Jk . Function Schedule(S, Jk , Jl , Ju ) returns time
moments of tasks of Jl from a certain schedule σ of Jk ∪ Jl ∪ Ju subject to the following conditions:
• start moment Sj (σ) of any task j ∈ Jk is fixed, Sj (σ) ∈ S;
• all constraints for tasks from the set Jk ∪ Jl ∪ Ju are fulfilled.
In other words, we (1) fix start moments of Jk , (2) build a schedule for Jl ∪ Ju provided that all conditions for
Jk ∪ Jl ∪ Ju are fulfilled and (3) save time moments for Jl . If there is no such schedule, the function returns
an appropriate message. To calculate this function, we used solver IBM ILOG CPLEX CP 12.6.21 . Below we
present an algorithm for constructing a feasible solution of problem (1),(3)–(15).
Algorithm 1 Feasible solution building
Precondition: J¯ = {J1 , J2 , . . . , Jm }, Jper
¯ Jper )
1: function Run(J,
2: S ← Schedule(∅, ∅, J t , Jper )
3: Jf ix ← J t
4: for i ← 1 to m do
5: S ← S ∪ Schedule(S, Jf ix , Ji , Jper )
6: Jf ix ← Jf ix ∪ Ji
7: end for
8: return S ∪ Schedule(S, Jf ix , Jper , ∅)
9: end function
Thus, at each step of the algorithm we add to the already existing schedule a new set of on-board systems
that either need to be studied later than the already considered ones, or can be studied in parallel with them,
but have a lower priority. In addition, at each iteration, periodical tasks are added, but the moments of their
starts are not fixed for the next iteration.
In table 1 numerical results are presented. We tested our algorithm on two problems with real world input data.
The first problem is a cosmonauts training planning problem for the case when all cosmonauts are experienced.
It means that each cosmonaut in the crew has the minimum possible set of tasks. The second problem is for all
inexperienced crew members. It is a case of maximum possible size of the set J. We use the following notations:
N is a number of the problem, Plan.horizon is a number of weeks in the schedule, Var. is a number of variables
in the problem, Constr. is a number of constraints, Branches is a number of inner branches of the solver, Time
is a runtime of the algorithm. Number m of subsets Ji was equaled to 10. The calculations were performed on
a workstation with an Intel Xeon processor E5-2673, 2.4GHz and 15Gb of RAM.
Table 1: Numerical results
N Plan.horizon Var. Const. Branches Time, m:c
1 21 4572 149997 123613 3:45.46
2 60 6963 156168 392026 9:56.16
5 Conclusion
The article presents a mathematical formulation of the cosmonauts training planning problem. An algorithm
based on CP for finding a feasible solution of the problem is proposed. The algorithm was tested on real data
1 http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/
368
for a large planning horizon. However, we did not consider a complete set of on-board systems, since we do not
yet have real data for the remaining cosmonauts trainings. The solving of the cosmonauts training planning
problem on the entire horizon of planning is our priority goal. Also our further research will be devoted to the
construction of optimal weekly and monthly schedules with a known set of tasks.
Acknowledgements
This work was supported by the Russian Science Foundation (grant 17-19-01665).
References
[Musatova et al., 2016] Musatova, E., Lazarev A., Ponomarev K., Yadrentsev D., Bronnikov S., & Khusnullin N.
(2016). A Mathematical Model for the Astronaut Training Scheduling Problem. IFAC-PapersOnLine,
49(12), 221-225.
[Bronnikov et al., 2015] Bronnikov, S., Dolgui, A., Lazarev, A., Morozov N., Petrov A., Sadykov R., Sologub
A., Werner F., Yadrentsev D., Musatova E., & Khusnullin N. (2015). Approaches for Planning the ISS
Cosmonaut Training. Preprint 12/15, Faculty of mathematics, Otto-von-Guericke-University Magde-
burg.
[Lazarev et al., 2016] Lazarev, A.A., Bronnikov, S.V., Gerasimov, A.R., Musatova, E.G., Petrov, A.S., Pono-
marev K.V., Kharlamov, M., Khusnullin, N.F., & Yadrentsev. D.A. (2016). Mathematical modeling of
the astronaut training scheduling. UBS, 63, 129154.
[Dechter, 2003] Dechter, R. (2003). Constraint Processing. San Francisco, USA: Morgan Kaufmann Publishers.
[Artigues et al., 2008] Ed. Artigues, C., Demassey, S., & Neron, E. (2008). Resource-Constrained Project Schedul-
ing: Models, Algorithms, Extensions and Applications. Wiley-ISTE.
[Bartusch et al., 1988] Bartusch, M., Mohring, R.H., & Radermache, F.J. (1988). Scheduling project networks
with resource constraints and time windows Annals of Operations Research, 16, 201-240.
[Brucker et al., 1999] Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E. (1999). Resource-constrained
project scheduling: Notation, classification, models, and methods. European Journal of Operational
Research, 112, 3-41.
[Kolisch & Hartmann, 2006] Kolisch, R, & Hartmann, S. (2006). Experimental investigation of heuristics for
resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1),
23-37.
[Valls et al., 2003] Valls, V., Quintanilla, M.S., Ballestin, F. (2003). Resource-constrained project scheduling: A
critical activity reordering heuristic. European Journal of Operational Research, 149(2), 282-301.
[Homberger, 2007] Homberger, J. (2007). A multi-agent system for the decentralized resource-constrained multi-
project scheduling problem. Intl. Trans. in Op. Res., 14, 565-589.
[Debels & Vanhoucke, 2007] Debels, D., & Vanhoucke, M. (2007). A Decomposition-Based Genetic Algorithm
for the Resource-Constrained Project-Scheduling Problem. Operations Research, 55(3), 457-469.
369