Worker Order

This notebook addresses a question (“[Ordering of resources for maximizing success[(https://math.stackexchange.com/questions/4271163/ordering-of-resources-for-maximizing-success)”) on Mathematics Stack Exchange. The problem is as follows. There are 32 workers and 16 tasks. Any worker can attempt any task. Success is random, with worker \(i\) having probability \(w_i\) of success on any task. Note that (a) the probability of success depends on the worker but is independent of the task and (b) success on any task does not alter the likelihood of success on the next task. If a worker fails on a task, the next worker attempts the task and the worker that failed becomes unavailable for any future tasks.

The objective is to sequence the workers so as to maximize the probability that all tasks are completed. In this notebook, we will set up a random problem and experiment with different sequences.

Setup

Our first step is to set up a test data set. We limit individual probabilities to below an arbitrary threshold to avoid getting overall success probabilities within rounding error of 1.0, but the conclusions remain the same even if we set the upper limit to 1.0.

set.seed(308)                    # seed the random number generator
nTasks <- 16                     # set the number of tasks
nWorkers <- 32                   # set the number of workers
w <- runif(nWorkers, min = 0, max = 0.7)   # generate worker success probabilities

Next, we set up a function that takes a permutation of the probability vector and returns the probability that all tasks are completed successfully. To avoid redundant computations and to provide additional evidence (for verification/debugging) of how a result was obtained, the function will return a matrix with one row for each worker slot (so that row one corresponds to the first worker in the permuted sequence) and one column for each task. The value in the cell \((i,j)\) of the matrix will be the probability that the last \(j\) tasks are completed given that the worker in schedule slot \(i\) is assigned to the next remaining task.

# Input: x is a permutation of the worker success probabilities
# Output: a matrix of partial probabilities
p.success <- function(x) {
  # Initialize the matrix.
  pSuccess <- matrix(nrow = nWorkers, ncol = nTasks)
  # For the last task (one remaining, so column 1 of the matrix), the probability of
  # success is one minus the probability that all remaining workers fail (product of
  # the complements of their success probabilities).
  for (n in 1:nWorkers) {
    pSuccess[n, 1] <- 1 - prod(1 - x[n:nWorkers])
  }
  # For more than one task remaining, the probability of finishing them is the
  # probability that the next available worker succeeds in the current task times
  # the probability that the remaining workers including that one finish the
  # remaining tasks, plus the probability that the next worker fails times the
  # probability that the remaining workers excluding the current one finish the
  # remaining tasks including the current one.
  for (t in 2:nTasks) {
    # If we are down to one worker, the probability of success is the probability
    # that worker finishes all remaining tasks.
    pSuccess[nWorkers, t] <- x[nWorkers]^t
    # Otherwise, the probability of success is the probability that the current
    # worker succeeds in the current task and the current and remaining workers
    # succeed in the remaining tasks plus the probability that the current worker
    # fails the current task and the remaining workers complete the current and
    # remaining tasks.
    for (n in (nWorkers - 1):1) {
      pSuccess[n, t] <- x[n] * pSuccess[n, t - 1] + (1 - x[n]) * pSuccess[n + 1, t]
    }
  }
  # Return the probability matrix.
  pSuccess
}

Results

For all experiments, the overall probability of success is the entry in row 1 (first worker is up) and column nTasks (all tasks yet to be done) of the matrix.

First, we try the workers in their original order.

result <- p.success(w)
cat("Original order probability of success = ", result[1, nTasks], ".\n")

Original order probability of success =  0.792882 .

Next, we try sorting the workers into ascending order of success probability (worst worker first).

result <- p.success(sort(w))
cat("In ascending probability order, probability of success = ", result[1, nTasks], ".\n")

In ascending probability order, probability of success =  0.792882 .

Now we try descending probability order (best worker first).

result <- p.success(sort(w, decreasing = T))
cat("In descending probability order, probability of success = ", result[1, nTasks], ".\n")

In descending probability order, probability of success =  0.792882 .

Last, we randomize the worker order.

result <- p.success(sample(w, nWorkers))
cat("In randomized order, probability of success = ", result[1, nTasks], ".\n")

In randomized order, probability of success =  0.792882 .

In repeated experiments, order of workers does not affect the overall success probability.