A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties

作者：Keshavarz Taha^*; Savel**ergh Martin; Salmasi Nasser

来源：Applied Mathematical Modelling, 2015, 39(20): 6410-6424.

DOI：10.1016/j.apm.2015.01.069

• Minimization of earliness and tardiness
• Group scheduling
• Sequence-dependent setup time
• Time-indexed formulation
• Lagrangian relaxation
• Branch-and-bound algorithm

The NP-hard single machine sequence-dependent group scheduling problem with minimization of total weighted earliness and tardiness is investigated. An arc-time-indexed formulation is presented and a Lagrangian-based branch-and-bound algorithm is proposed. The Lagrangian relaxation of the arc-time-indexed formulation is solved as a shortest path problem. The results of an extensive computational study demonstrate the efficacy of the proposed algorithm and establish characteristics of some hard to solve instances.

• 出版日期2015-10-15