Adaptive flight program design, cargo flow and resource calculation scheduling for Russian segment of the International Space Station
The International Space Station (ISS) is one of the most complex projects in the history of mankind. Large groups of scientists and engineers from Russia, the USA and other countries are involved in its implementation.
Cargo flow management is one of the most important life-support tasks for ISS maintenance. It concerns the delivery of the important cargo to the station, such as air and water, fuel, food, equipment, as well as delivering results of experiments and other cargo back to Earth.
Cargo flow scheduling requires consideration of a number of various factors, decision-making criteria, constraints and preferences, including warehouse condition, station equipment resources, changing need for fuel, water and food, ballistics specifics in station movement and solar activity, types of spaceships and docking modules, and others.
Complexity of the problem is defined by the following aspects:
- more than a dozen of cargo and piloted spaceships dock to the station annually:
- the main priority is health and safety of the space crew;
- first and foremost, it is necessary to provide the crew (which changes regularly) with the supply of air, water, food, fuel, etc.;
- it is also important to deliver laboratory equipment, various materials and tools to the space station for the useful activity of the crew;
- cargo flow scheduling requires consideration of specific features of spaceship flights, launching, docking and undocking time and hundreds of other parameters;
- delivered cargo contains thousands of items and dozens of thousands of units of products and materials;
- constant monitoring of the available stock of resources on board via the on-board system IMS is required;
- failures and launch delays require rescheduling, taking into account the missed delivery cycle;
- it is necessary to track the expiring cargo and dispose of it in order to make space for allocation of the next shipment of cargo;
- cargo delivery plan has to be coordinated with the on-board scientific experiments program;
- ISS servicing is carried out under conditions of severe space, weight and time constraints.
Scheduling process specifics:
- though the Russian ISS segment is being scheduled, we have to consider plans of three other space agencies as well;
- there are strategic plans for several years, as well as annual and semi-annual tactical plans, including operational daily plans;
- 8 chief dispatchers (planners) and 150 cargo suppliers (curators) control the RS ISS scheduling process;
- there can be conflicts between the cargo with different priorities, etc.
Any significant event like changes in launch, docking and undocking dates, cargo spaceship failure, crew changes or on-board emergency jobs triggers a chain of rescheduling of many interconnected tasks that requires resource recalculation.
For instance, if the space waste appears on the station trajectory (due to the satellite failure, for example), it requires an attitude maneuver of the station and its trajectory correction. This, in turn, requires engines start and fuel consumption, which means that the next shipment of fuel has to be larger, and that leads to cargo rescheduling, etc.
Spaceship capacity is limited, so sudden need for delivery of some additional cargo, will cause the reduction of delivered amount of fuel (water or any other cargo), and that will cause rescheduling of the future cargo transportations.
Up until recently, cargo planners and curators had to schedule the ISS cargo flow manually and a working schedule took numerous iterations and constant interaction to reach a compromise solution.
The main challenge of scheduling is that all the plans and decisions are connected and it requires semantic concordance and actions coordination, considering all the listed factors.
A multi-agent system for efficient cargo flow management has been developed. Scheduling of flight programs, cargo flow and resources for ISS has several interconnected stages with different scheduling horizons.
At the first stage, a strategic model of cargo flow is created, which helps to calculate the number of required transportation flights per year based on the number of expected expeditions and crew members. At this stage, it is important to achieve an agreement between all involved parties on the number and times of dockings and un-dockings of spaceships to ISS modules, considering timeframes of possible launches of spaceships, the solar activity, configuration and expected position of ISS, space crew requirements, etc. Several versions of the flight program are created and examined at this stage before the corporation management and space research program sign and publish the final plan.
Then the interactive design of the flight program starts. It involves numerous iterations for conflicts resolution between curators and planners. At this stage, cargo volumes are distributed among transportation space flights and manned flights based on the data on the average daily consumption of resources by the space crew and station systems. The signed-off flight program contains the number of astronauts and information about dates of launches and dockings. Fuel deliveries are calculated based on the data about the planned ISS position corrections and its current state, which is also important for docking calculations, scheduling of extravehicular activity with space experiments and other space operations.
Cargo flow plan is used for scheduling cargo disposal and return from the ISS back to Earth on the cargo ships that are later flooded in the ocean, or on the piloted space ships that bring the results of experiments back to Earth.
Integration with ISS resource management system allows for updating the schedule daily according to the actual data and initiating rescheduling in real time.
Virtual World of each scheduler is based on the Demand-Resource Network concept and has specialised types of agents.
For example, Flight Program Scheduler has Spaceship Agent, Expedition Agent and Astronaut Agent types, whilst Cargo Flow Scheduler has Cargo Agent and Flight Agent types. Some agent types exist in two or more Virtual Worlds, serving different functions, but at the same time facilitating interaction between the schedulers.
If the launch of a spaceship flight is postponed due to its preparation delay, the Flight Agent (that exists in the Flight Program Virtual World) changes its plan, i.e. shifts the dates of the launch, docking and undocking. It acts both in flight program and cargo flow scene, therefore it reports about the changes to the Cargo Agent in cargo flow scheduler, and cargoes that need to be delivered earlier can “switch” to the other spaceship. Vice versa, if cargo volume is reduced, the utilization rate of the flight can become too low, which will increase the Flight Agent dissatisfaction.
This agent will try to shift its flight to a later time in the flight program to become more efficient and attractive for other Cargo Agents.
The system was designed in 2010-2012 and is in experimental and industrial operation since 2013.
The following results of the system operation and integration in 2010-2014 were obtained:
- the number of errors in the RS ISS documentation on cargo flow was sufficiently reduced (in practice, almost brought to nought);
- it is now possible to monitor and control the unnecessary (excessive) or missing equipment and station resources;
- RS ISS cargo flow design time is down from 176 to 8 hours and the coordination process now takes 88 hours instead of 264 hours;
- all the hundreds of yearly change notifications are now formed automatically (previously, each took 1-2 hours);
- automatic cargo flow update saved up to 200 hours per year;
- adaptive cargo flow rescheduling (for example, in case of a risk of losing a cargo ship) takes 8 hours instead of 1 month;
- 320 hours per year are saved on the emergency backup flight program design;
- total time of cargo allocation schedule design decreased from 264 hours to 128 hours;
- total time saving in cargo flow scheduling is 544 hours per year for TCV (Transport Cargo Vehicle) “Progress” and 320 hours for Manned Transport Vehicle “Soyuz”;
- automatic check of the disposed cargo list for backups, carried out by Mission Control Centre, saves around 312 hours per year;
- food, water, fuel and crew time balance calculation time-saving is 10-15% for each module, which is about 270 hours per year.
It is important to note, that the System enabled the client to design and compare several options of flight programs and cargo flow scheduling, including possible reactions to disruptive events, like the TCV “Progress” failure back in 2012.
Adaptive scheduling of machine-building enterprise workshops
The key result of the system implementation for increasing operation efficiency of a machine-building enterprise is to reduce the workload and scheduling time, therefore enabling different schedule options design. Also, its goal is to support negotiations and interactions focused on finding the best reaction to the disruptive events and schedule adaptation “on-the-fly”.
These features help to minimize the possible risks and to be prepared for the disruptive events operational control.
Managing resources of machine-building enterprise workshops is a complex multi-criteria task that often requires situational solution, considering order specifics, implementation technologies, resources availability, corporate economy and a number of constraints and preferences.
Project goal is to provide dynamic shift-day tasks design for workshop workers of the electronic engineering enterprise.
Tool-shop problem complexity is defined by the following parameters:
- number of all the workshop employees – 120 operators (turners, technicians, milling-machine operators, etc.);
- product range: work tools, molding tools, die tools, custom tooling, electrode holders, milling tools, package, etc.;
- order volume is about 30-40 product orders per day, each consists of 20-30 components;
- machine tool fleet (lathe machines, grinding machines, milling machines, grinders, drilling machines, boring machines, furnaces, presses, etc.) contains 300 equipment units;
- average order execution labor intensity is 35 working hours (in the tool shop);
- maximum labor intensity is 4000 working hours (in the tool shop);
- workshop monthly workload is 17000 working hours;
- maximum number of components in a product is 150;
- maximum number of nesting levels is 10, etc.
One of the most complex projects of manufacturing workshops is connected to the jet aircraft engines assembly workshop:
- engine assembly – more than 50000 parts;
- each product requires 10 to 300 technological operations;
- 10 orders per day, scheduling horizon – from a month to a year;
- 150 thousand interconnected tasks on scheduling horizon;
- it is important to consider technological process specifics, workers’ skills, possible defects, stocks availability, workshop sections organization specifics, etc.
Typical decision-making criteria in machine-building industry are:
- to provide the highest quality of the product assembly;
- to minimize the order execution cost;
- to minimize the order execution time;
- to provide a balanced resource load;
- to provide minimum risks of missing the order deadline, etc.
The problem of shift-day tasks management for products manufacturing can be defined as the process of allocation, scheduling, optimization and control of the workshop manufacturing resources (for instance, machines, workers, materials, subproducts, etc.) for the orders in time. This process is carried out under the frequent occurrence of disruptive events, such as new orders arrival, changes in the order parameters, new resources appearance or failure of the existing ones, delays, errors, etc.
At the first stage, a task of resource management automation and shift-day tasks dynamic redesign in one workshop was set. The chosen workshop is one of the most problematic at the enterprise.
In order to solve the problem, a multi-agent system for adaptive real-time resource management of a machine-building enterprise was designed.
The basic system functionality:
- Directory management: the system allows imputing data about customers, orders, technological processes, machines and workers’ skills..
- Automated dynamic scheduling:
- the system builds a master-plan and shift-day tasks automatically;
- shift foreman receives a list of the top-prioritized tasks for his workers daily and makes decisions about tasks reallocation;
- the foreman can approve the suggested shift-day task fully or partially with a possibility of rescheduling;
- flexible rescheduling in case there are defective products, etc;
- Facts input (work performance marks): the developed system allows inputting work performance marks and building a shift report in electronic form suitable for an autofill of standards, technological operations and assembly units fields, automatic calculation of the estimation fields and work progress for every worker.
- Integration with the ADEM, Team Center, 1C and other systems:
- orders import from the enterprise sales department;
- technological process duplication for certain assembly units;
- assembly units tree duplication including data about materials;
- automated generation of the subproducts work orders;
- time standards import (for example from the ADEM system);
- total workload automated calculation;
- salary accounting and export to the 1C.
- Analytics for workshop and enterprise management:
- business radar for workshop operation forecast, considering the workshop current situation;
- reports generation for orders and workshop resources.
- Convenient services for a foreman:
- for the daily use of the system: prompt messages and highlights, rescheduling in case of defects, transportation matrix consideration, etc.;
- touch-sensitive terminals for workers, tablets for foremen, etc.
- Worker’s terminal gives the ability to input workers preferences and operations selection for the task, work performance marks, events input, etc.
The developed system can be integrated with typical PLM- and ERP-systems of the enterprise.
Adaptive multi-agent schedulers rapidly react to disruptive events and try to increase the enterprise profit and other significant factors by improving the allocation of resources to orders, for instance, adjusting the orders operations when there is a downtime for workers.
The schedulers are designed to work interactively with workshop managers, foremen and workers, allowing them to change the schedule designed by agents based on the events in real time.
Virtual World of the workshop adaptive scheduler contains the following agents: Order Agent, Enterprise Agent, Worker Agent, Machine Tool Agent, Process Agent, Operation Agent, Product Agent, Materials Agent and others. Examples of agent tasks are: for Order Agent, it is to get the best possible resources and workers; for Worker Agent – to get the schedule, which will ensure the best wages or tasks that will improve worker’s skills, and for Machine Tool Agent – to get the full workload, etc.
Agent negotiations are aimed at conflicts resolution. These conflicts are usually caused by a new operation that wants to occupy the time slot, already occupied by other operations. A conflict is usually eliminated by a series of negotiations attempting to move the previously allocated operations forward or back in time to accommodate the new operation.
This approach provides a number of significant advantages in comparison to the traditional resource scheduling methods.
As a result, continuous dynamic, flexible and efficient adaptive rescheduling of the workshop operation based on the real-time events is provided.
The first industrial version of the adaptive scheduler was developed in 2011, and for several years now it has been in the continuous operation at a number of enterprises, including “Axion-Holding”, JSC “Avia-Agregat”, JSC “Kuznetcov” and others.
At the XXII annual exhibition “Soft-tool – 2011” for information and communication technologies, our system was awarded as the best product in the automated management systems area.
Up to 30 users interact with the system daily at each enterprise, including mostly workshop managers, planning and logistics office dispatchers, foremen, production engineers, rate-setters and supervisors.
Among the main advantages of the system, users name the following:
- Full transparency of the workshop operation, which allows maintaining control and optimizing the work process.
- Workshop productivity increased while the number of resources remained the same.
- The input data about objects and technological processes is reusable, which leads to the increase of labor efficiency for production engineers and rate-setters.
- The workshop system is integrated into the enterprise informational space: orders are being imported from the Project Management Office (PMO) into MAS, workers’ wage is calculated based on the MAS data and is sent to the 1C.
- Integration with the enterprise PMO reduces the workload on the Planning and Logistics Office (PLO) and increases efficiency (response time) of the new orders arrival, which, in turn, speeds up the new parts manufacture.
- Our system supports full management cycle: from events’ input to results scheduling and monitoring via the work performance marks and to the “plan vs. fact” analysis.
- Workshop operation schedule can be quickly and flexibly rearranged or recalculated, considering specifics of every order and resource.
- The transition process from the paper to the electronic form of documents storage in workshops became faster.
- Decisions became more reliable, valid, accurate and free from human error.
- Strategic scheduling also became easier, quicker and more efficient. “Master-plan” AWS (automated working station) builds a production schedule for the scheduling horizon of up to 2 years in 10-15 minutes.
- Foremen’s special knowledge about machines, technologies and workers are now objective and can be used for the further increase of the scheduling quality.
- A platform for the workshop development without increasing the number of the management personnel has been created.
A significant increase of workshops’ management efficiency is noted due to the following features of the system application at “Axion-Holding”:
- Production cycle analysis can be performed to determine when and where there were difficulties during order execution (when the technology was given, when it was normalized, when the materials arrived and when the order execution started, when the order was made and which operation caused the order delay) – 256 working hours.
- Workers productivity and workload is being analyzed regularly – 48 working hours (during the first 3 months of implementation the system showed that about 17% of the operations have an excessive labor intensity).
- Shift-day tasks are automatically formed one month ahead. Before the system implementation, that process took 2 workdays of four people. It saves about 64 working hours a month.
- All of the routine operations are now automated, which reduces the management labor intensity (for instance, the costs and amount of work in progress are calculated automatically, as well as the shift-day tasks) – 528 working hours.
- Basic operations workload forecast allows for analyzing thedemand for workers of a certain specialization – 36 working hours.
As a result of the system implementation in one workshop, the savings are about 1163 working hours a month or 7 man-hours a month, which in 2013 equaled 84 * 40 000 = 3 360 000 rubles per year.
For a large engineering enterprise with 20-30 workshops, the total savings can exceed the amount of 60-90 million rubles per year.
Adaptive management of mobile teams for gas distribution companies
Our customer manages a big regional network of emergency maintenance teams, including call-center, control center and 27 equipped mobile teams of workers servicing gas supply facilities of industrial enterprises and hundreds of thousands of region citizens.
We joined the project when there were no call- or control centers, and mobile teams were distributed according to districts. As a result, since orders came irregularly, some teams constantly stood idle while others were overloaded.
Besides, it was initially supposed that teams come to the office in the morning, get tasks from dispatchers and then execute these tasks until evening. It is obvious that even with GPS/GLONASS sensors in the cars, it was difficult to re-direct teams to new urgent emergency and maintenance orders, since work plans and volumes were absolutely unclear.
As a result, unprocessed orders accumulated and the company’s KPI was decreasing. Ineffective routes were planned with overmileage, and gas consumers were unsatisfied since it was difficult to schedule work of the teams.
Moreover, dispatchers were overloaded and unsatisfied with their work and concentrated only on their own orders, not having the full vision of the situation. Attempts to coordinate work of the service when urgent unforeseen events occurred faced resistance of teams. Hence, the number of high-priority but unsatisfied orders was increasing.
Plans were disrupted quite often due to changes of situation, including cancellations of orders, transport breakdowns, delays in task execution, etc.
As a result of our preliminary survey, the following key problem features of planning processes were detected:
- Complexity of distribution of a large number of orders with limited resources and time.
- Need for quick, flexible and efficient reaction in conditions of uncertainty and fast-changing situation
- High load of dispatchers bearing personal responsibility.
- Low performance efficiency of mobile teams due to non-optimal distribution of resources depending on orders. This resulted in delays, idle run or lack of qualified and well equipped teams.
- Need for an individual approach to each occurring order and resource.
- Low efficiency and coordination of performance of teams and dispatchers.
- Human factor as the reason of failures and mistakes.
- Difficulties with growth and development of the company connected with further increase in the number of consumers.
The customer had to start searching for a solution of the problem and studied all proposals existing in the market.
It was decided to find an adaptive scheduler that would first of all be capable of decreasing the following:
— Labor intensity and scheduling time of servicing tasks;
— total transport mileage of mobile teams;
— time for processing orders for servicing;
— total number of unexecuted orders.
In other words, the customer needed an adaptive scheduler capable of increasing productivity and efficiency of performance of emergency and maintenance teams.
Such tasks are characteristic of many other operation fields of mobile teams, including teams of firemen, policemen, electricians as well as workers of water supply and waste water treatment enterprises.
To solve the problem, we developed a multi-agent system for managing mobile teams in real time, capable of allocating, planning and optimizing tasks between teams “on the fly”, according to events occurring in real time.
Main functions of the developed system include:
- keeping journals of teams and shifts.
- knowledge base for formalization and accumulation of peculiarities of orders and resources.
- intelligent decision-making support of a dispatcher in order execution with real-time situation analysis.
- Selection of a team which suits the most for task execution;
- Planning the route of a team taking into account traffic regulations, traffic jams, etc.
- Planning teams’ routing and driving time
- Adaptation of schedule in case of unforeseen events;
- Minimization of driving time (as soon as possible for urgent orders);
- Decrease of total mileage (for low-priority tasks);
- Monitoring and control of task execution.
- Efficient adaptive planning of works depending on events in real time (with changing work plans assigned before).
- Providing individual approach to planning of each order.
- Display of routes and schedules on the map.
- Monitoring and control of execution of business processes using inexpensive mobile phones.
- Rescheduling in case of discrepancies between the plan and the actual situation.
- Integration with the Call Center, accounting systems, wages, etc.
- Forming reports on teams’ performance.
Interaction with users of the system is provided via mobile phone of a team’s supervisor. The phone receives information about orders, and the team can enter information about events into it: successful order execution, delays or breakdowns, time until order completion, etc.
New orders arrive in the Call Center, where operators introduce them into the system and see them on the map. After that, orders go to dispatchers.
The system knows all the information about the order and data about location, as well as the current load and plans of teams, hence it selects the team which is the nearest and is going to be free, and offers the order to it. If successful, the team is reserved for this order.
If a new order appears in the district close to the team which is going to be free soon, dispatcher can reach an agreement with the client that the team will come as soon as possible. Hence, there is no need to come back to the head office and go to that district again. This allows for saving time and efforts and reduce idle mileage.
Similarly, re-routing is possible in case of traffic jams or road repair works as well as any other unforeseen events.
Virtual world of mobile teams consists of typical agents of demand and resource network for building self-organizing schedules:
- Order Agent. Its aim is searching for the most suitable team capable of starting and finishing work as soon as possible and with the highest quality.
- District Agent helps balancing allocation of cars between districts with due account of the forecast of order arriving.
- Route Agent. Its aim is to significantly reduce driving time between orders and complete as many orders during the shift as possible.
- Team Agent. Its aim is searching for orders and routes in order to increase productivity level of the team.
- Enterprise Agent tries to improve the most problematic parts of the schedule of the company’s mobile teams.
All decisions on allocation and scheduling of teams’ works are the result of self-organization and negotiations between corresponding agents. They are proposed to dispatcher who can change schedule of any team interactively.
Using the adaptive scheduler for processing incoming orders in real time allowed for increasing productivity level of service teams by 40%. Now each gas distribution team executes on average 12 tasks a day instead of 7 as it was before.
Besides, the developed scheduler enables operators, technical specialists, dispatchers and managers of the company to get a clear vision of works of all teams at any time. It includes not only displaying location of the team on the map, but also showing their work plan for a certain period of time. That is where and which task a team is executing at the moment, current progress of task execution for each team; current productivity level of each separate specialist and each team as well as of the company on the whole and of costs for each operation.
Important results that have been recognized by the customer include:
- Reducing reaction time to unforeseen events;
- Increasing interest and productivity levels of the teams’ work;
- Support of flexible planning in real time;
- Reducing labor intensity and the number of dispatchers’ mistakes;
- Reducing time for training new dispatchers.
Multi-agent system «Smart Field Service» won a prize “Product of the year” at the international exhibition «Soft-Tools — 2011» in the nomination “The most technological Startup of the year”.