Será adotada a nomenclatura básica introduzida por Brucker (1998), a qual tem o objetivo de criar uma classificação para os diversos tipos de problemas de escalonamento. A notação é composta por três campos ordenados α β γ , onde o primeiro campo descreve os recursos, o segundo as tarefas e o último o critério de otimização.
3.2.1.1.1 Campo αααα - Recursos
Os tipos mais comuns de recursos em sistemas de manufatura são as máquinas paralelas e as máquinas tipo “shop” (especializadas). No caso das máquinas paralelas as tarefas podem ser completadas por uma única máquina. Para o caso de máquinas do tipo shop, existem tarefas que podem precisar ser executadas em máquinas distintas. As máquinas paralelas não constituem o escopo deste trabalho.
3.2.1.1.1.1 Máquinas Shop (Especializadas)
No sistema de manufatura a ser abordado nesta pesquisa, as máquinas são consideradas como dedicadas, ao invés de paralelas. A organização dessas máquinas nos sistemas produtivos dá-se segundo os três principais modelos descritos na Tabela 3.1 e suas possíveis variações.
Tabela 3.1 - Variações de Máquinas do Tipo Shop.
Tipo Descrição
Flow-Shop (Fm)
No modelo flow-shop (line-transfer), todas as tarefas têm o mesmo número de operações as quais são executadas na mesma ordem, por todas as m máquinas em série. Após a execução em uma máquina, a tarefa entra na fila para execução na próxima máquina. Geralmente as filas seguem a disciplina FIFO (first in
first out);
Open-Shop (Om)
Neste modelo as tarefas também devem ser executadas por todas as m máquinas, entretanto, alguns tempos de execução podem ser nulos. Não existem restrições quanto à ordem das máquinas onde cada uma das tarefas deve passar;
Job-Shop (Jm)
Neste modelo cada uma das tarefas possui um roteiro pré- determinado. O número de máquinas, como nos modelos anteriores também é m. Um tipo especial de job-shop onde uma tarefa pode visitar uma máquina mais do que uma vez, é denominado por recirculação (com a palavra recrc no segundo campo).
3.2.1.1.2 Campo ββββ - Tarefas
Além das características das tarefas mostradas anteriormente como tamanho (tempo de execução), data de disponibilidade e data de término, serão introduzidas aqui outras características bastante comuns, conforme a Tabela 3.2.
Tabela 3.2 - Outras características do campo de tarefas.
Tempo de preparação (setup) da máquina (sjk)
Dadas duas tarefas tj e tk, sjk corresponde ao tempo de
preparação de uma máquina que executou uma tarefa tj e
vai executar uma tarefa tk. Caso este tempo também
dependa da máquina mi em questão, usa-se a notação sijk.
No caso de tj ser a primeira (ou última) tarefa executada na
máquina, o tempo de preparação é denotado por s0j e sj0,
respectivamente.
Relações de precedência (prec) Quando existir, a ordem para a execução das tarefas geralmente é representada por um grafo orientado, onde os vértices correspondem às tarefas e os arcos às relações diretas de precedência. Um arco de uma tarefa tj a uma
tarefa tk faz com que a tarefa tkpossa iniciar sua execução
apenas após o término da tarefa tj. Caso o grafo de
precedência pertença a uma família específica, ao invés de
prec, coloca-se o nome da família no segundo campo. Os mais comuns são: intree, outree, chains, split-compute-
merge, dentre outros.
Tempo de comunicação entre máquinas (cjk)
No caso de precedência entre duas tarefas tj e tk, se a tarefa
tk finaliza a sua execução no instante t na máquina mi, a
tarefa tk não pode iniciar a sua execução antes do instante t,
na mesma máquina mi, ou do instante t + cjk em qualquer
outra máquina.
Interrupção ou preempção (prmp)
Quando é possível interromper uma tarefa, ela não precisa necessariamente terminar na mesma máquina em que começou a sua execução. O tempo de execução utilizado até a interrupção não é perdido. Quando a tarefa volta a uma máquina qualquer, ela só precisa ser executada durante o tempo restante após a última interrupção.
Restrições de escolha de máquina (Mj)
Este item aparece no segundo campo quando a tarefa tj só
No caso de problemas de escalonamento que não se adaptem as variações apresentadas na tabela, pode-se definir novos parâmetros para os campos, desde que a notação de Brucker para os campos recurso, tarefa e critério de otimização sejam respeitados (BRUCKER, 1998).
3.2.1.1.3 Campo γγγγ - Critério de Otimização
Para a definição dos principais critérios de otimização usados em problemas de escalonamento, torna-se necessário denotar o instante em que cada tarefa tj termina a sua execução, sendo este instante normalmente chamado de Cj. Para cada tarefa é
associada uma função de custo fj(Cj). A função de custo total para a maioria dos
critérios de otimização corresponde ao máximo,
max{ fj(Cj) 1 ≤ j ≤ n}, (3.1)
ou a soma de todos os custos,
( )
= n jCj
fj
1 (3.2) O problema de escalonamento consiste em encontrar uma solução que minimize a função de custo total. As funções de custo mais comuns são definidas na Tabela 3.3.Tabela 3.3 - Funções de Custo mais Comuns.
Tipo Descrição
makespan (Cmax) Definido como o instante de tempo em que a última
tarefa é finalizada, Cmax = max{C1,...,Cn}. Neste caso o
critério corresponde ao máximo e as funções fj( ) são
funções identidade.
Tempo total de término
(
Cj)
Definido como a soma dos instantes de término de cada tarefa, = = n j Cj Cj 1
Tempo total de término ponderado
(
ωjCj)
Definido como a soma dos instantes de término de cada tarefa com peso jω ,
= = n j jCj jCj 1 ω ω
Lateness (grau de atraso) Lj = Cj – dj , pode assumir valores negativos
Earliness (grau de
adiantamento)
Ej = max{0, dj – Cj}
Tardiness (grau de atraso
efetivo)
Tj = max{0, Cj – dj}
Penalidade unitária por
atraso > ≤ = dj Cj se dj Cj se
U
j 1 0Da mesma forma que o makespan, definido por max{Cj}, é denotado por Cmax, os
critérios de maximização também são denotados por Lmax, Emax, Tmax e Umax.
Dessa maneira, para o problema de escalonamento de tarefas para as células de manufatura virtuais independentes adotadas neste trabalho, com tempo de execução
pij, relações de precedência arbitradas por grafos de precedência em m máquinas
notação dos três campos α β γ , em que a representação para o problema de escalonamento para a produção proposta para essa pesquisa é dada a seguir, na eq.(3.3), onde o critério de otimização segue uma heurística simples41 resultante da combinação de duas outras regras heurísticas também simples e bem conhecidas dos pesquisadores da área:
Jm | prec;recrc;Pij;Cij;t;di;Sijk;Mi⊂ P | Regra Heurística (3.3)
Portanto, devido ao indeterminismo quanto aos instantes de chegada das tarefas, usar-se-á uma regra heurística combinada para o terceiro campo do problema descrito pela notação da eq.(3.3), e o sistema se baseará em regras de despacho.