Sequencing Stochastic Jobs with a Single Sample

Puck te Rietmole, Marc Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Downloads (Pure)

Abstract

This paper revisits the single machine scheduling problem to minimize total weighted completion times. The twist is that job sizes are stochastic from unknown distributions, and the scheduler has access to only a single sample from the distributions. For this restricted information regime, we analyze the simplest and probably only reasonable scheduling algorithm, namely to schedule by ordering the jobs by weight over sampled processing times. In general, this algorithm can be tricked by adversarial input distributions, performing in expectation arbitrarily worse even in comparison to choosing a random schedule. The paper suggests notions to capture the idea that this algorithm, on reasonable inputs, should exhibit a provably good expected performance.

Original languageEnglish
Title of host publicationCombinatorial Optimization - 8th International Symposium, ISCO 2024, Revised Selected Papers
EditorsAmitabh Basu, Ali Ridha Mahjoub, Ali Ridha Mahjoub, Juan José Salazar González
PublisherSpringer
Pages235-247
Number of pages13
ISBN (Electronic)978-3-031-60924-4
ISBN (Print)9783031609237
DOIs
Publication statusPublished - 22 May 2024
Event8th International Symposium on Combinatorial Optimization, ISCO 2024 - La Laguna, Spain
Duration: 22 May 202424 May 2024
Conference number: 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14594 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Symposium on Combinatorial Optimization, ISCO 2024
Abbreviated titleISCO 2024
Country/TerritorySpain
CityLa Laguna
Period22/05/2424/05/24

Keywords

  • 2024 OA procedure
  • Sampling
  • Stochastic scheduling
  • Approximation

Fingerprint

Dive into the research topics of 'Sequencing Stochastic Jobs with a Single Sample'. Together they form a unique fingerprint.

Cite this