Skip to Main content Skip to Navigation
Conference papers

Campaign Scheduling

Résumé : We study the problem of scheduling in parallel systems with many users. We analyze scenarios with many submissions issued over time by several users. These submissions contain one or more jobs; the set of submissions are organized in successive campaigns. Jobs belonging to a single campaign are sequential and independent, but any job from a campaign cannot start until all the jobs from the previous campaign are completed. Each user's goal is to minimize the sum of flow times of his campaigns. We define a theoretical model for Campaign scheduling and show that, in the general case, it is NP-hard. For the single-user case, we show that an ρ-approximation scheduling algorithm for the (classic) parallel job scheduling problem is also an ρ-approximation for the Campaign scheduling problem. For the general case with k users, we establish a fairness criterion inspired by time sharing. We propose FAIRCAMP, a scheduling algorithm which uses campaign deadlines to achieve fairness among users between consecutive campaigns. We prove that FAIRCAMP increases the flow time of each user by a factor of at most kρ compared with a machine dedicated to the user. We also prove that FAIRCAMP is a ρ-approximation algorithm for the maximum stretch. By simulation, we compare FAIRCAMP to the First-Come-First-Served (FCFS). We show that, compared with FCFS, FAIRCAMP reduces the maximum stretch by up to 3.4 times. The difference is significant in systems used by many (k > 5) users. Our results show that, rather than just individual, independent jobs, campaigns of jobs can be handled by the scheduler efficiently and fairly.
Complete list of metadatas
Contributor : Grégory Mounié <>
Submitted on : Saturday, March 2, 2013 - 2:13:49 PM
Last modification on : Wednesday, July 8, 2020 - 5:03:21 PM




Vinicius Pinheiro, Krzysztof Razdca, Denis Trystram. Campaign Scheduling. HiPC 2012 - 19th international Conference on High Performance Computing, Dec 2012, Pune, India. pp.1-10, ⟨10.1109/HiPC.2012.6507489⟩. ⟨hal-00796259⟩