Scheduling Tasks with Non-Overlap & Precedent Requirements

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,
'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?