Problem I want to optimize (complete in the shortest time possible) my morning routine with my family. There are steps that we have to do individually (ex. I shower), and there are steps we have to do together (ex. me & my daughter have to make her breakfast together, since she's quite young). Each person can only do one thing at a time, and there are relationships between some steps that dictate order (ex. me & my daughter must make breakfast, before she can eat it).
Model I've modeled this as a linear programming / optimization problem with a series of jobs that all have unique durations, precedents, and resources.
- The duration of each job is how long is must run
- The precedents is a list of other jobs that must complete before this one can start (this list can be zero or more other jobs)
- The resources is a list of resources (in this case, person/people) needed to complete the job.
All precedent jobs must be complete before a job can be run. And a resource (person) can only do one thing at a time.
Here is some pseudo-code representing some example data
'make_kid_breakfast': {
'title': 'Make Kid Breakfast',
'duration': 4,
'resources': ['dad', 'kid'],
'precedents': ['wake_kid']
}
'kid_eat': {
'title': 'Kid Eats Breakfast',
'duration': 15,
'resources': ['kid'],
'precedents': ['make_kid_breakfast']
}
'kid_dress': {
'title': 'Kid Gets Dressed',
'duration': 7,
'resources': ['kid'],
'precedents': ['layout_kid_clothes', 'kid_eat']
},
Constraints The precedent constraints are fairly straight forward. I've answered another's question around this part of the problem here.
Project scheduling using linear programming
The answer, I think, is simply to ensure that a job starts after all its precedent jobs have completed.
for j in jobs:
for p in precedents:
add_constraint(start_time_of_j >= start_time_of_p + duration_of_p)
Where I get stuck is in the resource constraint. The above appropriately de-conflicts all the precedents, but it's still possible for a single resource to get "over-booked". For example, my shower isn't related to me making breakfast with my daughter (I could technically make breakfast before or after the shower); however, I can't do two things at once.
I have an answer, but I'm concerned for two reasons. (1) It converts the problem to a MIP and (2) it just seems inefficient. It uses the answer here to prevent two jobs from overlapping by ensuring that either the start_time of job 1 is after the end time of job 2 or the end_time of job 1 is before the start_time of job 2.
Linear Programming - Preventing Staff Scheduling Shift Overlap?
$$ \begin{align} &S_i\ge (S_j + D_j) - M\delta_{i,j} \\ &S_j\ge (S_i + D_i) - M (1-\delta_{i,j})\\ &\delta_{i,j}\in \{0,1\} \end{align} $$
- where $S_x$ is the start-time of job x
- where $D_x$ is the duration of job x
- these combined mean that $S_x + D_x$ is the end-time of job x
- where $M$ is a large enough constant (e.g. length of planning window)
- where $\delta_{i,j}$ is a binary variable for each combination of jobs $i$ and $j$
To create these non-overlaps I have to choose every combination of jobs that are assigned to a resource. For example, if I am a resource on 10 jobs, then I get every pair of jobs within the 10 (10 choose 2 = 45) and create the two constraints (a total of 90 constraints) for each one. I then repeat this process for each resource’s list of jobs.
I also seem to get some serious performance variability depending on the $M$ value I pick. And it doesn't seem right that it should vary so drastically (the difference of taking a few seconds to taking a few minutes) based on M. Because then I worry about how to pick $M$ in each case.
Summary So the summary of the answer I have is (1) ensure precedents of jobs is respected and then (2) ensure that every resource is only working on one thing at a time.
¿Can anyone thing of a better way to structure an LP for this that avoids the MIP formulation or makes it more efficient/consistent?