Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem (Q2482376)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5264784
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem |
scientific article; zbMATH DE number 5264784 |
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
0.8010300397872925
0 references
0.787015974521637
0 references
0.7719711065292358
0 references
0.7719166874885559
0 references
0.7572723627090454
0 references
