Modeling Activities with Earliest-Start and Latest-End

Translate release dates and deadlines into start- and end-time constraints on interval variables, check individual feasibility for mandatory activities, guard the window for optional activities, and compute latest-start and slack.

Step 1 of 157%

Tutorial

Earliest Start and Latest End on a Single Interval

Each scheduled activity is represented by an interval variable xix_i with three attributes:

  • the start time si=startOf(xi),s_i = \mathrm{startOf}(x_i),
  • the end time ei=endOf(xi),e_i = \mathrm{endOf}(x_i),
  • the duration pi=sizeOf(xi),p_i = \mathrm{sizeOf}(x_i),

related by ei=si+pi.e_i = s_i + p_i.

Two of the most common bounds on a scheduled activity are its earliest-start time (also called the release date) rir_i and its latest-end time (also called the deadline) di.d_i. These translate directly into two constraints on the interval:

si≥ri,ei≤di.s_i \geq r_i, \qquad e_i \leq d_i.

Substituting ei=si+pie_i = s_i + p_i into the second inequality gives si+pi≤di,s_i + p_i \leq d_i, or equivalently si≤di−pi.s_i \leq d_i - p_i. Combining the two:

ri  ≤  si  ≤  di−pi.r_i \;\leq\; s_i \;\leq\; d_i - p_i.

For example, an activity with ri=3,r_i = 3, di=15,d_i = 15, and pi=5p_i = 5 must start somewhere in [3, 10],[3,\, 10], since di−pi=15−5=10.d_i - p_i = 15 - 5 = 10.

↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle