On arrival scheduling of real-time precedence constrained tasks on multi-processor systems using genetic algorithm

摘要

This paper models the problem of precedence based real-time task scheduling as a dynamic constraint problem. It presents a new scheduling approach, termed as 'Dynamic Genetic Algorithm for Real-Time Scheduling' ((d)GA-RTS). The significant feature of (d)GA-RTS is that it can handle dynamic as well as static scheduling of inter-dependent tasks for real-time systems. In parallel or distributed systems, the main aim of dynamic task scheduling is to allocate processors to a given set of tasks to execute them within optimized completion times without violating the task dependencies, if any. The (d)GA-RTS schedules the tasks in the waiting list when any new task arrives in the scheduler and minimizes the overall schedule length of the task set ensuring deadline compliance. We also illustrate an implementation technique to deal with synchronization problems in multi-processor systems. In order to exhibit the applicability of our approach, we perform experiments with suitable benchmark as well as synthetic test cases. Further, we conduct extensive simulations and compare the results with different performance metrics. The comparative study of the results with existing approaches indicates that our proposed approach is more efficient in generating feasible solutions. (C) 2018 Elsevier B.V. All rights reserved.