An approach based on operation insertion for one-machine real-time scheduling

摘要

In this paper, we address a one-machine real-time scheduling problem with a continuous input of new jobs subject to time limit constraints. Our aim was to build up an approach that optimizes the execution number of input tasks but which maintains the actual tasks available at the beginning of the processing within their characteristic temporal intervals. We have proposed to solve this problem by constructing a new schedule that accounts for the new circumstances relative to the occurrence of a task arrival. The proposed approach aims at characterizing an insertion position (if any) so as to satisfy the temporal constraints and optimize the criterion. Two algorithms solving such real-time scheduling problem have been elaborated for specific features of the input tasks. Application examples are discussed.