2435. Stochastic Online Scheduling on Parallel Machines
Invited abstract in session WE-4: GOR Master Thesis Awards, stream PC Stream.
Wednesday, 16:30-18:00Room: H6
Authors (first author is the speaker)
| 1. | Marta Piperno
|
Abstract
This work addresses the stochastic online scheduling problem of minimizing the expected total weighted completion time on identical parallel machines. Building on previous research, we analyze the performance of the deterministic algorithm DSOS and the randomized algorithm RSOS. We prove that the DSOS algorithm has performance ratios of 2.309 + 1.309 D, where D is an upper bound on the squared coefficient of variation of the processing times. Notably, this is currently the strongest bound on the performance guarantee of deterministic algorithms for problems with general processing time distributions. Additionally, we establish a performance guarantee of 1.618 + 1.309 D for the DSOS algorithm on a single machine, improving previous results for D lower than 0.764. Furthermore, we derive a deterministic offline variant from the RSOS algorithm that preserves its performance guarantee and improves previous results in the offline setting for D lower than the number of machines. Finally, we conduct a computational study on simulated data to evaluate the performance of the analyzed algorithms in practice.
Keywords
- Approximation Algorithms
- Computational Experiments
- Scheduling
Status: accepted
Back to the list of papers