Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

DOI10.1287/MOOR.22.3.513zbMath0883.90064OpenAlexW2148204686MaRDI QIDQ4361782

David B. Shmoys, Leslie A. Hall, Andreas S. Schulz, Joel M. Wein

Publication date: 28 October 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/9043

zbMATH Keywords

approximation algorithms\({\mathcal N}{\mathcal P}\)-hard scheduling problemsweighted sum of the job completion times

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

Single machine scheduling problems with uncertain parameters and the OWA criterion ⋮ Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines ⋮ Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time ⋮ Approximate Deadline-Scheduling with Precedence Constraints ⋮ Optimal restricted due date assignment in scheduling ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Approximating total flow time on parallel machines ⋮ A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Online scheduling on bounded batch machines to minimize the maximum weighted completion time ⋮ Minimizing makespan on parallel machines with release time and machine eligibility restrictions ⋮ A 2-OPT procedure to reduce total inspection time in a serial inspection process ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ Online scheduling to minimize the total weighted completion time plus the rejection cost ⋮ Partially ordered knapsack and applications to scheduling ⋮ Scheduling orders for multiple product types to minimize total weighted completion time ⋮ Approximation Algorithms for Scheduling with Resource and Precedence Constraints ⋮ The efficiency-fairness balance of round robin scheduling ⋮ Minimizing the sum of weighted completion times in a concurrent open shop ⋮ A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Decorous combinatorial lower bounds for row layout problems ⋮ News from the online traveling repairman. ⋮ Splitting versus setup trade-offs for scheduling to minimize weighted completion time ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Performance analysis of active schedules in identical parallel machine ⋮ A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time ⋮ An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time ⋮ Precedence constrained scheduling to minimize sum of weighted completion times on a single machine ⋮ Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine ⋮ Approximating Weighted Completion Time for Order Scheduling with Setup Times ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Online scheduling with linear deteriorating jobs to minimize the total weighted completion time ⋮ Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time ⋮ Scheduling problems in master-slave model ⋮ A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates ⋮ Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ Resource cost aware scheduling ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ Preemptive and non-preemptive generalized min sum set cover ⋮ Reference points and approximation algorithms in multicriteria discrete optimization ⋮ Maximizing business value by optimal assignment of jobs to resources in grid computing ⋮ 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 ⋮ Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates ⋮ On-line scheduling to minimize average completion time revisited. ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Risk Averse Scheduling with Scenarios ⋮ 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 ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ An approximation scheme for the bi-scenario sum of completion times trade-off problem ⋮ A modified modeling approach and a heuristic procedure for the multi-mode resource constrained project scheduling problem with activity splitting ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ Scheduling hybrid flowshop with parallel batching machines and compatibilities ⋮ Interval-indexed formulation based heuristics for single machine total weighted tardiness problem ⋮ A new approximation algorithm for unrelated parallel machine scheduling with release dates ⋮ A \(2.28\)-competitive algorithm for online scheduling on identical machines ⋮ Corrigendum: Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ On-line scheduling of parallel machines to minimize total completion times ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Scheduling of tasks with effectiveness precedence constraints ⋮ LP-based online scheduling: From single to parallel machines ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ SINGLE MACHINE DUE DATE ASSIGNMENT SCHEDULING PROBLEM WITH PRECEDENCE CONSTRAINTS AND CONTROLLABLE PROCESSING TIMES IN FUZZY ENVIRONMENT ⋮ Combinatorial algorithms for data migration to minimize average completion time ⋮ A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ Online scheduling to minimize modified total tardiness with an availability constraint ⋮ New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints ⋮ Scheduling MapReduce jobs on identical and unrelated processors ⋮ Minimizing average completion time in the presence of release dates ⋮ Approximation results for a bicriteria job scheduling problem on a single machine without preemption ⋮ A 1. 47-approximation for a preemptive single-machine scheduling problem ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines ⋮ A PTAS for the average weighted completion time problem on unrelated machines. ⋮ Restarts can help in the on-line minimization of the maximum delivery time on a single machine ⋮ Off-line admission control for general scheduling problems ⋮ Lower bounds on precedence-constrained scheduling for parallel processors. ⋮ A 2-approximation algorithm for the network substitution problem ⋮ The power of \(\alpha\)-points in preemptive single machine scheduling. ⋮ Approximation algorithms for shop scheduling problems with minsum objective

This page was built for publication: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms