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?