0
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You are right, I need more assumptions on this cost function ... $\endgroup$
    – Optidad
    Jun 16 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.