Asymptotic scheduling

We deal with the following scheduling problem: a finite set of jobs is given and each job consists in the execution of an infinite number of tasks. A task is a sequence of operations and each operation requires a specific machine. A machine can process only one operation at a time and preemption is not allowed. Performance measures of the processing system involve fixing a time horizon $T$, counting the number of tasks completed within $T$ for each job and maximizing a specified function of these numbers to estimate the throughput of the schedule. Whilst computing the throughput for a given $T$ is in general an extremely difficult problem, it is shown in this paper that the limit, as $T$ tends to infinity, of the average throughput (i.e$.$ the throughput divided by $ T $) can be easily computed via Linear Programming under fairly mild conditions. This quantity, which may be called the asymptotic throughput, can be used to assess a bound on performance measures of real systems. Buffers play a crucial role and buffer sizes can be taken care of in assessing the system performance.