Updating an optimal structured scheme

T. E. Safonova

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part V, Tome 111 (1981), pp. 151-161

Résumé

An optimal structured schedule at time $t$ is considered for a set of jobs $Z$ with given start and due date $[\alpha_i,D_i]$ volumes $V_i$ (volume is defined as the number of homogeneous independent elementary operations of unit length that comprise the job), and penalty functions. The penalty for selecting an element of job $i\in Z$ at time $t$ is $\varphi_i(t)$. The schedule penalty is the total penalty of all the elements of all the jobs. An optimal schedule is a minimum-penalty schedule. We investigate the impact of changing the volume of a job from the set $Z$ on the structure of the optimal schedule. Algorithms are proposed for handling the modified job set with both reduced and enlarged job volumes. These algorithms require $k$ computer operations, where $k$ is the number of jobs in the original set, $l$ is the change in job volume (expressed by the number of units), and $c$ is a constant.