Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem (Q2482376)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem |
scientific article |
Statements
Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem (English)
0 references
16 April 2008
0 references
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.
0 references
single machine scheduling
0 references
Lagrangian relaxation, \(\alpha\)-point
0 references
proximal bundle method
0 references
0 references
0 references
