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

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.