common due date

Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

  • M.-C. Plateau
  • Yasmin Rios-Solis
    • Categories Applications - OR and Management Sciences, Quadratic Programming, Scheduling Tags , ,

    In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before … Read more

    A new lower bound for one-machine earliness-tardiness scheduling

  • Francis Sourd
    • Categories Scheduling Tags , , , ,

    In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound … Read more