In a distributed environment, there are two directions that we can follow to process a set of jobs. In the first direction, each server executes a specific type of job; in the second direction, the servers may be switched dynamically and preemptively from one type of job to another. Care should be taken, however, since switching costs may not be negligible. This work follows the second direction, and studies optimal and heuristic policies for dynamic allocation.
It is assumed that there are M different job types. For example, one job type can be a Web site access, whereas another type can be a costly database operation. Two different job types have different processing costs, resource consumption, and completion demands. These factors make the allocation decision a very challenging research problem.
Two key issues are investigated: the determination of an optimal allocation policy, and the application of heuristics that try to reduce the overall cost as much as possible.
In addition to the theoretical investigation of the issue, experimental results are given, demonstrating that the applied heuristics perform very well. The average execution cost of the heuristic-based allocation is slightly worse than that of the optimal allocation policy. In general, the best policy is the optimal one, the second best policy is the one based on heuristics, and the static allocation shows the worse performance in all cases studied. The results of this study can be used in modern distributed environments, where the end user is not aware of the server that executes a submitted job.