Study on Scheduling for Real-time Task by Hybrid Multiobjective Genetic Algorithm

Study on Scheduling for Real-time Task by Hybrid Multiobjective Genetic Algorithm

多目的ハイブリッド型遺伝的アルゴリズムによる リアルタイム・タスクのためのスケジューリングに関する研究

2006 年 2 月

兪 明 連

Study on Scheduling for Real-time Task by Hybrid Multiobjective Genetic Algorithm

多目的ハイブリッド型遺伝的アルゴリズムによる リアルタイム・タスクのためのスケジューリングに関する研究

2006 年 2 月

早稲田大学大学院情報生産システム研究科 情報生産システム工学専攻

ソフトコンピューテイング研究

兪 明 連

CONTENTS

1. Introduction

1

1.1 Backgrounds and Objective of the Study ………..……… 1

1.2 Organization of the Dissertation………...……… 2

2. Real-time Task Scheduling Problem 4

2.1 Hard Real-time Task Scheduling……… 4

2.1.1 Rate Monotonic (RM) Scheduling Algorithm..……… 4

2.1.2 Earliest Deadline First (EDF) Scheduling Algorithm.……… 6

2.1.3 Analysis for Scheduling Algorithms Derived from RM and EDF……… 7

2.2 Soft Real-time Task Scheduling…….……… 7

2.2.1 Rate Regulating Proportional Share (rrPS) Scheduling Algorithm ……… 7

2.2.2 Modified Proportional Share (mPS) Scheduling Algorithm ……… 10

3. Hybrid Multiobjective Genetic Algorithm 13

3.1 Basic of Genetic Algorithm ……… 13

3.2 Implementation of Genetic Algorithm……...……… 15

3.2.1 Genetic Representation……… 15

3.2.2 Fitness Evaluation……… 16

3.2.3 Genetic Operators……… 16

3.2.4 Major Advantages of Genetic Algorithm.……… 18

3.3 Multiobjective Optimization Problems...…………....……...………..…19

3.3.1 The Concept of Pareto Solution……… 19

3.3.2 Adaptive Weight Approach……….……… 21

3.4 Hybrid Multiobjective Genetic Algorithm...………....……...……….. 23

4. Continuous Task Scheduling 25

4.1 Continuous Task Scheduling on Uniprocessor System………...……....…25

4.1.1 Continuous Task Scheduling Problem……… 25

4.1.2 Mathematical Model……….………...…… 27

4.1.3 Substantial Components of GA……….……… 30

4.1.4 Numerical Results………..……….……… 33

4.1.5 Summary……….……….……… 35

4.2 Continuous Task Scheduling on Multiprocessor System……….……...……....…35

4.2.1 Continuous Task Scheduling Problem……… 36

4.2.2 Mathematical Model……….………...…… 37

4.2.3 GA Approach for Continuous Task……….……… 38

4.2.4 Numerical Results………..……….……… 42

4.2.5 Summary……….……….……… 49

5. Real-time Task Scheduling in Homogeneous Multiprocessor System 50

5.1 Soft Real-time Task Scheduling Problem without Communication Time…...……....…51

5.1.1 Soft Real-time Task Scheduling Problem (sr-TSP)……… 51

5.1.2 Mathematical Model……….………...…… 52

5.1.3 GA Approach……….……….……… 54

5.1.4 Validation………..……….……… 61

5.1.5 Summary……….……….……… 70

5.2 Soft Real-time Task Scheduling Problem with Communication Time………....…70

5.2.1 Soft Real-time Task Scheduling Problem (sr-TSP) and Mathematical Model…… 71

5.2.2 GA Approach combined with SA……….……… 73

5.2.3 Validation………..……….……… 81

5.2.4 Summary……….……….……… 89

6. Real-time Task Scheduling in Heterogeneous Multiprocessor System 90

6.1 Soft Real-time Task Scheduling Problem with Single Objective…...…..……..……....…90

6.1.1 Soft Real-time Task Scheduling Problem (sr-TSP) and Mathematical Model…… 90

6.1.2 GA Approach combined with SA……….……… 92

6.1.3 Validation………..……….……… 98

6.1.4 Summary……….……….……… 106

6.2 Soft Real-time Task Scheduling Problem with Multiobjective………….…...……....…107

6.2.1 Soft Real-time Task Scheduling Problem (sr-TSP) and Mathematical Model… 107 6.2.2 GA Approach combined with SA……….……… 109

6.2.3 Validation………..……….……… 115

6.2.4 Summary……….……….……… 121

7. Conclusions 122

Bibliography 124

Publication List 127

Chapter 1 Introduction

1.1 Backgrounds and Objective of the Study

Real-time tasks can be classified to many kinds. Some real-time tasks are invoked repetitively.

For example, one may wish to monitor the speed, altitude, and attitude of an aircraft every 100ms. This sensor information will be used by periodic tasks that control the control surfaces of the aircraft, in order to maintain stability and other desired characteristics. In contrast, there are many other tasks that are aperiodic, that occur only occasionally. Aperiodic tasks with a bounded interarrival time are called sporadic tasks. Real-time tasks can also be classified according to the consequences of their not being executed on time. Critical (or hard real-time) tasks are those whose timely execution is critical. If deadline are missed, catastrophes occur.

Noncritical (or soft real-time) tasks are, as name implies, not critical to the application (Krishna and Kang, 1997).

For task scheduling, the purpose of general task scheduling is fairness which means that the computer’s resources must be shared out equitably among users. However, the purpose of hard real-time task scheduling is to execute, by the appropriate deadlines, its critical control tasks and the objective of the scheduling soft real-time tasks is to minimize total tardiness (Yoo, Ahn, Lee and Kim, 2001).

There are some traditional scheduling algorithm for hard real-time tasks on uniprocessor, such as Rate Monotonic (RM) and Earliest Deadline First (EDF) (Liu and Layland, 1973) scheduling algorithm. They guarantee the optimality in somewhat restricted environments.

Several derived algorithm from RM, EDF is used for soft real-time tasks. However, these algorithms have some drawbacks in resource utilization and pattern of degradation under the overloaded situation. With the growth of soft real time applications, the necessity of scheduling algorithms for soft real-time tasks is on the increase. Rate Regulating Proportional Share (rrPS) (Kim, Lee and Lee, 1997) scheduling algorithm and Modified Proportional Share (mPS) (Yoo, 2002) scheduling algorithm are designed for soft real-time tasks. However, these algorithms also cannot show the graceful degradation of performance under an overloaded situation and are restricted in a uniprocessor system.

Furthermore, the scheduling on multiprocessor system is NP-hard problem. According to Yalaoui and Chu (2002), the problem of scheduling tasks on identical parallel processors to minimize the total tardiness is at least NP-hard problem since Du and Leung showed that the problem is NP-hard problem for a single processor case (Du and Leung, 1990). Lenstra et al.

also showed that the problem with two processors is NP-hard problem (Lenstra, Kan and Brucker, 1977). Nevertheless the exact complexity of this problem remains open for more than two processors. Consequently various modern heuristics based algorithms have been proposed for practical reason.

In this study, scheduling algorithms for soft real-time tasks using Genetic algorithm (GA) are proposed. GA has been known to offer significant advantages against conventional heuristics by using simultaneously several search principles and heuristics. GA has been used already for scheduling problem in manufacturing system such as job shop scheduling, flow shop scheduling and machine scheduling.

The objective of this study is to propose reasonable solutions for NP-hard scheduling problem which much less difficulties than those of traditional mathematical methods.

The main contents of this study are as follows:

1) The proposed algorithms are validated through various kinds of scheduling model such as uniprocessor or multiprocessor system, periodic or sporadic tasks, and homogeneous multiprocessor or heterogeneous multiprocessor system.

2) The scheduling algorithm by hybrid GA (hGA), which is combined with Simulated Annealing (SA), is proposed. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of the new trial solutions. This hybridization does not hurt own advantages of GA but finds more accurate solutions in later stage of searching process.

3) The multiobjective GA (moGA) for soft real-time tasks is proposed. Not only minimization the total tardiness but also minimization the total number of processor used and the makespan are taken into considerations. However, since these objectives are in conflicting (trade-offs) relations, the Pareto optimum concept is introduced to solution process.

1.2 Organization of the dissertation

This dissertation is organized as 7 chapters. Chapter 2 describes the real-time task scheduling.

The Rate Monotonic (RM) scheduling algorithm and the Earliest Deadline First (EDF) scheduling algorithm as well known scheduling algorithms for hard real-time tasks are introduced and the Rate Regulating Proportional Share (rrPS) scheduling algorithm and Modified Proportional Share (mPS) scheduling algorithm as the scheduling algorithm for soft real-time tasks are introduced.

Chapter 3 presents the basic definition and implementation procedure of Genetic Algorithm

(GA). The Pareto concept and Adaptive Weight Approach (AWA) (Gen and Cheng, 2000) for multiobjective problem are also mentioned in this chapter. GA is the basic method of in this study and AWA is also used in the proposed algorithms with multiobjective.

New scheduling algorithms for periodic task are proposed in chapter 4. Chapter 4 is composed of two parts. The system considered in the first part is uniprocessor system. The proposed algorithm is to determine execution sequence of tasks with the objective of minimizing the weighted sum of variance of tardiness and the total number of context switching among tasks. In this part, three evaluation methods are compared. In the second part, the scheduling algorithm on multiprocessor system is proposed. The proposed algorithm is to determine the execution sequence of tasks with the objective of minimizing the total tardiness.

Chapter 5 introduces new scheduling algorithms on homogeneous multiprocessor system.

Chapter 5 is composed two parts. The multiprocessor system without communication time is considered in the first part. The objective of proposed scheduling algorithm is to minimize the total tardiness and total number of processors used. The AWA is used for these multiobjectives.

The multiprocessor system with communication time between processors is considered in the second part. In solution algorithms, the hybrid GA (hGA), which combines the multiobjective Genetic Algorithm (moGA) and the Simulated Annealing (SA), is proposed. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of new trial solution. The objective of proposed scheduling algorithm is to minimize the total tardiness and total number of processors used simultaneously. The AWA that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point, is combined for these conflicting objectives.

Chapter 6 proposes new scheduling algorithms on heterogeneous multiprocessor system.

Chapter 6 is also composed two parts. The scheduling algorithm with single objective, to minimize the total tardiness, is proposed in the first part. In solution algorithms, the hGA, which combines the moGA and the SA, is proposed.

In the second part, the scheduling algorithm with multiobjective is proposed. A new task scheduling algorithm is proposed. The objective of the proposed scheduling algorithm is to minimize the total tardiness and completion time simultaneously. The hGA combined with SA and AWA are used for this problem.

Finally, chapter 7 provides a conclusion of this study and rooms for discussions for future research.

Chapter 2 Real-time Task Scheduling Problem

Real-time tasks are characterized by computational activities with timing constraints and classified into two categories: Hard real-time task and Soft real-time task. In this chapter, the scheduling problem for real-time tasks is explained.

2.1 Hard Real-time Task Scheduling

In hard real-time task, the violation of timing constraints of certain task should not be acceptable (Zhu, Zhuang and Viniotis, 2001; Budin, Domagoj and Marin, 1999).The consequences of not executing a task before its deadline may lead to catastrophic consequences in certain environments i.e., in patient monitoring system, nuclear plant control, etc.

In hard real-time task, the performance of scheduling algorithm is measured by its ability to generate a feasible schedule for a set of real-time tasks. If all the tasks start after their release time and complete before their deadlines, the scheduling algorithm is feasible. Typically, there is Rate Monotonic (RM) and Earliest Deadline First (EDF) derived scheduling algorithms for hard real-time tasks (Diaz, Garcia and Lopez, 2004; Bernat, Burns and Liamosi, 2001). They guarantee the optimality in somewhat restricted environments.

2.1.1 Rate Monotonic (RM) Scheduling Algorithm

RM Scheduling is proposed by Liu and Layland (Liu and Layland, 1973). This Scheduling Algorithm is based on uniprocessor static-priority preemptive scheme and optimal among all fixed priority scheduling algorithm. This Algorithm assigns static priority to the tasks such that tasks with shorter period get higher priorities.

This Algorithm assumes followings;

1) No task has any nonpreemptable section and the cost of preemption is negligible.

2) Only processing requirements are significant; memory, I/O, and other resource requirements are negligible.

3) All tasks are independent; there are no precedence constraints.

4) All tasks in the tasks set are periodic.

5) The relative deadline of a task is equal to its period.

The algorithm of RM scheduling is following as;

algorithm 2.1: RM Scheduling Algorithm

step 1: Set up all tasks’ priority inversely to their period.

Set up all tasks’ start time, end time, remaining time and deadline.

step 2: If system is idle, then add task to schedule and go to step 4. Otherwise go to step 3.

step 3: If new task’s priority is higher then processing task’s priority, then update processing task’s remaining time and exchange tasks. Otherwise update new task’s start time.

step 4: If all the tasks have not been scheduled, then go to step 2. Otherwise stop.

Figure 2.1 represents the example of RM scheduling. Where τ_i is ith task, i is the number of task, ci is the computation time of task i, ri is the release time of task i and pi is the period of task i. In this figure, τ3’s period is longer then τ2’s period. So, τ3 can not preempt τ2 at time 3. The other hand, τ₁ preempts τ₃ at time 4.5.

i computation time ci release time ri deadline pi

1 0.50 0 2

2 2.00 1 6

3 1.75 3 10

τ₁ τ₂ τ₁ τ₂ τ₃ τ₁ τ₃ τ₁

0 1 2 3 4 5 6 7 τ₁

(0.5)

τ₁ (0.5

τ₁ (0.5)

τ₁ (0.5) τ₂

(1.0)

τ₂ (1.0)

τ₃ (0.5)

τ₃ (1.25)

τ₁ τ₂ τ₃

p₁ p₁

p₂

p₃

5.75

Processor

p₁

τ₁ τ₂ τ₁ τ₂ τ₃ τ₁ τ₃ τ₁

0 1 2 3 4 5 6 7 τ₁

(0.5)

τ₁ (0.5

τ₁ (0.5)

τ₁ (0.5) τ₂

(1.0)

τ₂ (1.0)

τ₃ (0.5)

τ₃ (1.25)

τ₁ τ₂ τ₃

p₁ p₁

p₂

p₃

5.75

Processor

p₁

Figure 2.1 RM scheduling

If the total utilization of the tasks is no greater than n(2^1/n-1), where n is the number of tasks to be scheduled, then RM scheduling algorithm will schedule all the tasks to meet their respective deadlines. The goal of RM scheduling algorithm is to meet all task deadlines and to keep the feasibility of scheduling through admission control n(2^1/n-1). Strict admission control prevents unpredictable behaviors when the overloaded condition occurs. But it may cause low

utilization of resources.

2.1.2 Earliest Deadline First (EDF) Scheduling Algorithm

EDF Scheduling is proposed by Liu and Layland (Liu and Layland, 1973). This Scheduling Algorithm is based on uniprocessor dynamic-priority preemptive scheme and optimal among all dynamic priority scheduling algorithm. This Algorithm schedules the task with the earliest deadline first.

This Algorithm assumes followings;

1) No task has any nonpreemptable section and the cost of preemption is negligible.

2) Only processing requirements are significant; memory, I/O, and other resource requirements are negligible.

3) All tasks are independent; there are no precedence constraints.

4) All tasks in the tasks set are periodic.

5) The relative deadline of a task is equal to its period.

The algorithm of EDF scheduling is following as;

algorithm 2.2: EDF Scheduling Algorithm

step 1: Set up all tasks’ start time, end time, remaining time and deadline.

step 2: If system is idle, then add task to schedule and go to step 4. Otherwise go to step 3.

step 3: If new task’s deadline is earlier than processing task’s deadline, then update processing task’s remaining time and exchange tasks. Otherwise update new task’s start time.

step 4: If all the tasks have not been scheduled, then go to step 2. Otherwise stop.

Figure 2.2 represents the example of EDF scheduling. Where τi is ith task, i is the number of task, c_i is the computation time of task i and p_i is the period of task i.

i Computation time ci period pi

1 1.0 3

2 0.5 2

3 2.0 5

0 1 2 3 4 5 6

τ_２ τ₁ τ_３ τ₂ τ_３ τ_１ τ_２ τ_３

τ₂ (0.5)

τ₁ (1.0)

τ_３ (0.5)

τ₂ (0.5)

τ_３ (1.5)

τ₁ (1.0)

τ_２ (0.5)

τ_３ (0.5)

τ₁ τ₂ τ₃

p₁

p₂

p₃ Processor

p₁

p₂ p₂

0 1 2 3 4 5 6

τ_２ τ₁ τ_３ τ₂ τ_３ τ_１ τ_２ τ_３

τ₂ (0.5)

τ₁ (1.0)

τ_３ (0.5)

τ₂ (0.5)

τ_３ (1.5)

τ₁ (1.0)

τ_２ (0.5)

τ_３ (0.5)

τ₁ τ₂ τ₃

p₁

p₂

p₃ Processor

p₁

p₂ p₂

Figure 2.2 EDF scheduling

If the total utilization of the task set is no greater than 1, the task set can be feasibly scheduled on a single processor by the EDF scheduling algorithm. The goal of EDF scheduling algorithm is to meet all task deadlines and to keep the feasibility of scheduling through admission control 1. Strict admission control prevents unpredictable behaviors when the overloaded condition occurs. But it may cause low utilization of resources.

2.1.3 Analysis for Scheduling Algorithms Derived from RM and EDF

There are several RM and EDF derived algorithms for soft real-time task. But, these algorithms have some drawbacks to cope with continuous tasks in soft real-time tasks related resource utilization and pattern of degradation under the overloaded situation. Firstly, in continuous tasks, it is not necessary for every instance of a repetitive task to meet its deadline. For soft real-time tasks, slight violence of time limits is not so critical. Secondly, RM and EDF scheduling algorithms are required the strict admission control to prevent unpredictable behaviors when the overloaded situation occurs. The strict admission control may cause low utilization of resources (Kim, Lee and Lee, 1997).

2.2 Soft Real-time Task Scheduling

The usefulness of results produced by a task decreases over time after the deadline expires without causing any damage to the controlled environment (Krishna and Kang, 1997).

Recently, Rate Regulating Proportional Share (rrPS) and Modified Proportional Share (mPS) Scheduling algorithm is designed for continuous task in soft real-time tasks.

2.2.1 Rate Regulating Proportional Share (rrPS) Scheduling Algorithm

rrPS scheduling algorithm is proposed by Kim and Lee (Kim, Lee and Lee, 1997). rrPS scheduling algorithm is based on the stride scheduler and is proposed to schedule continuous

tasks. To specify timing requirements of continuous media, a pair of parameters (pi, ci) is introduced, where pi means the period of a task i and ci means the computation time of task i needed over each period.

Three parameters, which are tci, sdi and psi, are used in this scheduling algorithm. The tci is the period of a task and the computation time during the period. It represents the relative amount of resources that should receive. The sdi is inversely proportional to the ticket and represents the interval between selections. The psi represents the virtual time index for next selection and has the same value as the stride at the first stage. The task with the minimum pass is selected, and its pass is advanced by its stride.

The rate regulator, the key concept of the scheduling algorithm, prevents certain tasks from taking more resources than its share for a given period. It can be represented as Equation (2.1).

i t i

s j

i p

j c t

∑

_ia ≤

=

)

1 ( (2.1)

where

t : time index i : task index

si : the start time of task i

∑ai : total number of allocations that task i has received from start to current time ci : the computation time of task i

pi : the period of task i

The algorithm of rrPS scheduling is following as;

algorithm 2.3: rrPS Scheduling Algorithm step 1: Set up all tasks’ tci, sdi and psi. step 2: Select task with minimum psi.

step 3: If task satisfies rate regulator, then update psi and go to step 5. Otherwise go to step 4.

step 4: Select a task with the minimum psi in remains and go to step 3.

step 5: if all the tasks have not been scheduled, then go to step 2. Otherwise stop.

Figure 2.3 represents the example of rrPS scheduling. Where τ_i is ith task, i is the number of task, ci is the computation time of task i and pi is the period of task i. rrPS scheduling algorithm contributes to process the scheduling of continuous media.

i computation time ci period pi tci sdi

1 1 5 0.20 5 2 2 4 0.50 2 3 3 6 0.33 3

0 1 2 3 4 5 6 τ₂

τ₁

τ_２

τ₃

τ₂

p₁

p₂

p₃ Processor

τ₃ τ₃

τ₂

τ₂

τ₁

τ₁

τ₂

τ₂

0 1 2 3 4 5 6 τ₂

τ₁

τ_２

τ₃

τ₂

p₁

p₂

p₃ Processor

τ₃ τ₃

τ₂

τ₂

τ₁

τ₁

τ₂

τ₂

Figure 2.3 rrPS scheduling

This algorithm considers time dependency of continuous media and it keeps fairness of resource allocation under normal scheduling condition. Even though rrPS scheduling algorithm has several the advantages, it has some difficulties to adapt continuous media as follows.

First, this algorithm does not show graceful degradation of performance under the overloaded condition. It works as if it kept fairness for the number of time quantum that was not served from the scheduler. However it loses fairness for the ratio of computation time that is not served from the scheduler. In other words, weights which are not served a given time quantum are different in the length of the computation time of tasks

Second, this algorithm also has the possibility of avoidable context switching overhead. It means that the rate regulator can cause unnecessary context switching in task scheduling.

Since overheads of the context switching are machine dependent factors, which are page size, memory cycle time, number of registers, types of instruction format, and etc. Since the portion of context switching overhead can be relatively small, it is seldom considered in many scheduling algorithm designs. When systems schedule many number of tasks, excessive context switching induces the trashing due to hot conflicts for systems and resources among tasks can cause serious degradation of system performance.

To avoid the above two drawbacks, the following points are considered (Yoo, 2002).

1) Graceful degradation of performance under the overloaded condition.

2) Elimination of unnecessary context switching overhead.

3) Protection of the admission control policy that may cause deteriorating resources.

2.2.2 Modified Proportional Share (mPS) Scheduling Algorithm

mPS scheduling algorithm is proposed by author (Yoo, Ahn, Lee and Kim, 2001). In this scheduling algorithm, tc’i of mPS scheduling algorithm represents the relative amount of resources that should receive. It can be defined as Equation (2.2). It considers the ratio of resource allocation in both normal condition and overloaded condition.

⎪⎪

⎪

⎩

⎪⎪

⎪

⎨

⎧

∀

≤

∀

>

′ =

∑

∑ ∑

=

= =

i tc

if tc

i tc

tc if tc c

t

n

j j i

n

j n j

j j i

i

, 1

, 1

1 1

1 (2.2)

p i tc c

i i

i = , ∀ (2.3)

where

i : task index

n : the total number of tasks ci : the computation time of task i p_i : the period of task i

The psi represents the virtual time index for next selection. It is 0 at the first stage and is updated as Equation (2.4) in every time quantum.

t i j

i a c t t

ps

ⁱ

s

j i

i i

i

, , ) 1 (

)

( = ′ − ∑ ∀

=

(2.4)

where

t : time index i : task index

si : the start time of task i

∑ai : total number of allocations that task i has received from start to current time ci : the computation time of task i

pi : the period of task i

In the previous time quantum, the selected task has preferential right to schedule and if it did

not violate the upper bound of rate regulator, it is selected again. If not, other task with the maximum pass will be selected.

By Equations (2.2) and (2.4), the rate regulator of mPS scheduling algorithm can be defined as Equation (2.5).

t i t

ps

_i

( ) > 0 , ∀ ,

(2.5)

The number of context switching using this policy of preferential right is decreased.

The tc’i and psi of a task are determined by its period and computation time. And mPS scheduling algorithm selects a task by comparing the tc’i and psi of the task. During scheduling, the number of context switching is decreased. The mPS scheduling algorithm shows graceful degradation of performance using tc’i, which is considered the rate regulating overloaded condition as shown Equation (2.5).

The algorithm of mPS scheduling is following as;

algorithm 2.4: mPS Scheduling Algorithm step 1: Set up all tasks’ tc’i and psi.

step 2: Select task with maximum tc’i. step 3: Update all tasks’ psi.

step 4: If task satisfies rate regulator, then go to step 5. Otherwise go to step 6.

step 5: Select a task with the maximum psi in remains and go to step 4.

step 5: if all the tasks have not been scheduled, then go to step 3. Otherwise stop.

Figure 2.4 represents the example of mPS scheduling. Where τi is ith task, i is the number of task, ci is the computation time of task i and pi is the period of task i.

The mPS scheduling algorithm shows better performance than rrPS scheduling algorithm for graceful degradation of performance under the overloaded condition and fewer context switching. However, computational burden and solution accuracy of mPS could be improved by new algorithm based on Genetic Algorithm (GA).

i computation time ci period pi tci

1 1 5 0.19

2 2 4 0.48

3 3 6 0.32

0 1 2 3 4 5 6 τ₂

τ₁

τ₂

τ₃

τ₂

p₁

p₂

p₃ τ₃

τ₃

τ₁

τ₁

τ₂

τ₂

τ₃ τ₃

τ₂

τ₂ Processor

0 1 2 3 4 5 6 τ₂

τ₁

τ₂

τ₃

τ₂

p₁

p₂

p₃ τ₃

τ₃

τ₁

τ₁

τ₂

τ₂

τ₃ τ₃

τ₂

τ₂ Processor

Figure 2.4 mPS scheduling

Chapter 3 Hybrid Multiobjective Genetic Algorithm

Genetic Algorithm (GA) has been theoretically and empirically proved to provide a robust search in complex search spaces. Having been established as a valid approach to the complex problems requiring effective search, GA is now finding more widespread application in business, scientific, and engineering circles. The reasons behind the growing numbers of applications are clear. This algorithm is computationally simple and also powerful in its search for the improvement of the solution. In this chapter, the basic concept of GA and the expanded multiobjective optimization problem is explained.

3.1 Basic of Genetic Algorithm

The general form of GA was described by Goldberg (1989). GAs are stochastic search algorithms based on the mechanism of natural selection and natural genetics. GAs, differing from conventional search techniques, start with an initial set of random solutions called population. Each individual in the population is called a chromosome, encoding a solution to the problem at hand. The chromosomes evolve through successive iterations, called generations.

During each generation, the chromosomes are evaluated, using some measures of fitness (Fogel and Ghozeil, 1996). To create the next generation, new chromosomes, called offspring, are formed by either merging two chromosomes from current generation using a crossover operator or modifying a chromosome using a mutation operator. A new generation is formed by the selection of good individuals according to their fitness values. After several generations, the algorithm converges to the best individual, which hopefully represents the optimal solution or near-optimal solution for the problem. Figure 3.1 shows a general structure of GA, (Gen and Cheng, 1997).

Initial solutions

start ^1100110001

0011011001 1011101110 1100101010

1100110001 0011011001 1011101110 1100101010 encoding

chromosome

1011101110 1100101010 1011101110 1100101010

1011101010 1100101110 1011101010 1100101110

0011011001 0011011001 0011001001 0011001001 crossover

mutation

0011001001 1011101010 1100101110

0011001001 1011101010 1100101110

solutions candidates decoding

fitness computation evaluation roulette wheel

selection

termination condition?

Y N

best solution stop

new population

offspring

offspring

Figure 3.1: General structure of GA

The general implementation structure of GA is described as follows. In this procedure, P(t) and C(t) is parents and offspring in current generation t,

procedure 3.1: Genetic algorithm input: GA parameters

output: best solution begin

t ← 0;

initialize P(t) by encoding routine;

evaluate P(t) by decoding routine;

while (not termination condition) do begin

crossover P(t) to yield C(t);

mutation P(t) to yield C(t);

evaluate C(t) by decoding routine;

select P(t+1) from P(t) and C(t);

t ← t+1;

end

output best solution;

end

During iteration t, the GA maintains a population P(t) of solution. Each individual represents

solution to the problem at hand. Each solution is evaluated by computing a measure of fitness of the solution. Some individuals undergo stochastic transformations by means of genetic operators such as crossover and mutation operators in order to form new individuals, and new individuals called offspring C(t) are then evaluated. A new population is formed by selecting good individuals from the parent population and the offspring population.

3.2 Implementation of Genetic Algorithm

For implementing GA, several GA components should be considered. First, genetic representation method of solution is decided. Secondly, the fitness evaluation of the solution using the objective functions subjected to constraints is used. Lastly, genetic operators such as crossover operator, mutation operator and selection methods are applied to the population of GA. These implementation processes are repeated until the predefined generation number is satisfied or the optimal solution is located. The detailed implementation logics and procedures of GA are suggested in the following subsections.

3.2.1 Genetic Representation

In general, there are two types in representing design variables in GA. The first type is a bit string representation and the second type is real-number representation (Gen and Cheng, 1997).

Bit-string representation is the most common representation used by many GA researchers.

Coding the parameters in bit-string representation implies the design of encoder and decoder algorithms in order to ensure that the solution found by GA can be translated into a feasible solution of the original problem. In several cases, especially complex optimization problems, these design methods are not an easy task as described in (Michalewicz, 1994), and this representation method probably does not also employed in hybrid algorithms since most of conventional heuristics do not tend to use bit-string representation.

On the other hand, real-number representation generally offers the advantages being better adapted to numerical optimization for continuous variables problems, speeding up the search and making easier the development of approaches hybridized with other methods. During the past 20 years, various real-number representation methods have been developed for particular problems, e.g., real number encoding for constrained optimization problems and integer encoding (also called ordered permutation encoding) for combinatorial optimization problems.

Choosing an appropriate representation of candidate solutions to the problem at hand is the foundation for applying GAs to solve real world problems, which conditions all the subsequent steps of GAs. As yet, there has not been a general methodology in which any problems may be encoded by on strategy. Even two similar problems may require a completely different genetic representation.

3.2.2 Fitness Evaluation

Fitness evaluation is to check the solution value of the objective function subjected to constraints. In general, the objective function provides the mechanism evaluating each individual. However, its range of values varies from problem to problem. To maintain uniformity over various problem domains, the fitness function could be normalized to a range of 0 to 1. The normalized value of the objective function is the fitness of the individual, and the selection mechanism uses to evaluate the individuals of the population.

When the search of GA proceeds, the population undergoes evolution with fitness, and forming new population. At that time, in each generation, relatively good solutions are reproduced and relatively bad solutions are died in order that the offspring composed of the good solutions are reproduced. To distinguish between the solutions, an evaluation function (also called fitness function) plays an important role in the environment, and scaling mechanisms are also necessary to be applied in objective function for being fitness function.

3.2.3 Genetic Operators

When GA proceeds, both the search direction to optimal solution and the search speed should be considered as an important factor, in order to keep a balance between exploration and exploitation in search space. In general, the exploitation of the accumulated information resulting from GA search is done by the selection mechanism, while the exploration to new regions of the search space is accounted for by genetic operators.

The genetic operators mimic the process of heredity of genes to create new offspring at each generation. The operators are used to alter the genetic composition of individuals during representation. In essence, the operators perform a random search, and cannot guarantee to yield an improved offspring. There are three common genetic operators: crossover, mutation and selection.

1) Crossover

Crossover may be a main genetic operator. Crossover operator selects two chromosomes at a time and generates offspring by combining both individual’s features. A simple way to achieve crossover is to choose a random cut-point and generate the offspring by combining the segment of one parent to the left of the cut-point with the segment of the other parent to the right of the cut-point. Figure 3.2 shows an example of one-cut point crossover operation.

9 8

1 7

4 3

2

parent 1 2 3 4 7 1 8 9

parent 1

7 9

8 2

6 4

8

parent 2 8 4 6 2 8 9 7

parent 2

7 9

8 7

4 3

2

offspring 1 2 3 4 7 8 9 7

offspring 1

9 8

1 2

6 4

8

offspring 2 8 4 6 2 1 8 9

offspring 2

cut-point

Figure 3.2 Example of one-cut point crossover operation

In Figure 3.2, the right side genes of the selecting point in the two individuals, v₁ and v₂, are exchanged each other. After the crossover operation, the new individuals, v1’ and v2‘, are produced.

Up to now, various types of crossover operators have been developed, which can be roughly put into four classes: conventional, arithmetical, direction-based and stochastic. The conventional operators are made by extending the operators for binary representation into the real-coding case. The conventional crossover operators can be broadly divided by two kinds of crossover: simple crossover (one cut-point, two cut-point, multi cut-point or uniform), and random crossover (flat crossover, blend crossover). The arithmetical operators are constructed by borrowing the concept of linear combination of vectors from the area of convex set theory.

Operated on the floating point genetic representation, the arithmetical crossover operators, such as convex, affine, linear, average, intermediate, extended intermediate crossover, are usually adopted.

The direction-based operators are formed by introducing the approximate gradient (sub-gradient) direction into genetic operators. The direction-based crossover operator uses the value of objective function in determining the direction of genetic search. The stochastic operators give offspring by altering parents by random numbers with some distribution, typically a Gaussian distribution. Uni-model normal distribution crossover that can be classified as the stochastic crossover operator generates two children from a region of normal distribution defined by three parents.

2) Mutation

Mutation is usually used as a background operator, which produces spontaneous random changes in various individuals. A simple way to achieve mutation would be to alter one or more genes. Figure 3.3 shows an example of mutation operation.

9 2 3 8 7 2 6

parent 6 2 7 8 3 2 9

parent

9 2 3 8 7 2 6

offspring 6 2 7 8 3 2 9

offspring

select a position at random

replace with a digit at random

Figure 3.3 Example of mutation operation

In Figure 3.3, the value of the gene at the selection point is changed to 0. In general, mutation operator serves the crucial role of either replacing the genes lost from the population during the selection process so that they can be tried in a new context or providing the genes that were not present in the initial population. The mutation operator arbitrarily alters one or more components of a selected structure, and this increases the variability of the population.

3) Selection

New offspring for next generation of GA are formed by selection method according to their fitness values. The selection process is known as evolution operator, directing a GA search toward promising region in the search space. There have been presented various types of selection strategies such as elitist selection strategy, stochastic tournament selection strategy, and so on, in order to improve population to more evolved population (with better fitness).

These selection strategies provide the driving force in a GA and the selection pressure is critical in it. At one extreme, the search will terminate prematurely; while at the other extreme progress will be slower than necessary. It seems that there are two important issues in the evolution process of genetic search: population diversity and selective pressure. These factors are strongly related: an increase in the selective pressure decreases the diversity of the population, and vice versa. In other words, strong selective pressure supports the premature convergence of the GA search; a weak selective pressure is recommended at the end in order to exploit the most promising regions of the search space. Thus it is important to strike a balance between these two factors.

3.2.4 Major Advantages of Genetic Algorithm

GA has received considerable attention regarding their potential as a novel optimization technique (Yun, 2005). There are three major advantages when applying GA to optimization problems:

1) Adaptability

GA does not have much mathematical requirements about the optimization problems. Due

to the evolutionary nature, GA will search for solutions without regard to the specific inner workings of the problem. GA can handle any kind of objective functions and any kind of constraints, i.e., linear or nonlinear, defined on discrete, continuous or mixed search spaces.

2) Robustness

The use of evolution operators makes GA very effective in performing global search (in probability), while most of conventional heuristics usually perform local search. It has been proved by many studies that GA is more efficient and more robust in locating optimal solution and reducing computational effort than other conventional heuristics.

3) Flexibility

GA provides us a great flexibility to hybridize with domain-dependent heuristics to make an efficient implementation for a specific problem.

3.3 Multiobjective Optimization Problems

During the last two decades, the genetic algorithms have received considerable attention regarding their potential as a novel approach to the multiobjective optimization problems, known as evolutionary multiobjective optimization or genetic multiobjective optimization.

Multiobjective optimization problem with

q

objectives and m constraints will be formulated as follows:

)}

( ,...,

) ( ,

) ( {

max z

₁

= f

₁

x z

₂

= f

₂

x z

_q

= f

_q

x

(3.1)

m i

g

_i

( ) 0 , 1 , 2 ,..., t.

s. x ≤ =

(3.2)

3.3.1 The Concept of Pareto Solution

In the most existing methods, the Pareto solutions are identified at each generation and used to calculate fitness values or ranks for each chromosome only. The Pareto solution is based on nondominated concept. For a given point z0∈Z, it is nondominated if and only if there does not exist another point z∈Z such that, for the maximization case,

q z

z_q ≥ _q⁰, for all (3.3)

q z

z_q > _q⁰, for at least one (3.4)

where, z0 is a dominated point in the criterion space Z.

No mechanism is provided to guarantee that the Pareto solutions generated during the evolutionary process enter the next generation. A special pool for preserving the Pareto solutions is added onto the basic structure of genetic algorithms. At each generation, the set of Pareto solutions

E (t )

is updated by deleting all dominated solutions and adding all newly generated Pareto solutions (Xu and Vukovich, 1998). Fonseca and Fleming’s Pareto ranking method (Fonseca and Fleming, 1995) is used for creating and updating Pareto set. In this method, all nondominated chromosomes are assigned to rank 1, and any other chromosomes are assigned a rank equal to the number of its dominating chromosomes plus one. This method proceeds by sorting the population according to the ranks, and ties may be broken by random choice. Figure 3.4 shows an example of Fonseca and Fleming’s Pareto ranking method.

1

1

1

1

1 3

5

2 f₁

f₂

Figure 3.4 Simple case with two objectives (f1, f2) to be minimized using moGA The overall structure of the approach is given as follows:

procedure 3.2: Pareto genetic algorithms begin

t

← 0 ;

initialize

P (t )

; objective

P (t )

; create Pareto

E (t )

; fitness eval(P);

while (not termination condition) do crossover

P (t )

to yield

C (t )

; mutation

P (t )

to yield

C (t )

; objective C(t);

update Pareto E(P,C);

fitness eval(P,C);

selection

P ( t + 1 )

from

P (t )

and C(t);

t

←

t

+1 ; end

end

3.3.2 Adaptive Weight Approach

Gen and Cheng proposed an adaptive weights approach which utilizes some useful information from current population to readjust weights in order to obtain a search pressure towards to positive ideal point (Ishii, Shiode and Murata, 1998; Gen and Kim, 1999).

For the examined solutions at each generation, two extreme points are defined: the maximum extreme point

z

⁺ and the minimum extreme pint

z

⁻ in criteria space as the follows:

} ,..., ,

{z₁^max z₂^max z_q^max

z⁺ = (3.5)

} ,..., ,

{z₁^min z₂^min z_q^min

z⁻ = (3.6)

where

z

_k^min and

z

_k^max are the maximal value and minimal value for objective k in current population. Let

P

denote the set of current population. For a given individual

x

, the maximal value and minimal value for each objective are defined as the follows:

z_k^max =max{f_k(x)|x∈P}, k=1,2,...,q (3.7) q

k P f

x

z_k^min=min { _k(x)|x∈ }, =1,2,..., (3.8)

The hyper parallelogram defined by the two extreme points is a minimal hyper parallelogram containing all current solutions. The two extreme points are renewed at each generation. The maximum extreme point will gradually approximate to the positive ideal point.

The adaptive weight for objective k is calculated by the following equation:

q z k

w z

k k

k

1 , 1 , 2 ,...,

min

max

=

= −

(3.9)

For a given individual

x

, the weighted-sum objective function is given by the following equation:

∑

=

−

= ^q

k

k k

k z z

w z

1

min) (

)

(x (3.10)

∑

=

−

=

^q

−

k k k

k k

z z

z z

1 max min

min

(3.11)

∑

=

−

=

^q

−

k k k

k k

z z

z f

1 max min

)

min

(x

(3.12)

As the extreme points are renewed at each generation, the weights are renewed accordingly.

Equation 3.10 is a hyperplane defined by the following extreme point in current solutions:

) ..., , ..., , ,

(z₁^max z₂^min z_k^min z_q^min (3.13)

K

) ..., , ..., , ,

(z₁^min z₂^min z_k^max z_q^min (3.14) K

) ..., , ..., , ,

(z₁^min z₂^min z_k^min z_q^max (3.15)

For example of a bicriteria maximization problem, it is an adaptive moving line defined by extreme points (z₁^max,z^min₂ ) and (z₁^min,z₂^max), as shown Figure.3.5. The rectangle defined by the extreme points (z₁^max,z^min₂ ) and (z₁^min,z₂^max) is the minimal rectangle containing all current solutions.

z+

z

1

z

2

min

z2

max

z1 max

z2

min

z1

subspace corresponding to

current solutions

adaptive moving line

whole criteria space Z positive ideal point minimal rectangle containing

all current solutions

maximum extreme point

minimum extreme point

z−

) , (z₁^min z₂^max

) , (z₁^max z^min₂

z+

z

1

z

2

min

z2

max

z1 max

z2

min

z1

subspace corresponding to

current solutions

adaptive moving line

whole criteria space Z positive ideal point minimal rectangle containing

all current solutions

maximum extreme point

minimum extreme point

z−

) , (z₁^min z₂^max

) , (z₁^max z^min₂

Figure 3.5 Adaptive weights and adaptive hyperplane

3.4 Hybrid Multiobjective Genetic Algorithm

The convergence speed to the local optimum of the GA can be improved by adopting the probability of Simulated Annealing (SA). The SA means the simulation of the annealing process of metal. If the temperature is lowered carefully from a high temperature in the annealing process, the melted metal will produce the crystal at 0 K. Kirkpatrick developed an algorithm that finds the optimal solution by substituting the random movement of the solution for the fluctuation of a particle in the system in the annealing process and making the objective function value correspond to the energy of the system, which decreases (involving the temporary increase by Boltzman’s probability) with the descent of temperature (Kim, Hayashi and Nara, 1997; Kirkpatrick, Gelatt and Vecchi, 1983). Even though the fitness function value of newly produced strings is lower than those of current strings, the newly produced ones are fully accepted in the early stages of the searching process. However, in later stages, a string with a lower fitness function value is seldom accepted. The procedure of improved GA by the probability of SA will be written as follows:

procedure 3.3: Improving of GA chromosome by the probability of SA input: parent chromosome V, proto-offspring chromosomes V’, temperature T,

cooling rate of SA ρ

output: offspring chromosomes V’’

begin

r ← random[0,1];

∆E ← eval(V’)-eval(V);

if ( ∆E >0 || r <Exp(∆E/T) ) V’’ ← V’;

else

V’’ ← V;

T ← T xρ;

output offspring chromosomes V’’

end

In this procedure, V and V’ are mean parent chromosome and proto-offspring chromosome.

V’’ means offspring chromosome which produced by this procedure. The T means the temperature and the ρ means the cooling rate of SA.

The procedure of hybrid multiobjective GA combined with SA will be written as followings;

procedure 3.4: Pareto genetic algorithms

begin

t

← 0 ;

initialize

P (t )

; objective

P (t )

; create Pareto

E (t )

; fitness eval(P);

while (not termination condition) do crossover

P (t )

to yield

C (t )

; mutation

P (t )

to yield

C (t )

; objective C(t);

update Pareto E(P,C); fitness eval(P,C);

selection

P ( t + 1 )

from

P (t )

and C(t);

t

←

t

+1 ; end

end

Chapter 4 Continuous Task Scheduling

Recent advances in computing, storage, and communication technologies have made a wide variety of multimedia applications possible. Multimedia systems combine a various information sources, such as audio, video, text, graphics and image, into the wide range of application (Chen, 1996). Video and audio data are referred to as continuous media due to their real-time delivery requirements, whereas text, graphics and image data are referred to as discrete media.

Since continuous media are displayed within a certain time constraint, their computation and manipulation of continuous media should be handled under more limited condition than that of discrete media. For example, continuous media should be completed computation before their predetermined deadlines (Tsun and Babak, 1999). In this chapter, the scheduling for periodic continuous tasks is tested.

4.1 Continuous Task Scheduling on Uniprocessor System

The continuous media of multimedia system is typical the soft real-time task.

Rate Regulating Proportional Share (rrPS) scheduling algorithm and Modified Proportional Share (mPS) Scheduling algorithm is designed for continuous soft real-time task. However, computational burden and solution accuracy of these algorithms could be improved by new algorithm based on Genetic Algorithm (GA).

The proportion-based GA is proposed for this task scheduling problem. The objective of proposed scheduling algorithm is to minimize the weighted sum of variance of tardiness and the total number of context switching among tasks. Some drawbacks (i.e. low resource utilization and avoidable context switching overhead) of Rate Monotonic (RM) and Earliest Deadline First (EDF) derived algorithms for soft real-time tasks could be fixed in proposed algorithm. Not only advantages of RM and EDF approaches but plus side of GA, such as, high speed, parallel searching and high adaptability is kept.

4.1.1 Continuous Task Scheduling Problem

In this study, the followings are assumed:

1) All tasks are periodic.

2) All tasks are assigned to same processor (uniprocessor system)