Category: NSO

Categories
Master OR semester project NSO

DKE Scheduling Project

rp-or-heu-userinterface2

Students: Anton Bulat, Fatimah Mulan Ahmed, Fred Shen, Maxime Laschet
Supervisor: Dr. Matúš Mihalák
Semester 2015-2016

Problem statement and motivation:

The aim of this work is to compute an optimal schedule for the students and teachers of the Department Data Science of Knowledge Engineering at Maastricht University. The research and the mathematically modeling of a solution take a central aspect of this project.
The work has split into two groups: The Integer Linear Programming and the heuristics group. This report will focus on the work of the heuristics group. It will explain the conceptuation of the model including all constraints, the application of Local search and some heuristics approaches and experiments to improve feasible solutions.

Research questions:

In the present project we aimed at answering the following research questions:

  • How an academic timetable can be effectively constructed, using the local search techniques and heuristic approaches?
  • How the application can distinct between a good and a worse schedule?

Major outcomes:

  • The local search algorithm starts with a given solution. Local movements of not feasible events in relation to new start conditions will lead to a feasible solution step by step. Addtionally the ILP group’s output is parsed and translated as input for our algorithm.
  • The second main part is the verification of some rules which are decided to provide a better solution. The algorithm tries to minimize penalty values which are calculated for each event in each possible time point.
  • The user has the possibility to make manual changes on the proposed solution and rerun the algorithm until a satisfying solution is generated.
  • From the user interface the user is able to generate a PDF output of the timetable.

References:

  • Arntzen, Halvard, and Arne Løkketangen. “A local search heuristic for a university timetabling problem.” nine 1.T2 (2003): T45.
  • Rossi-Doria, Olivia. “A local search for the timetabling problem.” Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, PATAT. 2002.
  • Müller, Tomáš, Keith Murray, and Stephanie Schluttenhofer. “University course timetabling & student sectioning system.” Space Management and Academic Scheduling, Purdue University (2007).
  • Ponnalagu, Karthikeyan, Renuka Sindhgatta Rajan, and Bikram Sengupta. “Automatically generating high quality soa design from business process maps based on specified quality goals.” U.S. Patent Application No. 12/885,870.

Download: report

Categories
Bachelor thesis NSO

Criticality of Tasks within Project Management

Example project with 5 phases and 6 tasks labeled

Example project with 5 phases and 6 tasks labeledStudent: Ashley Peternella
Supervisor: Dr. Jean Derks
Semester: 2015-2016

Problem statement and motivation:

Project managers are charged with the responsibility of managing all the tasks within a project to ensure that the project is completed within an agreed deadline, with a certain quality, and for an agreed price. To know how much attention they need to invest in each task, managers need a measure that can capture the feature of ‘criticality’ of the tasks of a specified project. Criticality is defined as the importance of managing the duration of a task.

Changing a task's link
Changing a task’s link to test criticality based on dependency

Inspired by the pessimistic bankruptcy game for the problem of cost sharing, this article explores the idea of using the combination of cooperative game theory and the Shapley value as a method for capturing the expected features of criticality.

Those features are: correlation between task duration and duration of the entire project, probability of being on ‘the critical path’, relation to other tasks, and task dependencies.

The research presented will show that pessimistic games in their purist forms only further formalise the concept of cruciality, which is the importance of managing the duration- uncertainty of tasks. An adapted method is created, which will be proven to capture the desired features of criticality, and serve as proof of concept.

Research hypothesis:

Cooperative game theory could help define the feature of criticality of tasks within project management.

Major outcome:

The adapted method seems to capture all desired features of criticality and thus serves as proof of concept.

References:

  • Branzei, R., Ferrari, G., Fragnelli, V., and Tijs, S. (2002). Two approaches to the problem of sharing delay costs in joint projects. Annals of Operational Research, Vol. 109, pp. 359–374.
  • Castro, J., Daniel, G., and Tejada, J. (2007). A project game for PERT networks. Operations Research Letters 35, pp. 791–798.
  • Elmaghraby, S.E. (2000). On criticality and sensitivity in activity networks. European Journal of Operational Research, Vol. 127, No. 2, pp. 220–238.
  • Steiner, G.A. (1969). Top management planning macmillan. Quoted on page 481 of Project Management Handbook, 2nd edition.
  • Williams, T. (2003). The contribution of mathematical modelling to the practice of project management. IMA J Management Math, Vol. 14, No. 1, pp. 3–30.

Download: Report

Categories
Game AI Master AI semester project NSO

And the Winner is… Solving Triomineering using Combinatorial Game Theory

Student(s): Daniel Brüggemann, Mantas Gagelas, Maarten Weber, Bas Willemse;
Supervisor(s): Dr. Jos Uiterwijk;
Semester: 2015-2016;

Fig 1. – Triomineering 6×6 board. Horizontal starts and wins.

Problem statement and motivation:

Games without randomness and with perfect information normally can only be solved for a specific game environment. Small changes like changing the board size or modifying the pieces used by players usually introduce new challenges for the implementation of the game solver. A precise understanding of the specific game domain and its properties is needed, and extending the domain to new areas might help to improve this understanding and reveal new techniques for a more efficient solver. We look at the combinatorial game Domineering, where one player places vertical and the other places horizontal dominoes on a board, and the player who first cannot place a new domino loses. We extend its rules by using not dominoes, but 3-tile-pieces (Triomineering), and build a solver for this variant of the game. The solver uses a combination of search heuristics and strategies from the field of Combinatorial Game Theory, especially using the representation of a board state as a combinatorial game value. We explain how to calculate these game values of sub-games and how these can be used to make the solver more efficient, meaning how to reduce the number of game tree branches that need to be searched by the solver. The developed results might allow a better insight into the general domain of Domineering and how to solve it efficiently.

Research questions/hypotheses:

  • Is it possible to make a solver for Triomineering using the combination of minimax and Combinatorial Game Theory?
  • Is there a large improvement from combining these techniques in the solver?
  • Are there similarities to be found in solving the game of Domineering and Triomineering?

Main outcomes:

  • Combinatorial Game Values provide useful support in checking the results of the solver throughout development.
  • It has proven to be difficult to combine solver heuristics and CGT values, because certain advantages of e.g. solver pruning seem to not work correctly with CGT values.
  • Move ordering and transposition tables, as in solving Domineering, each provide a great solving speed improvement.

Downloads:

Final report