On the optimality of static priority policies in stochastic scheduling on parallel machines

Journal of Applied Probability - Tập 24 Số 2 - Trang 430-448 - 1987
Thomas Kämpke1
1Universität Passau

Tóm tắt

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g(U) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of wi while job i is incomplete, the sufficient condition is simply w1 ≧ … ≧ wn and λ1 w1 ≧ … ≧ λn wn.

Từ khóa


Tài liệu tham khảo

Trivedi, 1982, Probability and Statistics with Reliability, Queuing and Computer Science Applications.

10.1007/978-3-642-68874-4_10

10.1145/322234.322242

10.1017/S0021900200107843

10.1007/978-3-642-46534-5_6

Möhring, 1985, Stochastic scheduling problems II: set strategies, Z. Operat. Res., 29, 65

Prasad, 1982, Letter to the editor, J. Appl. Prob., 19, 741, 10.2307/3213539

Weber, 1982, Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime, J. Appl. Prob., 19, 167, 10.2307/3213926

10.1017/S0021900200112008

10.1017/S0021900200046921

Thông tin
Thông tin xuất bản

Journal of Applied Probability

Tập 24 Số 2

430-448

Thông tin tác giả