OREANDA-NEWS. July 10, 2015. The Institute of Mathematics for Industry(1) at Kyushu University (IMI) and Fujitsu Laboratories Ltd. today announced the development of a supercomputer-based technology that can quickly formulate optimum work schedules for disaster recovery, such as for repairing lifelines and road networks.

Major disasters can bring secondary disasters and a variety of other outcomes, such as impassable roads, and conditions can change dramatically in a short period of time. This creates an urgent need to quickly formulate schedules for recovery work and to take swift action. However, since conditions can change even as plans are being formulated, it is difficult to perform the calculations based on massive volumes of data in real time needed to propose an ideal plan that reflects those changing conditions.

Fujitsu Laboratories and IMI have developed a numerical-optimization technology that runs on a supercomputer to efficiently formulate large-scale recovery plans while taking into account complex conditions on the ground, creating real-time scheduling for recovery work.

This makes it possible to put together the newest recovery plans that respond to evolving conditions, such as changes in the extent of the affected area or the pace of recovery work, contributing to better optimized disaster responses.

Details of this technology are being presented by Kyushu University at the International Symposium on Mathematical Programming (ISMP2015), opening July 12 in Pittsburgh, and at the International Supercomputing Conference (ISC15), opening July 12 in Frankfurt.

Background

Major disasters can bring secondary disasters and a variety of other outcomes, such as impassable roads, and conditions can change dramatically very quickly. This creates an urgent need to expedite the formulation of schedules for recovery work and to take swift action, including evacuations, instructions, and rebuilding plans. Implementing these measures requires that massive volumes of data, including geographic data and data on the disaster, be processed in real time in order to formulate an optimized plan.

Issues

During disasters, the restoration of lifelines and other efforts are undertaken under a complex set of conditions that make the efficient pursuit of optimum work schedules no easy task. For example, interdependence among utility workers, which may constrain sequences of operations and require that joint operations be conducted mid process, and the working hours and skills of individual workers must be factored in. Existing techniques for formulating optimized schedules in large-scale disaster-recovery work have not been able to deal with expanding the scope of recovery work as the disaster itself unfolds.

About the Research and Technology

The division of Fujitsu Social Mathematics and Laboratory of Advanced Software in Mathematics in IMI and Fujitsu Laboratories have jointly developed a numerical-optimization algorithm that can quickly propose personnel allocation and scheduling for disaster recovery, even under complex constraints. Run on a supercomputer, this algorithm can produce real-time results.

The partners developed a localized-search algorithm that can efficiently formulate an optimized work schedule, taking into account numerous complex constraining conditions, including the ordering of task priority, merging tasks, prioritizing by area of activity, and limits on working hours, from among the vast number of possible scheduling combinations.

This algorithm runs on Fujitsu's computer server FUJITSU Server PRIMERGY CX400, the high performance computing server system used by Kyushu University's Research Institute for Information Technology, and uses highly efficient parallel computing to calculate schedules in real time.

This research makes use of and trials High-Performance Parallelization Technology for Multi-Processor Shared-Memory Computer Systems, software being developed for the Advanced Computing & Optimization Infrastructure for Extremely Large-Scale Graphs on Post Peta-Scale Supercomputers project in the Japan Science and Technology Agency's CREST strategic-research program.

Research and development of the localized-search algorithm was supported in part by Grant 26730010 from the Japan Society for the Promotion of Science.

Results

When used with 506 recovery sites and 64 work teams, this technology was able to formulate an appropriate recovery-work schedule that satisfied all constraining conditions in roughly three minutes. This would be able to quickly present the most recent plan that responds to changing conditions, including the extent of an area affected by a disaster and the pace of recovery work.

Also, the newly developed algorithm and computing environment have potential applications for delivery scheduling in distribution and logistics, as well as to related work schedules and personnel allocations. It may be possible to formulate detailed delivery plans that respond to complex conditions during the delivery process.