9

I've got a real-world problem that I'm trying to represent and automate. I've simplified and abstracted it down to the following:

  • There are n places of work (P1, P2, ..., Pn).
  • Each place, Pn has a key, Kn.
  • There are m Workers, (W1, W2, ..., Wm).
  • In order to work at Pn, a worker must hold Kn.
  • Each key can either be held by a worker, or left at the Exchange, E.

  • A worker can make a trip to the Exchange at any time to pick up some unclaimed keys or drop off some keys for others to use.

  • Now, there is an exogenous work schedule that must be completed in a strict order. For example:

    • 2016-04-21 W1 must work at P6
    • 2016-04-21 W2 must work at P3
    • ** exchange of keys required **
    • 2016-04-22 W3 must work at P3
    • 2016-04-22 W2 must work at P6

  • Any number of workers might have to work at Pn at some point in their schedule, although never on the same day

We know:

  • The starting location of all the keys, either with workers or at E
  • The future work orders that each worker will have to fulfil

So, I'm struggling to model this whole situation. Can you suggest data structures and algorithms I should be looking at in order to get a grip on it and start to optimise the trips to the exchange for each worker?

What I want to minimise is the total number of trips to E. A secondary goal would be to ensure that no worker makes a disproportionate number of trips.

Thanks in advance!!

Improve this question
7
  • 2
    Average number of trips to E per worker = "total number of trips" / m. So if m is constant, your two goals are the same goal. More interesting: I guess each worker can carry more than one key at the same time?
    – Doc Brown
    Commented Apr 21, 2016 at 12:14
  • Yes, workers can carry any number of keys. Regarding "average" I think I expressed myself poorly. I was thinking more about fairness, that no worker should have to complete a disproportionate number of trips, so a low variance. (edited question to match)
    – Gareth Lloyd
    Commented Apr 21, 2016 at 12:43
  • Since workers are obviously trusted with keys and may keep keys over night and for as long as necessary - as long as an exchange is not required - why not make a set of keys for each worker that they keep permanently? Alternatively, create a set of keys for each worker for all places they go for a given time period, say, a week. Keys are duplicated as needed to make a week-set for every worker. All workers exchange keys once a week.
    – radarbob
    Commented Apr 21, 2016 at 13:52
  • Is there a cost (money or time) to go to the exchange?
    – Dan Pichelman
    Commented Apr 21, 2016 at 14:53
  • Yes, more trips to the exchange is a worse outcome.
    – Gareth Lloyd
    Commented Apr 21, 2016 at 15:00

1 Answer 1

Reset to default
1

The question is a little ambiguous on one key point: which elements are we attempting to solve for. Are we looking at optimizing the order in which resources are delegated? Minimizing trips to the exchange? Maximizing work order throughput?

With that in mind, I'm going to assume that we could be doing any mixture of these things and keep the answer fairly high level.

The first thing that comes to my mind is that the interrelated problems that this attempts to solve are mostly centered around dependency management. Workers, keys and locations can be thought of as dependencies that must be resolved in order to complete work jobs.

Taking this to the next level, I would look at an adaptation of topological sorting (https://en.wikipedia.org/wiki/Topological_sorting). Model the problem space as a large graph (modern graph databases might be a good medium for some of this analysis as well) and then use various topological sorts to solve for different aspects of the problem space.

On a slight tangent, this sounds like a really fun project. Today, I envy you sir.

Improve this answer
2

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.