1.3 Job Allocation Problem [20 points] A mobile phone company has a number of technicians (workers) with the task of repairing faults that occur in its network. Every day the company creates a list of all repair jobs that have to be performed and assigns each job to a worker. However there are certain constraints: each worker can service only one repair job per day each worker can potentially service a subset of the repair jobs, i.e. workers have different abilities, each worker has a different cost of performing a specific repair job For example, assume that there are nine technicians (workers) employed and at the specific day there were nine repair jobs. The table below presents information regarding workers and jobs, indicating for each worker, the ordered list of jobs he/she can perform. Worker ID Jobs 1 4,1,3,5 2 6,3,5,2 3 8,4,5,7 4 3,7,8,9 5 7,1,5,6 6 8,4,7,9 7 5,6,7,4 8 2,6,8,3 9 1,3,9,6 A problem instance for the job allocation problem. Order in the list of jobs is associated with the cost of servicing each job by a worker. For example, according to the table above: Worker 1 can do jobs 4, 1, 3, 5 with costs 1, 2, 3, 4 respectively Worker 2 can do jobs 6, 3,5, 2 with costs 1, 2, 3, 4 respectively, etc. The total cost of repairing all the faults is the sum of costs for each repair job. Obviously, the company would like each day to have a valid allocation of jobs to workers that has the minimum cost. In general, a job allocation problem of size N, consists of N workers and N repair jobs to be allocated, with each worker being able to perform N div 2 jobs (N II 2) out of the N jobs. The subset of jobs that the worker can service is ordered, indicating the worker's cost of repairing each job. A solution is an allocation of jobs to workers that is valid, i.e. workers get jobs that appear in their job list, each worker gets one job and no two workers are assigned the same job. The total cost of solution is the sum of all repair costs. An optimal solution is a valid solution with minimum cost. Formally define the job allocation problem and justify the state description and operators you selected. Note that your definition should describe the general problem i.e. for problems concerning any number of workers and jobs. 1.3 Job Allocation Problem [20 points] A mobile phone company has a number of technicians (workers) with the task of repairing faults that occur in its network. Every day the company creates a list of all repair jobs that have to be performed and assigns each job to a worker. However there are certain constraints: each worker can service only one repair job per day each worker can potentially service a subset of the repair jobs, i.e. workers have different abilities, each worker has a different cost of performing a specific repair job For example, assume that there are nine technicians (workers) employed and at the specific day there were nine repair jobs. The table below presents information regarding workers and jobs, indicating for each worker, the ordered list of jobs he/she can perform. Worker ID Jobs 1 4,1,3,5 2 6,3,5,2 3 8,4,5,7 4 3,7,8,9 5 7,1,5,6 6 8,4,7,9 7 5,6,7,4 8 2,6,8,3 9 1,3,9,6 A problem instance for the job allocation problem. Order in the list of jobs is associated with the cost of servicing each job by a worker. For example, according to the table above: Worker 1 can do jobs 4, 1, 3, 5 with costs 1, 2, 3, 4 respectively Worker 2 can do jobs 6, 3,5, 2 with costs 1, 2, 3, 4 respectively, etc. The total cost of repairing all the faults is the sum of costs for each repair job. Obviously, the company would like each day to have a valid allocation of jobs to workers that has the minimum cost. In general, a job allocation problem of size N, consists of N workers and N repair jobs to be allocated, with each worker being able to perform N div 2 jobs (N II 2) out of the N jobs. The subset of jobs that the worker can service is ordered, indicating the worker's cost of repairing each job. A solution is an allocation of jobs to workers that is valid, i.e. workers get jobs that appear in their job list, each worker gets one job and no two workers are assigned the same job. The total cost of solution is the sum of all repair costs. An optimal solution is a valid solution with minimum cost. Formally define the job allocation problem and justify the state description and operators you selected. Note that your definition should describe the general problem i.e. for problems concerning any number of workers and jobs