Order Scheduling Models: Hardness and Algorithms

DOI10.1007/978-3-540-77050-3_8zbMath1135.90345OpenAlexW169464267MaRDI QIDQ5458825

Amit Kumar, Vinayaka Pandit, Naveen Garg

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)

Related Items

Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures ⋮ Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time ⋮ GEODIS: towards the optimization of data locality-aware job scheduling in geo-distributed data centers ⋮ Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ Minimizing the sum of weighted completion times in a concurrent open shop ⋮ Minimizing the total weighted completion time of fully parallel jobs with integer parallel units ⋮ On scheduling coflows ⋮ Scheduling Fully Parallel Jobs with Integer Parallel Units ⋮ Metaheuristics for order scheduling problem with unequal ready times ⋮ Unnamed Item ⋮ Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms ⋮ Select and permute: an improved online framework for scheduling to minimize weighted completion time ⋮ Scheduling fully parallel jobs

Uses Software

• HTCondor MW
• SUTIL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the complexity of the concurrent open shop problem
• Optimization, approximation, and complexity classes
• Open shops with jobs overlap
• Structure of a simple scheduling polyhedron
• Solving large quadratic assignment problems on computational grids
• Decomposition algorithms for stochastic programming on a computational grid
• Minimizing the flow time without migration
• 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
• Automata, Languages and Programming