Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem (Q2482376)

In this paper the NP-hard single machine problem \(1 \mid r_j \mid \sum w_jC_j\) is studied. Given is a set of jobs which have to be scheduled without preemption on a single machine such that release dates of the jobs are respected and the weighted sum of completion times is minimized. Based on a time-indexed LP formulation with binary variables \(x_{jt}\) indicating whether job \(j\) completes at time \(t\) or not a Lagrangian relaxation method is proposed and solved with a two-stage proximal bundle algorithm. Numerical results are presented and compared with approximate solutions obtained by an \(\alpha\)-point heuristic.