The computer science laboratory of Ecole Polytechnique (LIX) offers in
collaboration with the company Konatus (co-located on the campus of IP
Paris) an M1 or M2 internship on a resource-constrained scheduling
problem. The internship has an empirical focus with a theoretical
foundation. Hence, interest in both areas is very welcome.
The scheduling problem at hand is concerned with the automated
management of development processes in companies. In such processes,
different projects are split into smaller parts (such as work elements
or tasks), which need to be assigned to different teams. Each team has
various skills and capacities, and each task has a priority, a start and
an end date, a cost, and other factors. The aim is to assign the
different parts of each project to the teams such that all constraints
are satisfied and that the overall time spent on the projects is minimized.
Due to various constraints as well as the diverse nature of projects and
set-up of teams, this problem is challenging. To this end, heuristic
solvers are employed, which provide a great compromise between finding
good solutions and reducing the run time of the solver. At the moment,
Konatus uses an evolutionary algorithm as such a heuristic solver. This
algorithm acts as the baseline for the internship. The goal of the
internship is to come up with an improved heuristic solver for the
scheduling problem. This new algorithm can be tested on different data
sets provided by Konatus (both artificial and from the real world).
The internship is going to be financed by Konatus, and Max Stellmacher
(max.stellmacher@konatus.io) from Konatus acts as domain experts during
the internship. From LIX, Martin Krejca
(martin.krejca@polytechnique.edu) acts as the scientific advisor of this
project. Initially, the student should study the theoretical aspects of
this problem and determine to what end it can be decomposed or optimal
sub-problems can be solved. Based on such insights, the next step is to
implement a solver that computes good schedules, which ideally
outperform the baseline (in terms of solution quality and run time).
This internship has the potential to be continued as a CIFRE thesis.
If you are interested or have further questions, please contact Martin
(martin.krejca@polytechnique.edu).
Best regards,
Martin
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
