Parallel job scheduling using marginal analysis

Marginal analysis pervades economic and physical theory. Yet, little research in the area of parallel job scheduling has exploited this technique in order to allocate processors among parallel jobs in a multiprocessing, multiprocessor environment. In this paper, we examine "where best" to (re)allocate each of m processors based on a comparison of its marginal benefit among a set of n (n less than or equal to 5 m) malleable jobs. Using this strategy with full a priori information available to the job scheduler, we compare the average time-to-completion and overall time-to-completion (or throughput) with the benchmark strategy of "shortest job first". The simulation results demonstrate that marginal analysis markedly improves both system efficiency and system performance over the "shortest job first".