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

We consider a schedule of bitasks. A bitask is a pair of tasks separated by an idle period. The bitasks concerned by the schedule are processed on a single resource. A task is non-preemptive. The criterion used to build this schedule is the minimzation of the sum of the delays. The schedule is given. An unexpected bitask appears in the system. The processing time of each one of the tasks as well as the idle period between the tasks are known only when the bitask appears. We know that the processing times of the two tasks of the bitask are the same. The bitask that appears has a deadline that cannot be violated. The goal is to insert this bitask in the schedule while increasing as little as possible the sum of the delays of the initial schedule. The difficulty of this problem is to proceed in real-time. To reach this goal, we propose an algorithm in which the main part of the computation is performed off-line. We take advantage of the problem features and of parallelism engineering to reduce the computation time of this part. The complexity of the remaining computation, that is the computation that should be performed on-line, is polynomial.