Grid-enabled evolution strategies for large-scale home care crew scheduling Articles uri icon

publication date

  • June 2018

start page

  • 1261

end page

  • 1273

issue

  • 2

volume

  • 21

international standard serial number (ISSN)

  • 1386-7857

electronic international standard serial number (EISSN)

  • 1573-7543

abstract

  • The home care crew scheduling (HCCS) problem is a planning task whose goal is to allocate a set of professional caregivers in the most efficient way to perform a number of assistencial and health care visits to the customers private homes. This is part of an important trend in advanced health care systems, to promote "independent living" specially in situations of dependency on long-term care. This not only ensures a higher quality of life but also a lower cost for society. Real instances of the HCCS problem are large and highly constrained due to both caregivers' contract limitations and customers' needs. This paper presents an advanced parallel model that solves HCCS problems using a grid-based asynchronous evolutionary algorithm (EA). Our approach has been tested using a grid computing facility of up to 300 nodes. The algorithm is a modified (1 + lambda) EA, parallelized using a master/worker model that minimizes communication requirements and processor bottlenecks by distributing both the execution of the EA operators and the evaluation of solutions. We have used three large real-world instances provided by a private company to perform experimentation with different configurations of the EA and number of workers. Results show that our algorithm achieves solutions that clearly outperform the solution provided by the company and the grid-based algorithm is able to handle real world HCCS problems

keywords

  • home care scheduling; parallelism; grid computing; evolutionary algorithms; optimization; metaheuristics; management; models