Analysis of a linearization heuristic for single-machine scheduling to maximize profit
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.
- Single machine scheduling with nonlinear cost functions
- Maximization problems in single machine scheduling
- Analysis of a linear programming heuristic for scheduling unrelated parallel machines
- scientific article; zbMATH DE number 4012297
- A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions
- A dual algorithm for the one-machine scheduling problem
- Analysis of a linearization heuristic for single-machine scheduling to maximize profit
- Bounds on Multiprocessing Timing Anomalies
- Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related Tasks
- scientific article; zbMATH DE number 3550182 (Why is no real title available?)
- scientific article; zbMATH DE number 3550186 (Why is no real title available?)
- Minimizing Total Costs in One-Machine Scheduling
- Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Worst-Case Analysis of Heuristic Algorithms
- Scheduling crackdowns on illicit drug markets
- Scheduling in a multi-processor environment with deteriorating job processing times and decreasing values: the case of forest fires
- Single machine scheduling with nonlinear cost functions
- Analysis of a linearization heuristic for single-machine scheduling to maximize profit
- A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions
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)