Exact and Heuristic Solution Approaches for Busy Time Minimization in Temporal Bin Packing

Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the … Read more

A Combinatorial Flow-based Formulation for Temporal Bin Packing Problems

We consider two neighboring generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. To … 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

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

Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups

The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only … Read more

Compact Integer Linear Programming Formulations for the Temporal Bin Packing Problem with Fire-Ups

In this article we examine a specific version of the temporal bin packing problem (TBPP) that occurs in job-to-server scheduling. The TBPP represents a generalization of the well-known bin packing problem (BPP) with respect to an additional time dimension, and it requires to find the minimum number of bins (servers) to accommodate a given list … Read more

Improved Flow-based Formulations for the Skiving Stock Problem

Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to … Read more

A Special Complementarity Function Revisited

Recently, a local framework of Newton-type methods for constrained systems of equations has been developed which, applied to the solution of Karush-KuhnTucker (KKT) systems, enables local quadratic convergence under conditions that allow nonisolated and degenerate KKT points. This result is based on a reformulation of the KKT conditions as a constrained piecewise smooth system of … Read more