The nonpreemptive scheduling of $n \geqslant 1$ stochastic jobs is considered to minimize the expected number of parallel machines needed to meet given waiting-time constraints. The number of machines available is unlimited. The running times of the jobs are denoted $T_1 , \ldots ,T_n $ and are taken to be independent samples of an exponentially distributed random variable T with mean 1. Job waiting times are to be bounded stochastically by a nonnegative random variable W, independent of $T_1 , \ldots ,T_n $. At time zero, a timer is started with an initial value W, and job scheduling begins. When the timer expires, all jobs still waiting for a machine are assigned to available machines. Only the distributions of W and the job durations $T_1 , \ldots ,T_n $ are known to the scheduler in advance. A scheduling policy is defined which is proven to be optimal when W has an exponential distribution, and is asymptotically optimal as $n \to \infty $, when W is a constant (hard-deadline). In the exponential case, an explicit formula for the cost function is derived. The uniqueness question is also resolved. The paper concludes with a partial analysis of the general hard-deadline problem, which leads to a policy that we think is optimal. A proof of optimality, however, remains an open problem.

This paper provides an examination of an abstract moving-server system that models several computer applications, including software debugging and accessing compressed data. In this model, the server moves on the unit interval $[0,1]$, serving requests where they are encountered. The locations of successive requests are not known in advance, but they are known to be independent samples from a given distribution F on $[0,1]$. Before serving a request, the server must be moved to a reset point to the left of the request. There is a choice of two reset points, one fixed at 0 and one, called the checkpoint, that can be moved in the course of serving requests. The cost of serving a request is proportional to the distance moved to the request from the chosen reset point. This paper formulates a stochastic optimization problem whose solution, for a wide class of distributions F, yields a policy for deciding the successive locations of the checkpoint so as to minimize the expected total cost of serving a sequence of requests. Results for both finite and infinite-horizon variations of the problem are presented, along with the properties required of the distribution F.

The authors analyze a model of a movable-head disk system with two read/write heads maintained a fixed distance d apart on each arm. Successive request-addresses are assumed to be independent random variables, uniformly distributed over the set of cylinders. The purpose of the analysis is to find that value of d which minimizes the expected seek time per request, assuming that seek time varies linearly with the distance z traveled by the heads. The authors extend an earlier analysis of this model to more general seek-time characteristics which take into account nonlinear acceleration effects. Detailed results, combining both analysis and simulation experiments, are presented for seek times linear in z/sup alpha /, 0>

Two mathematical models dealing with optimal placement of directories on disk devices are analyzed. Storage addresses on the disk are approximated by points in the interval [0, 1]. Requests for information on the disk are represented by a sequence of file names. To process a request, a read-write head is first moved to a directory kept on the disk that specifies the address of the file, and then a head is moved to the specified address. The addresses are assumed to be independent and uniform on [0,1]. In the first model we consider a system of two heads separated by a fixed distance d and a directory situated at 0 ≤ x ≤ 1. In the second model we consider a system consisting of one head and n ≥ 2 directories at 0 ≤ x 1 < x 2 < … < x n ≤ 1. For both models we study the problem of finding those values of the parameters that minimize the expected head motion to process a request in statistical equilibrium.

A mathematical model of computer disk storage devices having two movable read/write heads is studied.Storage addresses are approximated by points in the continuous interval [0, 1], and requests for information on the disk are processed first-come-first-served.We assume that the disk heads are maintained a fixed distance d apart; that is, in processing a request, both heads are moved the same distance in the same direction.Assuming that successive requested locations are independently and uniformly distributed over [0, 1], we calculate the invariant measure of a Markov chain representing successive head positions under the nearer-server rule: Requests in [0, a t] are processed by the left head, those in [1 -d, 1] by the right head, and those in [d, 1 -d] by the nearer of the two heads.Our major objective is the equilibrium expected distance E(d) that the heads are moved in processing a request.For the problem of designing the separation distance d, we show that E (0.44657) ffi 0.16059 ffi mindE(d).Thus, a basic insight of the analysis is that a system with two heads performs more than twice as well as a system with a single head.The results are compared with those for other two-head disk systems.Finally, numerical results are presented that demonstrate that the nearer-server rule is very nearly optimal under the fixed head-separation constraint.