A Survey of Fuzzy Scheduling Algorithms

Robert T. Casey

EEL 270-RTOS

Spring 2007

A Survey of Fuzzy Scheduling Algorithms

Scheduling algorithms may be considered one of the key components of a real-time system, specifically in an RTOS, which can either enable the system to thrive or bring it to its knees. Considerthe simple priority inversion blunder of the Mars Rover in 1997 which crippled a significant portion of that mission [1]. This example clearly demonstrates the careful consideration which must be given to every aspect in the design of a real-time embedded system. Strict timing requirements must often be met within highly dynamic environments which do not lend themselves well to static scheduling algorithms. The level of uncertainty in dynamic, real-time environments is such as to require significant flexibility and adaptivity from an embedded system. Fuzzy systems fit this requirement, falling under the umbrella of the nascent field of soft computing, which seeks to merge the efforts of neural networks, evolutionary computing, probabilistic techniques, and chaos theory. A fuzzy scheduling algorithm builds into the real-time system flexibility and adaptation to the uncertainty inherent in real-time environments and offers a means to improve several important characteristics of real-time systems. This paper offers a brief, but informative, survey of a few reasonably successful attempts to extend popular scheduling algorithms to a fuzzy model. As a point of clarification, this paper will focus on short-term scheduling - that scheduling which executes most frequently and makes the fine-grained decision of which process to execute first [2].

The first paper reviewed, Real-Time Scheduling using Fuzzy Techniques, was not associated with a particular conference or journal, but was referenced in CiteSeer.IST [3]. Pettersson presents a limited survey of real-time scheduling algorithms using fuzzy techniques and serves as an adequate introduction to some of the key concepts behind fuzzy scheduling algorithms.

The author begins with a general overview of fuzzy set theory, membership functions, and linguistic variables. This material is important to those with limited exposure to fuzzy set theory. The first example presented covers the set of real numbers close to 7. Classical set theory would provide a membership function akin to a step function whose value is 0 for x < 6 and x > 8, and with value 1 for 6 <= x < = 8. By contrast, the fuzzy membership function (MF) is a continuous function possessing fractional degrees of membership. In this example, the graph of this function represents a triangle whose left edge is a line of increasing slope, beginning at x = 5.5 and y = 0. At x = 7, the vertex of the triangle, the triangle's right edge appears as a decreasing linear function until it reaches the next vertex, at x = 8.5 and y = 0. The fuzzy model of a MF does not feature hard boundaries between membership and non-membership. Instead, it more closely models the uncertainty inherent in language constructs by approximating membership through reasonably determined domains, such as 5.5 <= x <= 8.5 in this example.

Next the author covers linguistic variables and how fuzzy sets can be used to model such descriptions as “very young, young, old, and very old.” This introductory material is fairly sparse, but may help those with no previous exposure to fuzzy sets grasp the techniques used in the scheduling algorithms later presented.

The author mentions the real-time scheduling characteristics most nearly concerned with uncertainty: the execution time of tasks and the umbrella category of ”real-time constraints,” under which deadline, ready time, task period fall. The “most obvious place” to introduce fuzzy concepts for modeling uncertainty in scheduling algorithms is with a task's execution time. Typical scheduling algorithms assume this information to be a priori; this may or may not be reliable. Upon consideration of such a static specification, one questions the flexibility of such an approach, for example, if the environment quickly changes state. By modeling the execution time of a task with a fuzzy number, a system designer can build flexibility into the scheduling algorithm and adapt to such changes more adeptly. The previous points highlight one of the paper's strengths.

The first paper reviewed by Pettersson, A Fuzzy Rule-Based Approach to Real-time Scheduling, will be reviewed in depth at later by the author [4]. Pettersson's examination presents a brief overview of some of the high points of Lee's work and provides a much-appreciated service by reprinting legible copies of figures from Lee's paper which were mostly indecipherable in the online reference document. These figures covered the membership functions for laxity as well as criticality; laxity included the fuzzy sets of “early,” “medium,” and “late,” while criticality (task importance) included the fuzzy sets of “important,” “average,” and “unimportant.” As a side note, it would be curious to see what tasks were deemed as unimportant! After all, if a task is unimportant, then why create it? Perhaps more descriptive labels for the fuzzy sets in question might be “high priority,” “medium priority,” and “low priority.” But this is critiquing Lee's work, rather than Pettersson's, a discussion to be had later.

Pettersson mentions Lee's two goals: 1) maximize the number of tasks being scheduled, and 2) minimize the number of important tasks lost upon system overload; however, he misses the notion that these goals may conflict. Also, goal (1) comes across as vague; is a task which is “scheduled” actually completed? If this was the author's intent, then he describes Lee's work in a manner which agrees with what this author has surmised regarding Lee's work. If, however, the statement of goal (1) means simply that the task is piped into the ready queue or some other state of affairs, then he misses the mark, in this author's opinion. Lastly, the author mentions that Lee's algorithm is used for dynamic real-time scheduling and assumes a nonpreemptive scheduling architecture. However, the author fails to mention to the reader what dynamic scheduling entails other than that the Minimum Laxity First (MLF) algorithm is an example of such; simply mentioning that dynamic scheduling involves run-time priority calculations would have been sufficient and helpful.

A fairly significant omission in Pettersson's coverage of Lee's work is that Lee incorporated two versions of the MLF algorithm when generating comparisons against the fuzzy scheduling algorithm. Lee observed that the MLF algorithm does not take into account the task's priority (criticality), thus the initial comparison of an unmodified MLF against the fuzzy scheduler might unfairly place favor with the fuzzy algorithm, since it takes into account a factor which the MLF does not. To be more nearly fair, the authors of A Fuzzy Rule-based Approach to Real-time Scheduling extended the MLF in two ways: a weighted version and an averaged one. According to Lee, these extensions improved the performance of the core MLF algorithm, however, the fuzzy scheduler still performed better, which lends even greater credibility to the fuzzy approach.

The next paper mentioned in Pettersson's survey, Fuzzy Concepts Applied to Preemptive Real-time Tasks Scheduling by Mendoca, et al, features a deadline constraint rule which has been fuzzified. In this author's (RTC) limited knowledge, to “fuzzify” a number or a rule means to map a classical mathematical relation or number to one expressed with a fuzzy set or relation, either by MF generation or using a tool such as the extension principle [5]. Pettersson mentions a function called the “satisfaction index” which seems to correspond to a hypothetical fuzzy set labeled “possible finishing time for the task,” related to a scheduling criterion in Mendonca's work.

The author glosses over any results presented in the paper reviewed: “Mendonca et al (1996) claims that the schedule obtained by this algorithm takes advantage on the good properties of existing algorithms and automatically chooses the algorithm providing the best schedule.” The previous sentence raises more questions than it answers. First, which properties are optimized or utilized for advantage? The deadline scheduling criteria? Also, it is doubtful (though not impossible) that Mendonca would have stated something to the effect of “this schedule automatically chooses the algorithm providing the best schedule,” unless a proof was provided or the tasks of interest were of trivial running time, limited priority range, and short execution time. Otherwise, a “best schedule” is more of a goal than an absolutely realizable state, just as the “fastest computer” is more of an abstraction than a concrete entity.

Lastly, Pettersson mentions the work of Ishibuchi, et al, entitled Formulation of Fuzzy Flowshop Scheduling Problems with Fuzzy Processing Time. A flowshop perhaps deals with the problem of scheduling n jobs on m machines, thus introducing multiprocessor scheduling. The author describes very briefly how Ishibuchi's work includes a multi-objective genetic algorithm to find an optimum scheduling algorithm, using such properties as maximum delay and total delay.

In summary, Pettersson provided an adequate overview of a few fuzzy scheduling techniques which have been developed recently. The shortcomings previously mentioned lie in the fact that the paper is, itself, just an overview or survey of a few techniques and was not intended to provide an in-depth discussion of a broad range of fuzzy scheduling techniques.

Given Pettersson's introduction, let us now turn our attention to a more in-depth discussion of Lee, Tiao, and Yen's IEEE paper, A Fuzzy Rule-based Approach to Real-time Scheduling [4]. Conventional real-time scheduling algorithms suffer from one common problem: all constraints, such as computation times and deadlines, need to be known exactly before the algorithm can schedule the tasks. Thus the system suffers from a sort of “crystal ball” syndrome: the system itself should have the capability of predicting the computation times and deadlines before the tasks are really executed or it should be able to use with a high-degree of confidence the statically-provided estimate provided by the user or task creator. This approach relies on assumptions which may not necessarily hold water in all possible cases, especially in dynamic real-time environments. Even statistical estimation methods such as exponential averaging, though potentially accurate, are always “playing catch-up” rather than simply embracing the uncertainty which exists regarding these variables; also, these techniques may not be suitable in many practical situations. The inflexibility of constraints could be alleviated by using soft constraints in the scheduling algorithms. The authors admit that although such a dynamic scheduling system as the one they propose does have higher run-time costs than a similar static system, their system is more flexible and can easily adapt to the changes in the environment, thus illustrating robustness as a real-time system. The authors seem quite adept in the realm of soft computing, which is detailed eloquently by the founder of fuzzy set theory, Lotfi A. Zadeh:

The essence of soft computing is that unlike the traditional, hard computing, soft computing is aimed at an accommodation with the pervasive imprecision of the real world. Thus, the guiding principle of soft computing is to exploit the tolerance for imprecision, uncertainty, and partial truth to achieve tractability, robustness, low solution cost, and better rapport with reality [6].

Specifically, the authors' approach involves a non-preemptive, uniprocessor solution which utilizes a set of fuzzy rules to derive a feasible schedule. A “feasible schedule” is defined as one which contains all tasks and in which all tasks meet their deadlines; thus a feasible schedule is an ideal schedule. In addition to the goal of a feasible schedule, the authors seek a graceful degradation of system performance upon overload, thus enhancing its robustness. Ideally, a system will allow higher priority tasks to run upon overload and not drop an unacceptably high number of important tasks.

In the vein of many good research papers, the authors preface their work with a review of similar work in the field of real-time scheduling. They give credit to the significant work by Liu and Layland on the rate monotonic scheduler (RMS) as well as the minimum laxity first (MLF) algorithm [7].

The challenge addressed by Lee, et al concerns the “difficulty of developing a feasible and reliable scheduling algorithm.” Their setup involves a system handling a set of aperiodic tasks with more or less random arrival times. Periodic tasks are also handled, but each as an instance of an aperiodic task; this clever twist presumably simplifies a few implementation details.

At this point the authors delve into the meat and math of their approach. Decision alternatives are mentioned, which are basically an execution sequence of various tasks. For example, the notation T1 > T2 > T3 means that T1 runs first, then T2, followed by T3. To appreciate the enormity of the decision tree faced by scheduling algorithm designers, consider that for ntasks, there exist n! decision alternatives. Also, the authors briefly discuss an idea called “aggregation of judgments,” which is a process of obtaining the overall decision or conclusion from the individual contributing rules.

The authors treat the real-time scheduling problem as a multi-criteria optimization problem. The task constraints which are chosen to represent linguistic fuzzy variables are laxity and criticality (priority). The corresponding MFs for these variables were discussed previously in the above section on Pettersson's paper. The laxity of a task represents the maximum time that a task can wait before being executed ( deadline –computation time - arrival time). Laxity can be seen to be a measure of flexibility, or perhaps “clever laziness.” Again, the goals of the fuzzy scheduler are as follows:

1. Maximize the number of tasks being executed, and
2. Minimize the number of important tasks being lost if the system is overloaded.

Note that goal 1 and 2 may conflict with one another. According to a source in Lee's paper, there are two stages to multi-criteria optimization:

1.The aggregation of the judgments with respect to all goals and per decision alternative, and

2.the rank ordering of the decision alternatives according to the aggregated judgments.

At this point, the authors essentially use advanced fuzzy logic inference rules as well as combinational techniques to select the task to execute first.

Now let us discuss the authors' tested results using a simulation model and performance metrics to demonstrate the effectiveness of their solution. First, it should be noted that the tasks in the test cases were assumed to be aperiodic and to follow what is called a Poisson distribution in regards to their arrival rate. The Poisson distribution is a discrete probability distribution which expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate, and are independent of the time since the last event [8]. The performance metrics used included task loss ratio ( number of lost tasks / number of tasks arrived ) and average weight loss (total weight of lost tasks / number of lost tasks ), where a task's weight is its priority. The team then compared its fuzzy scheduler with a standard MLF algorithm. For “uniform” tasks (uniform with respect to which property?), the task loss ratio of the fuzzy algorithm approximated the optimal MLF. For the average weight loss metric, the fuzzy algorithm performed significantly better. For nonuniform tasks, the fuzzy algorithm performed better across the board. As mentioned previously, the “traditional” MLF algorithm does not take into account the task's priority (criticality), so the authors extended it to include this factor. The fuzzy scheduler showed improvements over even this enhanced version.

Overall, I was impressed with the authors' work. It was apparent that the team was highly confident in its approach; the fact that they essentially “bulked up” the competition through their MLF extension and then showed that their fuzzy scheduler outperformed even that was a convincing demonstration of the power of their approach. Additionally, their explanation was concise. One of the few limitations of the paper concerns the poor print quality of the figures and graphs. This was most likely a result of the archiving process and not directly related to the authors' efforts. It did, however, make gathering any information from these graphs next to impossible; in the end I was forced to more or less trust the authors' verbal description of their results.

In the next paper reviewed, entitled Scheduling Non-Preemptive Periodic Tasks in Soft Real-Time Systems Using Fuzzy Inference, the authors introduce a novel scheduling algorithm: highest fuzzy priority first, whose performance is matched with a nonpreemptive version of the Earliest Deadline First (EDF) algorithm [9]. Sabeghi, et al begin with a general introduction to the differences between an RTOS and a GPOS, hard vs. soft real-time systems, periodic vs. aperiodic tasks, the basic ideas behind scheduling, as well as preemption vs. non-preemption.

The authors chose to implement a non-preemptive solution to real-time scheduling for the following reasons: