Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

DOI10.1137/0215081zbMATH Open0621.68024OpenAlexW2021987086MaRDI QIDQ3757393FDOQ3757393

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215081

Recommendations

Worst Case Analysis of a New Lower Bound for Flow Shop Weighted Completion Time Problem
Worst-case analysis of an approximation algorithm for flow-shop scheduling
Some results of the worst-case analysis for flow shop scheduling
Minimization of mean flow time for some discrete-continuous scheduling problems
Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling
Probabilistic analysis of the minimum weighted flowtime scheduling problem
Scheduling algorithms for flexible flowshops: Worst and average case performance
The worst-case performance ratio with time-dependent single-scheduling problems
Mean flow time minimization with given bounds of processing times

identical processors independent tasks LRF schedule mean weighted flow-time worst case behavior of a heuristic algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited In (48)

Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
Scheduling fully parallel jobs
Scheduling to minimize the maximum total completion time per machine
Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
Preemptive multiprocessor order scheduling to minimize total weighted flowtime
Minimizing average completion time in the presence of release dates
Scheduling batch processing machines with incompatible job families
A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
Unrelated parallel machine scheduling with new criteria: complexity and models
Decorous combinatorial lower bounds for row layout problems
Analysis of Smith's rule in stochastic machine scheduling
A theoretical and empirical study of job scheduling in cloud computing environments: the weighted completion time minimization problem with capacitated parallel machines
Title not available (Why is that?)
Quality of move-optimal schedules for minimizing total weighted completion time
New Bounds for the Identical Parallel Processor Weighted Flow Time Problem
An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule
Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families
Designing PTASs for MIN-SUM scheduling problems
Coordination mechanisms with hybrid local policies
Cost-sharing mechanisms for scheduling under general demand settings
Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines
Frameworks for adaptable scheduling algorithms
Scheduling in a multi-processor environment with deteriorating job processing times and decreasing values: the case of forest fires
Scheduling jobs that arrive over time
A note on minimizing the sum of quadratic completion times on two identical parallel machines
Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines
Shapley value for parallel machine sequencing situation without initial order
Scheduling Fully Parallel Jobs with Integer Parallel Units
Approximation results in parallel machines stochastic scheduling
On the existence of schedules that are near-optimal for both makespan and total weighted completion time
Scheduling identical parallel machines to minimize total weighted completion time
Matching based very large-scale neighborhoods for parallel machine scheduling
Coordination mechanisms for parallel machine scheduling
The list scheduling algorithm for scheduling unreliable jobs on two parallel machines
A new dynamic programming algorithm for the parallel machines total weighted completion time problem
A PTAS for the average weighted completion time problem on unrelated machines.
On the minimization of total weighted flow time with identical and uniform parallel machines
A system-centric metric for the evaluation of online job schedules
On the integration of theoretical single-objective scheduling results for multi-objective problems
A note on weighted completion time minimization in a flexible flow shop
Weighted completion time minimization for capacitated parallel machines
Multicriteria scheduling
An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
Worst Case Analysis of a New Lower Bound for Flow Shop Weighted Completion Time Problem
Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines
Truthfulness for the Sum of Weighted Completion Times
Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines

This page was built for publication: Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

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