On Preemption and Learning in Stochastic Scheduling

• URL: http://arxiv.org/abs/2205.15695v3
• Date: Thu, 1 Jun 2023 14:58:02 GMT
• Title: On Preemption and Learning in Stochastic Scheduling
• Authors: Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, Vianney Perchet
• Abstract summary: We study single-machine scheduling of jobs belonging to a job type that determines its duration distribution. We design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case.
• Score: 22.32180964593702
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.

Related papers

• Predicting Case Suffixes With Activity Start and End Times: A Sweep-Line Based Approach [0.35684665108045377]
  This paper introduces a technique for predicting case suffixes consisting of activities with start and end timestamps.<n>The proposed technique predicts both the waiting time and the processing time of each activity.<n>An evaluation on real-life and synthetic datasets compares the accuracy of different instantiations of this approach.
  arXiv  Detail & Related papers  (2025-09-18T02:01:30Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
  arXiv  Detail & Related papers  (2023-01-30T13:17:15Z)
• Multi-task Bias-Variance Trade-off Through Functional Constraints [102.64082402388192]
  Multi-task learning aims to acquire a set of functions that perform well for diverse tasks. In this paper we draw intuition from the two extreme learning scenarios -- a single function for all tasks, and a task-specific function that ignores the other tasks. We introduce a constrained learning formulation that enforces domain specific solutions to a central function.
  arXiv  Detail & Related papers  (2022-10-27T16:06:47Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Metalearning Linear Bandits by Prior Update [7.519872646378836]
  Fully Bayesian approaches assume that problem parameters are generated from a known prior, while in practice, such information is often lacking. This problem is exacerbated in decision-making setups with partial information, where using a misspecified prior may lead to poor exploration and inferior performance. In this work we prove, in the context of linear bandits and Gaussian priors, that as long as the prior estimate is sufficiently close to the true prior, the performance of an algorithm that uses the misspecified prior is close to that of an algorithm that uses the true prior.
  arXiv  Detail & Related papers  (2021-07-12T11:17:01Z)
• Learning to Schedule [3.5408022972081685]
  This paper proposes a learning and scheduling algorithm to minimize the expected cumulative holding cost incurred by jobs. In each time slot, the server can process a job while receiving the realized random holding costs of the jobs remaining in the system.
  arXiv  Detail & Related papers  (2021-05-28T08:04:06Z)
• Discriminative, Generative and Self-Supervised Approaches for Target-Agnostic Learning [8.666667951130892]
  generative and self-supervised learning models are shown to perform well at the task. Our derived theorem for the pseudo-likelihood theory also shows that they are related for inferring a joint distribution model.
  arXiv  Detail & Related papers  (2020-11-12T15:03:40Z)
• Temporally Correlated Task Scheduling for Sequence Learning [143.70523777803723]
  In many applications, a sequence learning task is usually associated with multiple temporally correlated auxiliary tasks. We introduce a learnable scheduler to sequence learning, which can adaptively select auxiliary tasks for training. Our method significantly improves the performance of simultaneous machine translation and stock trend forecasting.
  arXiv  Detail & Related papers  (2020-07-10T10:28:54Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• Sequence-to-sequence models for workload interference [1.988145627448243]
  Co-scheduling of jobs in data-centers is a challenging scenario, where jobs can compete for resources yielding to severe slowdowns or failed executions. Current techniques, most of them already involving machine learning and job modeling, are based on workload behavior summarization across time. We propose a methodology for modeling co-scheduling of jobs on data-centers, based on their behavior towards resources and execution time.
  arXiv  Detail & Related papers  (2020-06-25T14:11:46Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  We propose an extension of the Multiple Hypothesis Prediction (MHP) model to handle ambiguous predictions with sequential data. We also introduce a novel metric for ambiguous problems, which is better suited to account for uncertainties.
  arXiv  Detail & Related papers  (2020-03-10T09:15:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.