3
$\begingroup$

Consider the well-known Number Partitioning / "Multiprocessor Scheduling Problem": You want to partition a set $S$ of objects (jobs) $i$ with weights $w_i$ (process time) into subsets $S_k$ (e.g. processor queues), such that the following value is minimal ("when all jobs are finished"):

$$max_k\left(\sum_{i\in S_k} w_i\right)$$

I would be strongly interested in the following generalizations, which I try to formulate in the above language: Suppose you had sessions on the multiprocessor with each maximal weight/length $W$. You want to partition $S$ into subsets $S_{l,k}$ ($l$ the session, $k$ the specific processor queue), such that the following value is minimal ("overall running time")

$$\sum_{l} max_k\left(\sum_{i\in S_{l,k}} w_i\right) \qquad \forall_{l,k} \sum_{i\in S_{l,k} w_i}\leq W$$

Does this problem exist in literature? Or can I transform it to a different standard-task? Or has anyone ad-hoc a clue how to solve this fast? (I have an idea with dynamical programming, but I'm not experienced at these sort of things)

$\endgroup$
2
  • 3
    $\begingroup$ OK. So what is your question? Gerhard "Ask Me About System Design" Paseman, 2013.03.15 $\endgroup$ Mar 15, 2013 at 17:43
  • $\begingroup$ Sorry (added it)....of course I want to solve it algorithmically ;-) $\endgroup$ Mar 17, 2013 at 1:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.