Optimal schedulings with gaps for independent jobs in a service system with~$N$ servers

K. V. Shakhbazyan ; N. B. Lebedinskaya

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms, Tome 70 (1977), pp. 205-231

Résumé

One considers the problem of forming the optimal schedulings with gaps for a service system with $N$ identical parallel processors. In the service one performs $K$ jobs, each of which consists of $V_1$ homogeneous independent operations and has lower and upper directive times $d_i$ and $D_i$. For the operations which constitute the jobs, one considers linear penalty functions outside the interval $[d_i,D_i]$. One solves the problem of finding the schedulings with a minimal total penalty and having the origin in a given interval $[t_1,t_2]$. It is proved that for an arbitrary set $Z$ of jobs, the penalty function $F_Z(t)$, where $t$ is the origin of the scheduling, has a unique minimum for $t\in(-\infty,\infty)$. We present an algorithm for the construction of the optimal scheduling requiring $C\cdot K(\max_i\{D_i\}-\min_i\{d_i\}+\sum_1^kV_i)$operations on an electronic computer.