Vedlegget finnes som vedlegg 2 til hovedrapporten

Alguns autores, tais como Li et al (2015), Xu et al (2012) e Mathirajan et al (2010),

consideram o trabalho de Ikura e Gimple (1986) como um dos primeiros a tratarem do

problema abordado. Os autores consideraram tamanhos idˆenticos e tempo de processa-

mento dos lotes constante, com o objetivo de minimizar o tempo de t´ermino final. Algumas

simplifica¸c˜oes foram assumidas nesse trabalho. A primeira ocorre quando n˜ao s˜ao consi-

deradas datas de entrega, e nesse caso, foi proposto o algoritmo First-Only-Empty, com

o primeiro lote parcialmente vazio e os demais completos, o que resulta em um m´ınimo

n´umero de lotes. A segunda ocorre quando as tarefas s˜ao idˆenticas e, nesse caso, ´e poss´ıvel

atribuir as datas de entrega `as tarefas na ordem em que elas chegam, fazendo com que as

datas de libera¸c˜ao sejam proporcionais `as de entrega (r

h

< r

j

, d

h

< d

j

); para esse caso foi

proposto o algoritmo Greedy-Adjusted-Bunching, que utiliza o procedimento guloso Greedy

Bunching, o qual tenta colocar a m´axima quantidade de tarefas poss´ıvel em um lote, desde

que a data de entrega da pr´oxima tarefa seja atendida.

Glassey e Weng (1991) resolveram um problema real de dimensionamento dinˆamico

de lotes presente na ind´ustria de semicondutores, determinando quando a m´aquina deve

iniciar um novo lote, com o objetivo de minimizar o tempo de espera na fila. O tempo

de processamento foi considerado constante para cada opera¸c˜ao, estando o tempo de

prepara¸c˜ao j´a incluso, e datas de libera¸c˜ao referentes `a chegada dos produtos em lotes

para serem processados foram tamb´em consideradas. O n´umero de itens em cada lote de

chegada ´e constante e a capacidade da m´aquina ´e um m´ultiplo inteiro do n´umero de lotes.

Os autores apresentaram duas abordagens: uma regra em que o in´ıcio do processamento

deve ser aguardado at´e que o n´umero de lotes na fila exceda um certo tamanho; e uma

heur´ıstica que prevˆe o instante de tempo em que lotes chegam no sistema e minimiza o

tempo de espera dos lotes na fila e de lotes que chegar˜ao no futuro. O tempo m´edio de

espera foi investigado em fun¸c˜ao de dois parˆametros: coeficiente de varia¸c˜ao do tempo de

chegada e intensidade do tr´afego.

Lee et al (1992) apresentaram algoritmos baseados em Programa¸c˜ao Dinˆamica (PD)

que minimizam v´arias medidas de desempenho, entre elas o atraso m´aximo e o n´umero

de tarefas em atraso. No caso do atraso m´aximo, assumiram que todos os tempos de

processamento s˜ao iguais e que as datas de libera¸c˜ao e de entrega s˜ao proporcionais.

Avaliaram tamb´em para essa fun¸c˜ao objetivo o caso em que n˜ao h´a datas de libera¸c˜ao e os

tempos de processamento e datas de entrega s˜ao proporcionais. Para quando a finalidade ´e

minimizar o n´umero de tarefas em atraso, foram propostos dois algoritmos: o primeiro com

tempos de processamento das tarefas iguais; o segundo considerando que as tarefas est˜ao

dispon´ıveis no instante de tempo zero, com tempos de processamento e datas de entrega

proporcionais. Al´em disso, propuseram heur´ısticas para o caso de m´aquinas paralelas, com

o objetivo de minimizar o makespan e o m´aximo lateness.

Os problemas de minimiza¸c˜ao do tempo de t´ermino total em uma m´aquina e em

m´aquinas paralelas foram resolvidos por Chandru et al (1993a). Os autores propuseram

um algoritmo Branch-and-Bound (B&B) para o primeiro caso e uma heur´ıstica nomeada

Greedy Ratio para ambos. Li e Lee (1997) abordaram o problema de minimiza¸c˜ao do

atraso m´aximo e de minimiza¸c˜ao do n´umero de tarefas em atraso. Os autores mostraram

que o 1/r

j

, batch/T

max

e o 1/r

j

, batch/P U

j

, com r

h

< r

j

implicando em d

h

< d

j

, s˜ao

problemas do tipo_{N P-dif´ıcil. Quando os tempos de processamento tamb´em s˜ao conside-}

rados proporcionais em conjunto com as datas de libera¸c˜ao e de entrega, pode-se resolvˆe-lo

em tempo polinomial. Foram desenvolvidos para esse caso dois algoritmos baseados em

PD, um para cada fun¸c˜ao objetivo.

Webster e Baker (1995) apresentaram uma vis˜ao geral e propriedades de trˆes vari-

antes do problema de sequenciamento de lotes com datas de libera¸c˜ao distintas, com o

objetivo de minimizar o total dos tempos de fluxo ponderados, como tamb´em de mini-

mizar o m´aximo lateness. O primeiro caso, nomeado sequenciamento de fam´ılias, se refere

ao agrupamento de tarefas pertencentes `a mesma fam´ılia, sendo o setup necess´ario apenas

entre tarefas de fam´ılias distintas. Esse caso n˜ao ser´a descrito neste trabalho por conside-

rar tempos de setup. Outra variante tratada foi o problema de sequenciamento de lotes

com tarefas de tamanhos idˆenticos, tempo de processamento do lote constante e datas de

libera¸c˜ao. Al´em dos objetivos descritos anteriormente, os autores consideraram, para esse

problema, a minimiza¸c˜ao do makespan. Por fim, descreveram o caso em que o tempo de

processamento de um lote ´e o maior dentre os tempos de processamento das tarefas que

fazem parte do mesmo.

Para a minimiza¸c˜ao do total dos tempos de t´ermino ponderados, Uzsoy e Yang

(1997) apresentaram um algoritmo B&B, bem como limites inferiores e condi¸c˜oes de do-

minˆancia. Al´em disso, desenvolveram heur´ısticas para esse problema. A primeira delas

procura manter a m´aquina com uso m´aximo em rela¸c˜ao `a sua capacidade sempre que

houver tarefas em espera para serem processadas. A segunda heur´ıstica ´e baseada no algo-

ritmo proposto por Chandru et al (1993a), com os lotes formados por tarefas consecutivas.

Entretanto, quando consideradas prioridades distintas das tarefas, essa ´ultima propriedade

pode ser violada. Dessa forma, outras heur´ısticas foram propostas para tentar corrigir essa

viola¸c˜ao, as quais geram um lote considerando os demais ainda n˜ao sequenciados.

Hochbaum e Landy (1997) desenvolveram uma heur´ıstica para uma vers˜ao restrita

do problema de minimiza¸c˜ao do somat´orio dos tempos de t´ermino. No problema abordado

pelos autores, referenciado como t-type burn-in, existe um n´umero fixo t de tipos de tarefas,

e os tempos de processamento das tarefas dependem apenas do seu tipo. O problema t-type

burn-in foi tamb´em resolvido em m´aquinas paralelas. Foi provado que este ´ultimo pode

ser resolvido em tempo pseudo-polinomial a partir de um m´etodo exato, ou em tempo

polinomial com uma raz˜ao de pior caso igual `a (1 +

√2)/2. Entende-se por raz˜ao de

pior caso, neste e em outros trabalhos, a raz˜ao entre o resultado da solu¸c˜ao obtida pelo

algoritmo de aproxima¸c˜ao e o resultado de uma solu¸c˜ao ´otima, dada uma mesma instˆancia.

O problema de minimiza¸c˜ao de crit´erios regulares, entendidos como aqueles que

possuem tempos de t´ermino das tarefas crescentes, foi estudado por Brucker et al (1998).

Foram abordados casos em que a capacidade da m´aquina ´e ilimitada, como tamb´em quando

a capacidade ´e limitada. Al´em disso, em alguns destes, s˜ao consideradas datas de venci-

mento. Para quando a capacidade da m´aquina ´e ilimitada, foi proposta uma caracteriza¸c˜ao

de uma classe de sequˆencias ´otimas, com a utiliza¸c˜ao de um algoritmo PD gen´erico para a

resolu¸c˜ao do problema em tempo pseudo-polinomial. Al´em disso, provaram que minimizar

o n´umero ponderado de tarefas em atraso e minimizar a soma dos atrasos ponderados s˜ao

problemas

_{N P-dif´ıceis. Para o caso em que a capacidade ´e limitada, foi proposto um al-}

goritmo de PD para a minimiza¸c˜ao do tempo de t´ermino total, al´em de um algoritmo para

o caso em que o n´umero de tempos de processamento distintos ´e conhecido. Provaram

tamb´em que quando a fun¸c˜ao objetivo ´e baseada nas datas de entrega, o problema ´e tido

comoN P-dif´ıcil. Por fim, mostraram que uma fun¸c˜ao de custo regular arbitr´aria pode ser

minimizada em tempo polinomial para um n´umero fixo de lotes.

Qi e Tu (1999) propuseram um algoritmo baseado de PD de tempo polinomial para o

problema de minimiza¸c˜ao do total de atraso e antecipa¸c˜ao, com o tempo de processamento

por lote constante. Entretanto, segundos os autores, o algoritmo proposto n˜ao apresentou

bom desempenho devido `a quantidade de mem´oria utilizada. Um segundo algoritmo tam-

b´em baseado em PD foi, ent˜ao, desenvolvido, com tempo de resolu¸c˜ao pseudo-polinomial.

Por fim, foi analisado o problema de minimiza¸c˜ao dos atrasos e antecipa¸c˜oes ponderados,

considerando datas de libera¸c˜ao e datas de entrega proporcionais e tarefas com janelas de

tempo referente `as datas de entrega.

O problema de minimiza¸c˜ao do makespan considerando datas de libera¸c˜ao foi tratado

por Lee e Uzsoy (1999). Os autores mostraram que casos especiais desse problema podem

ser resolvidos em tempo polinomial e pseudo-polinomial e propuseram heur´ısticas para o

problema geral abordado. Liu e Yu (2000) mostraram que esse mesmo problema ´e

N P-

dif´ıcil, mesmo quando s˜ao considerados apenas dois poss´ıveis valores de datas de libera¸c˜ao.

Al´em disso, propuseram um algoritmo pseudo-polinomial baseado em PD para quando o

n´umero de datas de libera¸c˜ao ´e conhecido. Desenvolveram tamb´em uma heur´ıstica gulosa

para o problema geral, onde opta-se por sequenciar a tarefa vi´avel de maior tempo de

processamento, respeitando a capacidade da m´aquina na forma¸c˜ao de lotes.

Sung e Choung (2000) analisaram o problema de minimiza¸c˜ao do makespan, tanto

para quando todas as tarefas est˜ao dispon´ıveis para serem processadas no instante de

tempo zero, como tamb´em para quando s˜ao consideradas datas de libera¸c˜ao. Um algo-

ritmo de tempo polinomial foi proposto para o caso inicial; na segunda situa¸c˜ao, foram

identificadas propriedades da solu¸c˜ao, com base nas quais um algoritmo B&B e v´arias

heur´ısticas foram constru´ıdas.

Baptiste (2000) abordou o problema de sequenciamento de lotes com tempo cons-

tante de processamento das tarefas e a existˆencia de datas de libera¸c˜ao. Dois tipos de

m´aquinas de processamento de lotes foram considerados: s_{− batch, com tempo de setup}

constante entre o processamento de lotes; e p_{−batch, sem a existˆencia de tempos de setup.}

O autor mostrou para ambos os casos que, quando utilizadas fun¸c˜oes objetivo ordered ou

que podem ser transformadas nestas, as quais s˜ao, dentre outras caracter´ısticas, fun¸c˜oes

n˜ao decrescentes, o problema pode ser resolvido em tempo polinomial por meio de uma

PD.

Zhang et al (2001a) estudaram o problema de minimiza¸c˜ao do makespan em uma

configura¸c˜ao online, considerando datas de libera¸c˜ao. Diferente da configura¸c˜ao offline

normalmente utilizada, no problema de sequenciamento online, as tarefas chegam ao longo

do tempo e, portanto, o conjunto de tarefas n˜ao ´e conhecido a priori e suas caracter´ısticas

s˜ao fornecidas quando chegam no sistema. Duas situa¸c˜oes foram avaliadas: quando a

capacidade ´e ilimitada; e quando a capacidade ´e limitada e existem apenas dois valores

poss´ıveis de datas de libera¸c˜ao. Os algoritmos propostos para os dois casos possuem a raz˜ao

de pior caso igual `a (√5 + 1)/2. Esses algoritmos foram generalizados para o caso geral,

possuindo uma raz˜ao de pior caso igual `a 2. Por fim, os autores estudaram o problema de

sequenciamento de lotes em m´aquinas paralelas com capacidades ilimitadas.

Um m´etodo considerando datas de libera¸c˜ao para a minimiza¸c˜ao do m´aximo late-

ness foi apresentado por Wang e Uzsoy (2002). Os autores identificaram a possibilidade

de gera¸c˜ao de lotes com datas de entrega vi´aveis dada uma sequˆencia de tarefas, com base

em um algoritmo de PD proposto por Lee et al (1992). Em seguida, apresentaram um

Algoritmo Gen´etico (AG), com a jun¸c˜ao da referida PD com uma codifica¸c˜ao aleat´oria de

chaves proposta por Bean (1994).

Deng et al (2003) descreveram algoritmos para casos especiais do problema de mi-

nimiza¸c˜ao do makespan com datas de libera¸c˜ao, a saber: um algoritmo pseudo-polinomial,

baseado na regra Full Batch Largest Processing Time (FBLPT), proposto por Bartholdi

(1988, apud Deng et al, 2003), para quando o n´umero de datas de libera¸c˜ao ´e conhecido

e todos os dados do problema s˜ao n´umeros inteiros; um esquema de aproxima¸c˜ao para o

caso em que todos os dados n˜ao s˜ao necessariamente n´umeros inteiros; e o caso geral deste

´

ultimo. Al´em disso, consideraram o problema de configura¸c˜ao online, onde as datas de

libera¸c˜ao s˜ao desconhecidas at´e que sejam processadas. Para esse ´ultimo caso, um limite

inferior para a raz˜ao de qualquer algoritmo de aproxima¸c˜ao com capacidade maior que

1 foi apresentado, al´em de ter sido mostrado que esse limite ´e apertado para quando a

capacidade ´e ilimitada.

Poon e Zhang (2004) propuseram v´arios algoritmos para casos especiais a partir

de modifica¸c˜oes em algoritmos dispon´ıveis na literatura baseados em PD, considerando

datas de libera¸c˜ao, com o objetivo de minimizar o makespan. Para o caso em que existe

um n´umero t de valores poss´ıveis de datas de libera¸c˜ao e todos os dados s˜ao n´umeros

inteiros, foi proposto um algoritmo com tempo de execu¸c˜ao O(n(QR

max

)

t−1

(2/t)

t−3

), onde

R

max

´e igual a diferen¸ca entre a maior e a menor data de libera¸c˜ao. Para o caso com

u poss´ıveis valores de tempos de processamento e t datas de libera¸c˜ao, foi proposto um

algoritmo com tempo de execu¸c˜ao da ordem de O(nlogt + u

u+2

_Q

u+1

_t

2

_{logt). Al´em disso,}

foram desenvolvidos algoritmos mais eficientes para quando t = 2 e u = 1. Os autores

apresentaram tamb´em um algoritmo com tempo de execu¸c˜ao O(nlogn) para o problema

com capacidade ilimitada.

Deng et al (2005) desenvolveram esquemas de aproxima¸c˜ao em tempo polinomial

para o problema de minimiza¸c˜ao do tempo total de t´ermino, considerando datas de libera-

¸c˜ao, para os seguintes casos: quando todas as tarefas s˜ao ditas curtas, ou seja, seu tempo

de processamento ´e menor que um determinado limite; quando existe um n´umero pequeno

de tarefas; e quando tarefas de tempos de processamento maiores s˜ao adiadas. M¨onch et al

(2006) abordaram o problema de minimiza¸c˜ao do atraso e antecipa¸c˜ao total, considerando

uma restri¸c˜ao de atraso m´aximo. Os autores apresentaram, para esse problema, v´arias

heur´ısticas de duas fases. Algumas delas n˜ao consideram, na primeira fase, a restri¸c˜ao

de atraso m´aximo permitido, sendo a sequˆencia modificada, se necess´ario, para satisfazer

essa restri¸c˜ao. Tais heur´ısticas s˜ao baseadas em AG e regras de dominˆancia das solu¸c˜oes

´otimas.

O problema de minimiza¸c˜ao do atraso total e do n´umero ponderado de tarefas

em atraso foram abordados por Liu et al (2007), sob a condi¸c˜ao de que os tempos de

processamento e as datas de entrega s˜ao proporcionais. Para quando a fun¸c˜ao objetivo ´e de

minimiza¸c˜ao do atraso total, os autores provaram ser este um problemaN P-dif´ıcil, mesmo

quando a capacidade da m´aquina ´e de apenas duas tarefas, al´em de terem desenvolvido um

algoritmo pseudo-polinomial para um caso especial desse problema. Propuseram tamb´em

um algoritmo pseudo-polinomial para o problema de minimiza¸c˜ao do n´umero ponderado

de tarefas em atraso, tido como

_{N P-dif´ıcil.}

Liu et al (2009) estudaram o problema de minimiza¸c˜ao simultˆanea de dois obje-

tivos, com tempos constantes de processamento das tarefas. Foram propostos neste tra-

balho v´arios algoritmos de tempo polinomial que fornecem solu¸c˜oes ´otimas para diferentes

combina¸c˜oes de objetivos, seja na minimiza¸c˜ao de um objetivo em primeiro lugar, seguido

da minimiza¸c˜ao de um segundo objetivo, ou a partir da considera¸c˜ao de pesos dos dois

objetivos, com a minimiza¸c˜ao da soma ponderada dos mesmos.

Li et al (2009) estudaram o problema de maximizar o n´umero de tarefas antecipadas,

com tempos de processamento iguais a um, configura¸c˜ao online e aquisi¸c˜ao das informa¸c˜oes

antecipada por um determinado intervalo de tempo. Neste trabalho, foi proposto um

algoritmo online guloso com uma melhor raz˜ao de pior caso poss´ıvel, de 1/min_{{n, Q + 1}.}

A partir desta conclus˜ao, os autores mostraram que a capacidade de previs˜ao ´e in´util

quando o intervalo de tempo referente `a previs˜ao ´e menor que 1. Quando esse intervalo ´e

maior ou igual a 1 e menor que 2, foram propostos limites superiores com raz˜ao de pior

caso de 39/100 para quando a capacidade ´e ilimitada e 2/3 para capacidade limitada, al´em

de terem sido desenvolvidos, para esses dois casos, algoritmos online com raz˜ao de pior

caso igual a 1/4 e 1/5, respectivamente.

Cao e Yang (2009) propuseram algoritmos para o problema com datas de libera¸c˜ao e

possibilidade de rejei¸c˜ao das tarefas, com o objetivo de minimizar a soma do makespan das

tarefas aceitas com o total de penalidades das tarefas rejeitadas. No caso em que as tarefas

podem ser rejeitadas, todas elas n˜ao s˜ao obrigatoriamente processadas, sendo considerada

uma penalidade em caso de rejei¸c˜ao de uma tarefa. Os autores apresentaram vers˜oes do

algoritmo FBLPT e algoritmos baseados em PD para o caso geral desse problema, como

tamb´em para quando as tarefas s˜ao ditas curtas, ou seja, seus tempos de processamento

s˜ao inferiores a um determinado limite.

O mesmo problema que o abordado no trabalho anterior foi tratado por Lu et al

(2009). Um algoritmo de tempo polinomial baseado em PD foi proposto para quando

todas as tarefas possuem a mesma data de libera¸c˜ao. Um algoritmo tamb´em baseado em

PD, entretanto de tempo pseudo-polinomial, foi desenvolvido para quando o n´umero de

valores distintos de datas de libera¸c˜ao ´e conhecido. Por fim, foi proposto um algoritmo

de aproxima¸c˜ao e um esquema de aproxima¸c˜ao de tempo polinomial para o caso geral do

referido problema.

He et al (2015) consideraram a possibilidade de rejei¸c˜ao de tarefas e, para quando

a capacidade da m´aquina ´e considerada ilimitada, foram inclu´ıdas datas de libera¸c˜ao.

Inicialmente, os autores abordaram o problema de minimiza¸c˜ao do makespan sujeito a

restri¸c˜ao de que o custo total de rejei¸c˜oes ´e limitado. Em seguida, estudaram o problema

de minimiza¸c˜ao do custo total de rejei¸c˜oes com a restri¸c˜ao de que o makespan deve respeitar

um determinado limite. Para o primeiro caso, foi proposto um algoritmo de aproxima¸c˜ao

para o caso com capacidade finita, como tamb´em para quando a capacidade ´e infinita.

J´a para ambos os casos, foram desenvolvidos algoritmos baseados em PD e esquemas de

aproxima¸c˜ao de tempo polinomial, tanto para quando a capacidade ´e limitada, como para

quando a capacidade ´e ilimitada.

A Tabela 3.1 apresenta de forma resumida os problemas tratados pelos trabalhos

envolvendo tarefas compat´ıveis com tamanhos iguais a uma constante. Para cada tra-

balho, est˜ao indicadas as seguintes informa¸c˜oes na respectiva ordem: a fun¸c˜ao objetivo

do problema desenvolvido; a considera¸c˜ao de datas de libera¸c˜ao indicada por um “x”; a

indica¸c˜ao, quando for o caso, de que os tempos de processamento de cada tarefa s˜ao iguais;

a indica¸c˜ao de que os tempos de processamento dos lotes s˜ao iguais a uma constante; a

configura¸c˜ao do problema classificada como offline ou online; e algumas outras caracte-

r´ısticas consideradas al´em das citadas anteriormente. Observa-se que existe uma grande

heterogeneidade nas variantes abordadas e que muitos dos autores abordam caracter´ısticas

particulares do problema em quest˜ao. Esse fator dificulta a compara¸c˜ao entre os resulta-

dos dos diferentes m´etodos. A partir do exposto nesta se¸c˜ao, percebe-se tamb´em a vasta

variedade de m´etodos empregados para a resolu¸c˜ao dos problemas estudados.

Tabela 3.1: Resumo dos trabalhos com compt, Q < n, s

j

= cte,∀j ∈ J

Fun¸c˜ao Objetivo

arja

apja ap(Bi)a Config.

Outras caracter´ısticas (min) cte cte aOffa aOna

Ikura e Gimple (1986) Cmax x x x r1≤ · · · ≤ rne d1≤ · · · ≤ dn Glassey e Weng (1991) Espera na fila x x x

x x x r1≤ · · · ≤ rne d1≤ · · · ≤ dn Lee et al (1992) Lmax x p1≤ · · · ≤ pne d1≤ · · · ≤ dn x x x Lee et al (1992) PUj x p1≤ · · · ≤ pne d1≤ · · · ≤ dn Chandru et al (1993a) PCj x

Webster e Baker (1995) PwjCj, Lmaxou Cmax x x

r1≤ · · · ≤ rn, p1≤ · · · ≤ pne Li e Lee (1997) TmaxouPUj x x

d1≤ · · · ≤ dn Uzsoy e Yang (1997) PwjCj x

Hochbaum e Landy (1997) PCj x N´umero fixo de tipos de tarefas Brucker et al (1998) Pfj(Cj) x d¯j x x x x x r1≤ · · · ≤ rne d1≤ · · · ≤ dn Qi e Tu (1999) P|Cj− dj| x x Intervalos de dj Qi e Tu (1999) P(αEj+ βTj) x x

Lee e Uzsoy (1999) Cmax x x

x x

Liu e Yu (2000) Cmax

x x #rj= cte

Sung e Choung (2000) Cmax x x Baptiste (2000) Pfj(Cj) x x x

Zhang et al (2001a) Cmax x x #rj= 2 Wang e Uzsoy (2002) Lmax x x

x x

Deng et al (2003) Cmax

x x

Poon e Zhang (2004) Cmax x x

Deng et al (2005) PCj x x

M¨onch et al (2006) P|Cj− dj| x Atraso m´aximo definido Liu et al (2007) PTj x p1≤ · · · ≤ pne d1≤ · · · ≤ dn Liu et al (2007) PwjUj x p1≤ · · · ≤ pne d1≤ · · · ≤ dn Liu et al (2009) Pfj(Cj) ePgj(Cj) x x

Li et al (2009) PEj* x x

Cao e Yang (2009) Cmax+P_J

j∈Rwj x x Possibilidade de rejei¸c˜ao Lu et al (2009) Cmax+PJj∈Rwj x x Possibilidade de rejei¸c˜ao

In document tA' SIMULERINGSRAPPORT FREMTIDIG BANESTRØMFORSYNING PÅ GJØVIKBANEN (sider 77-87)