On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions

DOI10.1287/opre.1060.0270zbMath1167.90521OpenAlexW2098959416MaRDI QIDQ3391992

Mabel C. Chou, Hui Liu, David Simchi-Levi, Maurice Queyranne

Publication date: 13 August 2009

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.1060.0270

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Production models (90B30) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (13)

Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines ⋮ The expected asymptotical ratio for preemptive stochastic online problem ⋮ Dynamic scheduling with uncertain job types ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Randomized mechanism design for decentralized network scheduling ⋮ Online scheduling for outpatient services with heterogeneous patients and physicians ⋮ An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan ⋮ Preemptive stochastic online scheduling on two uniform machines ⋮ Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Stochastic Online Scheduling Revisited

This page was built for publication: On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions