Consider the basic E/T problem with due dates as decisions, and suppose that the due dates follow the SLK rule. (See Chapter 2.) That is, each job has equal slack, so the form of the due date for job j is dj = pj + k.

a. Find an expression for the sum of earliness and tardiness in the form of a scalar product that can be minimized by matching the smallest coefficient with the largest processing time, the second smallest coefficient with the next largest processing time, and so on.

b. Find the optimal value of k.

c. Now suppose that the due dates follow the CON rule. That is, each job has the same flow allowance, or dj = k. Repeat

(a) and

(b) for this case, and show that, for any given set of processing times, the optimal value of the objective function is the same for CON and SLK.