The cosmonauts training planning problem is a problem of construction 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 resourceconstrained 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.
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 programming [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
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: We input a set of tasks which are active at the time moment t:
Sj − Si ≥ pi ∀(i; j) ∈ Γ:
At = {j ∈ J | Sj ≤ t < Sj + pj }: 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: j∈At (1) (2) (3) 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 solving: priority-rule based scheduling methods, truncated branch-and-bound, integer programming based heuristics, 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 cosmonauts training problem there are many other additional constraints that lead to additional difficulties for 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: 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:
∑ j∈Aik;d(Sj)=d
∑ j∈Bki;w(Sj)=w pj ≤ ak ∀i ∈ I; ∀d ∈ D; ∀k ∈ {1; 2; : : : ; Kai}; pj ≤ bk ∀i ∈ I; ∀w ∈ W; ∀k ∈ {1; 2; : : : ; Kbi}: 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: where H¯ j is a set of impossible beginning moments of the task j.
Some tasks are performed by all crew members simultaneously: 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:
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: 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): where J d is a set of tasks with day restrictions and Hj 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 ) ∈ Hj ∀j ∈ J d; h(Sj ) ∈= H¯ j ∀j ∈ J 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 [tj1; tj2] are established:
∑ j∈JR(r);d(Sj)=d
pj ≤ ck ∀d ∈ D; ∀r ∈ RI ; tj1 ≤ Sj ≤ tj2 ∀j ∈ J t: Sj1 = Sj2 = Sj3 ∀(j1; j2; j3) ∈ J 123;
Sj1 = Sj2 ∀(j1; j2) ∈ J 12: Sj2 = Sj1 + pj1 + gj′1;j2 ∀(j1; j2) ∈ Γ′: (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) 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) ∈ Γ′′:
Every week a cosmonaut should remain f i time units for administrative duties (for example, self-preparation, work with documentation, etc.):
W L −
∑ j∈Ji;w(Sj)=w
pj ≥ f i ∀i ∈ I; ∀w ∈ 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
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 (14) (15) 6 5 8 4
10 7 2 25 2 3 1 18 • 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).
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 1: function Run(J¯, Jper) 2: S ← Schedule(∅; ∅; J t; Jper) 3: Jfix ← J t 4: for i ← 1 to m do 5: S ← S ∪ Schedule(S; Jfix; Ji; Jper) 6: Jfix ← Jfix ∪ Ji 7: end for 8: return S ∪ Schedule(S; Jfix; 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. 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).