Sigrid Knust

Universität Osnabrück

Loading and Unloading Problems in Storage Areas

Abstract:

We consider the process of loading and unloading items from a storage area (e.g., a warehouse, depot, container terminal, etc.). The items are stored in stacks  where only the topmost item of each stack can be directly accessed and the  objective is to minimize the number of reshuffles in the retrieval stage.

The following three problem settings are covered in the talk:

In the parallel stack loading problem incoming items have to be stored according to a fixed arrival sequence. We study two surrogate objective functions to estimate the number of reshuffles and compare them theoretically as well as in a computational study. For this purpose, MIP formulations and a simulated annealing algorithm are proposed.

In the second setting, storage loading problems under uncertainty are considered. Incoming items arriving at a partly filled storage area have to be assigned to stacks under the restriction that not every item may be stacked on top of every other item and taking into account that some items with uncertain data will arrive later. Following the robust optimization paradigm, we propose different MIP formulations for the strictly and adjustable robust counterparts of the uncertain problem and compare them in a computational study.

In the third setting, we study an unloading problem, where each item belongs to a certain family indicating the main type of the item. For a given sequence of families, it has to be decided which item of each demanded family is unloaded from the storage with the objective to minimize the total number of reshuffles. Besides complexity results, we present solutions algorithms and some computational results.

[More Information]

Přemysl Šůcha

Czech Technical University in Prague

Machine Learning in Decomposition-Based Scheduling

Abstract:

Various decomposition approaches have been successfully used for decades to solve large scheduling problems. These techniques break a complex scheduling problem into smaller, simpler subproblems that can be solved independently or sequentially, and whose results can then be combined into a complete schedule. This approach provides many opportunities to apply machine learning (ML) to further reduce computational time and increase the scalability of decomposition-based methods.

There are several reasons why it is advantageous to deploy ML within the decomposition rather than on the entire problem. First, subproblems are often solved repeatedly or recursively, meaning that similar instances are encountered multiple times. Second, subproblems are smaller and therefore easier to combine with ML techniques. Finally, it is usually much easier to generate training data for ML at the level of subproblems than for the entire problem.

In this talk, we focus on branch-and-price and Lawler’s decomposition. The use of ML techniques is illustrated on a range of problems, including nurse rostering, operating-room scheduling, and single-machine scheduling with tardiness-based objectives. The lecture highlights common design principles and lessons learned about when and how machine learning can effectively accelerate optimization algorithms in practice.

[More Information]

Norbert Trautmann

Universität Bern

Mathematical Programming in Project Scheduling

Abstract:

The formulation of project scheduling problems as mixed-integer linear programming (MILP) models plays a significant role in the literature. Besides describing the optimization problem precisely, these models are often used as a solution approach, either with standard solver software alone or as part of a matheuristic, i.e., a combination of a heuristic approach and standard solver software. In this talk, we analyze two groups of models from the literature: discrete-time (DT) and continuous-time (CT). In DT models, the planning horizon is divided into equal-length intervals, with binary variables indicating whether an activity starts at the beginning of an interval, ends at the completion of an interval, or is in progress during an interval. In CT models, the start times of activities are represented by continuous variables, and binary variables indicate sequencing relations between activities. Focusing on the original resource-constrained project scheduling problem (RCPSP), we illustrate the solution process of standard solver software for the different models. We also elaborate on the results of an extensive computational performance analysis for which we employed various test sets from the literature. Additionally, we discuss model formulations for RCPSP extensions and the integration of DT and CT models in matheuristics. 

[More Information]