0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.