Scheduling functionality is described for resolving conflicts in the schedules of respective client devices, where the schedules are used to govern the recordation of media programs by the respective client devices. The client devices use virtual tuner functionality to receive media programs over respective communication channels, each channel having a prescribed amount of available bandwidth in which to receive media information. The scheduling functionality includes a conflict identification module for identifying conflicts in the schedules, a solution enumeration module for enumerating solutions to the conflicts, and a conflict resolution module for resolving the conflicts based on the output of the solution enumeration module. In one case, the schedules can be partitioned into a plurality of time segments, and solutions can be enumerated for each time segment in turn.