Insertion of a random task in a schedule: a real-time approach

We consider a set of tasks defined by their duration and their due-date. They are performed by a single resource and scheduled in order to minimize the sum of the delays. This schedule is given. An unexpected task appears in the system. Its duration, as well as its due date that cannot be violated, are known at the instant of the appearance. The aim is to insert this task in the schedule while increasing as little as possible the criterion of the existing schedule that is the sum of the delays. We then consider the case when the unexpected task is made of two subtasks separated by a fixed period. In both cases the main difficulty is to insert the unexpected task in real time, which implies that the proposed method should manage to make most of the computation off-line.