Multi-agent planning and scheduling concerns finding a joint plan to achieve some set of common goals with several independent agents each aiming to find a plan or schedule for their part of the goals. To avoid conflicts in these individual plans or schedules decoupling is used. Such a decoupling entails adding local constraints for the agents such that they can schedule autonomously within those constraints, while they guarantee that a conflict-free global solution can be constructed from the individual agents’ schedules. In this paper we investigate finding an ‘optimal’ decoupling, that maximizes the sum of the agents’ preferences about their scheduling of tasks. We show using a Linear Programming (LP) approach that optimal decouplings can be found efficiently by exploiting the properties of a task scheduling instance.