Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime

DOI10.1007/S10951-015-0467-4zbMath1353.90066arXiv1312.3345OpenAlexW2963313703MaRDI QIDQ341463

Mohammad Hasan, M. Dambrine

Publication date: 16 November 2016

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

Full work available at URL: https://arxiv.org/abs/1312.3345

zbMATH Keywords

makespantotal completion timeparallel identical machinesapproximation algorithms for scheduling

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (2)

Multi-level bottleneck assignment problems: complexity and sparsity-exploiting formulations ⋮ Approximation ratio of LD algorithm for multi-processor scheduling and the Coffman-Sethi conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the exact upper bound for the Multifit processor scheduling algorithm
• Bin packing can be solved within 1+epsilon in linear time
• A simple proof of the inequality \(R_ M(MF(k)) \leq 1.2 + (1/2^ k)\) in multiprocessor scheduling
• Algorithms minimizing mean flow time: Schedule-length properties
• The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
• Makespan minimization subject to flowtime optimality on identical parallel machines
• Exact performance of MULTIFIT for nonsimultaneous machines
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum
• Dynamic Bin Packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• An Application of Bin-Packing to Multiprocessor Scheduling
• On the Minimization of the Makespan Subject to Flowtime Optimality
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Minimizing makespan subject to minimum flowtime on two identical parallel machines

This page was built for publication: Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime