Analysis of a linearization heuristic for single-machine scheduling to maximize profit

From MaRDI portal





Consider the problem of scheduling jobs \(j=1,...,n\) without preemption on a single machine to maximize total profit, where the profit of job j is given by a nonincreasing, concave function \(p_ j(t)\) of its starting time t. This problem may be solved by the following heuristic. Assume that a set \(S\subseteq \{1,...,n\}\) of jobs already has been scheduled and let \(t=\sum_{j\in S}t_ j\) be the finish time of the last of these jobs. Then schedule next a job \(i\in \{1,...,n\}\backslash S\) for which the value \((p_ i(t)-p_ i(T))/t_ i\) with \(T=\sum^{n}_{j=1}t_ j\) is maximal. Let Z denote the optimal profit and \(Z_ H\) denote the heuristic profit. The authors prove that \(Z_ H\geq z/2\). The lower bound 1/2 can be improved to 2/3 as has been shown in a different paper. A family of examples is given for which \(Z_ H/Z\) approaches 2/3.











This page was built for publication: Analysis of a linearization heuristic for single-machine scheduling to maximize profit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313596)