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";

Talk: International Workshop on Model-Based Metaheuristics, Brüssel, Belgien; 2016-09-04 - 2016-09-07; in: "Proceedings of the Sixth International Workshop on Model-based Metaheuristics", (2016), 104 - 107.

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.

http://publik.tuwien.ac.at/files/publik_257778.pdf

Created from the Publication Database of the Vienna University of Technology.