Greedy approach suggestions for assigning objects
This problem reduces to finding a maximum matching in a bipartite graph, which can be done easily by e.g. the Ford-Fulkerson algorithm. You construct the graph as follows:
Take all elements of type $a$ on one side and all elements of type $b$ on the other. Then, for any two elements $a_i,b_j$, draw an edge between them if they do not belong to the same category.
If there is a matching in the set with only, say, $k$ pairs belonging to the same category, then we can find a matching in our graph on $m-k$ edges, where $m$ is the number of a's (or b's).