Managing a Complex of Jobs with Uncertain Execution Request Arrivals

Abstract. This paper considers the scheduling problem for a complex of basic jobs under the condition that at some uncertain times, execution requests for supplementary higher-priority jobs are received. If a supplementary job request arrives during the execution of a basic job, then the latter is terminated and must be restarted at some time upon the complete service of the former. All jobs (basic and supplementary) are executed without interruption. By assumption, during the execution of a basic job, two or more supplementary job requests are unlikely to arrive, and such cases are not analyzed. Also, a supplementary job request can arrive only after the complete service of the previous supplementary request. Two problem formulations are studied as follows. In the first, the performance criterion is the completion time of the basic job complex, and the problem is to minimize this time. In the second formulation, the probability of a collision is minimized, as a situation where a supplementary job request arrives during the execution of a basic job. The problems are solved via their reduction to infinite zero-sum two-player (antagonistic) games and the discrete approximation of the latter by finite games. Model examples are considered. The problem formulation with non-fixed durations of the basic jobs, linearly dependent on the amount of additional resources allocated, is investigated as well. In this case, job scheduling is reduced to a linear programming problem.

Keywords: job scheduling, collision, zero-sum two-player game, antagonistic game, non-renewable resources, mixed strategy, optimal strategy.