Question

Problem from the book Scheduling: Theory, Algorithms and Systems, Fifth Ed by Michael L Pinedo Chapter 3 3.20. Consider the problem 1 || Lmax. The Minimum Slack first (MS) rule selects at time t, when a machine is freed, among the remaining jobs the job with the minimum slack max(dj − pj − t, 0). Show through a counterexample that this rule is not necessarily optimal.

Answer 1

The challenge with minimum slack first rule is that it takes into consideration the current slack time only. It compares between the two values of either dj – pj – t and 0 to see which one is maximum. In most case the value of t is constant between all the tasks this makes it affectively a comparison of dj – pj.

While the pj is a fixed value for a given process, the dj value changes as we select and begin the operation on any task. Let us consider the beginning time as x and ending time as y. This means we also need to consider the

(dy-dx) – (py-px) for every process. However if we do not consider this, then there may be tasks where the dj < pj.

Thus in the beginning even though dj > pj, by the end of a task, there is a possibility that dj < pj. This would mean that the system is falling behind in the schedule. This is not optimal.