Improved bounds on relaxations of a parallel machine scheduling problem

DOI10.1023/A:1009750913529zbMATH Open0911.90219OpenAlexW1586637507MaRDI QIDQ1383802FDOQ1383802

David B. Shmoys, Joel Wein, Clifford Stein, Cynthia Phillips, Andreas S. Schulz

Publication date: 5 May 1999

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009750913529

zbMATH Keywords

release datesidentical parallel machinesaverage completion timeoptimal nonpreemptive scheduleoptimal preemptive schedule

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cited In (4)

• A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting
• On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
• An exact method for \(Pm/sds, r_{i}/ \sum^{n}_{i=1} C_{i}\) problem
• Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem

   Recommendations

• Lower bounds for parallel machine scheduling problems 👍 👎
• Tight bounds for the identical parallel machine scheduling problem 👍 👎
• Improved approximation schemes for scheduling unrelated parallel machines 👍 👎
• Tight bounds for the identical parallel machine‐scheduling problem: Part II 👍 👎
• Title not available (Why is that?) 👍 👎
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems 👍 👎
• An approximation algorithm for a parallel machine scheduling problem with constraints 👍 👎
• On the exact solution of a large class of parallel machine scheduling problems 👍 👎
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines 👍 👎
• An improved algorithm for parallel machine scheduling under additional resource constraints 👍 👎

This page was built for publication: Improved bounds on relaxations of a parallel machine scheduling problem

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