Inequalities and bounds for the scheduling of stochastic jobs on parallel machines

Journal of Applied Probability - Tập 22 Số 3 - Trang 739-744 - 1985
Michael Pinedo1, Zvi Schechner1
1Columbia University

Tóm tắt

Consider n jobs and m machines. The m machines are identical and set up in parallel. All n jobs are available at t = 0 and each job has to be processed on one of the machines; any one can do. The processing time of job j is Xj, a random variable with distribution Fj. The sequence in which the jobs start with their processing is predetermined and preemptions are not allowed. We investigate the effect of the variability of the processing times on the expected makespan and the expected time to first idleness. Bounds are presented for these quantities in case the distributions of the processing times of the jobs are new better (worse) than used.

Từ khóa


Tài liệu tham khảo

10.1017/S0021900200097345

Feller, 1966, An Introduction to Probability Theory and its Applications, 2

Coffman E. G. Jr , Frederickson G. N. and Lucker G. S. (1984) A note on expected makespans for largest-fit sequences of independent tasks on two processors. Math. Operat. Res.

10.1002/nav.3800130402

Marshall, 1972, Classes of distributions applicable in replacement with renewal theory applications, Proc. 6th Berkeley Symp. Math. Statist. Prob., 1, 395

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

Journal of Applied Probability

Tập 22 Số 3

739-744

Thông tin tác giả