Computation of approximate -points for large scale single machine scheduling problem
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.
- List Scheduling in Order of α-Points on a Single Machine
- Near-optimal solutions of large-scale single-machine scheduling problems
- The power of \(\alpha\)-points in preemptive single machine scheduling.
- An experimental study of LP-based approximation algorithms for scheduling problems
- Single machine scheduling with release dates
- A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
- A Cholesky dual method for proximal piecewise linear programming
- A time indexed formulation of non-preemptive single machine scheduling problems
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- About Lagrangian methods in integer optimization
- An experimental study of LP-based approximation algorithms for scheduling problems
- Comparison of bundle and classical column generation
- Efficiency of proximal bundle methods
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- scientific article; zbMATH DE number 3550182 (Why is no real title available?)
- scientific article; zbMATH DE number 3614502 (Why is no real title available?)
- scientific article; zbMATH DE number 2084780 (Why is no real title available?)
- scientific article; zbMATH DE number 2109192 (Why is no real title available?)
- scientific article; zbMATH DE number 830382 (Why is no real title available?)
- Lagrangean relaxation. (With comments and rejoinder).
- Minimizing average completion time in the presence of release dates
- New approaches for optimizing over the semimetric polytope
- Proximity control in bundle methods for convex nondifferentiable minimization
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Single machine scheduling with release dates
- Solving semidefinite quadratic problems within nonsmooth optimization algorithms
- Survey of Bundle Methods for Nonsmooth Optimization
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
- Variable target value subgradient method
- Near-optimal solutions of large-scale single-machine scheduling problems
- A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time
- Machine Scheduling to Minimize Weighted Completion Times
- List Scheduling in Order of α-Points on a Single Machine
- Integer Programming and Combinatorial Optimization
- An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts
This page was built for publication: Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482376)
