Flow Formulation

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

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , , , ,

    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

  • John Martinovic
  • Nico Strasdat
  • José Valério de Carvalho
  • Fabio Furini
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , , ,

    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