Minimization of the maximum deviation with preemption

N. B. Lebedinskaya

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms, Tome 80 (1978), pp. 117-124

Résumé

We solve the scheduling problem to minimize the maximum deviation of the job completion times from the respective deadlines, with the starting time at an integer point in the interval $[t_1,t_2]$. It is shown that for an arbitrary set of jobs $Z$. the optimal-schedule penalty function $F_Z(t)$ (as a function of the integer argument $t$) is such that $\Delta F_Z(t)= \begin{cases} -1, & t\in(-\infty,a(Z)-1],\\ 0, & t\in[a(Z),b(Z)-1],\\ +1, & t\in[b(Z),+\infty) \end{cases}$ for some integer $a(Z)\leqslant b(Z)$. If $a(Z)$ and $b(Z)$ coincide, the function $\Delta F_Z(t)$ has no zero values. An optimal scheduling algorithm is proposed which requires $C\cdot K\bigl(\max_i\{D_i\}-\min_i\{d_i\}+\sum_1^kV_i\bigr)$ computer operations.