0

Cyclic allocation is a method of assigning $n$ tasks to $p$ workers. The foreman allocates task $k$ to worker $k \mod p$.

$$a = k \mod p$$

Now I am interested in how the worker can calculate his allocation without the help of the foreman. As he knows his id number, he can simply compute the his set of work including the task with the same id number as himself, adding $id + p$, $id + p + p$ and so on until the task number is greater than $n$.

Now for the questions:

  1. Is a set the best way to define the tasks each worker has to do? How
  2. can I formally define the worker's set, as calculated by himself?
  3. Are there any other ways to define these tasks?
Asaf Karagila
  • 393,674
jsj
  • 535

1 Answers1

1

Yes, a set seems appropriate (unless the tasks have to be performed in a particular order, then a suitable tuple (which includes an ordering for the tasks) would make more sense).

You could represent the task set of worker $k$ as follows:

$${\rm Tasks}(k) = \{m\mid 1 \le m \le n \text{ and } m \equiv k \pmod p\}$$

where $m \equiv k \pmod p$ simply denotes that $m$ and $k$ have the same remainder modulo $p$.

In an ordered tuple rendering, you'd probably end up with something like:

$${\rm Tasks}(k) = (k, k+p, \ldots,k+lp)$$

where $l = \left\lfloor\frac{n-k}p\right\rfloor$ is used to determine the last task that worker $k$ has to perform.

Lord_Farin
  • 17,743