|
Abstract:
|
Scheduling problems mainly consist in finding an assignment of execution times (a schedule) to
a set of activities of a project that optimizes an objective function. There are many constraints
imposed over the activities that any schedule must satisfy. The most usual constraints establish
precedence relations between activities, or limit the amount of some resources that the activities
can consume. There are many scheduling problems in the literature that have been and
are currently still being studied. A paradigmatic example is the Resource-Constraint Project
Scheduling Problem (RCPSP). It consists in finding a start time for each one of the activities of
a project, respecting pre-defined precedence relations between activities and without exceeding
the capacity of a set of resources that the activities consume. The goal is to find a schedule
with the minimum makespan (total execution time of the project). The RCPSP has many generalizations,
one of which is the Multimode Resource-Constrained Project Scheduling Problem
(MRCPSP). In this variation, each activity has several available execution modes that differ in
the duration of the activity or the demand of resources. A solution for the MRCPSP determines
the start times of the activities and also an execution mode for each one. These problems are
NP-hard, and are known in the literature to be especially hard, with moderately small instances
of 50 activities that are still open.
There are many approaches to solving RCPSP and MRCPSP in the literature. They are
often tackled with metaheuristics due to their high complexity, but there are also some exact approaches,
including Mixed Integer Linear Programming (MILP), Branch-and-Bound algorithms
or Boolean Satisfiability (SAT), which have shown to be competitive and in many cases even
better than metaheuristics. One of the exact methods that is growing in use in the field of constrained
optimization is SAT Modulo Theories (SMT). This thesis is the continuation of previous
works carried out in the Logic and Programming (L ∧ P) group of Universitat de Girona, which
used SMT to tackle RCPSP and MRCPSP. Excluding these, there have not been any other
attempts to use SMT to solve the MRCPSP. SMT solvers (like other generic methods such as
SAT or MILP) do not know which is the problem they are dealing with. It is the work of the
modeler to provide a representation of the problem (i.e. an encoding) in the language that the
solver admits.
The main goal of this thesis is to use SMT to solve the Multimode Resource-Constraint
Project Scheduling Problem. We focus on two already existing encodings for the MRCPSP,
namely the time encoding and the task encoding. We use some existing preprocessing methods
that contribute to the formulation of time and task, and present new preprocessings. Most of
them are based on the idea of incompatibility between two activities, i.e., the impossibility that
two activities run at the same time instant. These incompatibilities let us discharge some con-
figurations of the solutions prior to encode the problem. Consequently, the use of preprocessings
helps to reduce the size of the encodings in terms of variables and clauses. Another contribution
of this work is the study of the time and task encodings and the differences that they present.
We refine these encodings to provide more compact versions. Moreover, two new versions of these
encodings are presented, which mainly differ in the codification of the constraints over the use
of resources. One of them is based on Linear Integer Arithmetic expressions, and the other one
in Pseudo-Boolean constraints and Integer Difference Logic. Another contribution of this work
is the presentation of an ad-hoc optimization algorithm based on a linear search that mainly
consists in three steps. First of all it simplifies the problem to efficiently ensure or discharge the
feasibility of the instance, then it finds a first non-optimal solution by using a quick heuristic
method, and finally it optimizes the problem making use of the knowledge acquired with the preprocessings to boost the search. We also present an initial work on a more intrusive approach
consisting in modifying the internal heuristic of the SMT solver for the decision of literals. This
work involves the study of a state-of-the-art implementation of an SMT solver, and its modification
to include a framework to specify heuristics related with the encoding of the problem. We
give some initial results on custom heuristics for the time and task encodings of the MRCPSP.
Finally, we test our system with the benchmark sets of instances for the MRCPSP available in
the literature, and compare our performance with a state-of-the-art exact solver for the MRCPSP.
The results show that we are able to solve the major part of the benchmark sets. Moreover, we
show to be competitive with the state-of-the-art solver of Vílim et. al. for the MRCPSP, being
our system slower in solving the easiest benchmark instances, but outperforming the solver of
Vílim et. al. in solving the hardest instances |
