Three different items are to be routed through three machines. Each item must be processed first on machine 1, then on machine 2, and finally on machine 3. The sequence of items may differ for each machine. Assume that the times ti j required to perform the work on item i by machine j are known and are integers. Our objective is to minimize the total time necessary to process all the items.

a) Formulate the problem as an integer programming problem. [Hint. Let xi j be the starting time of processing item i on machine j. Your model must prevent two items from occupying the same machine at the same time; also, an item may not start processing on machine (j + 1) unless it has completed processing on machine j.]

b) Suppose we want the items to be processed in the same sequence on each machine. Change the formulation in part (a) accordingly.