An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
From MaRDI portal
Publication:2890462
DOI10.1287/ijoc.1030.0055zbMath1239.90053MaRDI 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
90B35: Deterministic scheduling theory in operations research
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Related Items
An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts, Network construction problems with due dates, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies, A branch and cut heuristic for a runway scheduling problem, A time-indexed LP-based approach for min-sum job-shop problems, Analysis of bounds for a capacitated single-item lot-sizing problem, LP-based online scheduling: From single to parallel machines, Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars, A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness, Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem, Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems, 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, A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems, Almost sure asymptotic optimality for online routing and machine scheduling problems