Algorithm for scheduling jobs on processors

Question

As per iehrlich's comment (thanks btw), the term "scheduling" might be misleading and this might be a more appropriate description: given a matrix N*N, find a row permutation that will yield the largest diagonal sum.

I have a set of N jobs and N processors. All processors can be different from each other. For each (job, processor) pair, I have the performance of that job running on that processor. Performance is measured in IPC (Instructions Per Cycle).

I'm trying to find a schedule (1-to-1 allocation) that maximizes the overall sum of IPC. I can do it by going over all possible schedules, with O(N!), which is not viable.

I then tried to use the "stable matching" algorithm O(N^2), using the IPCs to sort the workloads' and the processors' preferences. It runs very fast and returns a decent schedule, but not the optimal one.

My questions are:

1) I really expected the stable matching algorithm to be able to return the optimal assignment. Can somebody explain why it fails? My best guess so far is the existence of ties between different (job, processor) pairs. I also tried the "stable matching with indifference" algorithm with no luck. I should mention that the algorithm doesn't fail because of my implementation of it. I'm looking for a more theoretical answer as to why the algorithm itself cannot solve this problem.

2) Do you know of an algorithm I can use for this? Does one even exist?

Answer 1

The reason why stable matching is the wrong algorithm is that you can wind up with a matching where a pair of processors would each prefer each other's jobs, but one of the jobs prefers the processor that it is on. Switching makes someone worse off, so this matching is stable.

However in your problem we care if the global optimum. If the improvement in one job exceeds how much worse the other gets, you want to switch. For the global optimum being a stable matching is necessary but not sufficient.

The Hungarian algorithm in fact is the right one to to find the globally optimal solution.