The throughput of pipelined processing of heterogeneous multitasked jobs is computed and optimized in this study. There are K job classes. Each job has M tasks which have to be processed in a given order (same for all tasks) on a pipeline of M processors. Tasks have random processing times. The jobs of each class form a stationary and ergodic sequence (with respect to their task processing times). Classes are differentiated by distinct statistics and may not be jointly stationary or ergodic. Thus, the jobs are overall statistically heterogeneous. The authors are interested in the average execution time per job nτ, when the job populations of the various classes become very large (asymptotically). This is shown to depend on the order in which jobs enter the pipeline. Under the natural class-based ordering, where all jobs of the first class enter first, followed by those of the second, third, and so on, the quantity nτ is computed, but is shown not to attain its minimal value in general. On the contrary, appropriate statistical multiplexing of jobs of different classes on the pipeline is shown to minimize the average execution time per job on every sample path (with probability one). The procedure, called balanced statistical multiplexing, is constructed and the minimal nτ is computed in terms of the average execution times of the job tasks.
