8
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Since this looks a lot like a homework question, it would be best to show you intermediate steps of your attempt to solve it $\endgroup$
    – Michael Feldmeier
    Jun 18, 2019 at 9:20
  • 1
    $\begingroup$ 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. (or.meta.stackexchange.com/questions/163/…) Also, welcome to OR.SE, @Tango! $\endgroup$
    – E. Tucker
    Jun 18, 2019 at 14:15
  • $\begingroup$ @E. Tucke At Cross Validated 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. $\endgroup$
    – Mark L. Stone
    Jun 18, 2019 at 23:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – E. Tucker
    Jun 19, 2019 at 12:13

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Tango
    Jun 18, 2019 at 14:26
  • $\begingroup$ The least uncovered element will be $2$. Note that line $5$ will be unmarked after step 3. $\endgroup$
    – Marcus Ritt
    Jun 19, 2019 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.