Online scheduling of time-critical tasks to minimize the number of calibrations

DOI10.1016/J.TCS.2022.01.040zbMATH Open1490.90122OpenAlexW4210475952MaRDI QIDQ2124226FDOQ2124226

Authors Zuzhi Chen, Jialin Zhang 

Publication date 19 April 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.08482

zbMATH Keywords

calibrationonline schedulingtime-critical

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Abstract: We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take $lambda$ time steps as the activation time, and then the machine will remain calibrated status for $T$ time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an $mathcalO(lambda)$-competitive algorithm, which is asymptotically optimal. When $lambda=0$, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of $3e+7(approx15.16)$ which improves upon the previous results for such problems.

Recommendations

• Calibration scheduling with time slot cost
• Calibration scheduling with time slot cost
• On-line scheduling of parallel machines to minimize total completion times
• Online scheduling to minimize maximum response time and maximum delay factor
• Online scheduling of equal-processing-time task systems
• scientific article; zbMATH DE number 7051282
• A class of on-line scheduling algorithms to minimize total completion time
• Online Scheduling of Precedence Constrained Tasks

Cites work

• scientific article; zbMATH DE number 6971073 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• scientific article; zbMATH DE number 2114378 (Why is no real title available?)
• Competitive design and analysis for machine-minimizing job scheduling problem
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals
• On the Complexity of Minimizing the Total Calibration Cost
• Renting a cloud

This page was built for publication: Online scheduling of time-critical tasks to minimize the number of calibrations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2124226)