# Modelling a complex work schedule

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.

• 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? 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) 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. Apr 21, 2016 at 13:52
• Is there a cost (money or time) to go to the exchange? Apr 21, 2016 at 14:53
• Yes, more trips to the exchange is a worse outcome. Apr 21, 2016 at 15:00