OPTIHPER: A Computer-Based Decision Support System for Employee Timetabling Problems

by Antonio Lova, Pilar Tormos and Federico Barber

A high degree of job satisfaction is an essential factor in the success of a company. A company's objectives, labour conditions and worker preferences must be optimized in a complex space of solutions. OPTIHPER (Optimización de Horarios de Personal - Employee Timetabling Optimization) is a computer-aided system able to efficiently assign employees to tasks while verifying a wide set of constraints and optimizing organizational objectives and employee preferences. The system is currently in use by leading commercial companies with very good results

Employee Timetabling Problems (ETPs) arise in any organization with a set of tasks that must be assigned to a set of employees, each with their own qualifications, constraints and preferences. This problem arises in many institutions (hospitals, supermarkets etc) where the assignment of employees is usually performed manually. However, in companies with a large number of workers and working centres, the use of computer-based tools is essential for making organizational objectives compatible with worker preferences.

ETPs can be formulated as a constraint network, where the main entities that define the problem are tasks, workers and timetables. Tasks can be sporadic or can be repeated along one shift. They can have either a fixed duration or require a certain amount of work (man-hours) to complete. Workers may have different degrees of qualification for each task and can be assigned to different timetables.

Timetables are defined by the start/finish time and the shift (usually morning, afternoon, evening and night). Once assigned, shifts are maintained during a period of time and follow rotation patterns.

A number of constraints arise in ETPs. Hard constraints must be satisfied for a solution to be feasible. For instance, task constraints require that each task be assigned only to the most skilled available workers. Worker constraints may require that the timetable assigned to each worker belongs to its feasible set of timetables (working hours according to their contract) and is kept for a given period of time. Meal breaks must be assigned to workers within the limits allowed by company requirements, but while guaranteeing task requirements.

Soft constraints should be met as far as possible, but without affecting the quality of the final solution. Some examples are:

timetables with start/finish times as late/early as possible in morning/ evening shifts are preferred
workers prefer to alternate morning and evening shifts instead of repeating shifts
assignments of uncomfortable timetables should be equilibrated over a period of time.

A solution of the problem is an assignment that fulfils the set of hard and soft constraints and optimizes an objective function. This is an NP-hard problem that requires the use of efficient heuristics.

OPTIHPER: A Software System to Solve Employee Timetabling Problems
OPTIHPER is a software system developed at the Polytechnic University of Valencia to efficiently assign employees to tasks while taking into consideration a wide range of constraints, and optimizing organizational objectives and worker preferences. OPTIHPER is able to deal with a variety of tasks, workforces, worker preferences and qualifications, shifts, and organizational constraints and objectives.

Solving Process: A Multi-Start Randomized Algorithm
OPTIHPER performs an anytime heuristically guided multi-start process to search for the best solution with two phases. The construction phase builds a feasible solution, whose neighbourhood is explored until a local optimum solution is found in the local search phase. OPTIHPER has two execution modes:

'Standard mode' computes optimized task assignments considering all available workers
"Opti-Staff mode" does so for a limited number of workers, thereby allowing us to determine the optimum size/qualification of the staff.

Architecture of OPTIHPER
OPTIHPER is a multi-platform system implemented in standard ANSI C. It takes the required data either from standard databases or input files (see Figure 1). After its execution, OPTIHPER generates several statistical and graphical reports (see Figures 2 and 3).

Figure 1: Flow Chart of OPTIHPER.

Conclusions
OPTIHPER integrates AI/OR techniques able to cope with complex ETPs arising in the real world. It can obtain optimized assignments for when the entire staff is available or when the number of workers is fixed below the total available. Means technological transference agreements, customized versions of this system, are in operation with excellent results in leading European distribution companies. Standard scenarios involve the assignment of over one hundred workers, fifty types of task and sixty labour timetables. Assuming a planning horizon of four weeks, this implies personnel assignments of more than 15,000 hours. The optimized solution is obtained in a few seconds. The performance of the system, along with its flexibility and efficiency, make OPTIHPER an essential tool for staff allocation in many contexts, allowing companies to increase their competitiveness and to optimize their workers' skills and preferences.