8

There are five jobs to be assigned to five machines and associated cost matrix is as follows $$ \begin{matrix} \text{Machine} & 1 & 2 & 3 & 4 & 5 \\ \text{Job A} & [11, &17, &8, &16, &20] \\ \text{Job B} & [9, &7, &12, &6, &15] \\ \text{Job C} & [13, &16, &15, &12, &16] \\ \text{Job D} & [21, &24, &16, &28, &26] \\ \text{Job E} & [14, &10, &12, &11, &15] \end{matrix} $$ The question is now: Find the assignment of machines to jobs that will minimize the total cost?

I solved it using the Hungarian method but for job A and D I had only one zero that too in the same column. I don't know how to solve further if this happens.

JakobS
  • 2,757
  • 1
  • 10
  • 28
Tango
  • 83
  • 3
  • 4
    Since this looks a lot like a homework question, it would be best to show you intermediate steps of your attempt to solve it – Michael Feldmeier Jun 18 '19 at 09:20
  • 1
    As a note, I voted to reject a tag edit of "self-study" because I think that would be a meta-tag. Not sure that we fully settled on that as a policy, but I think we were leaning that direction. (https://or.meta.stackexchange.com/questions/163/what-is-the-soft-question-tag) Also, welcome to OR.SE, @Tango! – E. Tucker Jun 18 '19 at 14:15
  • @E. Tucke At Cross Validated https://stats.stackexchange.com/ , self-study tag is applied to all homework problems, and even for questions requesting help understanding passages in textbooks, even f being used in self-study outside any courses. – Mark L. Stone Jun 18 '19 at 23:12
  • 1
    @MarkL.Stone Sounds good! The tag seems accurate; it's more that it's a meta-tag. If the community wants to go that direction, that's fine by me. – E. Tucker Jun 19 '19 at 12:13

1 Answers1

5

I assume you're applying the matrix version of the algorithm. When you happen to have only one $0$ for A and D the matrix is \begin{align*} \pmatrix{2&9&0&8&8\\2&1&6&0&5\\0&4&3&0&0\\4&8&0&12&6\\3&0&2&1&1} \end{align*} Now continue with Step 3: cover all zeros minimally, and adjust the weights. After that step you will find a solution.

Marcus Ritt
  • 2,715
  • 13
  • 35
  • That is exact matrix I got now when covering all zeros I have r=4 covering lines and since problem has n=5 since r<n. STEP3: now 1 is least uncovered element subtracting 1 from all uncover element and adding 1 to element at intersection of covering line I am left with matrix that has same problem only one zero in A and D but now r=n . Can i use same step again when I have r=n – Tango Jun 18 '19 at 14:26
  • The least uncovered element will be $2$. Note that line $5$ will be unmarked after step 3. – Marcus Ritt Jun 19 '19 at 05:14