A manufacturing processconsists of five operations that can be performed simulta

Question

A manufacturing processconsists of five operations that can be performed simultaneously onfive

machines. The tablebelow gives for each operation the time in minutes it takes toperform on each

machine. Is it possibleto assign the five operations to the five machines so that thewhole manufacturing

process is completedwithin 4 minutes? (Hint: Use an appropriate bipartite graph tomodel the

problem. Show that arequired assignment of operations to the machines corresponds to aperfect

matching in thegraph.)

      M1 M2M3 M4M5

O1 4    5    3    6      4

O2  5     6    2    3      5

O3 3     4    5     2    4

O4 4    8    3     2   7

O1 2     6    6    4     5

Explanation / Answer

This identical problem is discussed on page 569 of the book"Graph Theory And Its Applications", 2nd Edition, by Gross andYellen if you want to read more about it at the library. To solveit you need to replace each entry in your 5x5 matrix which is 4 orless with a 1. Anything more than 4 is replaced with a zero. Youthen need to check and see if there are 5 ones, no two of which arein the same row or column. If you do this you'll see that themanufacturing can be done in 4 minutes. There are 3, and only 3,ways in which this is possible: First Way:    {O1-M5, O2-M3, O3-M2, O4-M1, O5-M4} Second Way:    {O1-M5, O2-M3, O3-M2, O4-M4, O5-M1} Third Way:    {O1-M5, O2-M4, O3-M2, O4-M3, O5-M1} You should now be able to show that this assignment is aperfect graph.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---