Temporal Bin Packing with Half-Capacity Jobs

Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more

Worst-Case Analysis of Heuristic Approaches for the Temporal Bin Packing Problem with Fire-Ups

We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing … Read more

An Efficient Pixel-based Packing Algorithm for Additive Manufacturing Production Planning

Additive Manufacturing (AM), the technology of rapid prototyping directly from 3D digital models, has made a significant impact on both academia and industry. When facing the growing demand of AM services, AM production planning (AMPP) plays a vital role in reducing makespan and costs for AM service companies. This research focuses on the AMPP problem … Read more

Fully Adaptive Distributionally Robust Multi-stage Framework for Uncertain Unit Commitment Based on Mixed Decision Rules

With growing penetration of wind power into the power grid, while achieving low cost sustainable electricity supply, it also introduces technical challenges with the associated intermittency. This paper proposes a fully adaptive Was-serstein-based distributionally robust multi-stage frame-work based on mixed decision rules (MDR) for uncertain unit commitment problem (UUC) to better adapt wind pow-er respecting … Read more

Lexicographic Branch-and-Bound Column Search

We present an exact generic method for solving the pricing subproblem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and simultaneously returns all columns with a reduced-cost value below a certain threshold. The approach is based on an idea … Read more

An efficient solution methodology for the airport slot allocation problem with preprocessing and column generation

Airport coordination is a demand control mechanism that maximizes the use of existing infrastructure at congested airports. Aircraft operators submit a list of regular flights that they wish to operate over a five to seven-month period and a designated coordinator is responsible for allocating the available airport slots, which represent the permission to operate a … Read more

Parallel Dual Dynamic Integer Programming for Large-Scale Hydrothermal Unit-Commitment

Unit commitment has been at the center of power system operation for well over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization solvers to tackle this challenging problem, and often resort to simplifications to make the problem more tractable and solvable in … Read more

Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups

The temporal bin packing problem with fire-ups (TBPP-FU) is a two-dimensional packing problem where one geometric dimension is replaced by a time horizon. The given items (jobs) are characterized by a resource consumption, that occurs exclusively during an activity interval, and they have to be placed on servers so that the capacity constraint is respected … Read more

Scalable Timing-Aware Network Design via Lagrangian Decomposition

This paper addresses instances of the temporal fixed-charge multi-commodity flow (tfMCF) problem that arise in a very large scale dynamic transportation application. We model the tfMCF as a discrete-time Resource Task Network (RTN) with cyclic schedule, and formulate it as a mixed-integer program. These problems are notoriously difficult due to their time-expanded nature, and their … Read more

Interval Scheduling with Economies of Scale

Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, … Read more