Minimizing average completion time in the presence of release dates
From MaRDI portal
Publication:1290642
DOI10.1007/BF01585872zbMath0920.90074MaRDI QIDQ1290642
Clifford Stein, Joel M. Wein, Cynthia A. Phillips
Publication date: 3 June 1999
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
NP-hardrelaxationsaverage completion timeaverage weighted completion timeconstant-factor approximation algorithmsparallel machine modelspreemptive and nonpreemptive schedules
Related Items
Preemption in single machine earliness/tardiness scheduling, Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining, Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time, A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection, Online scheduling to minimize the total weighted completion time plus the rejection cost, Online scheduling of simple linear deteriorating jobs to minimize the total general completion time, On competitive analysis for polling systems, Online Single Machine Scheduling to Minimize the Maximum Starting Time, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, An improved greedy algorithm for stochastic online scheduling on unrelated machines, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Unnamed Item, An improved analysis of SRPT scheduling algorithm on the basis of functional optimization, An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Scheduling problems in master-slave model, Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines, Resource cost aware scheduling, A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, On-line scheduling to minimize average completion time revisited., Robust algorithms for total completion time, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates, On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems, An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time, Applying ``peeling onion approach for competitive analysis in online scheduling with rejection, A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting, Interval-indexed formulation based heuristics for single machine total weighted tardiness problem, A \(2.28\)-competitive algorithm for online scheduling on identical machines, Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems, LP-based online scheduling: From single to parallel machines, A class of on-line scheduling algorithms to minimize total completion time, A note on ``An optimal online algorithm for single machine scheduling to minimize total general completion time, An optimal online algorithm for single-processor scheduling problem with learning effect, A 1. 47-approximation for a preemptive single-machine scheduling problem, Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, A Semi-Online Algorithm for Single Machine Scheduling with Rejection, Common due date assignment and scheduling with ready times, Randomized algorithms for on-line scheduling problems: How low can't you go?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing mean flow time with release time constraint
- Scheduling with Deadlines and Loss Functions
- Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Open Shop Scheduling to Minimize Finish Time
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Improved Approximation Algorithms for Shop Scheduling Problems
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Task Scheduling in Networks
- Scheduling independent tasks to reduce mean finishing time
- Technical Note—Minimizing Average Flow Time with Parallel Machines
