Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime

Journal of Applied Probability - Tập 23 Số 3 - Trang 841-847 - 1986
Richard Weber1, Pravin Varaiya2, Jean Walrand2
1University of Cambridge
2University of California, Berkeley

Tóm tắt

A number of jobs are to be processed using a number of identical machines which operate in parallel. The processing times of the jobs are stochastic, but have known distributions which are stochastically ordered. A reward r(t) is acquired when a job is completed at time t. The function r(t) is assumed to be convex and decreasing in t. It is shown that within the class of non-preemptive scheduling strategies the strategy SEPT maximizes the expected total reward. This strategy is one which whenever a machine becomes available starts processing the remaining job with the shortest expected processing time. In particular, for r(t) = – t, this strategy minimizes the expected flowtime.

Từ khóa


Tài liệu tham khảo

10.1017/S0021900200107843

10.1017/S0021900200046921

Conway, 1967, The Theory of Scheduling.

Weber, 1980, Optimal Organization of Multi-server Systems

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

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

Journal of Applied Probability

Tập 23 Số 3

841-847

Thông tin tác giả