1
$\begingroup$

I am currently working in the area of operations research / scheduling and am attempting to write a short proof. We are working with a directed acyclic graph of activities (Activity-on-Node-representation) that need to be scheduled while adhering to precedence constraints. We are using the critical-path-method to determine earliest start times ($ES_j$) and earliest finish times ($EF_j$) of these activities, see screen shot. $p_j$ is the duration of an activity $j$.

Forward-recursion earliest start times

This is very straight forward established theory.

However in the problem at hand, the durations $p_j$ of activities are not fixed, but can be freely chosen, the only requirement being some imposed bounds ($p_{j,max}$ and $p_{j,min}$) on the activity durations.

I now have to prove that when choosing $p_j = p_{j,min}$, so all activities are being processed with their minimum durations, that then the earliest start times of all activities are also minimized. This should be so trivial to show, however I have only very little experience when it comes to formalizing these thoughts.

Because of this recursive nature of the algorithm in the screen shot, I believe that proof by induction is the most suitable approach here. Could anyone guide me in the right direction here? I believe that the final "proof" will boil down to a one-liner as the whole idea is fairly trivial.

If all predecessors of an activity $j$ are assigned their "minimum-duration" $p_{i,min}$, then the earliest start of that activity $j$ will also be minimized.

Or something along the lines of: "The earliest start time of the final activity $j=J+1$ is minimized when all earliest finish times of its predecessors ($P_j$) are minimized. For the earliest finish times of these predecessors to be minimized, they need to be processed with their respective minimum duration $p_{i,min}$, where $i \in P_j$ as well as having their earliest start $ES_i$ minimized." Then, we again are left with the problem of minimizing all $ES_i$, so basically the same problem as we started with, revealing the recursive nature of the problem.

Alternative approach via Linear Programming:

An alternative I have thought of (which however might be a little "overkill") comes from linear programming theory and is the following: Model the problem as a linear program with the objective to minimize all earliest finish times and then show that only setting the activity durations to their corresponding minimum durations will result in the optimal solution. The argument is that only when setting activity durations to their minimum [and have the corresponding constraints regarding lower bounds of activity durations bind], only then the shadow prices of all constraints are non-negative.

The LP would look something like this:

$min \; z = \sum^{J+1}_{j=0} ES_j$
$s.t.$
$ES_i+p_i \leq ES_j \quad\forall\; j \in J \quad\forall\; i \in P_j $
$p_j \leq p_{j,max} \quad\forall\; j \in J$
$p_j \geq p_{j,min} \quad\forall\; j \in J$
$ES_0 = 0$

Quick verbal explanation: Minimize the sum of all finish times, subject to: The earliest start of an activity ($ES_j$) is larger or equal than the largest finish time of all its predecessors, the set of predecessors being denoted as $P_j$. [The expression $ES_i + p_i$ simply captures the earliest finish time of a predecessor $i$]. The duration of an activity is a decision variable in the model and is denoted as $p_j$. $p_j$ has to lie inbetween $p_{j,min}$ and $p_{j,max}$. The earliest start of activity $j=0$ is 0: $ES_0 = 0$.

$\endgroup$
2
  • $\begingroup$ For the first part, you could suppose the bound of each duration such that the current duration $P_j$ has been the minimum bound. (e.g. $P_1 = 2 \implies P_1(2,5)$ which $2$ should be lower bound. By this assumption, the critical path and the rest of the definitions hold the same. For the second part, I doubt for minimizing The earliest start time of the final activity $j$, the only way would be to minimize the earliest finish times of its predecessors. $\endgroup$
    – A.Omidi
    Nov 10, 2021 at 8:46
  • $\begingroup$ Also, please, be aware that the critical path occurs on the activities with zero slack, and by changing the activities duration, it may change the critical path. Is that what you are looking for? $\endgroup$
    – A.Omidi
    Nov 10, 2021 at 8:46

1 Answer 1

1
$\begingroup$

I would go with proof by contradiction. Let S be the schedule obtained using minimal processing times and let S' be a schedule for which at least one task j starts earlier than it does in S. Now look at the predecessors of j and identify the predecessor j' of j for which j' starts earlier in S' than in S and no predecessor of j' starts earlier. Note that (a) j' could be j and (b) a "first" task j' with earlier start must exist because j has finitely many predecessors.

Now derive a contradiction by showing that if all predecessors of j' start at least as early in S as in S', and they all have minimal processing time, j' cannot start earlier in S' than in S.

$\endgroup$
1
  • $\begingroup$ Thank you so much for your input, Prof. Rubin! Your help is highly appreciated (not only for my specific question at hand but also for the whole OR community in general). $\endgroup$
    – derhendrik
    Nov 15, 2021 at 10:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.