Scheduling Algorithms

Question

I Need to send a number of packets from A to B. A and B are connected by different paths of different lengths (all disjoint). Paths have different capacities too (like I can't overfill them).

I have a number of paths to choose from. I can send packets concurrently.

Which strategy should I follow to get the fastest completion time (of all packets sent)?

Shortest path First? Round Robin?

Is there a way to quantitatively order them based on capacity and length?

Answer 1

If my understanding is correct, this is like minimizing the total completion time of $n$ tasks (packets) on $m$ machines (paths)…You can solve this with integer programming.

Create the following variables:

• $z\ge 0$: completion time

• $t_{ip}\ge 0$: time at which item $i$ (fills $c_i$ capacities) takes path $p$ (of length $l_p$ and capacity $C_p$)

• $y_{ip}=1$ if and only if item $i$ takes path $p$, 0 otherwise
• $\omega_{ij}^p=1$ if and only if items $i$ and $j$ take path $p$ simultaneously

So you want to minimize the overall completion time: $$ Minimize\quad z$$ subject to:

• $\sum_{p\in Paths}y_{ip}=1$ for all items $i$ (you want to send all items)
• $z\ge t_{ip}+l_p$ for all items $i$, paths $p$ (this will give you the overall completion time)
• $c_iy_{ip}+\sum_{j\neq i}c_j\omega_{ij}^p\le C_p$ forall items $i$, paths $p$ (capacity constraints for all paths $p$)
• $+$ linking constraints between variables $t$ and $\omega$, still trying to figure it out

Answer 2

I am wondering if there isn't a simpler solution to this problem.

Suppose you have $n$ items. For every path $p$ of length $l_p$, create $n-1$ other paths $p_2,\cdots,p_n$ with lengths $2l_p$, $3l_p$, … , $nl_p$, and identical capacities as path $p$.

Here is how to interpret these extra arcs. If an item takes path $p_2$ for example, this means that other items necessarily took path $p_1$ saturating its capacity, so the item has to wait for the path to be empty, hence a $2l_p$ length.

Now, this is a simple minimum cost flow algorithm. Does this make any sense?