An efficient algorithm for the earliness-tardiness scheduling problem

  • Safia Kedad-Sidhoum
  • Francis Sourd
    • Categories Scheduling Tags Short URL: https://optimization-online.org/?p=9802

    This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.

    Citation

    Published in Journal of Scheduling