Collective schedules: Axioms and algorithms

The collective scheduling problem consists in computing a schedule of tasks that are shared among multiple individuals. Tasks may have different durations, and individuals express preferences regarding the order in which these shared tasks should be executed. This problem has numerous applications, since tasks may represent public infrastructure projects, events scheduled in shared spaces, or collaborative work among coworkers. Given the individuals’ preferred schedules (provided by voters), the objective is to return a consensus schedule. We propose and study the collective scheduling problem by applying classical properties from computational social choice, and by introducing new properties that take into account task durations. We show that some of these properties are incompatible, and we analyze which properties are satisfied by four different rules. These rules are either generalizations of well-known voting rules from computational social choice (such as the Kemeny rule and the Spearman rule), or variants of classic scheduling approaches that aim to minimize task earliness and tardiness. We also conduct experiments to evaluate the performance of these rules with respect to different metrics. From an algorithmic perspective, we show that while one of these rules can be computed in polynomial time, the other three are NP-hard. Nevertheless, we provide dynamic programming algorithms that solve these NP-hard problems for realistic instance sizes.