Graph optimization for parallel processing

Question

Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color:

The structure can be represented by a weighted undirected graph (images being the nodes, edges representing overlaps and the weights representing overlap areas or time needed to process them):

The images are to be rendered on surface while overlaps require extra processing (e.g. avergaing the pixels for transparency).

For example, we can decide to merge A,B first. The situation becomes:

After each merge, the graph has to be updated. In this case, only images C,D are to be merged and the algorithm finishes with single composite image.

You can observe that if the merging algorithm runs in parallel, it can now process C and D simultaneously.

However, if we start merging A,C first, then B and D are blocked and the algorithm can run only sequentially (considering that individual image can be used by single thread / cannot be shared).

Given the graph, I would like to schedule parallel computation for $N$ computing units (e.g. CPU cores).

The schedule for $N=2$ can look like this

iteration #1
    core 1: A-B
    core 2: waiting
iteration #2
    core 1: (A-B)C
    core 2: (A-B)D

I think the scheduler should aim for two objectives:

1. Minimize the number of iterations (i.e. utilize maximum number of cores at any given time)
2. Balance load to all cores at any given iteration (i.e. assign them approximately same areas of overlap so that they will finish approximately at the same time; unnecessary waiting would spoil the benefits of parallel computation).

The first objective is important while the second is "nice to have" (the time needed to process an overlap is proportional to its area).

I am stuck with two major problems:

• What algorithm to use? Backtracking with storing current best solution?
• Would it be easier to schedule tasks for $N=\infty$ (maximize parallelism) rather that $N$ being corresponding to actual number of processing units available?
• Only the overlap areas between pairs of images are known, but since the image are merged in the process, how to compute new overlaps (e.g. C(A-B))?

The greedy version of the algorithm would look like this:

Grab as much overlapping image pairs as possible such that no two pairs themselves are overlapping.
Sort the pairs in N bins such that each bin contains roughly same total area.
Merge images in parallel.
Update graph and repeat until single node remains.

I know this question is maybe too broad. I believe this problem has been certainly solved many times in parallel computation projects so many people from parallel computing areas should have some immediate ideas and hints.

Once solved, I plan to write an elaborate answer to benefit you as well. But first I need something to start with. Thanks.