Scholarlink

<p>We investigate scheduling with testing in the multiprocessor environment. Scheduling with testing, disallowing job preemption, is a variant recently proposed by Dürr et al. and Albers et al. to model many real-life applications where the scheduler decides to either execute a job for a likely overestimated length of time, or test the job to obtain its exact processing time, followed by executing the job for the exact length of time on the same machine. We present an online algorithm with competitive ratio 2.8681, improving the previous best known guarantee of 2.9514; when every test operation takes one unit of time, we present an online algorithm with competitive ratio approaching 2.5276, improving the previous best known guarantee of 2.8081. Compared to the prior work, the novel design ideas in our algorithm for the general testing case are to set up multiple thresholds for job testing decision-making and to use multiple sorting/selection criteria to determine the job processing order. We also propose a way to construct a benchmark dataset from the one for the classic multiprocessor scheduling problem, and on this benchmark dataset we demonstrate the empirical performance of our algorithms against the prior algorithms.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Multiprocessor scheduling with testing: improved online algorithms and numerical experiments

  • 期刊论文

  • 发表日期：

    2025年8月4日

查看全文
  • Mingyang Gong,
  • Jing Fan,
  • Guohui Lin,
  • Bing Su,
  • Zihan Su,
  • Xiang Zhang

摘要

We investigate scheduling with testing in the multiprocessor environment. Scheduling with testing, disallowing job preemption, is a variant recently proposed by Dürr et al. and Albers et al. to model many real-life applications where the scheduler decides to either execute a job for a likely overestimated length of time, or test the job to obtain its exact processing time, followed by executing the job for the exact length of time on the same machine. We present an online algorithm with competitive ratio 2.8681, improving the previous best known guarantee of 2.9514; when every test operation takes one unit of time, we present an online algorithm with competitive ratio approaching 2.5276, improving the previous best known guarantee of 2.8081. Compared to the prior work, the novel design ideas in our algorithm for the general testing case are to set up multiple thresholds for job testing decision-making and to use multiple sorting/selection criteria to determine the job processing order. We also propose a way to construct a benchmark dataset from the one for the classic multiprocessor scheduling problem, and on this benchmark dataset we demonstrate the empirical performance of our algorithms against the prior algorithms.