Scheduling

New hybrid optimization algorithms for machine scheduling problems

  • Yunpeng Pan
  • Leyuan Shi
    • Categories Dynamic Programming, Scheduling Tags , ,

    Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling … Read more

    On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

  • Yunpeng Pan
  • Leyuan Shi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Scheduling

    New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer … Read more

    Robustness in Combinatorial Optimization and Scheduling Theory: An Extended Annotated Bibliography

  • Yury Nikulin
    • Categories Combinatorial Optimization, Robust Optimization, Scheduling

    This extended annotated bibliography focuses on what has been published during the last ten years in the area of combinatorial optimization and scheduling theory concerning robustness and other similar techniques dealing with worst case optimization under uncertainty and non-accuracy of problem data Citation Christian-Albrechts University in Kiel, Institute of Production and Logistics, Working paper Article … Read more

    Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

  • Alexandre Pigatti
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Meta Heuristics, Scheduling Tags , , ,

    The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … Read more

    A genetic algorithm for the resource constrained multi-project scheduling problem

  • José Fernando Gonçalves
  • Jorge Magalhaes-Mendes
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , ,

    This paper presents a genetic algorithm for the Resource Constrained Multi-Project Scheduling Problem (RCMPSP). The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on … Read more

    Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines

  • Safia Kedad-Sidhoum
  • Yasmin Rios-Solis
  • Francis Sourd
    • Categories Scheduling Tags , , , ,

    This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed … Read more

    Optimizing Call Center Staffing using Simulation and Analytic Center Cutting Plane Methods

  • Julius Atlason
  • Marina A. Epelman
  • Shane Henderson
    • Categories Cutting Plane Approaches, Optimization of Simulated Systems, Scheduling Tags , ,

    We present a simulation-based analytic center cutting plane method to solve a sample average approximation of a call center problem of minimizing staffing costs, while maintaining an acceptable level of service in multiple time periods. We establish convergence of the method when the service level functions are discrete pseudoconcave. An extensive numerical study of a … Read more

    Construction project scheduling problem with uncertain resource constraints

  • Tang Guochun
  • Zhong-Ping Wan
  • Julin He
    • Categories Applications - Science and Engineering, Scheduling

    This paper discusses that major problem is the construction project scheduling mathematical model and a simple algorithm in the uncertain resource environments. The project scheduling problem with uncertain resource constraints comprised mainly three parties: one of which its maximal limited capacity is fixed throughout the project duration; second maximal limited resource capacity is random variable; … Read more

    A hybrid bin-packing heuristic to multiprocessor scheduling

  • Adriana C. Alvim
  • Celso C. Ribeiro
    • Categories Meta Heuristics, Scheduling Tags , , ,

    The multiprocessor scheduling problem consists in scheduling a set of tasks with known processing times into a set of identical processors so as to minimize their makespan, i.e., the maximum processing time over all processors. We propose a new heuristic for solving the multiprocessor scheduling problem, based on a hybrid heuristic to the bin packing … Read more