=10-35 A line manager plans to complete six jobs on machines that have already been selected. It wishes to accomplish this over the next five time periods.

Conceivably, it could complete all the jobs in period 1 or wait to complete all the jobs in period 5. More likely, it will build complete one or more jobs in each time period.

(a) Characterize the selection problem in terms of linear constraints involving integer-valued variables.

Be sure to define your symbols and explain the meaning of each restriction. In each part below, show how the stated stipulation can be encompassed by an integer programming formulation.

Consider each of the parts separately.

(b) Jobs 1, 2, and 3 must be started no later than period 3.

(c) No more than two jobs can be started in any time period.

(d) No more than three jobs can be started in the first two periods, and no more than five jobs in the first four periods.

(e) Exactly three jobs must be started in the first two periods, and five jobs in the first four periods.

(f) Job 2 cannot be started before Job 1 (they can be started in the same period).

(g) Jobs 4, 5, and 6 cannot be started before Jobs 1, 2, and 3 are started, (all six jobs can be started in the same period).

(h) Jobs 1 and 2 must be started in the same period.

Similarly, Jobs 3, 4, and 5 must be started in the same period.

(i) If Jobs 1 and 2 are started in the same period, then no other Jobs can be started in that period.

(j) In Job 1, the company starts either Jobs 1 and 2 or Jobs 3 and 4. (Assume one of these two possibilities must occur.)

(k) In the first two periods, the company starts either Jobs 1 and 2, or Jobs 3 and 4. (Assume one of these two possibilities must occur).

(l) Job 1 can be started in period 1 only if either Job 2 or Job 3 is started, but not if both Jobs 2 and 3 are started.