Kirill Borissov
email: kirill@eu.spb.ru

Thierry Bréchet
email: thierry.brechet@uclouvain.be.

Stéphane Lambrecht
email: stephane.lambrecht@univ-lille1.fr

Environmental Maintenance in a Dynamic Model with Heterogenous Agents

Keywords: intertemporal choice and growth, discounting, government environmental policy, externalities, environmental taxes, voting equilibrium JEL Classification: D90, Q58, H23, D72

We assume a population of infinitely-lived households of the economy split into two groups : one with a high discount factor (the patient) and one with a low one (the impatient). The environmental quality is deteriorated by firm's polluting emissions. The governmental policy consists in proposing households to vote for a tax aimed at environmental maintenance. We study the voting equilibrium at steady states. The resulting equilibrium maintenance is the one of the median voter. We show that (i) an increase in total factor productivity may produce effects described by the Environmental Kuznets Curve, (ii) an increase in the patience of impatient households may foster environmental quality if the median voter is impatient and maintenance positive, (iii) a decrease in inequality among the patient households leads to an increase in environmental quality if the median voter is patient and maintenance is positive. We also show that, if the median income is lower than the mean, our model predict lower level of environmental quality than the representative agent model, and that increasing public debt decreases the level of environmental quality.

Introduction

With the growing importance of global environmental issues, such as global warming, and the emphasis put on the general question of sustainable growth and development, environmental policies and their financing have become a major subject of concern in many developing or developed countries. As a response, economic theory, and especially in macro-economics, elaborated dynamic models based on the representative agent assumption to disentangle the nexus between economic growth and pollution, or more generally environmental quality (see among many others, [START_REF] Gradus | The trade-off between environmental care and long-term growth: pollution in three prototype growth models[END_REF], [START_REF] Stokey | Are there limits to growth?[END_REF]), or Xepapadeas (2005)). Though, it is striking to notice that the public debate about environmental policies and their financing very often focus on the distributive aspects of the policies, and more precisely on the distribution of their burden among heterogenous agents. To capture that dimension, economists must get rid of the representative agent and must start considering heterogeneous agents in their macrodynamic models. There exist several ways of introducing heterogeneity, e.g. in wealth [START_REF] Kempf | Is inequality harmful for the environment in a growing economy?[END_REF]), in individual labor productivity [START_REF] Jouvet | Public and private environmental spending. A political economy approach[END_REF]), or in age with overlapping generations [START_REF] John | An overlapping generations model of growth and the environment[END_REF], [START_REF] Jouvet | Public and private environmental spending. A political economy approach[END_REF].

In this paper we consider heterogeneity in the agents' discount factor. 1 We assume that the population is exogenously divided into two groups, one with patient households and the other with impatient households. Each individual votes in favor, or against a public policy in environmental maintenance. Maintenance is a public policy, financed by a tax on households, and pollution flows from firm's activity. We define a voting equilibrium and the related general equilibrium of the economy at the steady state.

Our setting raises many issues. First, if the policy choice were onedimensional, then the median-voter theorem could apply. Unfortunately, in our dynamic multidimensional setting, it cannot. We will show that, at the steady state, a voting equilibrium will coincide with the solution that would result from the median voter theorem. In other words, we provide a logically consistent definition of the median voter theorem in a dynamic setting. This establishes the applicability of the median voter theorem on steady state equilibria. This result is important because, in the literature, it is always assumed that the median voter theorem can be applied after the steady state is defined, though the steady state equilibrium itself depends on the voting equilibrium (see e.g. [START_REF] Kempf | Is inequality harmful for the environment in a growing economy?[END_REF], [START_REF] Corbae | Politico-economic consequences of rising wage inequality[END_REF]). Our contribution is to prove that a dynamic voting equilibrium coincides with the application of the median voter theorem. This represents a contribution to the theoretical literature. Further, to stress the advantages of considering heterogenous agents, we compare our results with what the representative agent framework would provide. And the results differ in many respects.

Beyond the theoretical aspects, we also contribute the literature on political economy and environmental policy. With some comparative statics, we are able to show several novel results. We first show that, if the median voter is impatient, she consumes all her revenue, and maintenance will be zero. But if the median voter is patient, then maintenance will be positive, but not uniquely determined. Then we can go further and stress that there exist two channels of discount factors impact on the behavior of agents towards maintenance, a direct one and an indirect one. In our model, the higher the agent's discount factor, the larger is her desired level of maintenance. This is the direct channel. But at the same time, the richer the agent, the larger is her desired level of maintenance. It is well-known that only agents with a high discount factor have positive savings in the long run. Those with a low discount factor save nothing. Thus, the former will become wealthy in the long run and desire high levels of environmental maintenance, while the latter will become poorer and desire lower levels of maintenance. This is the indirect channel. This provides us with new insights about the relationship between economic development and environmental quality through the voting equilibrium (a new rationale for the so-called Environmental Kuznets Curve, see e.g. [START_REF] Dasgupta | Confronting the Environmental Kuznets Curve[END_REF], [START_REF] Prieur | The environmental kuznets curve in a world of irreversibility[END_REF]). We also show (among other results) that, when the median voter is patient, then a lower inequality among agents has a positive effect on the environmental quality.

This discussion also relates to the broad debate about the discounting rate in environmental economics.2 Even if discounting is often considered in the literature as a normative issue, it also has a positive content, as stressed by Dasgupta: "discount rates on consumption changes combine values with facts. (Dasgupta, 2008, p. 144) or by [START_REF] Arrow | Intertemporal Equity, Discounting, and Economic Efficiency[END_REF] who distinguishes prescriptive and descriptive positions. In environmental economics, a high discount rate implies relatively modest and slow environmental maintenance, while a low discount rate implies immediate and strong action. The common characteristics of all this literature is to rely on the assumption that there exists a representative agent in the economy whose preferences are considered as given by a benevolent social planner. This agent further acts as a benevolent social planner3 . We depart from the representative agent hypothesis by considering an economy populated with heterogeneous agents. Then, we are able to provide a microeconomic rationale to determine the implicit global discount rate in this economy. This departs from the normative discussion on what the discount rate should be. In our analysis, we take beforehand agents' preferences, and we scrutinize how the existence of heterogeneity shapes the policy in the global economy. This is a novel contribution to the debate on discounting based on a positive approach.

Applying the median voter theorem to dynamic models requires a suitable analytical redesign of the political settings in this model. Models of such a kind are much harder to analyze than their static counterparts or than the usual intertemporal models without political ingredients. It appears from the recent literature that the analysis of the performance of majoritarian settings in dynamic frameworks has attracted growing interest, see e.g. [START_REF] Baron | A dynamic theory of collective goods programs[END_REF], [START_REF] Krusell | Politico-economic equilibrium and economic growth[END_REF], [START_REF] Cooley | A positive theory of social security based on reputation[END_REF], Rangel (2001) and [START_REF] Bernheim | A Solution Concept for Majority Rule in Dynamic Settings[END_REF]. The stage of development of the theory is still in its infancy, and there is no consensus about how to model dynamic majoritarian voting. Without going into detail in this introduction, it should be stressed that our approach to voting is different from the approaches used in the above-mentioned papers. We propose a novel definition of voting equilibrium, which is related to Kramer-Shepsles equilibrium concept [START_REF] Kramer | Sophisticated voting over multidimensional choice spaces[END_REF], Shepsle (1979)). This definition will allow us to provide new theoretical results about voting equilibrium in a dynamical setting.

These results bring us to our last discussion on alternative financing schemes of the environmental maintenance. We look at the different impacts on heterogenous households and especially on the median voter, of financing maintenance both with taxes and with issuance of public bonds. We show that, under common assumption about income distribution, an increase in the public debt leads to a lower environmental quality.

The paper is organized as follows. In Section 2 we present the model, define the competitive equilibria and describe steady-state equilibria for a given policy. In Section 3 we endogenize the voting procedure on environmental maintenance, define the intertemporal and steady state voting equilibria, and show the logical consistency between the median voter theorem and the voting equilibrium in dynamic general equilibrium. In Section 4 the comparison with the representative agent framework is proposed. In Section 5 we perform some comparative statics exercises to determine under which circumstances environmental quality is positively impacted by an increase in total factor productivity, an increase in patience, and a decrease in inequality. The discussion about the impact of public debt on the environmental quality is carried out in Section 6. Finally, Section 7 concludes.

The model, and preliminary results

Our objective in this paper is to define and to study the intertemporal competitive equilibria with voting on maintenance. We define voting equilibria in two steps. In this section, we do the first step, namely we determine the competitive equilibrium production and consumption paths for a given maintenance. In the next section, we will do the second step, namely we will select, in the class of these competitive equilibria, the ones in which there is also a voting equilibrium.

The framework of analysis used in this paper is the one with infinitelylived consumers, supplying inelastically each time one unit of labor and with a representative globally polluting firm.

Production and pollution

Output is determined by means of a neoclassical production function F (K t , L t ) = Lf (k t ), where K t and L t are capital and labor at time t, k t = K t /L is capital intensity, f (k) = F (k, 1) is the production function in intensive form. Capital is assumed to depreciate completely within the period. Output can be used for consumption, investment or maintenance. Thus, the dynamics of capital is given by

K t+1 = F (K t , L t ) -C t -M t ,
where C t is time t aggregate consumption and M t is time t aggregate maintenance.

Pollution (the emissions level) at time t, P t , is proportional to output:

P t = λF (K t , L) = λLf (k t ), λ > 0. ( 1
)
We denote by Q t an index of environmental quality at time t and by M t the maintenance of environmental quality. The dynamics of Q t is given by

Q t+1 = Ψ(Q t -P t + M t µ ), (2)
where Ψ : R + → R + is a concave increasing function, µ > 0 is exogenously given coefficient. Since "marginal environmental productivity" of maintenance, ∂Q t+1 /∂M t = Ψ ′ (•)/µ, is negatively influenced by µ, we can interpret 1/µ as the environmental efficiency of maintenance. By Q we denote a unique positive solution to the following equation: Ψ(Q) = Q, i.e. the stationary value of environmental quality in the case with no pollution and no maintenance. For example, the following particular forms of Ψ(X) can be used: Ψ

(X) = X ν Q1-ν , with 0 < ν < 1, or Ψ(X) = νX +(1-ν) Q, with 0 < ν < 1. Let Φ(•) = Ψ -1 (•).
We can rewrite (2) as follows:

µΦ(Q t+1 ) = µ(Q t -P t ) + M t .
It should be noted that µΦ ′ (Q) can be interpreted as the marginal cost of quality improvement.

The representative firm maximizes its profit π t under the constraint of the technology F (K t , L t ) by choosing its preferred volumes of capital K t and labor L t , considering the real wage and interest rates, w t and r t , as given. The firm's problem is summarized as follows: max Kt,Lt

π t = F (K t , L t ) -(1 + r t )K t -w t L t , (3)
and admits the following first-order conditions:

F ′ K (K t , L t ) = 1 + r t and F ′ L (K t , L t ) = w t , or in intensive terms: f ′ (k t ) = 1 + r t and f (k t ) -f ′ (k t )k t = w t .

Consumers

Population consists of L consumers. Each consumer is endowed with one unit of labor force. For simplicity, L is integer and odd. The objective function of consumer i is

∞ t=0 β t i [u(c t ) + v(Q t )],
where c t is his consumption at time t, β i is his discount factor. We assume that u(c) and v(Q) satisfy the following conditions:

u ′ (c) > 0, u ′′ (c) < 0, u ′ (0) = ∞, v ′ (Q) > 0, v ′′ (Q) < 0, v ′ (0) = ∞. Each consumer i is patient (β i = β h ) or impatient (β i = β l ), 0 < β l < β h < 1.
We denote by H h the set of patient consumers (with discount factor equal to β h ) and by H l the set of impatient consumers (those with β l ).

Each consumer pays a tax m t = M t /L to finance the public provision of environmental maintenance and the budget constraints of a consumer at time t are

c t + s t + m t ≤ w t + (1 + r t )s t-1 , (4)
c t ≥ 0, s t ≥ 0,
where w t is the wage rate r t is the interest rate and s t are her savings consumer at time t. It should be emphasized that consumers are forbidden to borrow against their future labor income and hence their savings must be non-negative. The consumer's utility depends both on variables on which he has full control, c t and s t , and on the variable m t which is determined by the voting procedure, yet to be introduced. Thus, before analyzing the result of the voting procedure, solving the consumer's objective is equivalent to choosing the optimal values of c t and s t , ∀t, considering m t as given.

Suppose that at time τ consumer i is given his predetermined level of savings ŝi τ -1 , the predetermined level of environmental quality Qτ , the stream of pollution (P t ) ∞ t=τ and some maintenance policy which is represented by a sequence m = (m t ) ∞ t=0 of non-negative numbers. Then the problem of this consumer is

P 1 (τ ) =                        max (ct) +∞ t=τ ,(st) +∞ t=τ ,(Qt) +∞ t=τ ∞ t=τ β t i [u(c t ) + v(Q t )],
subject to

µΦ(Q t+1 ) = µ(Q t -P t ) + Lm t , t = τ, τ + 1, . . . , c t + s t + m t ≤ w t + (1 + r t )s t-1 , t = τ, τ + 1, . . . , s τ -1 = ŝi τ -1 , Q τ = Qτ , c t ≥ 0, s t ≥ 0, t = τ, τ + 1, . . . .                        It should be noticed that since m = (m t ) ∞ t=0 is given, the sequence (Q t ) +∞
t=τ is in fact predetermined by Qτ and m. Hence, the utility consumer i derives from environmental quality, ∞ t=τ β t i v(Q t ), does not depend on her choice, though, formally, Q t is a control variable in problem P 1 (τ ).

Competitive equilibrium paths and steady-state equilibria

Now we can give the definition of the equilibrium path supposing that the environmental policy is given and that no agent can change it. Let at time 0 the environmental policy be represented by some sequence m = (m t ) ∞ t=0 of non-negative numbers be given. Let an initial state {(ŝ i -1 ) L i=1 , k0 , Q0 } also be given. Here ŝi -1 ≥ 0 are the initial savings of consumers i = 1, . . . , L, k0 > 0 is the initial per capita stock of capital,

L i=1

ŝi -1 = L k0 , and Q0 > 0 is the initial value of environmental quality.

Definition 1. Competitive equilibrium path Given m, the sequence E m = {k * t , 1 + r * t , w * t , (s i * t-1 , c i * t ) L i=1 , P * t , Q * t } ∞ t=0 is called a competitive equilibrium path starting from {(ŝ i -1 ) L i=1 , k0 , Q0 } if
1. capital and labor markets clear at the following prices:

1 + r t = 1 + r * t = f ′ (k * t ), w t = w * t = f (k * t ) -f ′ (k * t )k * t , t = 0, 1, . . . ; 2. for each household i = 1, . . . , L the sequence (s i * t-1 , c i * t , Q * t ) ∞ t=0 is a solution to problem P 1 (0) at 1 + r t = 1 + r * t , w t = w * t , t = 0, 1, . . . ; 3. L i=1 s i * t-1 = Lk * t , t = 0, 1, . . . ; 4. P * t = λLf (k * t ), t = 0, 1, . . . ; 5. µΦ(Q * t+1 ) = µ(Q * t -P * t ) + Lm t , t = 0, 1, . . . .
Notice that, at each time t, maintenance m t is given and smaller than the wage rate w t . We will not discuss the existence of equilibrium paths. Our main emphasis will be made on steady-state equilibria. Reasonably, we define steady-state equilibria under the assumption that the environmental policy is given and constant over time.

Definition 2. Competitive steady state equilibrium

Let an m ≥ 0 be given and let

m = (m t ) ∞ t=0 , with m t = m, t = 0, 1, . . . . We call a tuple E m = {k * , 1 + r * , w * , (s i * , c i * ) L i=1 , P * , Q * } a competitive steady-state equilibrium if the sequence {k * t , 1 + r * t , w * t , (s i * t-1 , c i * t ) L i=1 , P * t , Q * t } ∞ t=0 given for all t = 0, 1, . . . by k * t = k * , 1 + r * t = 1 + r * , w * t = w * , (5)
(s i * t-1 , c i * t ) L i=1 = (s i * , c i * ) L i=1 , (6)
P * t = P * , Q * t = Q * . (7) is an equilibrium path starting from the initial state {(ŝ i -1 ) L i=1 , k0 , Q0 } = {(s i * ) L i=1 , k * , Q * }.
The following proposition describing the structure of steady-state equilibria is an adaptation to our model of the well-known results by [START_REF] Becker | On the long-run steady-state in a simple dynamic model of equilibrium with heterogeneous households[END_REF][START_REF] Becker | Equilibrium dynamics with many agents[END_REF].

Proposition 1. Structure of steady state equilibrium

A tuple E m = {k * , 1 + r * , w * , (s i * , c i * ) L
i=1 , P * , Q * } satisfying m < w * is a steady-state equilibrium if and only if

β h = 1 1 + r * , 1 + r * = f ′ (k * ), w * = f (k * ) -f ′ (k * )k * , (8)
P * = λLf (k * ), (9) µΦ(Q * ) = µ(Q * -P * ) + Lm, (10)
s i * = 0, i ∈ H l , (11)
s i * ≥ 0, i ∈ H h , (12)
L i=1

s i * = i∈H h s i * = Lk * ; (13) c * + s * + m = w * + (1 + r * )s * . (14) Proof. See Appendix A.1.
In this proposition, equation [START_REF] Arrow | Intertemporal Equity, Discounting, and Economic Efficiency[END_REF] shows that the steady-state capital intensity, interest rate, and the wage rate are determined by the discount factor of the patient consumer. Equations ( 11)-( 12) tell us that impatient consumers have zero savings. It means that all the capital is own by patient consumers. As a consequence, in a steady-state equilibrium all impatient consumers are identical in terms of income and savings. In contrast, the distribution of savings among patient consumers is indeterminate in a steady state equilibrium. As shown by equation ( 13), only aggregate savings is determined.

Voting equilibria

There is no reason for heterogenous agents to agree on the desired level of environmental maintenance. One way to solve this disagreement is to choose it by majority voting. If the level of maintenance is to be determined by majority voting, which level will be chosen? If policy choices were one-dimensional, we would refer to the median voter theorem, but in our intertemporal model this theorem cannot be applied directly since, formally speaking, in such models policy choices are multi-dimensional.

However, if we constraint our consideration to steady states, median voter approach to decision-making seems to be quite reasonable. At the same time, we should not mistakenly think that mere consideration of steady states only makes policy choices one-dimensional. Fortunately, as we show in this section, for some reasonable definition of voting equilibrium, in a voting steady-state equilibrium the level of maintenance will be chosen just by the median voter.

Let m = (m t ) ∞ t=0 be an environmental policy. The optimal value of problem P 1 (τ ) for consumer i is a function of ŝτ-1 , Qτ and m. We will denote this optimal value by V i,τ (ŝ τ -1 , Qτ , m). Definition 3. Preferred change in maintenance Suppose that the environmental policy is represented by some sequence m = ( mt ) ∞ t=0 of non-negative numbers and that at m = m the function

V i,τ (ŝ τ -1 , Qτ , m) is differentiable in m τ . We say that consumer i is in favor of increasing m τ if ∂V i,τ (ŝ τ -1 , Qτ ,m) ∂mτ
> 0 and is in favor of decreasing

m τ if ∂V i,τ (ŝ τ -1 , Qτ ,m) ∂mτ < 0 and mτ > 0.
Let us assume that, for an equilibrium path m) the number of consumers who are in favor of increasing mτ , and by N - τ (E m) the number of consumers who are in favor of decreasing mτ . Now we are ready to define intertemporal voting equilibria.

E m = {k * t , 1 + r * t , w * t , (s i * t-1 , c i * t ) L i=1 , P * t , Q * t } ∞ t=0 the function V i,τ (s * τ -1 , Q * τ , m) is differentiable in m τ at m = m. We denote by N + τ (E

Definition 4. Intertemporal voting equilibrium

Let m * = (m * t ) ∞ t=0 be a maintenance policy and E m * be an equilibrium path constructed at this policy. We call the couple (m * , E m * ) an intertemporal voting equilibrium path if at m = m * ∀τ = 0, 1, . . . the function

V i,τ (s * τ -1 , Q * τ , m) is differentiable in m τ , and N + τ (E m * ) < L 2 , N - τ (E m * ) < L 2 , ∀τ = 0, 1, . . . .
This definition is in line with the usual way of defining intertemporal equilibrium, as articulated by Hicks (1937) and, more recently, by Grandmond (1983). In our model, any intertemporal voting equilibrium can be seen as a sequence of temporary voting equilibria in which agents correctly anticipate the whole future, including voting results. Indeed, let (m * , E m * ) be an intertemporal voting equilibrium. Suppose that at time τ the agents are asked to vote on m τ and that they correctly anticipate m * t for all t = τ + 1, τ + 2, .... Then it is clear that all the conditions for the median voter theorem hold in this one-dimensional voting, and that the preferred value of m τ for the median voter coincides with m * τ . A key implication is that intertemporal voting equilibria are time consistent.

In the rest of the paper we shall focus on steady state voting equilibria. Consider a couple (m * , E m * ), where m * ≥ 0 and To answer the question of whether a couple (m * , E m * ) is a steady state voting equilibrium or not it is sufficient to know which consumers are in favor of increasing of m * 0 = m * at time 0 and which ones are in favor of its decreasing.

E m * = {k * , 1 + r * , w * , (s i * , c i * ) L i=1 , P * , Q * } is
We know that for each i the sequence (

s i t-1 , ci t , Qt ) ∞ t=0 given by si t-1 = s i * , ci t = c i * , Qt = Q * , (15)
is a solution to max

(ct) +∞ t=0 ,(Qt) +∞ t=0 ∞ t=0 β t i [u(c t ) + v(Q t )], (16)
µΦ(Q t+1 ) = µ(Q t -P * ) + Lm * t , t = 0, 1, . . . , (17)
c t + s t + m * t ≤ w * + (1 + r * )s t-1 , t = 0, 1, . . . , (18)
s i -1 = ŝi -1 , Q 0 = Q0 , (19) c t ≥ 0, s t ≥ 0, Q t ≥ 0, t = 0, 1, . . . ( 20
) at ŝi -1 = s i * , Q0 = Q * .
Lemma 1. Differentiability of value function w.r.t. maintenance and sign of derivative

Let for some i the sequence (s i t-1 , ci t , Qt ) ∞ t=0 given by (15) be a solution to problem ( 16)-( 20) at given m * t = m * ∈ [0, w * ), t = 0, 1, ... and at ŝi

-1 = s i * , Q0 = Q * . Then V i,0 (s i * , Q * , m * ) is differentiable in m * 0 and ∂V i,0 (s i * , Q * , m * ) ∂m * 0 0 ⇔ β i Lv ′ (Q * ) µu ′ (c i * )(Φ ′ (Q * ) -β i ). ( 21
)
Proof. See appendix A.2

The interpretation of Lemma 1 runs as follows. Consider the first inequality of equation ( 21) at a given maintenance m * 0 and suppose that the left-hand side is higher than the right-hand side . In this case, out of a marginal change in maintenance, the induced marginal utility of environmental quality, i.e. the LHS of equation ( 21), is larger than the induced marginal utility of consumption, i.e. the RHS of ( 21). This is likely to happen when the given maintenance level m * 0 is low. This entails that the consumer is in favor of an increase in maintenance. In the opposite case, the given maintenance m * 0 is likely to be large so that the induced marginal utility of consumption is higher than the induced marginal utility of quality and the consumer is in favor of decreasing maintenance.

To check whether a couple (m * , E m * ) is a voting steady-state equilibrium or not, consider the following problem in which household i is free to determine her preferred level of maintenance m t :

P 2 =                        max (ct) +∞ t=0 ,(st) +∞ t=0 ,(mt) +∞ t=0 ,(Qt) +∞ t=0 ∞ t=0 β t i [u(c t ) + v(Q t )],
subject to

µΦ(Q t+1 ) ≤ µ(Q t -P * ) + Lm t , t = 0, 1, . . . , c t + s t + m t ≤ w * + (1 + r * )s t-1 , t = 0, 1, . . . , s -1 = ŝ-1 , Q 0 = Q0 , c t ≥ 0, s t ≥ 0, m t ≥ 0, Q t ≥ 0, t = 0, 1, . . .                       
We say that (s, c, m, Q) ∈ R 4 + determines a steady-state solution to this problem if the sequence (s t-1 , ct , mt , Qt ) ∞ t=0 given by st

-1 = s, ct = c, mt = m, Qt = Q (22)
is its solution at ŝ-1 = s and Q0 = Q.

Prior to formulating the following lemma, remind that β h (1 + r * ) = 1 and hence that β i (1 + r * ) < 1, ∀i ∈ H l , and

β i (1 + r * ) = 1, ∀i ∈ H h .
Lemma 2. Characterization of steady state solution to P 2

The tuple (s, c, m, Q) ∈ R 4 + determines a steady-state solution to P 2 if and only if

β i (1 + r * ) < 1 ⇒ s = 0 (23) β i Lv ′ ( Q) ≤ µu ′ (c)(Φ ′ ( Q) -β i ) (= if m > 0) (24) c = w * + r * s -m (25) µ(Φ( Q) -Q + P * ) = L m (26)
Proof. See appendix A.3.

To simplify the presentation we can get rid of m by noticing that m > 0 ⇔ c < w * + r * s and rewriting conditions ( 24)-( 25) as follows:

c = (w * + r * s - µ L P * ) + µ L ( Q -Φ( Q)), ( 27
) c ≤ w * + r * s, ( 28
)
β i Lv ′ ( Q) ≤ µu ′ (c)(Φ ′ ( Q) -β i ) (= if c < w * + r * s). ( 29
)
Equation

β i Lv ′ (Q) = µu ′ (c)(Φ ′ (Q) -β i ) implies an increasing dependence of c on Q. As for equation c = (w * + r * s -µ L P * ) + µ L (Q -Φ(Q))
, for any given s, it specifies a dependence of c on Q which is simply decreasing, or is first increasing (Φ ′ (Q) < 1) and then decreasing (Φ ′ (Q) > 1).

Suppose we are given m * ∈ [0, w * ), where w * is given by [START_REF] Arrow | Intertemporal Equity, Discounting, and Economic Efficiency[END_REF]. Let E m * = {k * , 1 + r * , w * , (s i * , c i * ) L i=1 , P * , Q * } be a steady-state equilibrium constructed at the maintenance policy m * = (m * , m * , ...). Put all households in ascending order of their savings and take the median one, i m .4 Lemmas 1 and 2 lead to the following theorem.

Theorem 1. Steady state voting equilibrium and median voter

The couple (m * , E m * ) is a steady-state voting equilibrium if and only if for i = i m , the tuple (s i * , c i * , m * , Q * ) is a steady-state solution to problem P 2 . This theorem reads that, in the long-run, the capital stock depends on the discount factor of the patient households, while maintenance and environmental quality depend on the median discount factor and the median savings.

+ + 3 + 2 Q E * + 1 Q* + + 3 + 2 Q E * + 1 Q* Figure 1: Left: Zero-Maintenance Equilibrium (Regime 1) -Right: Positive Maintenance Equilibrium (Regime 2)
It follows from this theorem that, in equilibrium, there exist two possible cases, depending on whether c im * = w * + r * s im * (⇔ m * = 0) or c im * < w * + r * s im * (⇔ m * > 0). They are illustrated by the left and right panel of Fig. 1, on which we take s im * as given. On these graphs the three curves C 1 , C 2 and C 3 are defined as follows:

Curve C 1 :

β im Lv ′ (Q) = µu ′ (c)(Φ ′ (Q) -β im ) (30) Curve C 2 : c = w * + r * s im * (31) Curve C 3 : c = (w * + r * s im * - µ L P * ) + µ L (Q -Φ(Q)) (32)
Let us describe more precisely these two regimes:

Regime 1 -Zero-maintenance. The equilibrium point (Q * , c im * ) is at the intersection of the C 2 curve and the C 3 curve (see figure 1a) and, as far as curve C 1 is concerned, we have

β im Lv ′ (Q * ) < µu ′ (c im * )(Φ ′ (Q * )-β im ).
Regime 2 -Positive-maintenance. The equilibrium point (Q * , c im * ) is at the intersection of the C 1 curve with the C 3 curve (see figure 1b) and, as far as curve C 2 is concerned, we have c im * < w * + r * s im * .

In combination with the above-mentioned two regimes (m * > 0 and m * = 0), two cases must be distinguished:

Case 1 -Impatient median voter: β im = β l and savings of the median voter are determined uniquely, s im * = 0.

Case 2 -Patient median voter: β im = β h and the savings of the median voter, s im * , are not determined uniquely; they can take any value in the interval [0, 2 L+1 Lk * ]. In both cases, the regime of equilibrium maintenance can be nil or positive. In Case 1, the equilibrium levels of maintenance and environmental quality are determined uniquely. As for Case 2, if there exists at least one equilibrium with positive maintenance, the equilibrium levels of maintenance and environmental quality are indeterminate since there is a continuum of these.

Several words on the existence of steady-state voting equilibria are in order. It is clear that if the majority of consumers is impatient, then steadystate voting equilibria exist for any distribution of savings among patient consumers because in this case the solution to problem P 2 for the median voter, (s, c, m, Q), unconditionally satisfies m < w * . If if the majority of consumers is patient, steady-state voting equilibria exists for any distribution of savings among patient consumers where the savings of the median voter are nil or sufficiently small. However, if the majority of consumers is patient, and the savings of the median voter are sufficiently high, it may be that she will vote for maintenance which exceeds the wage rate and hence steady-state equilibrium does not exist.

How agents' heterogeneity shapes environmental maintenance

In this section we compare the level of environmental quality in voting steadystate equilibria of our model with that in steady-state equilibria of a similar economy populated with identical agents. We constraint our consideration to the case where the equilibrium values of capital stock and hence output is the same in both models. The question we raise is the following: what is the effect of agents' heterogeneity in discount factor and wealth on environmental maintenance when agents are asked to vote?5

We will identify the homogenous population model as a particular case of our model where the discount factors of all consumers are the same and equal to β h . Moreover, by steady-state equilibria in the homogenous population model we will mean symmetrical voting steady-state equilibria in this particular case of our model i.e. equilibria where the savings of all consumers are the same and hence consumption of all agents is the same. To be precise, for symmetrical equilibria voting is somewhat irrelevant because in such equilibria voting is unanimous.

Let {k * S , 1 + r * S , w * S , (s i * S , c i * S ) L i=1 , P S * , Q S * } be a symmetric steady-state voting equilibrium of our model with β i = β h , i = 1, . . . , L,, and {k * , 1 + r * , w * , (s i * , c i * ) L i=1 , P * , Q * } be a steady-state voting equilibrium in our model with arbitrarily chosen discount factors. By symmetric we mean that s 1 * S = . . . = s L * S . It should be noticed that

k * S = k * , r * S = r * , w * S = w *
and that, by assumption,

s i * S = k * , i = 1, . . . , L.
The last equation says that the savings of agents in the symmetric steadystate voting equilibrium with β i = β h , i = 1, . . . , L, are equal to the mean of the savings in the model in the heterogeneous agent case. We assume that in the former model the discount factor shared by all consumer is β h but not β l , because otherwise equilibrium stocks of capital and output would be different in the two models.

Let

m * = w * + r * s im * -c im * , m * S = w * S + r * S k * S -c * S (= w * + r * k * -c * S )
, where c * S = c 1 * S (= . . . = c L * S ). The following proposition can be proved by means of the argument analogous to those in the previous section.

Proposition 2. Homogenous vs. heterogeneous population equilibria average behavior. Indeed, in our case, by assumption, we fix capital intensity to be the same in both models. On the other hand we do not fix maintenance, nor do we look at the representative agent version of the model which would yield the same maintenance.

1) Suppose that β im = β l and hence s im * = 0 in the heterogenous agent economy. In this case:

1. if m * S = 0, then m * = 0 and Q * = Q * S ; 2. if m * S > 0, then m * < m * S and Q * < Q * S .
2) Suppose that β im = β h in the heterogenous agent economy. In this case:

1. if s im * ≤ s i * S = k * , then: (a) if m * S = 0, m * = 0 and Q * = Q * S (b) if m * S > 0, m * < m * S and Q * < Q * S 2. if s im * ≥ s i * S = k * , then: (a) if m i * = 0, m * S = 0 and Q * = Q * S (b) if m * > 0, then m * > m * S and Q * > Q * S
We will see in the next section that under some reasonable assumptions it is natural to expect that in less developed countries there is no maintenance and that it is positive in developed countries. Thus, the above proposition reads that for less developed countries the predictions of both models are the same: there is no maintenance in steady-state equilibria irrespective of whether the median voter is patient or impatient.

For developed countries the predictions of the models differ. If the majority of agents in our model is impatient, then the equilibrium levels of maintenance and environmental quality in our model are lower than those predicted by the homogenous population model. If the majority of agent is patient, then it is necessary to compare the median saving or income with the mean ones. If the median savings are lower than the mean, or, equivalently, the median income is lower then the mean income, then the equilibrium levels of maintenance and environmental quality in our model are lower that those in the homogenous population model. Otherwise, the situation is the opposite. The case where the median income is lower than the mean is usually considered as typical.

Thus our model suggests that, in most cases in the real world, lower levels of maintenance and environmental quality should be observed than what the homogenous agents population model would predict.

Some comparative statics on preferences, income inequality, and technology

As stressed above, if the median voter is patient, in a steady state the savings of the median voter, s im * , are not determined uniquely. They can take any value in the interval [0, 2 L+1 Lk * ]. Therefore when making a comparative statics exercise we should remember that a change in a parameter will have an indeterminate effect on the savings of the median voter. To circumvent this problem, in this section, we first assume that k * is kept unchanged wheras s im * changes and then we assume that the ratio s im * /( L i=1 s i * ) and hence the ratio s im * /k * remain intact when a parameter changes (notice that since k * = ( L i=1 s i * )/L shows the mean savings, s im * /k * shows the proportion between the median and mean savings).

5.1 An increase in s i m * other things equal First, we carry out a comparative statics exercise relevant only in Case 2, where the median voter is patient and, consequently, his savings can be positive. Assume that k * is kept unchanged and s im * increases. This means that the increase in s im * reflects a change in the distribution of savings among the patient consumers only. Consequently, it leads to a another income distribution (more precisely, an increase in the median income relative to the mean).

• under Zero-Maintenance Equilibrium (Regime 1), a small increase in s im * , other things equal, will shift C 2 and C 3 upwards by the same magnitude. Hence, consumption of the median voter c im * will increase, but the environmental quality Q * will remain unchanged. A larger increase in s im * may lead the economy to Regime 2.

• under Positive-Maintenance Equilibrium (Regime 2), a small increase in s im * , other things equal, will shift C 3 upwards, while letting C 1 untouched. Hence the environmental quality Q * will increase.

Following the politico-economic literature about income inequality (see e.g. [START_REF] Meltzer | A rational theory of the size of government[END_REF]), an income distribution is called more equal, the higher the median income is relative to the mean (this is only reasonable in the case where the median income does not exceed the mean, which is considered as a typical situation). For our model this implies that in developed economies, where maintenance is positive, lower inequality has a positive effect on environmental quality, whereas in less developed economies, where there is no maintenance, inequality itself does not effect environmental quality.

An increase in total factor productivity

In the following sub-sections we shall assume that the production function is Cobb-Douglas, f (k) = k α , 0 < α < 1, and that the fraction of output necessary to eliminate emissions is lower than the labor share in output, 1 -α > µλ. Geometrically, the latter assumption implies that the curve C 3 shifts upwards after an increase in capital intensity. In the following we will clearly indicate which of our conclusions rely on this assumption.

Let us first assume an increase in the total factor productivity by introducing a scale parameter a in the production function, which one becomes aF (K, L) = Laf (k), where a represents the total factor productivity. The impact of an increase in total factor productivity will depend on the regime the economy follows in equilibrium.

Regime 1. Zero-maintenance Equilibrium

In this regime, a small increase in a will lead to an increase in k * , w * and w * + r * s im * . Hence, it will also increase the output level Lf (k * ) and pollution P * but will not make maintenance positive. As a consequence, the environmental quality Q * will decrease. Graphically (see Figure 2, left panel), C 2 will shift upwards due to the increase in w * + r * s im * . C 3 will also shift upwards, but to a smaller extent, since both w * and P * increase. If the increase in a becomes too large, then the economy switches to Regime 2, the Positive-maintenance Equilibrium.

Regime 2. Positive-maintenance Equilibrium

In that regime an increase in a will shift C 3 upwards, as shown in Figure 2, right panel, and hence to an increase in Q * (this is not necessarily true if Assumption A does not fulfil).

To sum up, if the economy starts under Regime 1, then an increase in a from 0 to +∞ first leads to a decrease in the environmental quality Q * , and then to an increase, as shown in Figure 2. If one considers that less developed countries most likely correspond to Regime 1 and wealthy countries to Regime 2, then this conclusion means that technological progress first goes with a decrease in environmental quality, and after some stage of development to an increase in environmental quality. This result provides a new rationale for an Environmental Kuznets Curve (see e.g. Stockey, 1998, Dasgupta et al. 20 Let us now turn to two comparative statics related to households' preferences.

+ + 3 + 2 Q E * + 1 Q* + + 3 + 2 Q E * + 1 Q*

Patient agents become more patient: an increase in β h

We first consider an increase in β h , meaning that patient agents become even more patient. The effects on the environmental quality will depend on which regime the economy experiences. Under Zero-Maintenance Equilibrium (Regime 1), a small increase in β h leads to an increase in capital intensity k * , wage rate w * , output Lf (k * ) and pollution P * , but it cannot make maintenance positive. Hence Q * decreases as β h increases under Regime 1. Graphically (see Fig. 2, left panel), C 2 shifts upwards due to the increase in w * ; C 3 also shifts upwards, but to a smaller extent (w * will increase but P * will also increase). If moreover the median voter is patient, Case 2, then, C 1 shifts to the right. As a consequence the economy may switch the economy to the Positive-maintenance regime (regime 2).

Under Positive-Maintenance Equilibrium (Regime 2, see Fig. 2b) an in-crease in β h will lead to an upward shift of C 3 and, in Case 2, to a shift of C 1 to the right. Hence Q * will increase (this is not necessarily true if Assumption A does not fulfil).

5.4 Impatient agents become less impatient: an increase in β l

Now, let us consider an increase in β l , which means that impatient agents become less impatient. The effect on Q * will depend on whether the median consumer is impatient or patient, what we referred to as Case 1 and Case 2, respectively.

In the case where the median voter is impatient (Case 1, β im = β l ), then the two regimes must be considered.

• under Zero-Maintenance Equilibrium (Regime 1), a small increase in β l does not change k * , w * , Lf (k * ) or P * . It neither changes Q * . This case results in a shift of C 1 to the right, as illustrated in Fig. 3. Still, if the increase in β l becomes large enough, then the economy switches to Regime 2;

• under Positive-Maintenance Equilibrium (Regime 2), a small increase in β l does not change k * , w * , Lf (k * ) or P * , but it does increase Q * , as illustrated in Fig. 3.

In the case where the median voter is patient (Case 2, β im = β h ), then it is clear that changing β l has no effect on Q * .

6 Debt-financed versus tax-financed maintenance policy

We now turn to the analysis of some alternative policy scenarios. Up to now we assumed that the maintenance expenditure was financed by a a pay-asyou-go tax τ t . Such a scheme is called tax-finance. A debt-finance scheme would mean that the government can also issue public bonds to finance its expenditure. It is of interest for our approach since heterogenous households are likely to be hit differently by the taxes needed to finance public debt and by the interest earned on public bonds. The median voter could thus be changed in this alternative scenario. On the side of the government, financing environmental maitenance to a lesser extent by taxes may be a way

+ + 3 + 2 Q + 1 Regime 1 + 1 Regime 2
Figure 3: Impatient agents become less impatient to increase acceptability of its abatement policy. Moreover, the introduction of public debt in our infinitely-lived agent model has no impact on the equilibrium steady state capital intensity, so that we can focus on its impact on environmental quality.

In this section we shall assume that the government can both raise the voted taxe τ t and issue new one-period public bonds d t+1 to finance maintenance m t . As a result, an additional expenses appears in its budget constraint, namely the repayment of interests and principal of public bonds. It is also assumed that public bonds and physical capital are perfect substitute and bear the same interest rate r t . Let d t ≥ 0 be the per capita public debt and τ t ≥ 0 be the lump-sum tax at time t. These must satisfy the following government budget constraint:

τ t + d t+1 = m t + (1 + r t )d t .
The budget constraint of a consumer (4) now becomes:

c t + s t + τ t ≤ w t + (1 + r t )s t-1 , s t ≥ 0.
One can easily modify the definitions of competitive equilibrium path for this case. The only thing deserving attention is that condition 3 (equilibrium on the capital market) now becomes

L i=1 s i * t-1 = L(k * t + d t ), t = 0, 1, . . . .
Suppose that public debt is constant over time, d t = d, t = 0, 1, . . .. Then we can naturally define competitive steady-state equilibrium. Consider such an equilibrium, (m * , E m * ), where E m * = {k * , 1 + r * , w * , (s i * , c i * ) L i=1 , P * , Q * }. As in [START_REF] Mankiw | The savers-spenders theory of fiscal policy[END_REF], government debt does not affect the steady-state capital stock and national income. Namely, as in the case with no government debt,

β h = 1 1 + r * , 1 + r * = f ′ (k * ), w * = f (k * ) -f ′ (k * )k * .
At the same time, government debt does influence the distribution of income. A higher level of debt means a higher level of taxation to pay for the interest payments on the debt. The taxes fall on both patient and impatient consumers, but the interest payments go entirely to the patient consumers because only patient consumers save in a steady-state equilibrium.

In the steady-state equilibrium the budget constraint of the government becomes

τ t + d = m * + (1 + r * )d.
Hence, τ t = τ (d), t = 0, 1, . . . , where

τ (d) = m * + r * d.
Therefore, the budget constraint of a consumer in the steady-state equilibrium is as follows:

c t + s t ≤ w * -τ (d) + (1 + r * )s t-1 , s t ≥ 0.
If the median voter is impatient, in a steady-state equilibrium we have s im * = 0 and hence c im * + m * = w * -r * d.

Therefore, for the median voter, an increase in d is practically equivalent to a decrease in the post-tax wage rate. It follows that in the case where maintenance is positive, m * > 0, if the majority of agents is impatient, an increase in public debt unambiguously leads to a decrease in maintenance and environmental quality in the voting steady-state equilibrium.

If the median voter is patient, in a steady state the savings of the median voter, s im * , are not determined uniquely and hence a change in d will have an indeterminate effect on the savings of the median voter. Let us assume that the ratio s im * /( L i=1 s i * ) does not change. Since, in equilibrium, ( L i=1 s i * )/L = k * + d, this implies that the ratio γ = s im * /(k * + d), which shows the proportion between the median and the mean savings, stays unchanged. Under this assumption, the parameter γ plays the crucial role, because in this case in a steady-state voting equilibrium we have c im * + m * = w * + r * s im * -r * d = w * + r * (γk * + (γ -1)d).

It is clear that an increase in d leads to a decrease in c im * + m * , if γ < 1, and to an increase in c im * + m * , if γ > 1.

Thus, in the case where maintenance is positive, m * > 0, if the median savings and income are lower than the mean (γ < 1), an increase in public debt leads to a decrease in maintenance and environmental quality and if the median savings and income are higher than the mean (γ > 1), an increase in public debt results in an increase in maintenance and environmental quality. As noticed above, the case where the median savings and income are lower than the mean is usually considered as common.

Conclusion

In this paper, we assume that the population is exogenously divided into two groups: one with patient households and the other with impatient households. The environmental maintenance is voted by the households. We introduce the notion of voting equilibrium, look for steady state voting equilibria and find that for them the median voter theorem applies. If the majority of households is impatient the equilibrium levels of maintenance and environmental quality is determined uniquely, but if the majority of households is patient, there can be a continuum of these.

We fulfil comparative statics analysis for steady state voting equilibria and show that (i) an increase in total factor productivity may produce effects described by the Environmental Kuznets Curve, (ii) an increase in the patience of impatient households may improve the environmental quality if the median voter is impatient and maintenance positive, (iii) in the case where the median voter is patient and maintenance is positive, if the median income is lower than the mean, a decrease in inequality can lead to an increase in the environmental quality .

We also compare our model with a representative agent economy which is identified with the particular case of our model where all consumers are patient and savings are distributed evenly across agents. In the case of impatient median voter, the level of environmental quality predicted by our model is lower than the one predicted by a representative agent economy. The same holds true if the median voter is patient but the median income lower that the mean, which is the common case.

Finally, some policy implications of our model are discussed. In this purpose we introduce public debt as an alternative source of financing environmental maintenance. We show that, if the median income is lower than the mean, then an increase in public debt leads to a lower environmental quality in the long run. c t + s t ≤ (w * -m) + (1 + r * )s t-1 , s i -1 = s i * , c t ≥ 0, s t ≥ 0, and to refer to [START_REF] Becker | On the long-run steady-state in a simple dynamic model of equilibrium with heterogeneous households[END_REF][START_REF] Becker | Equilibrium dynamics with many agents[END_REF].

A.2 Proof of Lemma 1

We have:

∂V i,0 (s i * , Q * , m * ) ∂m * 0 = ∂Λ i,0 (Q * , m * ) ∂m * 0 + ∂Γ i,t (s i * , m * ) ∂m * 0 ,
where the functions Λ i,0 and Γ i,0 are defined as follows:

Λ i,0 (Q 0 , m * ) = max (Qt) ∞ t=1 { ∞ t=0 β t i v(Q t ) | µΦ(Q t+1 ) ≤ µ(Q t -P * ) + Lm * t , Q t+1 ≥ 0, t = 0, 1, . . .}, Γ i,0 (s -1 , m * ) = max (ct) ∞ t=0 ,(st) ∞ t=0 { ∞ t=0 β t i u(c t )
| c t + s t + m * t ≤ w * + (1 + r * )s t-1 , c t ≥ 0, s t ≥ 0, t = 0, 1, . . .}.

It is not difficult to check that

∂Λ i,0 (Q * , m * t ) ∂m * t = β i Lv ′ (Q * ) µ(Φ ′ (Q * ) -β i ) and ∂Γ i,0 (s i * , m * t ) ∂m * t = -u ′ (c * ).
Therefore,

∂V i,0 (s i * , Q * , m * ) ∂m * t = β i Lv ′ (Q * ) µ(Φ ′ (Q * ) -β i ) -u ′ (c * ),
which implies (21).

  a steady-state equilibrium constructed at the maintenance policy m * = (m * 0 , m * 1 , ...), m * t = m * , t = 0, 1, .... Let E m * be an equilibrium path corresponding to E m * . Definition 5. Steady state voting equilibrium We call the couple (m * , E m * ) a steady state voting equilibrium if the couple (m * , E m * ) is an intertemporal voting equilibrium path.

Figure 2 :

 2 Figure 2: An increase in total factor productivity in Regime 1 (Left) and Regime 2 (Right)

For a general survey of the literature on models of economic growth with consumers having different discount factors, see[START_REF] Becker | Equilibrium dynamics with many agents[END_REF].

Recently this debate has experienced a strong revival after the publication of the Stern Review[START_REF] Stern | The Stern Review of The Economics of Climate Change[END_REF][START_REF] Stern | The economics of climate change[END_REF]. Prominent economists have contributed to the debate, like[START_REF] Dasgupta | Discounting climate change[END_REF],[START_REF] Nordhaus | A review of the Stern Review on the economics of climate change[END_REF] or[START_REF] Weitzman | A review of the Stern Review on the economics of climate change[END_REF].

Or the social evaluator, to take Dasgupta's words.

More formally, we can put the set of households in an order such that, if β i < β j and if s i * < s j * , then i precedes j. Such an order exists because the impatient consumers do not save in a steady-state equilibrium. Now take the household median in the sense of the introduced order, i m .

Note that this is different from the question raised by[START_REF] Caselli | A Representative Consumer Theory of Distribution[END_REF] :under which condition does a model with heterogenous agents "admits" a representative agent model, namely a model with homogenous agents displaying the same aggregate and

Part of this research was conducted during several short visits of K. Borissov at the Université Lille as an invited professor during 2007 and 2010. K. Borissov was also visitor at CORE in 2009. He is grateful to the Russian Foundation for Basic Research (grant No. 08-06-00423) and Exxon Mobil for financial support. The paper was also finalized while Th. Bréchet was visiting research fellow at the Grantham Institute for Climate Change at Imperial College London, and visiting professor at the European University at St Petersburg, Russia.

A Appendices

A.1 Proof of Proposition 1

It is sufficient to notice that since in a steady-state equilibrium we have

and for each i, the sequence

given by si

A.3 Proof of Lemma 2

Using a traditional argument (see e.g. [START_REF] Mckenzie | Optimal economic growth, turnpike theorems and comparative dynamics[END_REF]) we can prove that a sequence (s t-1 , ct , mt , Qt ) ∞ t=0 given by ( 22) is a steady-state solution to problem P 2 if and only if there exist q and p such that for

the following relationships hold:

The existence of such q and p is equivalent to conditions (23)-( 24).


Julien Heulot
email: jheulot@insa-rennes.fr

Jani Boutellier
email: jani.boutellier@ee.oulu.fi

Maxime Pelcat
email: mpelcat@insa-rennes.fr

Jean-Franc ¸ois Nezan
email: jnezan@insa-rennes.fr

Slaheddine Aridhi
email: saridhi@ti.com

Applying the Adaptive Hybrid Flow-Shop Scheduling Method to Schedule a 3GPP LTE Physical Layer Algorithm onto Many-Core Digital Signal Processors

Currently, Multicore Digital Signal Processor (DSP) platforms are commonly used in telecommunications baseband processing. In the next few years, high performance DSPs are likely to combine many more DSP cores for signal processing with some General-Purpose Processor (GPP) cores for application control. As the number of cores increases in new DSP platform designs, scheduling of applications is becoming a complex operation. Meanwhile, the variability of the scheduled applications also tends to increase as applications become more sophisticated. Such variations require runtime adaptivity of application scheduling. This paper extends the previous work on adaptive scheduling by using the Hybrid Flow-Shop (HFS) scheduling method, which enables the device architecture to be modeled as a pipeline of Processing Elements (PEs) with multiple alternate PEs for each pipeline stage. HFS scheduling is applied to the scheduling of 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) telecommunication standard Uplink Physical Layer data processing (PUSCH).

The experiments, conducted on an ARM Cortex-A9 GPP, show that an HFS scheduling algorithm has an overhead that increases very slowly with the number of PEs. This makes the method suitable for executing the adaptive scheduling in less than 1 ms for the 501 actors of a LTE PUSCH dataflow description executed on a 256-core architecture.

I. INTRODUCTION

Today, multicore Digital Signal Processor (DSP) platforms are commonly used in signal processing, such as baseband processing in telecommunications and multimedia applications. Although the use of multi-core processors is widespread, the system-level complexity of the platforms causes myriad problems which still remain unsolved.

Computationally, the most powerful multi-core DSP platforms (Texas Instruments TMS320C6678 and Freescale P4080 for instance) currently comprise up to 8 DSP cores. The next generation DSP TMS320TCI6636 from Texas Instruments will combine a 4-core ARM Cortex-A15 General-Purpose Processor (GPP) and 8 c66x DSP cores. Combining GPP cores dedicated to control-oriented operations and application This work was supported by the ANR COMPA project scheduling and DSP cores dedicated to signal processing may become a typical internal architecture for computationally powerful DSP processors. Moreover, if the current trend to integrate increasingly more cores in processors continues [START_REF]Kalray MPPA[END_REF], many-core DSP processors, comprising a few GPP cores and many powerful DSP cores, made possible by higher integration density may prevail in a few years over other DSP processors.

Two major issues in multiprocessing are a) the nature of the interconnect topology [START_REF] Karam | Trends in Multicore DSP Platforms[END_REF] and b) the scheduling and synchronization of computations. In fact, these two issues can not be separated from each other, as the interconnect dictates the nature of the scheduling approach. In this paper, the term Processing Element (PE) is used to refer to either a DSP core or a dedicated co-processor.

Pipelined interconnects and their scheduling are of high relevance in DSP and multimedia applications [START_REF] Sriram | Embedded Multiprocessors: Scheduling and Synchronization[END_REF]Page 124]. An example of pipelined interconnects can be seen in Figure 1. Figure 1 a) depicts a classical pipeline with three stages, each consisting of one PE. Figure 1 b) depicts a slightly more complex pipeline where the second stage has two PEs (#2 and #3) that can process data concurrently.

In the Hybrid Flow-Shop (HFS) scheduling method [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF], used in the proposed methodology, the target architecture is modeled as in Figure 1 b). For multi-core architectures that allow bidirectional (isotropic) inter-processor communication, the HFS scheduling method restricts communication to fixed, unidirectional links. This dramatically reduces the complexity of adaptive scheduling and makes the overhead of scheduling up to 256 PEs manageable (Section V).

It has been shown previously [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF] that the highly dynamic nature of the Uplink Physical Layer data processing (PUSCH) decoding algorithm executed in 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) base stations does not allow the use of static multiprocessor schedules; fast adaptive scheduling is mandatory. [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF] used a list scheduling method to schedule 3GPP LTE PUSCH decoding on a multicore DSP. This method is not applicable to many-core adaptive scheduling (with hundreds of PEs), as 1/9 of the computation is dedicated to scheduling which involves 8 PEs. In this paper, we propose a method based on HFS scheduling to adaptively schedule the 3GPP LTE PUSCH algorithm onto many-core architectures. We show that HFS scheduling can be applied to schedule applications on pipelines of processors that have parallel PEs at arbitrary stages. As an application example we show how the 3GPP LTE telecommunication standard PUSCH can be modeled as an HFS scheduling problem and that the simplifying assumptions of HFS scheduling enable the fast computation of an efficient many-core schedule.

The adaptive scheduling of classical pipelines (as in Figure 1 a)) has been previously studied [START_REF] Boutellier | Low-overhead run-time scheduling for fine-grained acceleration of signal processing systems[END_REF], [START_REF] Boutellier | Quasi-static scheduling for fine-grained embedded multiprocessing[END_REF], whereas the more complex hybrid case containing stages with parallel PEs (as in Figure 1 b)) is still largely unexplored in the context of signal processing. This paper is formulated as follows: Section II discusses work related to the topics discussed in this publication; Section III presents the PUSCH application; Section IV shows how the PUSCH application can be modeled as an HFS scheduling problem; Section V shows experimental results on scheduling of 3GPP LTE PUSCH and Section VI concludes the paper.

II. RELATED WORK

The use and scheduling of PE pipelines in signal processing has been previously studied. In [START_REF] Boutellier | Low-overhead run-time scheduling for fine-grained acceleration of signal processing systems[END_REF], MPEG-4 macroblock decoding was modeled as a classical flow-shop scheduling problem and [START_REF] Boutellier | Quasi-static scheduling for fine-grained embedded multiprocessing[END_REF] extended the study to consider various intermediate buffers between the pipeline stages.

The scheduling of the 3GPP LTE PUSCH decoding process has previously been discussed in the work of Pelcat et al. [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF]. In this work it was shown that static scheduling of PUSCH is unfeasible and that an adaptive scheduler is necessary. The applied list scheduling method provided very high-quality schedules, but the context of [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF] was different to this work, as the assumed platform was isotropic and the resulting communications were not restricted in their direction.

The review article of Ruiz et al. [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF] gives an overview of available methods for solving HFS scheduling problems. However, only a small minority of these are applicable to the problem at hand, as task graphs that depict DSP algorithms (such as PUSCH) generally have precedence constraints. Finally, as our context is the adaptive scheduling of pipelined PEs, none of the presented solutions in [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF] are suitable due to their complexity or restricted applicability.

[3, Page 129] lists several approaches for compile-time mapping of DSP algorithms to pipelined multiprocessors. Due to the dynamic nature of the LTE PUSCH decoding process, these approaches are not applicable.

III. 3GPP LTE PUSCH PROCESSING

The 3GPP telecommunication standards, GSM and 3G, are used by billions of people over the world. The 3GPP LTE telecommunication standard improves the peak data rates in downlink to more than 100Mbit/s and peak uplink data rates to over 50Mbit/s. Theoretically, up to one hundred simultaneous users can share this available bandwidth.

The high performance is acquired by advanced techniques of Multiple Input Multiple Output (MIMO), Orthogonal Frequency-Division Multiple Access (OFDMA) in the downlink and Single-Carrier Frequency-Division Multiple Access (SC-FDMA) in the uplink processing [START_REF] Sesia | The UMTS Long Term Evolution: From Theory to Practice[END_REF]. These techniques must be implemented both in the physical layer of LTE base stations (which are also known as eNodeB) and in the User Equipment (UE) such as cell phones.

The use of these complex techniques in variable conditions requires high adaptivity from the processing platform. To maintain the real-time, power-efficiency and versatility requirements of the LTE physical layer processing, multi-core DSPs with hardware coprocessors are the platform of choice. However, the scheduling and synchronization of the physical layer processing on a multiprocessor platform is a considerable challenge. The physical layer decoding operation [START_REF] Sesia | The UMTS Long Term Evolution: From Theory to Practice[END_REF] can be roughly divided in two parts as shown in Figure 2 : 1) The static part: The Cyclic Prefix (CP) is removed, the symbols are converted into frequency domain by a Fast Fourier Transform (FFT) and equalized using channel estimation on received reference signals. The subcarriers are then reordered and, finally, an Inverse Discrete Fourier Transform (IDFT) reconverts the data back into the time domain per user basis.

A. PUSCH Processing Stages

2) The dynamic part: constellation demapping and bit processing. For these operations, the parameters are highly variable during runtime (number of connected UEs, number of allocated Code Blocks (CBs), modulation order, and so on). The multi-core scheduling of this dynamic part must be adaptive [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF]. A detailed graph description of this part is shown in Section III-B.

The first (static) part of processing can be represented as a Synchronous Dataflow graph (SDF [START_REF] Sriram | Embedded Multiprocessors: Scheduling and Synchronization[END_REF]) and represents a high level of parallelism. Consequently, a design tool can efficiently parallelize these operations at compile time. However, for the second (dynamic) part, the multi-core scheduling needs to be adapted to the varying parameters.

The LTE uplink physical layer bandwidth may vary between 1.4 MHz and 20 MHz. In the most complex case of 20MHz, the base station (eNodeB) Medium Access Control (MAC) scheduler can assign resources to about 20 dynamically allocated users and 30 Voice over LTE users (VoLTE) semipersistently. This translates to 50 variable size CBs, associated with these 50 UEs , being transmitted every millisecond. Given the number of UEs and their CB sizes, the dynamic part of PUSCH needs also to be rescheduled onto the multicore architecture every millisecond. The next section explains the model used to represent the dynamic part of the PUSCH algorithm.

B. Dataflow Description of the LTE PUSCH Decoding Dynamic Part

In order to schedule the decoding of one LTE PUSCH subframe every millisecond, a parameterized model of the algorithm is required. Dataflow has proven to be an efficient representation for signal processing applications [START_REF] Sriram | Embedded Multiprocessors: Scheduling and Synchronization[END_REF].

The vertices of dataflow graphs are known as actors. Actors consume data tokens on their input edges, process the data and produce result tokens on their output edges. Data between actors are exchanged exclusively via edges, representing First In, First Out data queues (FIFOs). An actor fires (executes) as long as there is data to consume on its input edges.

The graph model used to represent the dynamic part of LTE PUSCH is the Parameterized Cyclo-Static Directed Acyclic Graph (PCSDAG) [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF]. Rather than a new model, it is a subset of the Cyclo Static Dataflow Model (CSDF [START_REF] Bilsen | Cyclostatic data flow[END_REF]) parameterized obeying the semantics of [START_REF] Bhattacharya | Parameterized dataflow modeling for DSP systems[END_REF]. It has two main advantages:

• As a subset of CSDF, it can compactly model an algorithm with complex production or consumption patterns. This is the case of the current PUSCH algorithm because the size of the CB assigned to each user varies greatly, both in time and between users.

• The simplifications enable a fast computation of actor repetitions gathered in a repetition vector. A new graph called single rate Directed Acyclic Graph (srDAG) can then be generated, duplicating actors by their repetition factors.

Both data token production and consumption of each PCSDAG edge is set by the MAC scheduler based on UE time and frequency scheduling. Figure 3 shows a simplified view of the LTE PUSCH PCSDAG description. The shape of the graph depends on the following parameters:

• the current number of UEs: nb UE,

• A pattern of parameters giving the number of CBs allocated in each 1ms subframe to each UE: nb CB = {CBs UE1, CBs UE2, CBs UE3...}. This pattern has a maximum length of 50.

Other parameters influence the Deterministic Actor Execution Time (DAET) of each actor, i.e. the time needed to execute each LTE PUSCH actor on each processing element. Pattern parameters are shown in parentheses in Figure 3. The init phase is executed at system initialization while subinit phase is executed for each 1 ms subframe. Ignoring the effect of PCSDAG graph parameters on DAETs, the number of possible graph configurations is shown to be over 190 million [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF]. Taking into account the DAET modifications, the number of possible graphs is even higher; thus is not suitable to precompute and store schedules.

In the next section we show how the PCSDAG formulation can be transformed into a HFS scheduling problem, and we present a PE pipeline-targeting scheduling approach that is sufficiently fast given the constraint of the 1 ms time frame for scheduling the PUSCH algorithm. Dataflow actors are converted into flow-shop tasks. This transformation is illustrated in Figure 3 where actors are converted into tasks t i .

IV. PROPOSED SOLUTION

The origins of the flow-shop scheduling problem formulation are in factory production lines where multiple production machines work in parallel and products move from one machine to another as they are assembled. The flowshop scheduling problem involves the processing of N jobs on M machines. In the classical flow-shop formulation each job consists of a set of operations, so that each operation has to be processed on exactly one machine. Due to our context, we shall name the machines as PEs and operations as tasks.

In the classical flow-shop formulation it is assumed that tasks have deterministic execution timings. This constraint is respected in our study case as we suppose each actor to have a DAET. Each job must pass through the PEs in a prescribed order, although it is possible for individual tasks to skip PEs. We assume that the optimization objective of the flow-shop problem is makespan minimization instead of other possible scheduling objectives. This is compatible with LTE constraints.

The HFS scheduling method changes the setting by allowing several PEs to process one type of task [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF]. Figure 4 a) shows an application that consists of three tasks, t This little task graph represents a flow-shop job. The job exists in three instances: J a , J b and J c . Figure 4 b) shows the Gantt chart (schedule) when the job instances J a , J b and J c have been scheduled onto the pipelined multiprocessor architecture shown in Figure 1 a). Respectively, Figure 4 c) shows the same jobs scheduled on the pipelined architecture of Figure 1 b), where PE2 and PE3 are both capable of executing task t 2 . Figure 4 highlights the common situation where one kind of task (t 2 , in this case) is computationally more demanding than other tasks in the application and thus forms a bottleneck in the processing pipeline. The classical flow-shop formulation can not represent cases where a long-latency task is distributed to more than one PE, whereas in HFS scheduling method this is no problem. In LTE PUSCH the variance in task execution times is high: on a programmable DSP the individual PCSDAG actors have execution time differences of one order of magnitude [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF].

In this work, some common flow-shop assumptions are used: jobs are processed in every stage in the same order; each task is processed at most by one PE at each pipeline stage; all jobs are available simultaneously before the scheduling starts; tasks pre-emption is not allowed. We also assume that there is enough buffer space between pipeline stages to hold the data during inter-stage communication and that communication times are included to task execution times.

Next, in SubSection IV-A we show how the LTE PUSCH decoding process can be formulated as an HFS scheduling problem and SubSection IV-B describes how schedules are computed out of HFS job sequences.

A. Flow-shop jobs from PCSDAG

The PCSDAG graph is a simple linear graph that is capable of capturing all the variability of the PUSCH algorithm within its parameters. To enable HFS scheduling, the PUSCH PCSDAG graph must be transformed to HFS jobs. The HFS scheduling method requires that every job has only one kind of task for each pipeline stage. In practice, this means that the pipeline mapping of PCSDAG actors affects the transformation from PCSDAG to HFS jobs; the mapping of actors to pipeline stages is the first step in the transformation.

For general many-core platforms that have a full, isotropic interconnection network between PEs, applying HFS scheduling implies that only a subset of the full interconnect needs to be used. Similarly, the PEs that are assigned to computations must be grouped as different pipeline stages.

In the PUSCH algorithm model there are some actors that have very short execution times and which execute only infrequently. As an extension of the base HFS scheduling method, the infrequent actors are mapped to pipeline stages that also execute computationally more burdening actors.

After the assignment of actors to pipeline stages, jobs can be extracted from the PCSDAG graph. The PCSDAG graph has a basis repetition vector that expresses how many times each PCSDAG actor is to be executed. As described in [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF], the PCSDAG graph is transformed into a srDAG graph in which each vertex represents one HFS task instance. Figure 5 shows the transformation from a) PCSDAG to b) srDAG and finally to jobs, considering the 5-stage pipeline with 7 PEs in c).

In Figure 5 It is important to notice that the HFS jobs generated from the PCSDAG are not independent, as the case commonly is in the HFS scenario [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF]. Looking at Figure 5, it must be kept in mind that the causality relationships between the srDAG actors still hold for the HFS jobs. Practically this means that the scheduling order of jobs is restricted somewhat.

B. HFS scheduling

After the set of jobs, J i , i ∈ [1, N], has been defined and has been mapped to pipeline stages P j , j ∈ [1, M], the actual HFS scheduling can be conducted. In classical flowshop the scheduling consists of two phases: 1) job ordering and 2) timetabling [START_REF] Boutellier | Low-overhead run-time scheduling for fine-grained acceleration of signal processing systems[END_REF]. In HFS scheduling method, one more phase is added, which makes the sequence 1) job ordering, 2) assignment and 3) timetabling.

The purpose of job ordering is to place the jobs, J i , i ∈ [1, N], to a sequence with the aim of minimizing the makespan of the schedule. Job ordering for HFS scheduling has been studied extensively [START_REF] Ruiz | The hybrid flow shop scheduling problem[END_REF], but generally the ordering strategies are very time-consuming and not appropriate for runtime computations. For small job sets, there are simple job ordering heuristics [START_REF] French | Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop[END_REF], but as the number of jobs increases, the computation time of simple heuristics grows as well.

After job ordering has been conducted, the assignment phase selects the actual processing element P j,k out of the set of PEs in stage P j,k , k ∈ [1, M j ] to which task t m has been assigned. In this work, earliest start assignment was used: at each step, the chosen PE grants the earliest start of the current task.

Timetabling defines when a specific task t i,m job J is allowed to start on a pre-defined pipeline stage j [START_REF] French | Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop[END_REF]. In semi-active timetabling, each task t i,m is started when both the previous task on the same PE has finished and the previous task of the same job t i,m-1 has finished. In no-wait timetabling each task (t i,m ) within one job J is started immediately after the previous task (t i,m-1 ) of the same job has finished. Figure 6 shows the difference of semi-active timetabling and no-wait timetabling in Gantt-charts.

Figure 7 shows the multi-core HFS scheduling of the example in Figure 5. The pipeline shape of the schedule is already visible for this small number of actors.

V. EXPERIMENTAL RESULTS

The trend of computationally efficient DSPs in the next few years is likely to consist of combining GPP cores for control and scheduling with many DSP cores for signal processing. In this context, experimental results will focus on the comparison between list scheduling and HFS scheduling. Results have been acquired by scheduling a dataflow description of LTE PUSCH decoding for a many-core DSP on an ARM Cortex-A9 GPP processor. Experiments study the evolution of simulated makespan and adaptive scheduling time when PE count increases.

The timetabling approach used was semi-active. No-wait timetabling was also trialled, and produced almost identical makespans as semi-active timetabling. In the classical flowshop situation no-wait timetabling has the additional benefit of minimizing the buffer space requirements between PEs [START_REF] French | Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop[END_REF]. However, for HFS scheduling with jobs that have precedence constraints, the opposite is true. For this reason, no-wait timetabling was excluded from the present experiments.

A. Experiment Assumptions and Setup

Accordingly to Section III-B, the PUSCH algorithm comprises of two variable parameters. The first is the number of UEs and the second is the number of Resource Blocks (RBs) allocated to each UE. For the LTE 20 MHz system, the total number of RBs available is 100. In the presented results, the number of UEs is set to 50, so the number of RBs per UE will vary between 1 and 3, giving a total of 100 RBs for all users. Because of the high number of users and the small resource block allocation per user, there will be just one CB per UE. This scenario results in a total of 50 CBs and illustrates one of the worst LTE PUSCH scheduling cases.

The hardware platform contains a dual-core ARM Cortex-A9 processor with a clock frequency of up to 1 GHz. The experimental adaptive scheduler is written in C++ and runs as a Linux mono-threaded task on the ARM processor. The embedded Cycle Counter (CCNT) provides accurate cycle measurements.

In order to compare schedules, tasks need to have known durations. Timing measurements used in this paper are based on a Texas Instrument c64x+ DSP. These timings do not limit the study, as the paper goal is to compare scheduling algorithms rather than publishing absolute schedule timings. Communication times between PEs are assumed to be part of the task timings. The simulated platform is thus a homogeneous many-core platform with cores equivalent to c64x+ DSPs.

Two metrics are used to compare adaptive scheduling heuristics:

Makespan: The time difference between the start and the end of a given application graph execution. This is also known as latency.

Scheduling Overhead: The time necessary on the target platform to compute the adaptive scheduling algorithm, from acquiring PUSCH parameters to actor timetabling. As this time is not dedicated to signal processing, its minimization is necessary.

B. Results

Results on makespan (Figure 8) compare both list and HFS scheduling algorithms to Greedy Scheduling Theorem (GST) algorithm [START_REF] Leiserson | A minicourse on dynamic multithreaded algorithms[END_REF]. GST curve gives an idea of the speedup that can be obtained with greedy scheduling, no actor timing knowledge and a fully-connected isotropic architecture with infinite communication rates [START_REF] Pelcat | Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach for LTE eNodeB[END_REF].

In the test case, the algorithm critical path limits possible speedup to about 50 times. We see that list scheduling produces better speedup than HFS scheduling. List scheduling reaches critical path length limitation as soon as 50 PEs are available. On average, the makespan generated by HFS scheduling is 31% longer than that generated by list scheduling. The limitation of HFS scheduling in terms of makespan is due to its The main advantage of HFS method is that its scheduling overhead (Figure 9) is increasing very slowly with the number of PEs, making the HFS method a good solution for many-core adaptive scheduling. This is not the case for a list scheduler whose scheduling overhead increases significantly with the number of PEs. In Figure 9, it may be seen that the HFS scheduler is faster once 17 PEs (or more) are available on the architecture. For fewer than 17 PEs, the time needed to construct HFS jobs makes HFS scheduling more costly than list scheduling.

If we look at Figure 10, we can see that the HFS scheduling overhead is divided into srDAG and job transformations that do not depend on the number of PEs and mapping and scheduling that do depend on the number of PEs.

We may conclude from our experiments that the HFS method has a very low scheduling overhead compared to the optimized list scheduling method when for higher PE count. HFS scheduling presupposes pipelined PEs and orientates inter-PE communications, simplifying PE assignment when compared to the general isotropic and fully-connected architecture case. It also groups computing tasks into linear jobs, simplifying task scheduling while maintaining task precedence.

For the case of 256 PEs and for all LTE PUSCH configurations, the HFS method has a scheduling overhead under 1 Mcycles. This makes HFS scheduling suitable for realtime adaptive scheduling of studied LTE PUSCH worst case (comprising 501 actor instances) onto a 256-core architecture.

VI. CONCLUSION

In this paper, the HFS scheduling method was used to schedule the 3GPP LTE telecommunication standard PUSCH. The experiments demonstrated that a HFS scheduling algorithm on an embedded GPP has a very low computational scheduling overhead making the method suitable for adaptive scheduling of the LTE PUSCH algorithm onto manycore architectures. Moreover, the speedup degradation of the generated many-core schedule is limited when compared to the makespan produced by the more costly list scheduling.

Besides producing low computational scheduling overhead, the HFS formulation additionally simplifies the inter-processor communication requirements on a many-core system. Whilst list scheduling requires a fully connected, bidirectional processor interconnection network, HFS scheduling thrives with a considerably smaller number of unidirectional inter-processor links.

We have extended the previous work of applying flowshop scheduling to signal processing algorithms using HFS scheduling. HFS scheduling extends flow-shop scheduling by allowing each pipeline stage to have more than one PE, thus enabling pipeline balancing and makespan optimization. Experimental results show that HFS scheduling is a suitable method to schedule the worst case of the LTE PUSCH algorithm onto a 256-core architecture.

Directions for future work include evaluating the HFS scheduling on other applications to assess its capacity to schedule efficiently a wide range of applications.

Fig. 1 .

 1 Fig. 1. Three stage pipelines with a) one PE per stage, b) one or more PEs per stage.

Fig. 2 .

 2 Fig.2. PUSCH high level processing chain: static and dynamic parts.

Fig. 4 .

 4 Fig. 4. a) 3 instances of one job J consisting of three tasks. b) Instances of J scheduled on architecture shown in Figure 1 a). c) Instances of J scheduled on architecture shown in Figure 1 b).

P

Fig. 5 .

 5 Fig. 5. a) PCSDAG graph b) Transformation to flow-shop jobs c) Mapping to 7 PEs.

  b), individual job instances are delimited by dashed borders. The algorithm used to create jobs from the srDAG graph is shown in Algorithm 1.

P

Fig. 6 .Fig. 7 .

 67 Fig. 6. a) Semi-active and b) No-wait timetabling for the same set of jobs J a , J b and J c .

Fig. 9 .

 9 Fig. 8. Makespan vs. # of PEs

Fig. 10 .

 10 Fig. 10. Scheduling cost decomposition

  1 , t 2 and t 3 .

		Job J				Job instance J a	t a,1	t a,2	t a,3
	a)	t 1	t 2		t 3	Job instance J b	t b,1	t b,2	t b,3
						Job instance J c	t c,1	t c,2	t c,3
	b)	P 1,1	t a,1	t b,1	t c,1
		P 2,1		t a,2		t b,2		t c,2
		P 3,1				t a,3		t b,3	time t c,3
	c)	P 1,1	t a,1	t b,1	t c,1
		P 2,1		t a,2		t c,2
		P 2,2			t b,2
		P 3,1				t a,3	t b,3	t c,3	time