Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Continuous-Time MILP Models for Employee Scheduling in a Retail


Ch. Conte

Semester/Bachelor Thesis, HS 07

In this thesis, different continuous-time MILP models for employee scheduling are described. Two of these models are able to track sales profiles. Examination of complexity, model size in terms of variables and constraints as well as solver performance on these two models have shown, that the model described in section 4.2 using shift-based event points is the most suitable one for the present problem. It provides solutions of quite stable quality up to a certain problem size. On the other hand, the model using global event points, described in 4.3, turned out to be of higher complexity. Therefore, the solutions on that model are of less good quality, even though the number of variables is lower than in the model using shift-based event points. Also a third model, described in section 4.4 has been developed. This model is only able to model the presence to be always higher or lower than the sales. This, however, could be interesting for special applications, where the present employees mustnít be lower than the number of demanded. This requirement might not occur in a retail trade, but in other branches of business, for example in security business, it might be interesting as well. Since the solver could only find good solutions for small problem sizes, i.e. low number of employees, an iterative approach has been tried out to be able to deal with larger problems as well. This way, small subsets of the total set of employees are scheduled separately, while the shifts of the others are fixed. This way, schedules can be generated for larger models too. Nevertheless, the practical use of the continuous-time models is somehow limited, since only daily models could have been solved. The complexity for a weekly model also formulated, was too high to be solved. So, for this application, a discrete time model might still be the more appropriate way to get a good schedule. Nevertheless, the experiment made on the discrete-time model in section 5.2 has shown, that these kind of models become hard to solve too, if the number of timepoints becomes too large. In this a case, a continuous-time model could offer an interesting alternative, if it is adapted somehow to generate a weekly schedule as well. So, the task of generating the schedule could be split up in two stages, where in the first one, employees are scheduled onto days and in the second one, there is a daily schedule made with the employees working on these days. This might not give an optimal, but a good feasible solution in return. Supervisors ETH: Prof. M. Morari, Dr. C. Jones, Dr. K. Nolde


Type of Publication:

(13)Semester/Bachelor Thesis

M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhdThesis { Xxx:2007:IFA_3172
Permanent link