Campaign Scheduling

Download Now Date Added: Aug 2012
Format: PDF

The authors study the problem of scheduling in parallel systems with many users. They 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. They define a theoretical model for Campaign Scheduling and show that, in the general case, it is NP-hard.