The power of \(\alpha\)-points in preemptive single machine scheduling.

DOI10.1002/JOS.93zbMath1038.90037OpenAlexW2126520302MaRDI QIDQ1600001

Andreas S. Schulz

Publication date: 27 July 2003

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15940

zbMATH Keywords

combinatorial optimizationapproximation algorithmscheduling theoryon-line algorithmrandomized algorithmLP relaxation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (18)

Lower bounds for on-line single-machine scheduling. ⋮ Minimizing the stretch when scheduling flows of divisible requests ⋮ Online Appointment Scheduling in the Random Order Model ⋮ On-line production order scheduling with preemption penalties ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Online scheduling to minimize the total weighted completion time plus the rejection cost ⋮ Competitive analysis of preemptive single-machine scheduling ⋮ On competitive analysis for polling systems ⋮ On-line scheduling to minimize average completion time revisited. ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Preemptive scheduling with availability constraints to minimize total weighted completion times ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ LP-based online scheduling: From single to parallel machines ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Stochastic Online Scheduling Revisited ⋮ Approximation algorithms for shop scheduling problems with minsum objective

Cites Work

• Formulating the single machine sequencing problem with release dates as a mixed integer program
• A 1. 47-approximation for a preemptive single-machine scheduling problem
• A Sequencing Problem with Release Dates and Clustered Jobs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Some simple scheduling algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The power of \(\alpha\)-points in preemptive single machine scheduling.