Séminaire de Martin Durand

We investigate multi-organizational scheduling problems. In this setting, multiple organizations each own a set of identical machines and sequential jobs with distinct processing times. The challenge lies in optimally assigning jobs across organizations’ machines to minimize the overall makespan while ensuring no organization’s performance deteriorates. We investigate the conflicting objectives of obtaining an efficient schedule, in terms of minimization of a global objective function, and obtaining a fair schedule, in terms of satisfying each organization as much as possible. These two problems are studied in terms of approximation, i.e., how fair is a schedule maximizing efficiency and how efficient is a schedule maximizing fairness; and in terms of computational (parameterized) complexity.