## 3 Home Health Care Problem Definition
### Jobs  
Within this model, a patient has a list of needed jobs. The jobs \(\mathcal{J}_{\mathcal{P}}=\{1,\ldots,J\}\) are care services that must be performed at patients' homes and have different natures: providing medication, performing an injection, changing a bandage, etc. A single patient may relate to one or more jobs. However, job \(j\in\mathcal{J}_{\mathcal{P}}\) belongs to a unique patient. According to [PERSON] et al. [21], a patient is mostly related to three jobs per day. A caregiver usually performs six jobs per day. Each job has a priority and arduousness score [25; 26]. The lowest score means that the job \(j\in\mathcal{J}_{\mathcal{P}}\) has a low priority/arduousness. Sometimes, jobs have to be postponed until another day because no caregiver can perform the job on the current day or because of a lack of time. The priority scale is used to range jobs from basic to extremely important. Some jobs are more arduous than others (palliative care), and the caregiver can be affected by this job. These situations must be taken into account when building and scheduling the planning. The arduousness score is used to rate how much a job can affect a caregiver from low impact to deep impact. As an example and as illustrated in Figure 1, the first caregiver has three jobs scheduled. The first one has a low priority and a low arduousness level. The second job scheduled has a low priority and a high arduousness level. The third job scheduled has a medium priority and a high arduousness level. Taking care of how jobs are scheduled is important because as described in Figure 1, the first caregiver has to perform two jobs with the highest arduousness score, whereas the fourth caregiver only has jobs with a medium or low arduousness score. Let \(\mathcal{Q}\) be the set of qualifications required by a job. To perform a job \(j\), a caregiver must have the required qualification \(\mathcal{Q}_{i}\in\mathcal{Q}\), as illustrated in Figure 2. A job may need one or several qualifications, while a caregiver must have all qualifications required to perform the job. In Figure 2, Caregiver 2 is able to perform the second and third job because he/she has the required skills. As mentioned by [PERSON] [13], an HHC instance has about six different qualifications on average, which means that \(card(\mathcal{Q})\approx 6\). Moreover, as stated by [PERSON] [27] in his review, on average, eighty percent of caregivers are able to perform any kind of job. Each job related to a patient has a given time window \([s_{j},e_{j}]\) and a processing time \(dur_{j}\). A patient can be an elderly person living at home and who has an agreement with an HHC center for his/her medical and social care (bathing, nursing, etc.). Depending on the care service, a time window has to be set up. The time window indicates when a job must start. For example, for a patient \(p\in\mathcal{P}\) and a job \(j\in\mathcal{J}\), a time window is set up to start at 2.30 P.M. and finish at 3.30 P.M. This means that a caregiver \(c\in\mathcal{C}\) has to begin the job between 2.30 P.M. and 3.30 P.M. Normally, each caregiver follows his/her own route. However, some patients require two caregivers to be present simultaneously (synchronization constraint) or in a given order (precedence constraint) to proceed to their jobs. If a job is synchronized, two caregivers are needed simultaneously to perform the job at the patient's home. Synchronized jobs are often  
Figure 1: An example of priority and arduousness in an HCC scheduling problem. Figure 2: A qualification matrix (**C**) regarding job qualifications (**A**) and caregivers’ qualifications (**B**). met in the case of overweight patients or palliative care. The precedence constraint is met when, for example, medication has to be given by a caregiver before or after another task performed by another caregiver. Typically, ten to twenty percent of jobs in an HHC center follow such constraints.