A lot of three identical items is to be sequenced through three machines. Each item must be processed first on machine 1, then on machine 2, and finally on machine 3. It takes 20 minutes to process one item on machine 1, 12 minutes on machine 2, and 25 minutes on machine 3. The objective is to minimize the total work span to complete all the items.
a) Write a linear program to achieve our objective. (Hint. Let xi j be the starting time of processing item i on machine j. Two items may not occupy the same machine at the same time; also, an item may be processed on machine (j + 1) only after it has been completed on machine j.)
b) Cast the model above as a network problem. Draw the associated network and give an interpretation in terms of flow in networks. (Hint. Formulate and interpret the dual problem of the linear program obtained in (a).)
c) Find an initial feasible solution; solve completely.