Question

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.1. Describe the problem space consisting of state representation, start state, goal state (can be implicit) and operators.2. What is it’s branching factor?3. 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!)

Answer 1

1.The problem space consists of a set of jobs to be scheduled on a server farm and the machines that the jobs can be assigned to. The start state is a representation of the server farm with each job unassigned to a machine. The goal state is a state in which the jobs are assigned to the machines in such a way that the running time of the machine with the longest running time is minimized. The operators are the actions of assigning a job to a machine, which can be chosen based on the running time of each job and the current running time of each machine.

2.The branching factor is the number of machines that each job can be assigned to, which is equal to the number of machines in the server farm.

3.The cost associated with a state is the running time of the machine with the longest running time. The cost associated with an edge is the additional running time that would be added to the machine if the job is assigned to it.