# Efficient structure for pruning on job scheduling

This is an issue I encountered on several applications with different variants. But here is the common base for which I suspect to miss a more efficient approach.

There are $$K$$ different tasks to schedule on something (a product, some data, whatever...). Any order of actions is acceptable, but the cost (in time for exemple) of a task may be estimated with a complex function depending on the task and the combination of tasks already realized. The goal is to minimize the cost to achieve all tasks completion.

I use a bit array to keep track of the realized tasks (1=completed, 0=to do) and then explore the different paths with Dijkstra algorithm if $$K$$ is reasonable enough to look for optimal solution else with some heuristic variant. A state is a total cost and a task bit array.

Each time a new state is explored, one has to decide to eventually prune it. My idea is that if any other cheaper explored state (previously explored state using Dijkstra algorithm) has a greater task completion, it may be pruned. By greater, I mean that any task completed in the former is done in the latter. Using bitwise operations on two task bit arrays $$A$$ and $$B$$, it means: $$A \ge B \implies A \& B = B$$
Note that this is not an ordering, there is no way to compare for exemple $$0011$$ and $$0110$$.

But of course, it is not efficient to test every previously explored state at every new one. The best solution I found until now, is to keep a list $$L$$ of previous states to compare to. When a new state $$A$$ is explored, I compare it to every state $$S$$ of $$L$$ :

• if $$S \ge A$$, $$A$$ is pruned (stop looping)
• else if $$S \le A$$, A replaces $$S$$ in $$L$$ and is accepted (stop looping)

if I reach the end of the loop without filling one of these two conditions, I append $$A$$ to $$L$$ and accept it.

But I feel that there is a more efficient structure for explored states. Any idea ?

## 1 Answer

If you don't assume anything more about the "complex function" that returns the cost of a task, then in the worst case you will be forced to explore $$\binom{n}{n/2}$$ subsets of tasks.

Consider the following game for sake of argument. I play the role of the adversary (I decide the complex function) and you play the scheduler. I (hidden from you) select a special set S of $$n/2$$ tasks. As long as you ask what is the cost of a task, I will return 0 for the first $$n/2 - 1$$ tasks. Then when you get to the $$n/2$$ task, I will return 0 if and only if the set of tasks you selected so far is exactly S, and otherwise I return a large value $$M$$. Since there is no way for you to find out any information about S until you selected $$n/2$$ elements, all you can do is try all possible subsets of $$n/2$$ tasks.

• You are right, I need more assumptions on this cost function ... Jun 16 at 8:14