Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
From MaRDI portal
Publication:3757393
DOI10.1137/0215081zbMath0621.68024OpenAlexW2021987086MaRDI QIDQ3757393
Tsuyoshi 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
independent tasksidentical processorsLRF schedulemean weighted flow-timeworst case behavior of a heuristic algorithm
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)
Related Items
Unnamed Item, Scheduling jobs that arrive over time, Shapley value for parallel machine sequencing situation without initial order, On the existence of schedules that are near-optimal for both makespan and total weighted completion time, The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines, Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines, Unrelated parallel machine scheduling with new criteria: complexity and models, Coordination mechanisms for parallel machine scheduling, Minimizing the total weighted completion time of fully parallel jobs with integer parallel units, Decorous combinatorial lower bounds for row layout problems, Coordination mechanisms with hybrid local policies, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, Matching based very large-scale neighborhoods for parallel machine scheduling, An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule, A system-centric metric for the evaluation of online job schedules, Cost-sharing mechanisms for scheduling under general demand settings, Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines, Scheduling in a multi-processor environment with deteriorating job processing times and decreasing values: the case of forest fires, A note on minimizing the sum of quadratic completion times on two identical parallel machines, An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, Approximation results in parallel machines stochastic scheduling, The list scheduling algorithm for scheduling unreliable jobs on two parallel machines, Scheduling Fully Parallel Jobs with Integer Parallel Units, Analysis of Smith's rule in stochastic machine scheduling, Frameworks for adaptable scheduling algorithms, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems, A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Quality of move-optimal schedules for minimizing total weighted completion time, Preemptive multiprocessor order scheduling to minimize total weighted flowtime, Scheduling batch processing machines with incompatible job families, Designing PTASs for MIN-SUM scheduling problems, Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, A note on weighted completion time minimization in a flexible flow shop, Scheduling to minimize the maximum total completion time per machine, Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems, On the minimization of total weighted flow time with identical and uniform parallel machines, Truthfulness for the Sum of Weighted Completion Times, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Scheduling fully parallel jobs, Minimizing average completion time in the presence of release dates, Multicriteria scheduling, Weighted completion time minimization for capacitated parallel machines, A PTAS for the average weighted completion time problem on unrelated machines., Scheduling identical parallel machines to minimize total weighted completion time
