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

DOI10.1137/0215081MaRDI QIDQ3757393zbMATHOpenAlexFDO

Authors T. Kawaguchi, Seiki Kyan

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

zbMATH Keywords

identical processorsindependent tasksLRF schedulemean weighted flow-timeworst 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)

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

Cited in

(48)

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

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)