SCSC2003 Abstract S81743
A new dispatching rule for stochastic and dynamic job scheduling
A new dispatching rule for stochastic and dynamic job scheduling
Submitting Author: Dr. Umar Al-Turki
Abstract:
In this paper we consider the n job single machine scheduling problem were jobs with stochastic processing time requirements arrive to the system at random times. The performance measure combines both mean and variance of job completion time. Ordering jobs in nondecreasing order of their processing times is known to minimize the mean completion time of job completion times for the static and deterministic case. The optimal schedule for minimizing the variance of job completion time for the same problem is known to satisfy the V-shape property, i.e. the optimal schedule is V-shaped. However, finding the one that is optimal is an NP-hard problem. The problem we are considering in this paper combines the two performance measures for stochastic and dynamic environment. Simple dispatching rules are usually used in scheduling jobs in such environments.
A dispatching rule is designed to minimize the performance measure for the described system that takes into consideration the above cited results from scheduling theory. The suggested rule balances the two arms of the V-shape schedule over time in a way that reflects the relative weights of the two performance measures. That balance is controlled by a parameter, w, which is a function of the relative weights, � of the two measures. The relation between the two parameters is studied through extensive experimentation on a simulation model built using AWESIM. In addition some other variations of the rule are tested using the same model for selecting the best implementing policy of the rule. The final findings and recommendations are reported at the end of the study.
Back to SCSC2003 Abstracts