Online Linear Optimization for Job Scheduling Under Precedence Constraints

DOI10.1007/978-3-319-24486-0_22MaRDI QIDQ2835641zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Online Scheduling of Precedence Constrained Tasks
• scientific article; zbMATH DE number 1617256
• On-line scheduling with precedence constraints
• Online scheduling with linear deteriorating jobs to minimize the total weighted completion time
• An optimal algorithm for preemptive on-line scheduling
• Scheduling linearly shortening jobs under precedence constraints
• Online scheduling of simple linear deteriorating jobs to minimize the total general completion time
• Optimal on-line scheduling of parallel jobs with dependencies
• Preemptive online algorithms for scheduling
• Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times

Cites work

• scientific article; zbMATH DE number 1754642 (Why is no real title available?)
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Approximation in stochastic scheduling
• Combinatorial online prediction via metarounding
• Complexity of Scheduling under Precedence Constraints
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Efficient algorithms for online decision problems
• Efficient regularized isotonic regression with application to gene-gene interaction search
• Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems
• Introduction to algorithms.
• Large margin classification using the perceptron algorithm
• Learning permutations with exponential weights
• Least squares isotonic regression in two dimensions
• Lectures on Polytopes
• On the approximability of single-machine scheduling with precedence constraints
• Online linear optimization over permutations
• Online prediction under submodular constraints
• Playing Games with Approximation Algorithms
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Prediction, Learning, and Games
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Single-Machine Scheduling with Precedence Constraints
• Stochastic Machine Scheduling with Precedence Constraints
• Submodular functions and optimization.

Cited in

(1)

• An Optimal Control Framework for Online Job Scheduling with General Cost Functions

Describes a project that uses

Uses Software

• MAXFLOW

This page was built for publication: Online Linear Optimization for Job Scheduling Under Precedence Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835641)