[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

G. Raidl, T. Jatschka, M. Riedler, J. Maschler:
"Time-Bucket Relaxation Based Mixed Integer Programming Models for Scheduling Problems: A Promising Starting Point for Matheuristics";
Vortrag: International Workshop on Model-Based Metaheuristics, Brüssel, Belgien; 04.09.2016 - 07.09.2016; in: "Proceedings of the Sixth International Workshop on Model-based Metaheuristics", (2016), S. 104 - 107.



Kurzfassung englisch:
In job shop and project scheduling problems, generally speaking, a set
of activities shall be scheduled over time. The execution of the
activities typically depends on certain resources of limited
availability and diverse other restrictions like precedence constraints.
A feasible schedule is sought that minimizes some objective function
like the makespan. For such problems, mixed integer linear programming
(MIP) techniques are frequently considered, but also known to have
severe limitations. Here, we consider a relaxation of a potentially very
fine-grained TI model in which the set of possible starting times is
partitioned into so-called time-buckets. (TB). This TB relaxation is
typically much smaller than the original TI model and can be solved
relatively quickly. An obtained solution provides a lower bound for the
TI model's solution value but in general does not directly represent a
feasible schedule as activity start times are only restricted to certain
time-intervals. This solution, however, provides a promising starting
point for matheuristics. On the one hand, we may try to derive a
feasible schedule by heuristically relaxing the start times to specific
values, trying to full all constraints. On the other hand, we can
further subdivide some time-buckets and re-solve the resulting refined
model to obtain an improved bound and a model that comes closer to the
TI model. Doing this refinement iteratively yields a matheuristic that
in principle converges to a provably optimal solution. In practice, it
is crucial to subdivide the time-buckets in a sensible way in order to
increase the model's size only slowly while hopefully obtaining
significantly stronger bounds. (Meta-)heuristic techniques and dual
variable information may provide a strong guidance.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/publik_257778.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.