برنامه ریزی فازی با استفاده از سیستم های زمان واقعی

Task scheduling is a main activity in the design of real-time systems (RTS). It assures both functionality and safety of such systems. RTS can be modeled as a set of periodic tasks that must be completed before specific deadlines. In this paper, we investigate the fuzzy scheduling models on RTS and the main methodologies that solve these models. Thus, we present general periodic task scheduling models with fuzzy deadlines and fuzzy processing times; scheduling algorithms based on optimal assignment of the priorities; and a more general framework for designing RTS, Rate Monotonic Scheduling Theory, that includes the scheduling algorithms. A case study will illustrate the use of the theory.

Two di5erent research communities, operational research and computer science, have examined schedulingproblems from their own perspectives. The former focuses on o5-line techniques, the latter on dynamic scheduling. Also the problems are di5erent from a resources, time granularity and metrics point of view. In spite of these di5erences, the abstract problems have much in common. The general scheduling model consists of a system of tasks (), which should be sequenced on a set ofresources (R) under a set of constraints and a set of performance cost functions. Resources: In the most cases, resources are machines or processors: R={R1; R2; : : : ; Rm}: They may be identical or have di5erent processing speeds. In the most general case, there are additional resources as primary or secondary memory,input=output devices, etc. Tasks: A system of tasks can be described by =(T;6; [pij]; {Rj}; {Ij}; {dj}; {t0j}) such that: • T ={T1; T2; : : : ; Tn} is the set of tasks, where a task is an executable section of a program or a production activity;6 is a partial order relation de/ned on T, which speci/es the sequential constraints. Ti6Tj means Ti must be executed before Tj ; • [pij] is the matrix of processingtimes. pij is the time required by task Tj on the resource Ri. When the processors are identical, pj is the processing time of task Tj ; • Rj =[R1(Tj); : : : ; Rm(Tj)], 16j6n, denotes the quantity of resources of type Ri required by task Tj ; • Ij is the period of task Tj . Periodic tasks are those invoked regularly; they have a /nite /xed period. For non-periodic tasks, the periods Ij =∞. Tasks that are invoked more than once but at irregular moments are called aperiodic; • dj is the due date associated with task Tj . The task should be /nished after dj time units since its invocation. If the task must be completed before or at dj , the due date is a deadline. For tasks with no due date, dj =∞; • t0j is the moment of the /rst invocation for task Tj . Scheduling constraints: Usingconstraints, we de-/ne general scheduling conditions such as: • Non-preemptive scheduling: a task cannot be interrupted once it begins execution. • Preemptive scheduling: a task execution can be interrupted. • Priority lists. Performance cost functions: The performance criteria are cost functions de/ned with respect to due dates and completion times of the tasks (completion time is the moment when the execution of a task is completed).

A real-time schedulingmodel with fuzzy parameters was proposed. The model helps to bettercapture the design requirements and at the same time it provides the designer with a solution even in the case of over-constrained models. In the proposed models, tasks are periodic and have execution times and deadlines described by fuzzy numbers. To solve the models, we /rst de/ned a cost function called satisfaction. This function captures the worst case requirement of the real-time system. Algorithms for /ndingthe best assignment of priorities were then proposed. An extension of rate monotonic schedulingtheory has been presented as a case study. We discussed the main achievements of this theory and extended it such that it admits fuzzy parameters. We focused on demonstratingthe use of the theory in the design and analysis of practical real-time systems.