A Task Planning Problem in a Home Care Business ^†

Abstract

This work focuses on the study of a task planning problem in a home care business. The objective is to schedule the working days of the available nurses, in order to assist all the active clients. Due to the large size of the real cases that must be faced, it is not possible to obtain exact solutions of the problem in short periods of time. Therefore, we propose an algorithm, which is based on heuristic techniques, to provide approximated solutions to the incidents that arise daily in the company. The designed algorithm is validated by obtaining the automatic schedule to solve a battery of real-like examples.

1. Introduction

Home health care is a resource that allows elderly and/or dependent people to continue living at their homes despite being in a situation of dependency or in need of assistance to carry out different tasks of their daily lives. The company we are working with has been providing home care services since 1997, both in the city of A Coruña and in the neighboring municipalities. This company faces a scheduling problem, in which we have to determinate the routes the employees must follow and set the exact time at which the caregivers must perform the services assigned to them.

1.1. Concepts

The users of the service provided by the company are those who need health care support or require help in carrying out certain tasks and, to improve their quality of life, hire the company’s services. These users must specify the number of services they require, detailing the day and the time frame (morning, noon, afternoon or evening) within which they must be completed. Also, they should indicate the available (when the service must be performed) and optimal (when the user prefers to be attended) time windows of each service.

To provide its services the company has a set of caregivers, which may increase or decrease depending on the volume of work available. These caregivers are responsible for visiting users’ homes (at the time they have been instructed to do so) and carrying out the tasks assigned to them (for example: cooking meals, monitoring medication, cleaning chores, etc.). For each caregiver and user, the company sets a level of affinity, which establishes how suitable the caregiver is to assist the user.

Therefore, the company must carry out a work plan where, for each caregiver, the services to be provided are specified (establishing the tasks to be performed in each of them) and the times at which those services must be completed (always upholding the availability time windows established by the users). This work plan arranges the whole week, so the schedule is repeated over time until the need to modify it arises. In order to carry out this task, the company has several organizers who are in charge of managing the working days, for each caregiver, manually. Each organizer works with a set of users and assistants, according to the areas or neighborhoods he/she operates in.

1.2. Objective

The company’s objective is to obtain a computer tool that automatically modifies the caregivers’ previous plan in order to solve the following incidents: (i) registration of a user, (ii) discharging a user, (iii) increasing the number of services required by a user, (iv) decreasing the number of services required by a user, (v) alteration of any of the parameters of a service, (vi) repetition and/or combination of the previous instances.

To obtain the new schedules, the company asked us to consider the following objectives:

• The new plans should minimize time lost between services.
• The new plans should maximize the affinity levels between users and the caregivers that visit them.
• We must try not to change the previous planning in excess.
• The new plans should respect, as far as possible, the optimal time windows of the services.

The purpose of this work is to provide the company, employing different operational research techniques, with a computer tool that allows them to automatically modify the caregivers’ schedules in order to solve the abovementioned incidents.

2. Problem Solution

The problem presented by the company has been modeled as an integer linear programming problem. For real cases, such as those faced daily in the company, it presents a large number of variables and constraints. Therefore, it is not always possible to obtain the optimal schedule by solving the linear programming problem.

Because of this, the problem must be solved in an approximated way, through the use of metaheuristic techniques, in order to obtain admissible solutions in short computational times.

Algorithm

The algorithm developed to solve the company’s planning problem is based on the simulated annealing method. This algorithm consists of re-scheduling the services and optimizing the working days of the caregivers.

The algorithm is designed to solve the incidents the company works with, avoiding excessive modification of the previous planning. The aim we follow is to make the work plans feasible while trying to ensure that the caregivers have no gaps in their working hours. The most important steps of the algorithm are presented below:

• Preparation of elements: The algorithm starts with an initial solution, which is the previous schedule assigned to the caregivers. The services that need to be removed from this solution are deleted and, at the same time, we select the services that need to be rescheduled and the ones that need to be included in the plans.
• Service planning: Each of the services that must be planned is assigned to the best caregiver available. After that the service is scheduled in such a way that causes the least amount of overlap and break gaps (between the new one and the rest of services assigned to said caregiver). To establish how suitable a caregiver is to assist a user, the following aspects are considered: (i) the affinity level between them, (ii) the difference between the hours worked by the assistant and those specified in her contract, and (iii) the travel time from that user’s home to all the clients the caregiver is working with. In some cases, we don’t have services to plan, so the algorithm goes directly to the optimization phase.
• Optimization: After assigning a service to a caregiver, the schedule is optimized by applying the simulated annealing method to eliminate possible overlaps or breaks in the schedule. If, after the optimization, the previous overlaps have not been eliminated, the service must be assigned to the next best caregiver available. In the cases where there are no services to be scheduled, the caregivers’ plan is optimized to eliminate possible break gaps in it (in such circumstances there is no overlap between services).
• End: When all the services have been correctly planned, the overlaps have been eliminated and the breaks have been optimized, the algorithm ends, returning the optimized planning as the new solution.

The movements we considered in the implementation of the simulated annealing method are: rescheduling one service, rescheduling several services at once, exchanging the time in which two selected services are carried out, exchanging the caregivers that conduct two selected services, and changing the caregiver that performs a service.

The objective function considered to evaluate a schedule in the simulated annealing method is a lexicographic function, in which we want to minimize the following aspects: (i) the overlap time between services, (ii) the time lost between services, and (iii) the time that the services are carried out outside their optimal time window.

3. Conclusions

In this work, we analyze the problem presented by the company and we design a resolution method based on the metaheuristic technique of the simulated annealing. The purpose of this algorithm is to solve the incidents considered by the company, trying to modify the original schedules as little as possible.

To check the algorithm’s performance, we design a series of examples, in which we take into account all the different incidents that the company deals with, and we solve them using the method previously designed. Based on the results obtained, we can assume that the algorithm’s behavior is acceptable, since it correctly solves all the incidents considered while using low computational times.