Order Scheduling Models: Hardness and Algorithms

DOI10.1007/978-3-540-77050-3_8MaRDI QIDQ5458825zbMATH OpenOpenAlexFDO

Authors Naveen Garg, Amit Kumar, Vinayaka Pandit

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_8

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2221456
• Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time
• Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel
• Fixed-order scheduling on parallel machines
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

Cites work

• A note on the complexity of the concurrent open shop problem
• Automata, Languages and Programming
• Decomposition algorithms for stochastic programming on a computational grid
• scientific article; zbMATH DE number 1187164 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2102785 (Why is no real title available?)
• scientific article; zbMATH DE number 1445389 (Why is no real title available?)
• Minimizing the flow time without migration
• Open shops with jobs overlap
• Optimization, approximation, and complexity classes
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Solving large quadratic assignment problems on computational grids
• Structure of a simple scheduling polyhedron

Cited in

(18)

• An ordered independence system and its applications to scheduling problems
• Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures
• GEODIS: towards the optimization of data locality-aware job scheduling in geo-distributed data centers
• Metaheuristics for order scheduling problem with unequal ready times
• Scheduling In the random-order model
• On scheduling coflows
• Fixed-order scheduling on parallel machines
• Scheduling fully parallel jobs
• Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
• Scheduling fully parallel jobs with integer parallel units
• Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
• scientific article; zbMATH DE number 6843804 (Why is no real title available?)
• Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
• Matroid coflow scheduling
• scientific article; zbMATH DE number 2221456 (Why is no real title available?)
• Minimizing the sum of weighted completion times in a concurrent open shop
• Stochastic customer order scheduling to minimize long-run expected order cycle time
• Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms

Describes a project that uses

Uses Software

• SUTIL
• HTCondor MW

This page was built for publication: Order Scheduling Models: Hardness and Algorithms

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