On-line production order scheduling with preemption penalties

DOI10.1007/s10878-006-9027-3zbMath1198.90220MaRDI QIDQ2385487

Yanyan Li

Publication date: 12 October 2007

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

Full work available at URL: https://doi.org/10.1007/s10878-006-9027-3

zbMATH Keywords

Competitive ratio; On-line scheduling; Competitive strategy; Preemption penalty

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting, Online production planning to maximize the number of on-time orders, Lower bounds on online deadline scheduling with preemption penalties, On Job Scheduling with Preemption Penalties

Cites Work

• Unnamed Item
• On-line scheduling of jobs with fixed start and end times
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• A tighter extra-resource analysis of online deadline scheduling
• Minimizing total completion time subject to job release dates and preemption penalties
• Scheduling Broadcasts with Deadlines
• A Near Optimal Scheduler for On-Demand Data Broadcasts
• Improved On-Line Broadcast Scheduling with Deadlines
• Computing and Combinatorics
• Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
• Theoretical Computer Science
• Automata, Languages and Programming
• On-line scheduling on a single machine: Maximizing the number of early jobs