6533b7dcfe1ef96bd12729ca
RESEARCH PRODUCT
Scheduling independent stochastic tasks under deadline and budget constraints
Aurélie Kong Win ChangYves RobertFrédéric VivienLouis-claude CanonLouis-claude Canonsubject
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Mathematical optimizationOperations researchComputer science[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Cloud computing[INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE]02 engineering and technologyExpected valueTheoretical Computer ScienceScheduling (computing)[INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]deadline0202 electrical engineering electronic engineering information engineering[INFO]Computer Science [cs]schedulingComputer Science::Operating SystemsComputingMilieux_MISCELLANEOUSBudget constraint020203 distributed computingcloud platformindependent tasksbusiness.industry[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulationstochastic costAsymptotically optimal algorithmContinuous distributions[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA]Hardware and ArchitectureProbability distribution[INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET]020201 artificial intelligence & image processingInterrupt[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]businessSoftwarebudgetdescription
This article discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow independent and identically distributed probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an efficient heuristic which is shown to outperform standard approaches when running simulations for a variety of useful distribution laws.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2018-09-24 |