6
$\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.

$\endgroup$
  • 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 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 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 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 at 12:13
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.

$\endgroup$
  • $\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 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 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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