Online Linear Optimization for Job Scheduling Under Precedence Constraints

DOI10.1007/978-3-319-24486-0_22zbMath1471.68326OpenAlexW2296418806MaRDI QIDQ2835641

Takahiro Fujita, Kohei Hatano, Shuji Kijima, Eiji Takimoto

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2324/1786655

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Uses Software

• MAXFLOW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Least squares isotonic regression in two dimensions
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Large margin classification using the perceptron algorithm
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Efficient regularized isotonic regression with application to gene-gene interaction search
• Efficient algorithms for online decision problems
• Submodular functions and optimization.
• Combinatorial Online Prediction via Metarounding
• On the Approximability of Single-Machine Scheduling with Precedence Constraints
• Online Linear Optimization over Permutations
• Approximation in stochastic scheduling
• Online Prediction under Submodular Constraints
• Playing Games with Approximation Algorithms
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
• Complexity of Scheduling under Precedence Constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Lectures on Polytopes
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Stochastic Machine Scheduling with Precedence Constraints
• Single-Machine Scheduling with Precedence Constraints
• Prediction, Learning, and Games