An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
From MaRDI portal
Publication:2890462
DOI10.1287/ijoc.1030.0055zbMath1239.90053OpenAlexW2146321208MaRDI QIDQ2890462
Savelsbergh, Martin W. P., R. N. Uma, Joel M. Wein
Publication date: 8 June 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.1030.0055
Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Related Items
Network construction problems with due dates ⋮ A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies ⋮ Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems ⋮ A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness ⋮ An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ A branch and cut heuristic for a runway scheduling problem ⋮ Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem ⋮ Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ LP-based online scheduling: From single to parallel machines ⋮ Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars
This page was built for publication: An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
