Embed Size (px)
Citation preview
UM PROCESSO DE SCHEDULING PARA A PRODUÇÃO DE UM JORNAL
Plácido Rogério Pinheiro Universidade de Fortaleza
Mestrado em Informática Aplicada Av. Washington Soares, 1321 - Bloco J sala 30, CEP: 60811-905, Fortaleza, CE
Ana Karoline Araújo de Castro [email protected]
Gilberto George Conrado de Souza [email protected]
Editora Verdes Mares - Dept. de Informática Praça da Imprensa S/N, CEP: 60135-690, Fortaleza, CE
Resumo
Este trabalho propõe a definição de um modelo para a alocação de recursos, determinando o sequenciamento ótimo de n tarefas em m máquinas, obedecendo ao tempo de entrega das tarefas. Na aplicação deste modelo, é utilizado como estudo de caso, o problema do sequenciamento da impressão dos cadernos de um jornal. Alguns fatores podem influenciar na definição desta sequência. Com base em tais fatores, é então desenvolvido um modelo em Multicritério que auxilia na determinação da prioridade que os cadernos serão impressos. Palavras-chave: Problema de Scheduling, Programação Linear Inteira, Multicritério.
Abstract
This paper proposes a definition of a model for resources allocation, determining the best sequencing of n tasks in m machines, respecting the time that each task needs to be delivered. In the application of this model, the sequencing problem is used as an example, the problem of sequencing the printing of newspapers’ parts. Some factors can influence the definition of this sequence. According to these factors, a Multicriteria model is developed to help determining the priority of the parts to be printed. Keywords: Scheduling Problem, Integer linear programming, Multicriteria.
1206
1. Introdução
De acordo com [MÜLLER, 2002], problemas de sequenciamento existem por toda a parte, sejam os mais triviais, como os encontrados nas áreas de manufatura, transportes ou logística, como outros exemplos não tão evidentes, em áreas como: telecomunicações, alocação de espaços, comerciais e esportes. Muitos destes problemas, têm aplicações práticas bem definidas e, se forem bem resolvidos, os resultados obtidos podem trazer economias substanciais.
A proposta deste trabalho é desenvolver um modelo que sequenciamento de recursos, em programação linear inteira, tendo como base os problemas de cobertura. Aplicá-lo a um problema de alocação de cadernos em um jornal [CASTRO, 2004].
A empresa onde se dá a realização deste estudo é a Editora Verdes Mares, em Fortaleza, no Ceará, fundada em 1981, responsável pela edição do jornal Diário do Nordeste, periódico de maior tiragem do Estado.
Atualmente, a definição da seqüência de impressão dos cadernos é feita de forma empírica, de acordo com o “sentimento” do gerente de produção em conjunto com os funcionários da impressão. Segundo o gerente, o “sentimento” pode ser influenciado pelo atraso da entrega de algum caderno pela redação, pela tiragem do caderno, por uma grande quantidade de páginas coloridas em um determinado caderno. Diante dessa realidade, faz-se necessário um estudo visando auxiliar a área de produção do jornal na tomada de decisão de uma seqüência otimizada da impressão dos cadernos.
Apresenta-se uma abordagem do processo de produção do jornal, dando ênfase à área de impressão, foco principal neste trabalho. O problema de sequenciamento relacionado com a alocação de cadernos é aplicado durante uma semana onde introduz-se a uma abordagem de multicritério, necessária para a construção das escalas de valor a partir de julgamentos semânticos de valor, objetivando resolver o problema de definir a prioridade de impressão dos cadernos. 2. Uma Abordagem do Processo de Produção de um Jornal
Até um jornal ser impresso, ele passa por várias etapas para conseguir o seu objetivo final que é ser entregue todos os dias. Um jornal tem que cumprir vários tipos de entregas: saída do carro que vai para o Sul do Estado (cobrindo todo o interior do Ceará), a entrega via aérea, o jornal que é vendido nas ruas (sejam os gazeteiros, as bancas de revista, estabelecimentos comerciais e etc.) e os assinantes.
Isso tudo é um trabalho feito em conjunto, que reúne várias áreas: programação comercial (os anúncios), redação e área industrial (tratamento de imagens, revelação, gravação, impressão e intercalação). Será dado um foco principal na área de impressão. 2.1 Impressão 2.1.1 Máquinas A impressão do jornal é composta por duas linhas de produção, Linha I (figura 1) e Linha II (figura 2).
1207
Figura 1: Layout da Linha I.
Figura 2: Layout da Linha II.
2.1.2 Funcionários da Impressão
O quadro de funcionários da impressão é composto por: impressor chefe, encarregado de impressão e auxiliares de impressor. Durante a manhã, as máquinas ficam aos cuidados dos funcionários que realizam um trabalho normal de manutenção ou resolvendo algum problema ocasionado nas máquinas durante a impressão do jornal que ocorre durante o final da tarde e à noite.
Os funcionários que ficam alocados durante a impressão do jornal, estão divididos em dois turnos, cada um com 11 funcionários, trabalhando em turnos de 6 horas. 2.1.3 Descrição do Processo de Impressão A redação do jornal precisa obedecer a uma data de entrega do caderno (conforme descrito na tabela 1), para que ele possa ser impresso sem atraso.
1208
Tabela 1: Horário de fechamento da redação.
Depois de ocorrer a liberação através da redação, os cadernos ainda precisam passar pela revelação e gravação, antes de chegar na impressão. Uma descrição detalhada sobre cada um destes processos é mostrada em [CASTRO, 2004].
Quando as chapas chegam na impressão, elas são recebidas por um funcionário que as coloca na máquina dobradora de chapas (duas de suas pontas precisam ser dobradas antes de serem colocadas nas unidades). Após este processo, as chapas que foram dobradas são colocadas em cada uma das unidades. Também tem que ser verificada a questão dos tinteiros. Dependendo da seqüência das rodadas, eles podem ser limpos ou somente enchidos novamente. A limpeza pode ocorrer, por exemplo, caso na rodada anterior tenham sido utilizados tinteiros coloridos e na rodada seguinte sejam necessários tinteiros na cor preta, a limpeza é necessária, leva em média 40 minutos. Caso ocorra o contrário, a limpeza não será necessária. Antes da impressão de cada caderno também precisa ser verificada a passagem do papel. Entre uma rodada e outra esta passagem pode ser feita ou não. Por exemplo, se na rodada anterior tiver sido impresso os classificados na Linha I, na rodada seguinte se for impresso o 1º caderno, a passagem de papel não precisa ser refeita. A partir de todas as informações sobre os tempos de preparação das máquinas, e com os horários de liberação de cada caderno pela redação, é gerado o mapa diário de impressão, contendo a seqüência de execução das tarefas. A seguir será proposto um modelo em programação linear inteira, baseado em problemas de cobertura, que resolva o problema de alocação dos cadernos. 3. Modelo de Sequenciamento 3.1 Problemas de Sequenciamento
Segundo [MÜLLER, 2002], no mundo real, estes recursos: mão de obra, dinheiro, máquina entre outros, são na maioria das vezes restritos ou escassos, deste modo a alocação de recursos determina uma competição entre as tarefas que necessitam deles. As decisões que são tomadas referentes a este tipo de problema, mostram questões puramente combinatórias de como as listas de tarefas devem ser seqüenciadas.
Os problemas de sequenciamento são em geral difíceis de resolver, em virtude da grande explosão combinatória decorrente da necessidade de se verificar as várias alternativas de
HORÁRIOS CADERNOS HORÁRIOS CADERNOS15:00 ZOEIRA/CADERNO 3 15:00 ZOEIRA/TURISMO/AUTOMÓVEL/CADERNO 318:00 REGIONAL/CULTURA/INFANTIL 18:00 REGIONAL20:30 CLASSIFICADOS 20:30 CLASSIFICADOS23:00 NEGÓCIOS 23:00 NEGÓCIOS00:00 1º CADERNO/JOGADA 00:00 1º CADERNO/JOGADA01:00 NOSSA VEZ
HORÁRIOS CADERNOSHORÁRIOS CADERNOS 15:00 ZOEIRA/CADERNO 3
15:00 ZOEIRA/CADERNO 3/VIVA 18:00 REGIONAL/GENTE16:00 EVA 20:30 CLASSIFICADOS18:00 REGIONAL 23:00 NEGÓCIOS20:30 CLASSIFICADOS 00:00 1º CADERNO/JOGADA23:00 NEGÓCIOS00:00 1º CADERNO/JOGADA HORÁRIOS CADERNOS
10:00 NEGÓCIOSHORÁRIOS CADERNOS 14:00 1º CADERNO/JOGADA/ZOEIRA(SEG)
14:00 ZOEIRA(DOM) 15:00 Edição de segunda-feira: CLASSIFICADOS/CADERNO 3/REGIONAL15:00 ZOEIRA/CADERNO 318:00 REGIONAL20:30 CLASSIFICADOS23:00 NEGÓCIOS00:00 1º CADERNO/JOGADA01:00 CLASSIF(DOM)/CADERNO 3(DOM)/REGIONAL(DOM)
HORÁRIOS CADERNOS22:00 NEGÓCIOS00:00 1º CADERNO/JOGADA
SEXTA-FEIRA
DOMINGO
SÁBADO
SEGUNDA-FEIRA TERÇA-FEIRA
QUARTA-FEIRAQUINTA-FEIRA
1209
sequenciamento existentes em um problema. Assim, além de buscar o entendimento destes problemas que são tão complexos, também são buscados novos métodos para resolvê-los de modo rápido, trazendo como resultado, soluções que são de boa qualidade para resoluções práticas. Os trabalhos realizados na área de sequenciamento, são caracterizados pelo número virtualmente limitado dos tipos de problemas. As restrições assumidas neste trabalho são as seguintes: (i) uma restrição está relacionada com o tipo de recurso, que realiza uma atividade a cada momento. As atividades, são chamadas de tarefas, que podem ser realizadas em uma ou mais máquinas; (ii) outra restrição está relacionada com a natureza determinística dos problemas. 3.2 Modelo de Sequenciamento
Este trabalho apresenta uma proposta de um modelo de alocação de recursos. Esta alocação pode ser realizada em m máquinas e cada máquina pode receber n tarefas. Cada tarefa requer um tempo para ser realizada, obedecendo à data de sua entrega. Na sessão seguinte, mostra-se um estudo de caso abordando a alocação de tarefas na produção de um jornal.
Denominam-se as variáveis de decisão do modelo de tarefas. Cada tarefa pode ser composta por uma ou mais atividades que poderão ser realizadas e uma determinada máquina, no tempo estabelecido.
Definem-se as variáveis de decisão do problema como:
=contrário caso 0,
tarefada alocação possível se 1,t ijkh
Pretende-se otimizar a alocação das tarefas a partir da definição das atividades que deverão ser
realizadas. O modelo busca a melhor alocação destas tarefas, seguindo alguns critérios (que são particulares para cada problema de sequenciamento) de forma respeitar o tempo em que a tarefa deverá estar concluída.
Na função objetivo (1), denominam-se os índices de cada tarefa, da seguinte forma: (i) o índice i representa o dia da semana que a tarefa vai ser realizada; (ii) o índice j representa as atividades que serão realizadas pela tarefa; (iii) o índice k representa o tipo de máquina em que a tarefa vai ser realizada; (iv) o índice h representa a hora que a tarefa vai ser produzida. Cada tarefa pode ter um peso maior em relação a uma outra (cijkh), isto é determinado de acordo com a prioridade em que cada tarefa precisa ser executada.
(1) Máx ijkh
r
hijkh
q
k
p
j
n
itc∑∑∑∑
==== 1111
Quando a tarefa é liberada para a área de produção, define-se a quantidade de tempo que ainda resta para que ela seja concluída. Definem-se os possíveis dias da semana e os horários que as tarefas poderão ser alocadas. A restrição (2), é constituída pelo dia da semana, horário e tipo de máquina em que todas as tarefas que poderão ser realizadas neste dia, serão alocadas.
(2) r)1,..., h q;1,..., k n;1,..., (i 1, 1
===≤∑=
p
jijkht
Pode existir mais de um horário possível para que uma tarefa seja realizada. É necessário
garantir que cada tarefa será alocada somente uma vez. A restrição (3), é constituída pelos possíveis dias da semana, horários e tipos de máquinas em que uma determinada tarefa poderá ser realizada.
(3) p)1,...,(j 1, 111
=≤∑∑∑===
ijkh
r
h
q
k
n
it
1210
Como as tarefas podem ser alocadas ou não, definimos a restrição (4) como: (4) tijkh ∈ {0,1}, (i = 1,...,n; j = 1,...,p; k= 1,..,q; h = 1,...,r) Uma aplicação deste modelo, os resultados obtidos e uso da metodologia de multicritério são
apresentados a seguir 4. Aplicação do Modelo 4.1 Definição do Problema Diariamente a gerência de produção do jornal, a partir do horário de liberação dos cadernos pela redação, faz um mapa diário de impressão. Através deste mapa, os funcionários da impressão saberão os horários que os cadernos serão impressos. Consideram-se alguns fatores que influenciam na tomada de decisão da seqüência de impressão dos cadernos, de forma que o jornal não atrase.
Para a aplicação do modelo, foi considerada a seguinte situação: É necessária a impressão dos cadernos das edições de segunda-feira a domingo, incluindo o adiantamento da impressão de todos os cadernos da edição do domingo, que deverão estar impressos até a sexta-feira. Todas estas tarefas terão que estar alocadas de segunda-feira a domingo.
Nesta situação, 55 cadernos a serem impressos e 50 horários disponíveis nas duas linhas de produção.
i = n Dias da semana i = 2 (terça-feira) i = 4 (quinta-feira) i = 6 (sábado) i = 1 (segunda-feira) i = 3 (quarta-feira) i = 5 (sexta-feira) i = 7 (domingo)
Tabela 2: Corresponde ao dia da semana que a tarefa pode ser impressa.
Corresponde a tarefa a ser executada em cada dia da semana. Cada tarefa pode conter um ou dois cadernos
j = p Tipo de caderno
Cadernos da edição de segunda
Cadernos da edição de terça
Cadernos da edição de quarta
Cadernos da edição de quinta
j = 1 (cad3 - seg) j = 6 (cad3 - ter) j = 11 (cad3 - qua) j = 16 (zoeira - qui) j = 2 (zoeira/reg - seg) j = 7 (zoeira/reg - ter) j = 12 (zoeira/reg - qua) j = 17 (cad3/reg - qui)
j = 3 (classif - seg) j = 8 (classif - ter) j = 13 (classif - qua) j = 18 (classif - qui) j = 4 (neg/jog - seg) j = 9 (jog/neg - ter) j = 14 (jog/neg - qua) j = 19 (jog/neg - qui)
j = 5 (1º cad - seg) j = 10 (1º cad - ter) j = 15 (1º cad - qua) j = 20 (1º cad - qui) Cadernos da edição de sexta
Cadernos da edição de sábado
Cadernos da edição de domingo j = 21 (NossaVez)
j = 22 (cad3/reg - sex) j = 28 (classif - sab) j = 38 (classif - dom) Cadernos frios de domingo
j = 23 (zoeira - sex) j = 29 (zoeira - sab) j = 39 (1º cad - dom) j = 33 (viva/infantil) j = 24 (classif - sex) j = 30 (cad3/automovel) j = 40 (jog/neg - dom) j = 34 (eva/cultura) j = 25 (jog/neg - sex) j = 31 (jog/neg - sab) j = 35 (gente) j = 26 (1º cad - sex) j = 32 (1º cad - sab) j = 36 (zoeira - dom) j = 27 (turismo) j = 37 (regional- sab)
Tabela 3: Cadernos que deverão ser impressos durante uma semana.
Denominam-se de “cadernos quentes”, os cadernos que precisam circular diariamente em um jornal.
1211
Os “cadernos frios” são os que circulam semanalmente, estão incluídos nesta categoria, os cadernos: (i) Nossa Vez (que circula as quintas-feiras); (ii) Turismo (que circula as sextas-feiras); (iii) Automóvel (que circula aos sábados); (iv) Eva, Viva, Gente, Cultura e Infantil (que circulam aos domingos).
Corresponde ao tipo de máquina em que a tarefa vai ser realizada. Neste caso, serão consideradas duas linhas de produção (conforme mostrado nas figuras 1 e 2). A linha I possui melhor qualidade de impressão dos cadernos do que a linha II. Este detalhe é importante, em vista que, alguns cadernos necessitam ter uma ótima qualidade de impressão. Pode-se citar o caderno Gente, como exemplo de um caderno que precisa ter uma ótima qualidade de impressão, em virtude da grande quantidade de fotos e por ser um caderno destinado aos eventos ocorridos na sociedade de Fortaleza.
Os horários possíveis para a alocação das tarefas nas duas linhas de produção estão apresentados
na tabela 5
h = r Horário de execução da tarefa h = 1 (10:30) h = 7 (22:30) h = 2 (15:00) h = 8 (23:30) h = 3 (16:30) h = 9 (00:30) h = 4 (18:30) h = 10 (01:30) h = 5 (19:30) h = 11 (13:30) h = 6 (21:30) h = 12 (15:30)
Tabela 5: Horários disponíveis para o início da impressão dos cadernos
Considera-se que a duração da execução de uma tarefa leva em média três horas (incluindo as trocas de tinteiro e bobina). Durante os domingos e segundas-feiras, ocorre a folga de uma das turmas e a outra turma se divide nos dois horários. Deste modo, os horários disponíveis para a impressão das tarefas nas duas linhas de produção, ficam da seguinte forma: Segunda-feira Terça-feira a sexta-feira Sábado Domingo 18:30 – 21:30 – 00:30 16:30 – 19:30 – 22:30 – 01:30 10:30 – 13:30 – 15:30 – 18:30 21:30 – 00:30
Tabela 6: Horários que foram definidos para o início da impressão dos cadernos.
Na função objetiva do modelo, estão incluídos todos os cadernos quentes e frios que serão impressos durante a semana com os possíveis horários de alocação.
Máx ijkhijkhhkji
tc∑∑∑∑====
12
1
2
1
40
1
7
1
Todas as tarefas que estão disponíveis para serem impressas, estão divididas por dia da semana,
horário e tipo de máquina.
1,...,12) h 1,2; k 1,...,7; (i 1, 40
1
===≤∑=
ijkhj
t
Também será necessário garantir que a tarefa será alocada somente uma vez, em um
determinado dia da semana, horário e tipo de máquina.
Tabela 4: Tipos de máquinas.k = q Linha de produção k = 1 (linha 1) k = 2 (linha 2)
1212
1,...,7) (j 1, 12
1
2
1
7
1=≤∑∑∑
===ijkh
hkit
Por fim a restrição que indica se uma tarefa vai ser alocada ou não. tijkh ∈ {0,1}, (i = 1,...,7; j = 1,...,40; k= 1,2; h = 1,...,12)
Aplicando-se o modelo no software LINDO versão 6.1 da LINDO Systems, obtêm-se a seguinte alocação ótima que é descrita conforme a tabela 7. [SCHRAGE, 1998]:
Pode-se verificar que a alocação dos cadernos frios foi feita de forma satisfatória. O horário do
início da execução da tarefa, não ficou tão distante do horário que os cadernos foram liberados pela gravação.
Foi conseguido na segunda feira, alocar o Caderno 3 às 18:30 horas na linha II, em seguida às 21:30 horas nas linhas I e II respectivamente, foram alocados os cadernos Classificados, Zoeira e Regional e no último horário disponível para impressão, foram incluídos às 00:30 horas o 1º Caderno (linha I), Jogada e Negócios (linha II). A ordem de alocação destes cadernos, obedeceu a ordem do horário de fechamento da redação;
Na terça-feira, com o expediente na impressão começando um pouco mais cedo, conseguimos alocar o Caderno 3 às 16:30 horas na linha I. Depois, às 19:30 horas foram alocados os cadernos frios Nossa Vez e Turismo, nas linhas I e II respectivamente. Em seguida, às 22:30 horas nas linhas I e II alocamos os cadernos Classificados, Zoeira e Regional. E por fim, às 01:30 horas foram impressos o 1º Caderno (linha I), Jogada e Negócios (linha II). A ordem de alocação destes cadernos, obedeceu parcialmente a ordem do horário de fechamento da redação;
Na quarta-feira, no horário de 16:30 horas as linhas I e II ficaram paradas. A partir do horário de 19:30 horas, que o modelo conseguiu alocar o Caderno 3, Regional e Zoeira. Às 22:30 horas os Classificados foram alocados na linha I. E às 01:30 horas foram impressos o 1º Caderno (linha I), Jogada e Negócios (linha II). A ordem de alocação destes cadernos, obedeceu parcialmente a ordem do horário de fechamento da redação;
Tabela 7: Resultado na aplicação do modelo sem utilização de pesos na função objetivo.
HORÁRIOS LINHA I LINHA II HORÁRIOS LINHA I LINHA II18:30 CADERNO 3 16:30 CADERNO 321:30 CLASSIFICADOS ZOEIRA/REGIONAL 19:30 NOSSA VEZ TURISMO00:30 1º CADERNO JOGADA/NEGÓCIOS 22:30 CLASSIFICADOS ZOEIRA/REGIONAL
01:30 1º CADERNO JOGADA/NEGÓCIOSHORÁRIOS LINHA I LINHA II
16:30 HORÁRIOS LINHA I LINHA II19:30 CADERNO 3/REGIONAL ZOEIRA 16:30 VIVA/INFANTIL ZOEIRA22:30 CLASSIFICADOS 19:30 CADERNO 3/REGIONAL01:30 JOGADA/NEGOCIOS 1º CADERNO 22:30 EVA/CULTURA CLASSIFICADOS
01:30 1º CADERNO JOGADA/NEGOCIOSHORÁRIOS LINHA I LINHA II
16:30 CADERNO 3/AUTOMÓVEL GENTE HORÁRIOS LINHA I LINHA II19:30 REGIONAL ZOEIRA 10:30 CLASSIFICADOS22:30 ZOEIRA (DOM) CLASSIFICADOS 13:3001:30 JOGADA/NEGOCIOS 1º CADERNO 15:30 1º CADERNO JOGADA/NEGÓCIOS
18:30 ZOEIRA/REGIONAL CADERNO 3HORÁRIOS LINHA I LINHA II
21:30 CLASSIFICADOS00:30 1º CADERNO JOGADA/NEGÓCIOS
SEXTA-FEIRASÁBADO
DOMINGO
SEGUNDA-FEIRA TERÇA-FEIRA
QUARTA-FEIRAQUINTA-FEIRA
1213
Na quinta-feira, às 16:30 horas na linha I foram impressos os cadernos frios Viva e Infantil e na linha II o caderno Zoeira. Às 19:30 horas na linha I foram alocados o Caderno 3 e Regional. Nas linhas I e II respectivamente, às 22:30 horas, foram impressos os cadernos frios Eva e Cultura; e o caderno quente Classificados. E finalmente, às 01:30 horas o 1º Caderno (linha I) e Jogada e Negócios (linha II). A ordem de alocação destes cadernos, obedeceu parcialmente a ordem do horário de fechamento da redação;
Na sexta-feira, às 16:30 horas, foram impressos na linha I em uma mesma tarefa o caderno frio Automóvel com o Caderno 3 que é considerado quente. E neste mesmo horário na linha II o caderno frio Gente. Às 19:30 horas, foi alocado o caderno Regional (linha I) e caderno Zoeira (linha II). Às 22:30 horas, foi impresso o caderno frio Zoeira(dom) na linha I e os Classificados na linha II. Às 01:30 horas, na linha I os cadernos Jogada e Negócios e na linha II o 1º Caderno. A ordem de alocação destes cadernos, obedeceu parcialmente a ordem do horário de fechamento da redação;
No sábado, são impressos os quatro últimos cadernos da edição de domingo, considerados os mais quentes, e também alguns cadernos da edição de segunda-feira, que apesar de serem considerados cadernos quentes, durante o final de semana o fechamento destes cadernos, realizado pela redação é feito em forma de adiantamento. Com isso, os cadernos ficaram alocados da seguinte forma: às 10:30 horas na linha I os Classificados, no horário das 13:30 horas as linhas I e II ficaram desocupadas. Às 15:30 horas, foram impressos o 1º Caderno (linha I) e os cadernos Jogada e Negócios (linha II). Depois do fechamento da edição do domingo, foram alocados às 15:30 horas nas linhas I e II respectivamente os cadernos Zoeira, Regional e Caderno 3, que são adiantamentos da edição de segunda-feira. A ordem de alocação destes cadernos, obedeceu a ordem do horário de fechamento da redação;
No domingo, serão impressos o restante dos cadernos da edição de segunda-feira. Às 21:30 horas foram alocados os Classificados na linha II e às 00:30 horas nas linhas I e II respectivamente, foram alocados o 1º Caderno (linha I), Jogada e Negócios (linha II). A ordem de alocação destes cadernos, obedeceu a ordem do horário de fechamento da redação.
Os resultados obtidos com a alocação dos cadernos frios ainda não estão sendo satisfatórios. A meta de alocar os cadernos frios para que a sua impressão seja feita o mais cedo possível, não está sendo completamente obedecida.
Para este problema de alocação dos cadernos frios possa ser resolvido, precisamos definir critérios para algumas tarefas. Com isso, será necessário adicionar pesos na função objetiva do modelo.
Foram definidos quatro critérios que auxiliam a gerência de produção na tomada de decisão da seqüência em que os cadernos deverão ser impressos. Os critérios definidos foram os seguintes: data da distribuição do caderno, intercalação do caderno, qualidade de impressão do caderno e velocidade da linha de produção.
4.2 Ferramenta de Apoio a Decisão
A metodologia utilizada neste trabalho, para definir a prioridade da alocação dos cadernos frios, foi Multicritério. Possui duas características principais:
(i) existem múltiplos critérios; (ii) buscam encontrar soluções que melhor se encaixem nas necessidades dos atores
envolvidos. Uma leitura criteriosa sobre os métodos MCDA encontra-se em [BANA E COSTA,
1992,1999], [SOUZA, 2003] e [GOODWIN, 1998], onde os autores tratam as definições e as problemáticas que envolvem um processo de apoio a decisão.
Aplica-se a abordagem M-MACBETH for MCDA1 [BANA E COSTA, 2003] para auxiliar no julgamento. Inicialmente construí-se uma árvore para cada tarefa, com os seus critérios (ponto de vista
1 www.m-macbeth.com
1214
fundamentais - PVF). Na figura 3, mostra-se a árvore correspondente a tarefa de impressão dos cadernos Eva/Cultura.
Figura 3: Árvore de valor do problema. Cada PVF é constituído por ações, que serão todas as alocações possíveis para cada tarefa, a
partir do horário da liberação dos cadernos pela gravação. A ordem que as ações terão na matriz de julgamentos, será determinada pelo tipo de tarefa a ser executada.
Após ser julgado cada critério de uma tarefa, será feito um julgamento final com todos os critérios em uma única matriz, por prioridade. Data da distribuição do caderno (ENT), Intercalação do caderno (INT), Qualidade da impressão do caderno (QUA) e Velocidade da linha de produção (VEL). Na figura 4, mostra-se a matriz de julgamento de todos os critérios que correspondem a tarefa de impressão dos cadernos Eva/Cultura.
Após este julgamento, será calculado os valores que serão cobrados como pesos na função objetivo do modelo. Este cálculo é feito com base na análise de todos os critérios em relação a todas alocações possíveis para cada tarefa. O resultado deste cálculo encontra-se na figura 5, referente a coluna Overall do software M-MACBETH, estes valores deverão ser incluídos na tarefa correspondente da função objetiva do modelo.
Figura 4: Julgamento final de todos os critérios para definir a melhor alocação da impressão dos cadernos Eva/Cultura.
1215
Figura 5: Definição dos índices para cada alocação possível da tarefa.
Na figura 6, mostram-se todos os resultados obtidos no julgamento final dos critérios de todas
as tarefas que foram avaliadas. Estes índices deverão ser incluídos na tarefa correspondente na função objetivo do modelo.
Aplicando estes índices na função objetiva do modelo e no software LINDO, teremos a seguinte
alocação (tabela 8).
Como resultado desta aplicação, pode-se verificar um melhor sequenciamento dos cadernos frios.
Na terça-feira, foram alocados os cadernos Nossa Vez e Turismo mais cedo (às 16:30 horas na linha I e às 16:30 horas na linha II, respectivamente);
Conseguiu-se adiantar a impressão dos cadernos Eva e Cultura, que antes estavam alocados para quinta-feira às 22:30 horas na linha I para quarta-feira às 19:30 horas na linha I, é importante observar que o caderno se manteve na linha I, obedecendo o que foi proposto na geração dos custos, pois o caderno Eva exige boa qualidade de impressão, fato que a linha I proporciona.
Na impressão dos cadernos Viva e Infantil, a aplicação do custo na função objetiva, estavam alocados às 16:30 horas na linha I e agora estão alocados às 16:30 horas na linha II, como para estes dois cadernos a qualidade de impressão não é tão importante, a sua alocação foi satisfatória para os critérios de data da distribuição do caderno e intercalação do caderno.
Na alocação do caderno Gente, observou-se uma alteração muito importante, na primeira aplicação do modelo sem os custos, este caderno ficou alocado na sexta-feira às 16:30 horas na linha II. Com a aplicação dos custos, este caderno ficou alocado na quinta-feira às 19:30 horas na linha I, é
Figura 6: Índices obtidos para cada tarefa.
T22113 T22123 T22115 T22125 T32113 T32123 T32115 T3212521.86 19.50 20.01 17.03 15.75 10.97 8.15 0.70
T22713 T22723 T22715 T22725 T32713 T32723 T32715 T32725 T42713 T42723 T42715 T4272524.29 24.80 21.65 22.64 17.09 18.36 13.09 14.59 5.16 9.00 2.03 5.70
T33313 T33323 T33315 T33325 T43313 T43323 T43315 T43325 T53313 T53323 T53315 T5332522.21 22.68 20.13 20.39 15.63 15.94 10.48 10.85 4.81 6.13 1.82 3.73
T33415 T33425 T43413 T43423 T43415 T43425 T53413 T53423 T53415 T5342524.29 21.69 21.06 17.68 18.05 14.18 13.66 8.36 6.77 0.71
T43515 T43525 T53513 T53523 T53515 T5352522.48 19.55 20.14 15.18 13.19 0.75
T53613 T53623 T53615 T5362520.46 16.42 7.94 2.07
Gente
Zoeira (dom)
Turismo
Nossa Vez
Viva_Infantil
Eva_Cultura
HORÁRIOS LINHA I LINHA II HORÁRIOS LINHA I LINHA II18:30 CADERNO 3 16:30 NOSSA VEZ TURISMO21:30 CLASSIFICADOS ZOEIRA/REGIONAL 19:30 CADERNO 300:30 JOGADA/NEGÓCIOS 1º CADERNO 22:30 CLASSIFICADOS ZOEIRA/REGIONAL
01:30 1º CADERNO JOGADA/NEGÓCIOSHORÁRIOS LINHA I LINHA II
16:30 VIVA/INFANTIL HORÁRIOS LINHA I LINHA II19:30 EVA/CULTURA ZOEIRA 16:30 ZOEIRA22:30 CADERNO 3/REGIONAL CLASSIFICADOS 19:30 GENTE CADERNO 3/REGIONAL01:30 JOGADA/NEGOCIOS 1º CADERNO 22:30 CLASSIFICADOS
01:30 1º CADERNO JOGADA/NEGÓCIOSHORÁRIOS LINHA I LINHA II
16:30 ZOEIRA (DOM) CADERNO 3/AUTOMÓVEL HORÁRIOS LINHA I LINHA II19:30 REGIONAL 10:30 CLASSIFICADOS22:30 ZOEIRA CLASSIFICADOS 13:3001:30 1º CADERNO JOGADA/NEGÓCIOS 15:30 1º CADERNO JOGADA/NEGÓCIOS
18:30 ZOEIRA/REGIONAL CADERNO 3HORÁRIOS LINHA I LINHA II
21:30 CLASSIFICADOS00:30 1º CADERNO JOGADA/NEGÓCIOS
SEGUNDA-FEIRA
QUARTA-FEIRA
SEXTA-FEIRA
DOMINGO
TERÇA-FEIRA
QUINTA-FEIRA
SÁBADO
Tabela 8: Resultado na aplicação do modelo com utilização de pesos na função objetivo.
1216
satisfatório, porque este caderno exige uma melhor qualidade de impressão, obedecendo ao critério de qualidade de impressão do caderno.
Em relação a alocação do caderno Zoeira (dom) no primeiro modelo, ficou alocado na sexta-feira às 22:30 horas na linha I e com a aplicação do segundo modelo, continuou na sexta-feira, sendo que às 16:30 horas na linha I, lembrando que este caderno também exige uma boa qualidade de impressão. 5. Conclusão
A construção de um modelo para alocação de recursos, buscou-se a possibilidade de otimizar o processo do sequenciamento de tarefas, podendo ser aplicado nas mais diversas áreas em que seja necessária a produção de tarefas em uma única máquina, que obedeçam a uma data de entrega. A aplicação desse modelo de sequenciamento, na produção de um jornal, pôde atender aos objetivos que foram propostos na construção do modelo, para determinar o dia da semana, hora e tipo de máquina em que os cadernos “frios” e “quentes” serão impressos ao longo de uma semana. Com isso, buscou-se a substituição do método em uso existente desde a fundação do Diário do Nordeste, em que o gerente de produção, faz o mapa diário de impressão, de acordo com o seu “sentimento”, baseado em fatores empíricos.
Observou-se que, durante a definição da seqüência em que as tarefas serão impressas, pode existir a possibilidade de alguns cadernos serem prioridade em relação a outros. Assim, foram definidos critérios que foram construídos com base em dados empíricos fornecidos pela gerência de produção.
O uso da abordagem do MACBETH, apresentou-se adequada para a modelagem do problema em relação aos critérios. O resultado obtido foi utilizado em forma de custos, adicionados na função objetivo do modelo. 6. Bibliografia 1) BANA E COSTA, C. A. Structuration, construction et exploitation dún modèle multicritère d’aide à la décision. Thèse de doctorat pour l’obtention du titre de Docteur em Ingénierie de Systèmes - Instituto Técnico Superior, Universidade Técnica de Lisboa, 1992. 2) BANA E COSTA, C. A; ENSSLIN, L.; CORREA, E. C.; VANSNICK, J. C. Decision support systems in action: integrates application in a multicriteria decision aid process. European Journal of Operational Research, v. 133, p. 315-335, 1999. 3) BANA E COSTA, C. A.; Corte, J. M. D.; Vansnick, J. C. (2003) "MACBETH", LSE-OR Working Paper, 56. 4) CASTRO, A. K. A. Um Processo de Scheduling para a Produção de um Jornal. 2004. 69f.. Monografia (Curso de Informática) – Centro de Ciências Tecnológicas, Universidade de Fortaleza, Ceará. 5) GOODWIN, P.; WRIGHT, G. Decision analysis for management judgment, 2. ed. John Wiley & Sons, Chicester, 1998. 6) MÜLLER, FELIPE MARTINS. Problemas de Sequenciamento em Processadores Paralelos: Modelos e Algoritmos. XXV Congresso Nacional de Matemática Aplicada e Computacional, set. 2002. 7) SCHRAGE, L. Optimization Modeling with LINGO. LINDO Systems Inc, USA, First Edition, 1998. 8) SOUZA, G. G. C. de. Um Modelo de Multicritério para a Produção de um Jornal. 2003. 71f.. Dissertação (Mestrado em Informática Aplicada) - Universidade de Fortaleza, Ceará.
