Sign Out
Logged In:
 
 
 
 
 
Tab Image

Julian's Problem

- work assignment at a Disabled Care Centre

by Susanne Heipcke and Yves Colombani

The IntA centre that employs handicapped people wants to generate its weekly schedule according to the individual abilities and preferences of the involved persons. A set of different working areas has to be staffed on a daily basis, according to given varying upper and lower bounds on the number of people required. In addition, individual profiles of preferences, skills and dislikes have to be respected. We present a Constraint Programming solution to this problem implemented with the interval-based solver SchedEns.

-oo0oo-

MacIntyre Care is a registered charity that runs various projects for disabled people at different locations in the UK. In Milton Keynes, the organisation operates several small shops, a nursery, and craft shops at different sites. These work sites are all staffed with disabled people most of whom live at the main site, in Great Holm. At the end of each week the work plan for the coming week has to be set up indicating the employment of each person in the morning and afternoon of every working day. Each work site has minimal and maximal staffing limits that may vary on different days of the week. Some locations, especially the shops where there is direct interaction with the general public, need to be staffed partially with persons having a certain level of skill (high-skilled people). In addition, each person has his own set of preferences for the different work sites. These may consist of, for instance, a specialisation in some type(s) of work, (physical) disability or dislike for doing others, or the wish to experience a variety of working are as out of a set of more or less preferred jobs.

Some people cannot work together in the same area at any time because of incompatible personalities (referred to as clashes). Finally, every day some persons are absent either for a part (morning/afternoon) or for the entire day. These may be regularly occurring absences due to participation in courses (college) or parttime arrangements. Absences due to special training needs (eg Self advocacy, Social skills training), holidays and illness are specific to each single week.

The aim of the weekly plan to be generated is to ‘maximise the satisfaction’ of all persons involved while satisfying the different staffing constraints. Until now, this complicated exercise was accomplished by hand and did not really correspond to the planner's needs: it required a lot of time merely to generate ‘acceptable’ plans, usually violating many constraints and error prone as there was no mechanism to assure that each person present was assigned exactly once per time unit. Because of the problem's dimension (about 65 persons have to be assigned to 9 work sites over a period of 5 working days on a basis of half days, at the same time keeping in mind the previous week's results for checking everybody's preferences) it was virtually impossible to check consistency manually.

Departing from the current planning practice at MacIntyre, a tool for supporting the weekly planning has to provide at least two features: it must be able to verify whether a given schedule is correct or not regarding the specified constraints. In the latter case an indication of the cause for the inconsistency would be helpful. Moreover, the planning tool has to provide a means to generate a feasible schedule starting from a partial plan.

Based on these specifications, the authors have developed a planning system, Weekly Personnel Planner [Colombani and Heipcke 97b], consisting of a Constraint Programming (CP) [Van Hentenryck 89] application and a user interface in a spreadsheet environment. The choice of CP was dictated by the need to deal with very specific relations (staffing limits combined with high-skill conditions, preference profiles) and the objective of designing a flexible and easy to use tool (each parameter is subject to change). Even if Julian's Problem at first sight looks very much like a classical planning problem (such as Nurse Scheduling or Crew Rostering Problems), it cannot be solved by generic techniques in an easy way because of the specificity of the constraints it requires. For instance, formulating the skill and preferences constraints in an algebraic way as required by standard Mathematical Programming tools implies major reformulations significantly increasing model size coupled with a loss of all specific information in a sense the interpretation of the constraint relations.

The user interface has been designed through a widely used spreadsheet software. Not being specialists at all the end-users are only concerned with data input and evaluation of solutions or possible causes of inconsistencies: the weekly plan in the form of a timetable can be modified by the user as much as he wants and then submitted to the CP part of the application. The results are automatically displayed in the same table. In most cases the software suggests a feasible schedule within a couple of seconds.

Problem description

For each person a weekly working plan is to be generated. The schedule is organised in 10 time slices the mornings and afternoons of 5 working days. It should indicate the working area for every person on a daily basis.

The set of constraints that have to be satisfied by a feasible schedule may be divided into two parts:

1 Work sites
Each working area has lower and upper bounds on its staffing for each working day, ie Monday to Friday. Two cases must be taken into account:

  1. normal staffing: Any person can be assigned to this work site without further restrictions.
  2. high-skill staffing: This working area requires specific capability because of the responsibilities involved. So, at least half of the persons assigned to this area must be ‘high-skilled’.

2 Individuals
In addition to the staffing limits, several constraints concerning the persons involved have to be satisfied:

  1. Presence: Every morning, afternoon or entire day, some people are not available due to special training, holidays, or because they are working part-time on certain weekdays only.
  2. Continuity: All persons must be present the entire day work at the same location in the morning and afternoon unless fixed otherwise in the input data.
  3. Locations: Some working areas are not located at the main site, and several persons may not work at these off-site locations on certain days.
  4. Preferences: Every person has an individual profile indicating which are the preferred working areas (expressed via frequency per fortnight), and where this person cannot or does not want to work (preference value 0), or if they do always the same activities, or if they are assigned to a particular location on certain days.
  5. Clashes: Certain persons may not work together at the same work site.

The application structure

The Weekly Personnel Planner application consists of two main parts, the user interface and the Constraint Programming implementation. Figure 1 gives an overview of the organisation of the application. The Constraint Programming part is invisible to the user. Written in C it is based on the Constraint Programming library SchedEns [Colombani and Heipcke 97a], it contains the mathematical formulation of the problem, algorithms to solve it, and as well handles all data input and output. The data used by the CP implementation are contained in four files (the three last ones are spreadsheet tables saved in text format):

  • gnrl.dat contains fixed data information (activity names, staffing limits, individual preferences and skills);
  • last.csv is the previous week's plan;
  • current.csv is the user's proposed plan for the current week (it may be empty, partially or completely filled);
  • sol.csv the file in which the solution will be saved.

The system acts in two different ways depending on the input data:

Figure 1: Structure of the planning application

  1. The current.csv plan is complete. The software checks if it satisfies all the constraints. If it finds an inconsistency, it displays the assignment which has produced the inconsistency (for instance a person has been assigned to an activity that he cannot do).
  2. The current.csv plan is incomplete. A search is launched in order to find a feasible solution.

If a satisfying solution is available, it is saved into the indicated file and a final check is performed: all activity variables for every person are inspected in order to detect any time of unemployment that is not covered by the specified absences. If any exist, a list of these ‘unemployed people’ is displayed. This proceeding has become necessary due to an insufficient total number of workplaces available on certain weekdays. The people concerned may be given a day off, or entered manually into the plan (necessarily violating some constraints such as staffing limits).

The user interface

The visible part of the Weekly Personnel Planner application gives the user direct access to the current week's plan and all weekly input data. It is based on a set of macros written for a spreadsheet software. Via spreadsheet tables input data can be changed, and calculations (re)started. The main working environment consists of a template for a weekly schedule. Weekly variable data (fixed assignments or absences not occurring on a regular basis) are changed or entered directly into this plan. Whenever the constraint solver is started, it checks whether the currently displayed (partial) schedule is consistent with all constraints and completes it, if possible, to a week's plan (Figure 2). The application is operated by a special menu with different entries for directing data input and output, starting the constraint solver, and editing the so-called fixed input data (staffing limits, skills and preference profiles, clashes, part-time workers, and fixed assignments). Standard functionality of the spreadsheet software can be used for viewing and printing out weekly plans.

Figure 2: Example of a solution process

The solver part

The constraints

For this application we have extensively used the ability of directly implementing specialised relations within Constraint Programming. Indeed, the CP tool we are using provides the facility of incorporating new constraints (written in C) that handle the particularities of the problem. The following relations have been implemented:

  • For one day and one activity the relation ONEJOB guarantees that the lower and upper bounds on staffing are observed. One constraint per time slice and non high-skill activity needs to be established.
  • As an extension of the previous relation, ONEJOBHS also includes tests for the high-skill condition by treating the groups of high-skilled and unskilled persons separately. One constraint per time slice and high-skill activity needs to be established.
  • The relation WOPER implements the preference profiles per person and week. It mainly controls if lower and upper bounds on occurrences of activities can be satisfied.
  • Clashes are treated by means of the DIFFEZ constraint. This relation checks that two persons are not in the same place at a given time. This constraint must be used for each time slice and each pairing that leads to a clash.

The main algorithm first reads in the fixed data information and the proposed (in)complete plan for the current week. Consistency is checked for each new constraint and in the case of failure the program is terminated with an error message that indicates exactly which constraint has caused the inconsistency (type of constraint, information on indices like time slice, work site or person involved). Besides, warnings are printed out each time a person is assigned to an activity and at the same time scheduled for a complementary activity (training for instance) or some other type of absence. This case is not treated as an error though, giving the user the possibility to add absences to a partial or complete plan and test the effects. The constraint system takes charge of checking the consistency of the plan and possibly finds replacements for absent persons. When the system has been set up successfully, usually many activity variables (work assigned to every person per time slice) are still undecided. An enumeration strategy is thus needed to find a feasible solution or to prove that no solution is available.

The enumeration strategy

As no optimisation function has been defined, there is no need to carry out a complete search. The aim of the enumeration is just to find a feasible solution as quickly as possible in order to give the user the following choice: keeping the proposed solution or trying to find another, possibly better one (the notion of ‘better’ does not make any sense within the constraint system. It only reflect the user's point of view!). Because of the option to restart the search in order to find a different solution, the search algorithm needs to make sure that, although based on the same input data, a different (first) solution will be constructed. Indeed, most of the persons involved prefer their workplans to be as varied as possible. So a different plan is a ‘better’ plan. We have introduced a random parameter in the search strategy in order to obtain the desired behaviour: the week's days are planned one by one in a random order and if no solution is obtained within a fixed duration, a new search is launched with a different permutation of the working days. This restart mechanism is repeated a limited number of times. In practice, the algorithm finds a feasible schedule in a couple of seconds for almost all trials.

Results

The software is currently being used in real conditions at MacIntyre Care. The interface is appreciated and the detailed error messages (indicating inconsistencies) are found very helpful by the users. The software has successfully been used to ‘tidy up’ manually generated plans by pointing out persons employed in several places at the same time, work given to absent persons implying inconsistency in staffing limits, violations of staffing limits, and assigning work to persons left out unintentionally in the original plan. In a second period a set of possible plans have been built by giving the software the task of completing partially empty weekly plans (derived from the original set). The generated set is currently used as a basic several weeks rotation scheme for which only partial updates are required in order to adapt a plan to a specific week.

Acknowledgements

This project was partially funded by a LASEORS LEduF grant.

For the interested reader

  • [Colombani and Heipcke 97a] Colombani Y and Heipcke S (1997) ‘The Constraint Solver SchedEns, Tutorial and Documentation, Technical Report 241, Laboratoire d'Informatique de Marseille.
  • [Colombani and Heipcke 97b] Colombani Y and Heipcke S (1997) Weekly Personnel Planner Application Manual, Buckingham.
  • [Colombani and Heipcke 98] Colombani Y and Heipcke S (1998) ‘Julian's Problem: Personnel Assignment with Individual Skills and Preference Profiles’, In Proceedings of the Fourth International Conference on the Practical Application of Constraint Technology, PACT 98, London.
  • Van Hentenryck P (1989) Constraint Satisfaction in Logic Programming, MIT Press.

SUSANNE HEIPCKE currently completing her PhD in Management Science at the University of Buckingham (UK) funded by BASF-AG (Germany). Holds a diploma in mathematics from the Catholic University Eichst’att (Germany). Research centres around the application and combination of mathematical programming and constraint programming techniques for solving discrete optimisation problems, such as large-scale production planning.

YVES COLOMBANI, a computer scientist, has gained his doctorate in constraint programming from the University of Marseille (France) in 1997. Currently working for Dash Associates Ltd (UK). Research interests include constraint programming, especially its application to scheduling problems, and modelling languages.

First published to members of the Operational Research Society in OR Insight January - March 1999