Scheduling

Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

  • Alysson Machado Costa
  • Lana M. R. Santos
  • Maristela O. Santos
  • Landir Saviniec
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Scheduling Tags , , ,

    High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requisites. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient obtention of optimal or near-optimal solutions is still a challenge for many problems of practical size. In … Read more

    Analysis of Models for the Stochastic Outpatient Procedure Scheduling Problem

  • Amy Cohn
  • Marina A. Epelman
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , , ,

    In this paper, we present a new stochastic mixed-integer linear programming model for the Stochastic Outpatient Procedure Scheduling Problem (SOPSP). In this problem, we schedule a day’s worth of procedures for a single provider, where each procedure has a known type and associated probability distribution of random duration. Our objective is to minimize the expectation … Read more

    A Mixed Integer Linear Program for Optimizing the Utilization of Locomotives with Maintenance Constraints

  • Sarah Frisch
  • Philipp Hungerländer
  • Anna Jellen
  • Dominic Weinberger
    • Categories Applications - OR and Management Sciences, Scheduling Tags , ,

    In this paper we investigate the Locomotive Scheduling Problem, i.e., the optimization of locomotive utilization with prior known transports that must be performed. Since railway timetables are typically planned a year in advance, the aim is to assign locomotives to trains such that the locomotive utilization is maximized while maintenance constraints are taken into account. … Read more

    Tight MIP formulations for bounded length cyclic sequences

  • Thomas Kalinowski
  • Tomas Lidén
  • Hamish Waterer
    • Categories 0-1 Programming, Polyhedra, Scheduling

    We study cyclic binary strings with bounds on the lengths of the intervals of consecutive ones and zeros. This is motivated by scheduling problems where such binary strings can be used to represent the state (on/off) of a machine. In this context the bounds correspond to minimum and maximum lengths of on- or off-intervals, and … Read more

    Seamless Multimodal Transportation Scheduling

  • David Bergman
  • John Hooker
  • Arvind U. Raghunathan
  • Thiago Serra
  • Shingo Kobori
    • Categories Applications - OR and Management Sciences, Scheduling, Transportation

    Ride-hailing services have expanded the role of shared mobility in passenger transportation systems, creating new markets and creative planning solutions for major urban centers. In this paper, we consider their use for last-mile passenger transportation in coordination with a mass transit service to provide a seamless multimodal transportation experience for the user. A system that … Read more

    Leveraging Predictive Analytics to Control and Coordinate Operations, Asset Loading and Maintenance

  • Nagi Gebraeel
  • Xu Andy Sun
  • Murat Yildirim
    • Categories Applications - OR and Management Sciences, Energy, Scheduling Tags , , , ,

    This paper aims to advance decision-making in power systems by proposing an integrated framework that combines sensor data analytics and optimization. Our modeling framework consists of two components: (1) a predictive analytics methodology that uses real-time sensor data to predict future degradation and remaining lifetime of generators as a function of the loading conditions, and … Read more

    The Integrated Last-Mile Transportation Problem

  • David Bergman
  • John Hooker
  • Arvind U. Raghunathan
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Scheduling

    Last-mile transportation (LMT) refers to any service that moves passengers from a hub of mass transportation (MT), such as air, boat, bus, or train, to destinations, such as a home or an office. In this paper, we introduce the problem of scheduling passengers jointly on MT and LMT services, with passengers sharing a car, van, … Read more

    A new approximation algorithm for unrelated parallel machine scheduling problem with release dates

  • Zhi Pei
  • Ziteng Wang
  • Mingzhong Wan
    • Categories Approximation Algorithms, Scheduling, Semi-definite Programming

    In this research, we consider the unrelated parallel machine scheduling problem with release dates. The goal of this scheduling problem is to find an optimal job assignment with minimal sum of weighted completion times. As it is demonstrated in the present paper, this problem is NP-hard in the strong sense. Albeit the computational complexity, which … Read more

    Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

  • Andreas Bärmann
  • Maximilian Merkert
  • Thorsten Gellermann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This new special case, which we call staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible … Read more

    The Clique Problem with Multiple-Choice Constraints under a Cycle-Free Dependency Graph

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
    • Categories Graphs and Matroids, Polyhedra, Scheduling Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC) represents a very common substructure in many real-world applications, for example scheduling problems with precedence constraints. It consists in finding a clique in a graph whose nodes are partitioned into subsets, such that exactly one node from each subset is chosen. Even though we can show that (CPMC) … Read more