The machine shop depicted in the figure that follows has a heat treatment workstation at point 1, forges at points 2 and 3, machining centers at points 4, 5, and 6, and a grinding machine at 7.

Each grid square indicated is the same size.

Processing of a camshaft product begins with heat treatment, then goes to any forge, then moves to any machining center, and finishes at the grinding machine. Movement between workstations is rectilinear (i.e., north/south displacement plus east/west).

(a) Show that the problem of computing a minimum total movement camshaft routing can be modeled as a shortest path problem.
Also sketch the corresponding digraph, and label it with arc lengths.

(b) Is your digraph acyclic? Explain.

(c) Determine which of the algorithms of this chapter would solve your shortest path problem most efficiently, and justify your choice.

(d) Apply your chosen algorithm to compute an optimal movement.

Transcribed Image Text:

2 1 4 5 6 3 7