0
$\begingroup$

I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed before the second one can be started (and so on). What is an algorithm to find the best schedule for these jobs so that the total time is minimized?

$\endgroup$
  • $\begingroup$ The hint I was given mentioned branch and bound and memoization, but I don't know how that fits into this. $\endgroup$ – Brian Nov 19 at 5:03
0
$\begingroup$

There is a simple pseudo-polynomial time algorithm that works when all tasks take the same unit time. You can transform your problem into this by rounding all completion times to some greatest common divisor, and splitting all longer tasks up into copies of unit portions. E.g. if your original completion times were $6$, $8$ and $12$ seconds you could use $2$ seconds as your unit time. Then you'd have respectively 3 copies, 4 copies and 6 copies of the unit task in a row.

Let's name the two queues $A$ and $B$. Let $T[i,j]$ be the optimal time needed to run the first $i$ tasks from $A$ and the first $j$ tasks from $B$. Let $A[i]$ be the resources required for task $i$ from $A$ and similarly for $B$. Let $m$ be the maximum number of resources available.

Of course $T[x,0] = T[0,x] = x$. Then:

$$T[i,j] = 1 + \begin{cases}T[i-1, j-1] & \text{if }A[i] + B[j] \leq m\\\min (T[i-1,j], T[i,j-1]) &\text{otherwise}\end{cases} $$

If you keep track of your choices you can reconstruct the optimal solution. The above is also amenable to bottom-up dynamic programming, in fact you only need to have two arrays $T_i[j]$ and $T_{i-1}[j]$.


I'm not claiming the above is terribly good or an optimal solution, but it's a simple algorithm that gets the job done. Perhaps someone else has a better answer.

| cite | improve this answer | |
$\endgroup$

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.