I don't exactly understand what needs to be done in this problem. Could someone please explain what I am supposed to be doing a bit clearer than the book?
Four jobs need to be done, and four workers are available. The chart shows how long each worker takes to complete each job. If each job is to be assigned to a different worker, how should the jobs be assigned so that the total number of working hours is minimized?
This is the chart:
J1 J2 J3 J4
Joel 3 4 2 3
Noel 4 2 3 2
Zoel 3 3 2 2
Roel 1 3 2 3
The Js are the job and the names are on the left. The middle numbers are the hours it takes the worker for each job.
Could someone please help me?
Job 1 use Roel because it takes only 1 hr for the job to be done. All others take longer.
Job 2 use Noel because it takes only 2 hrs for the job to be done. All others take longer.
We have Noel and Zoel left.
Job 3 takes Joel and Zoel the same length of time (2 hrs) but job 4 takes Zoel 2 hrs but Joel 3 hrs; therefore, give job 4 to Zoel which leaves job 3 for Joel. Check my thinking.
In this problem, you have four jobs (J1, J2, J3, J4) that need to be assigned to four different workers (Joel, Noel, Zoel, Roel). The chart shows how long each worker takes to complete each job.
To minimize the total number of working hours, you need to assign the jobs in a way that distributes the workload evenly among the workers. One way to approach this is by using a technique called the Hungarian Algorithm or the Munkres Algorithm.
Step 1: Create a matrix based on the chart. The rows of the matrix represent the workers, and the columns represent the jobs. Fill in the matrix with the corresponding hours for each worker and job.
```
J1 J2 J3 J4
Joel 3 4 2 3
Noel 4 2 3 2
Zoel 3 3 2 2
Roel 1 3 2 3
```
Step 2: Find the smallest number in each row and subtract it from every number in that row. This step ensures that each worker is assigned the job they can complete with the least amount of time.
```
J1 J2 J3 J4
Joel 0 1 -1 0
Noel 2 0 1 0
Zoel 1 0 -1 -1
Roel 0 2 1 2
```
Step 3: Find the smallest number in each column and subtract it from every number in that column. This step ensures that each job is assigned to the worker who can complete it in the least amount of time.
```
J1 J2 J3 J4
Joel 0 1 -1 0
Noel 2 -1 0 0
Zoel 1 -1 -1 -1
Roel 0 1 0 1
```
Step 4: Check if the matrix contains a complete set of zeros. If it does, the optimal assignment of jobs to workers has been found. If not, proceed to step 5.
Since the matrix still contains negative and non-zero values, we need to continue to step 5.
Step 5: Identify the minimum number of lines (horizontal and vertical) that are required to cover all the zeros in the matrix.
In this case, we need a minimum of three lines (horizontal or vertical) to cover all the zeros. The lines can be drawn through the rows of workers Joel, Noel, and Roel. This is because the zeros in those rows can be matched directly without affecting any other zero.
```
J1 J2 J3 J4
Joel - - - -
Noel - - - -
Zoel - - -1 -1
Roel - - - -
```
Step 6: Adjust the matrix based on the lines drawn in step 5.
a) Find the smallest uncovered number in the matrix. Subtract it from all uncovered numbers and add it to all numbers that are covered by two lines.
The smallest uncovered number is -1. Subtracting it from the uncovered numbers and adding it to the numbers covered by two lines, we get:
```
J1 J2 J3 J4
Joel - - - -
Noel - - - -
Zoel - - 0 0
Roel - - - -
```
b) Find the smallest uncovered number and repeat step 6a until there are no more uncovered numbers.
No more uncovered numbers are present in the matrix.
Step 7: With the updated matrix, find the assignment of jobs to workers that minimizes the total number of working hours.
Assign J3 to Zoel, J4 to Joel, J1 to Noel, and J2 to Roel. This assignment yields the minimum total number of working hours.
Note: The solution obtained may not be unique. There can be multiple ways to assign the jobs, resulting in the same minimum total number of working hours.