Scheduling

Computational evaluation of cut-strengthening techniques in logic-based Benders’ decomposition

  • Aigerim Saken
  • Emil Karlsson
  • Stephen J. Maher
  • Elina Rönnberg
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Scheduling Tags , , , , ,

    Cut-strengthening techniques have a significant impact on the computational effectiveness of the Logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific and thus, no … Read more

    Γ-robust Optimization of Project Scheduling Problems

  • Arie M.C.A. Koster
  • Jenny Segschneider
    • Categories Applications - OR and Management Sciences, Scheduling Tags , , , ,

    \(\) In this paper, we investigate the problem of finding a robust baseline schedule for the project scheduling problem under uncertain process times. We assume that the probability distribution for the duration is unknown but an estimation together with an interval in which this time can vary is given. At most $ \Gamma $ of … Read more

    Scheduling of healthcare professionals using Bayesian Optimization

  • Guido Lagos
  • Francisco Jara-Moroni
    • Categories Applications - OR and Management Sciences, Scheduling, Stochastic Programming Tags , , ,

    In this paper we present a Bayesian optimization framework that iteratively “learns” good schedules for healthcare professionals of outpatient healthcare in a hospital, that minimize the overall number of patients in queue — we understand that a patient in schedule is one in queue. The hospital has several medical specialties and each is modeled as … Read more

    Stochastic Programming Models for a Fleet Sizing and Appointment Scheduling Problem with Random Service and Travel Times

  • Shutian Li
  • Karmel S. Shehadeh
  • Man Yiu Tsang
    • Categories Applications - OR and Management Sciences, Scheduling, Stochastic Programming Tags , , , ,

    We propose a new stochastic mixed-integer linear programming model for a home service fleet sizing and appointment scheduling problem (HFASP) with random service and travel times. Specifically, given a set of providers and a set of geographically distributed customers within a service region, our model solves the following decision problems simultaneously: (i) a fleet sizing … Read more

    Integer Programming Models for Round Robin Tournaments

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories Scheduling Tags , , ,

    Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than … Read more

    Temporal Bin Packing with Half-Capacity Jobs

  • Christopher Muir
  • Luke Marshall
  • Alejandro Toriello
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    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

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    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

  • Hu Kanxin
    • Categories Meta Heuristics, Production and Logistics, Scheduling Tags , , ,

    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

    Lexicographic Branch-and-Bound Column Search

  • Andreas Bärmann
  • Alexander Müller
  • Dieter Weninger
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Scheduling Tags , , , , ,

    We present an exact generic method for solving the pricing problem 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 returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke … Read more

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

  • Paula Fermín Cueto
  • Sergio García
  • Miguel F. Anjos
    • Categories Airline Optimization, Scheduling, Transportation Tags , , , ,

    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