Finish n jobs in d steps by backtracking

Question

I have several groups of tasks, each group is a chain of tasks, groups are independent of each other. Tasks within a group can only be processed in the order which is determined by the chain of that group.

Each task has an ID and a cost. Tasks are atomic, they can only be finished at once by investing time units equal to their cost into them (it's not possible to solve half of a task). At the beginning of each step there are m time units available.

I want to check if it is possible to finish all tasks within a given number of steps d.

Here are some pictures to clarify the situation, each task is a 2-tuple (ID, Cost), the tasks in the chains can only be solved from left to right.

Here is a graphic example of 6 tasks arranged into 3 groups:

Let's say that m = 5 (there are 5 time units available during each step) and that d = 4 (we want to check if all tasks can be finished within 4 steps). A possible soulution would be:

Another possible solution would be:

An invalid solution would be (it finishes all tasks in 5 steps, we said that the limit is 4):

My question:

For given:

• tasks which are arranged into groups
• a number of time units m available at each step
• and a number of steps d which are allowed

determine if it is possible to solve all tasks within d steps, if so then output a possible sequence (task ID's) in which the tasks can be solved such that <= d steps are done.

My current approach:

I try to find a solution by backtracking. I create a list of deques to model the groups, then I look at the set A (all the tasks which can be solved during the current step, the leftmost element of each group) and find all subsets B (subsets of A whose sum of costs is <= d and to which no other task can be added such that the sum of costs stays <= d). The subsets of set B represent the tasks which I consider solving during the current step, now each subset represents a choice, I do a recursive call for each of them (to explore each choice) where I pass the list of deques without elements in B (I remove them from the deques because from now on I consider them solved in this branch of recursion). The recursive calls stop once the depth of recursion is > d (the number of allowed steps is exceeded) or a solution is found (the list of deques is empty, all tasks have ben solved within <= d steps).

PseudoJavaish code:

// sequence[1] = j means that task 1 is done at step j
// the param steps is used to track the depth of recursion
findValidSequence (ArrayList<Deque> groups, int[] sequence, int steps) {

    if (steps > d)   // stop this branch since it exceeds the step limit d

    if (groups.isEmpty())  // 0 tasks left, a solution is found, output sequence

    Set A = getAllTasksSolvableDuringCurrentStep();

    Set B = determineAllTheOptionsForTheNextStep(A);

    // make a recursive call for each option to check if any of them leads to a valid sequence
    for (each element in B)  
        findValidSequence(groups.remove(B), sequence.setSolvedTasks(B), steps+1);


}

I get lost trying to implement this correctly, what do you think of my approach, how would you solve this problem?

Note:

The problem is pretty general as lots of scheduling problems (m machines and n precedence constrained jobs) can be reduced to such a problem.

Answer 1

Here’s a suggestion for calculating B. It’s a very good observation that it boils down to "Given an array of integers, find all subsets whose sum is <= m and to whom we can't add any other element from the array such that <= m is not violated". So I have solved this simpler problem only and trust you to adopt the solution to your situation.

As I aired in a comment, I am using recursion. Each recursive calls looks at one element from A and tries a solution with that element and a solution without that element.

In each call to the recursive method I am passing A and m, these are the same in every call. I pass a partial solution telling which of the previously considered elements are included in the subset currently being built, and the sum of the included elements just for convenience.

/**
 * Calculates all subsets of a that have a sum <= capacity
 * and to which one cannot add another element from a without exceeding the capacity.
 * @param a elements to put in sets;
 * even when two elements from a are equal, they are considered distinct
 * @param capacity maximum sum of a returned subset
 * @return collection of subsets of a.
 * Each subset is represented by a boolean array the same length as a
 * where true means that the element in the same index in a is included,
 * false that it is not included.
 */
private static Collection<boolean[]> maximalSubsetsWithinCapacity(int[] a, int capacity) {
    List<boolean[]> b = new ArrayList<>();
    addSubsets(a, capacity, new boolean[0], 0, Integer.MAX_VALUE, b);
    return b;
}

/** add to b all allowed subsets where the the membership for the first members of a is determined by paritalSubset
 * and where remaining capacity is smaller than smallestMemberLeftOut
 */
private static void addSubsets(int[] a, int capacity, boolean[] partialSubset, int sum,
        int smallestMemberLeftOut, List<boolean[]> b) {
    assert sum == IntStream.range(0, partialSubset.length)
            .filter(ix -> partialSubset[ix])
            .map(ix -> a[ix])
            .sum() 
            : Arrays.toString(a) + ' ' + Arrays.toString(partialSubset) + ' ' + sum;
    int remainingCapacity = capacity - sum;
    if (partialSubset.length == a.length) { // done
        // check capacity constraint: if there’s still room for a member of size smallestMemberLeftOut,
        // we have violated the maximality constraint
        if (remainingCapacity < smallestMemberLeftOut) { // OK, no more members could have been added
            b.add(partialSubset);
        }
    } else {
        // try next element from a.
        int nextElement = a[partialSubset.length];
        // i.e., decide whether  should be included.
        // try with and without.

        // is including nextElement a possibility?
        if (nextElement <= remainingCapacity) { // yes
            boolean[] newPartialSubset = Arrays.copyOf(partialSubset, partialSubset.length + 1);
            newPartialSubset[partialSubset.length] = true; // include member
            addSubsets(a, capacity, newPartialSubset, sum + nextElement, smallestMemberLeftOut, b);
        }

        // try leaving nextElement out
        boolean[] newPartialSubset = Arrays.copyOf(partialSubset, partialSubset.length + 1);
        newPartialSubset[partialSubset.length] = false; // exclude member
        int newSmallestMemberLeftOut = smallestMemberLeftOut;
        if (nextElement < smallestMemberLeftOut) {
            newSmallestMemberLeftOut = nextElement;
        }
        addSubsets(a, capacity, newPartialSubset, sum, newSmallestMemberLeftOut, b);
    }

It’s slightly tricky in a few spots. I hope my comments will help you through it. Otherwise please ask.

Let’s try it out:

    int[] a = { 5, 1, 2, 6 };
    Collection<boolean[]> b = maximalSubsetsWithinCapacity(a, 8);
    b.forEach(ba -> System.out.println(Arrays.toString(ba)));

This code prints:

[true, true, true, false]
[false, true, false, true]
[false, false, true, true]

• [true, true, true, false] means a subset of 5, 1 and 2. The sum is 8, so this fits the capacity of 8 exactly (m).
• [false, true, false, true] means 1 and 6, sum is 7 and we could not add 2 or we would exceed the capacity
• finally [false, false, true, true] means 2 and 6 and also fits the capacity m exactly.

I believe this exhausts the possibilities within your constraints.