Consider scheduling programs (jobs) on a server farm. Assume that the server farm is homogeneous (that is, that a job will take the same amount of time to run regardless of which machine it is run on). Each job will take a given (known) amount of time. We will assign each job to exactly one machine. Each machine, therefore, will have a set of jobs. The time it takes to run all of the jobs on a machine is just the sum of the times it takes to run each job assigned to the machine. The goal is to assign the jobs to minimize the running time of the machine with the longest running time.
a. Describe the state space for this problem.
b. What is it’s branching factor?
c. What is the cost associated with a state and an edge? (hint: start with the cost of the state. The cost of the edge will be calculated based on that!)