Approximation algorithms for shop scheduling problems with minsum objective

DOI10.1002/jos.96zbMath1009.90046OpenAlexW2170050590MaRDI QIDQ1607979

Maurice Queyranne, M. I. Sviridenko

Publication date: 8 August 2002

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

Full work available at URL: https://doi.org/10.1002/jos.96

zbMATH Keywords

approximation algorithmsshop scheduling

Mathematics Subject Classification ID

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

Related Items (13)

Optimal restricted due date assignment in scheduling ⋮ Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Approximation algorithms for shop scheduling problems with minsum objective: A correction ⋮ Approximation Algorithms for Scheduling with Resource and Precedence Constraints ⋮ Properties of optimal schedules in preemptive shop scheduling ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ On a local protocol for concurrent file transfers ⋮ Scheduling Problems over Network of Machines ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ Scheduling problems over a network of machines ⋮ Combinatorial algorithms for data migration to minimize average completion time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling open shops with parallel machines
• Geometric algorithms and combinatorial optimization
• Approximation schemes for scheduling on parallel machines
• Approximation algorithms for the multiprocessor open shop scheduling problem
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Makespan minimization in preemptive two machine job shops
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Structure of a simple scheduling polyhedron
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Single Machine Scheduling with Release Dates
• Scheduling the Open Shop to Minimize Mean Flow Time
• A Computational Study of the Job-Shop Scheduling Problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Improved Approximation Algorithms for Shop Scheduling Problems
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Tighter bounds on preemptive job shop scheduling with two machines

This page was built for publication: Approximation algorithms for shop scheduling problems with minsum objective