Timeline for How to allow multiple assignments for jobs in Hungarian Algorithm?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2020 at 10:20 | vote | accept | ephemeral | ||
| Jun 9, 2020 at 16:53 | answer | added | Mark L. Stone | timeline score: 8 | |
| Jun 9, 2020 at 16:41 | comment | added | ephemeral | @MarkL.Stone Yes it is optimal, I just added the formal description to render clarity upon the previous comments. I am in complete agreement with your answer. | |
| Jun 9, 2020 at 15:01 | comment | added | Mark L. Stone | Per my previous comment, for each row $i$ (job), assign it to the worker $j$ which minimiizes $C_{i,j}$. I.e., assign the job to the cheapest worker. For this problem the greedy algorithm is simple and optimal. If my algorithm does not optimally solve your problem, what is incorrect about my understanding? | |
| Jun 9, 2020 at 14:47 | comment | added | ephemeral | @MarkL.Stone I have updated the description formally, the cost matrix is known and does not vary according to the number of jobs assigned to a worker | |
| Jun 9, 2020 at 14:46 | history | edited | ephemeral | CC BY-SA 4.0 |
formal description
|
| Jun 9, 2020 at 11:47 | comment | added | Mark L. Stone | Is the cost per job for worker i to do job j the same no matter how many jobs are done by that worker? if so, for each job, just assign the cheapest worker. if there are limits on how many jobs a worker can do, or that cost is not linear in tghe number of jobs a worker does, you need to make that explicit. | |
| Jun 9, 2020 at 3:48 | comment | added | ephemeral | I have updated the statement. | |
| Jun 9, 2020 at 3:48 | history | edited | ephemeral | CC BY-SA 4.0 |
added 107 characters in body
|
| Jun 8, 2020 at 20:23 | comment | added | prubin♦ | Are you looking to assign multiple jobs to a single person, a single job to multiple people (to be split among them), or both? | |
| Jun 8, 2020 at 18:33 | comment | added | Mark L. Stone | What, exactly, do you wish the constraint (and objective) to be? | |
| Jun 8, 2020 at 17:53 | history | asked | ephemeral | CC BY-SA 4.0 |