Universidade Federal de Minas Gerais Instituto de Ciências Exatas Departamento de Ciência da Computação BRAULIO ALVES SILVA LARA Quadro de Horários Acadêmico: Uma Abordagem com Foco na Avaliação Institucional e na Gestão de Custos de Instituições de Ensino Superior Privadas Brasileiras Belo Horizonte 2006 2 BRAULIO ALVES SILVA LARA Quadro de Horários Acadêmico: Uma Abordagem com Foco na Avaliação Institucional e na Gestão de Custos de Instituições de Ensino Superior Privadas Brasileiras Dissertação apresentada ao Programa de Pós- Graduação em Ciência da Computação do Departamento de Ciência da Computação do Instituto de Ciências Exatas da Universidade Federal de Minas Gerais, como requisito parcial para a obtenção do grau de Mestre em Ciência da Computação. Orientador: Prof. Geraldo Robson Mateus Belo Horizonte 2006 i A Deus, a minha família e a minha namorada. ii Agradecimentos Agradeço ao professor Geraldo Robson Mateus pelo conhecimento, pelo incentivo e pela orientação. Agradeço os professores Denílson Alves Pereira, Mirian Lourenço Maia e Gilberto Miranda Júnior por terem confiado a indicação e pela motivação para realizar esse curso de Mestrado. Agradeço à Universidade Federal de Minas Gerais (UFMG), por meio do Programa de Pós-Graduação em Ciência da Computação (PPGCC) do Departamento de Ciência da Computação (DCC), pela oportunidade e ao Centro Universitário de Belo Horizonte (UNI- BH) pela experiência acadêmica e profissional que subsidiaram a criação desse trabalho. Agradeço também aqueles que, embora não citados, me ajudaram por esse caminho e colaboraram para a realização dessa dissertação. Agradeço a Deus, pela força em todos os momentos, à minha família e à minha namorada pelo suporte e compreensão durante todo o percurso. iii Resumo Essa dissertação apresenta o problema da construção de quadros de horários em instituições de ensino, conhecido como timetabling, por um ângulo diferente dos trabalhos descritos na literatura, que é aplicável ao cenário brasileiro. A elaboração de quadros de horários acadêmicos é uma atividade estrutural de uma instituição de ensino. No sistema de ensino superior brasileiro existem regras e normas que definem parâmetros de qualidade, os quais devem ser atendidos pelas instituições. Esse trabalho propõe uma metodologia para construção de quadros de horários acadêmicos, tal que os aspectos de custo operacional e atendimento aos requisitos legais sejam considerados. Os principais parâmetros utilizados são oriundos do SINAES (Sistema Nacional de Avaliação da Educação Superior), gerido pelo MEC (Ministério da Educação), por meio da Avaliação Institucional realizada pelo INEP (Instituto Nacional de Estudos e Pesquisas Educacionais Anísio Teixeira). Entre eles cabe destacar o regime de trabalho, a titulação, as publicações e produções do corpo docente. Então, com base nessas e outras informações, deseja-se realizar a alocação dos professores nas atividades institucionais de modo eficiente, a fim de se obter o nível de qualidade desejado e uma aplicação racional dos recursos docentes. Devido à abordagem da gestão de custos, o trabalho é direcionado às instituições de ensino superior privadas, pois vários critérios abordados não estão presentes no contexto público. Então, um processo para a construção de um quadro de horários é proposto, o qual inclui modelos de otimização para a alocação de professores às disciplinas ofertadas, tanto para instituições organizadas em um único campus como para instituições multicampi. iv Abstract This dissertation presents the timetabling problem to educational institutions showed in a different angle in relation with other works in the literature, applicable in the brazilian context. The construction of academic timetables is a structural activity in an educational institution. There are rules and standards in the brazilian superior education system that establish quality parameters, that should be fulfilled by institutions. This work proposes a methodology for the construction of academic timetables, so that the aspects of operational costs and the fulfillment of legal requirements are considered. The most important used parameters are from the SINAES (National Superior Education Evaluation System), managed by MEC (Ministry of Education), throughout Institutional Evaluation done by INEP (National Institute of Studies and Educational Research Anísio Teixeira). It’s important to highlight the work regimen, the academic degree, the publications and productions of academic staff. Based on these and other informations, it is desirable to make the teachers assignments in the institutional activities in an efficient mode, in order to get the quality level desired and rational academic resources application. Due to the line of costs management, this work is directed to the private superior educational institutions, once that various criteria are not applied to the public organization. Therefore, a process for the construction of timetables is proposed, which includes optimization models for the assignment to subjects offered, for institutions organized in an single campus and for multicampi institutions. v Lista de Ilustrações FIGURA 1 - Níveis de Formação da Educação Superior Brasileira ................................. 29 FIGURA 2 - Fases do Processo ....................................................................................... 62 FIGURA 3 - Diagrama de processo para construção do quadro de horários ..................... 66 FIGURA 4 - Modelo de dados utilizado .......................................................................... 85 FIGURA 5 - Modelo da rede multifluxo........................................................................ 130 GRÁFICO 1 - Carga Horária Total Mínima por tipo de IES .............................................. 55 GRÁFICO 2 - Proporção CHTM/CHE por tipo de IES...................................................... 56 GRÁFICO 3 - Proporção CHTM/CHE nas Universidades ................................................. 56 GRÁFICO 4 - Proporção CHTM/CHE nos Centros Universitários .................................... 57 GRÁFICO 5 - Proporção CHTM/CHE nas Faculdades...................................................... 57 GRÁFICO 6 - Número de Professores Mínimo por tipo de IES ......................................... 58 GRÁFICO 7 - Percentual de Professores em Tempo Integral por tipo de IES..................... 59 GRÁFICO 8 - Percentual de Professores em Tempo Integral nas Universidades................ 60 GRÁFICO 9 - Percentual de Professores em Tempo Integral nos Centros Universitários ... 60 GRÁFICO 10 - Evolução do gap para uma instância pequena ........................................... 115 GRÁFICO 11 - Evolução da função objetivo e do limite inferior para uma instância pequena ................................................................................................................ 116 GRÁFICO 12 - Evolução do gap para uma instância maior ............................................... 117 GRÁFICO 13 - Evolução da função objetivo e do limite inferior para uma instância maior117 Definição dos tipos de regime de trabalho.................................................. 24 Um quadro de horários solução.................................................................. 32 Distribuição de carga horária semanal dos professores (1).......................... 33 Distribuição de carga horária semanal dos professores (2).......................... 33 Distribuição de carga horária semanal dos professores (3).......................... 34 Conjunto de disciplinas a serem ofertadas de acordo com a grade curricular .................................................................................................................. 77 Quadro de oferta de disciplinas .................................................................. 81 Discretização dos regimes de trabalho........................................................ 82 Relação de ofertas de disciplinas afins aos professores............................... 86 Períodos de indisponibilidade dos professores............................................ 87 Quadro de horários final............................................................................. 91 Relação de ofertas de disciplinas afins aos professores (E4) ..................... 107 QUADRO 1 - QUADRO 2 - QUADRO 3 - QUADRO 4 - QUADRO 5 - QUADRO 6 - QUADRO 7 - QUADRO 8 - QUADRO 9 - QUADRO 10 - QUADRO 11 - QUADRO 12 - vi Lista de Tabelas 1 - Evolução das IES no Brasil – 1998-2004 ............................................................... 11 2 - Metas sobre titulação e regime de trabalho para o corpo docente ........................... 14 3 - Distribuição dos Pesos nas Dimensões do SINAES ............................................... 20 4 - Conceitos do Indicador Titulação (MT).................................................................. 23 5 - Conceitos do Indicador Regime de Trabalho (RT) ................................................. 24 6 - Conceitos do Indicador Publicações/Produções (N) ............................................... 25 7 - Carga horária por disciplina a ser ofertada ............................................................. 32 8 - Plano de oferta de disciplinas................................................................................. 78 9 - Regimes de trabalho considerados e seus parâmetros ............................................. 83 10 - Solução ótima (inteira) do modelo APRAC ........................................................... 83 11 - Custos marginais dos regimes de trabalho - solução linear do APRAC .................. 84 12 - Penalidade calculada para cada professor............................................................... 85 13 - Enquadramento dos professores na solução final ................................................... 88 14 - Distribuição de horas de ensino final por professor ................................................ 89 15 - Enquadramento dos professores na solução final (E1)............................................ 95 16 - Distribuição de horas de ensino final por professor (E1) ........................................ 96 17 - Enquadramento dos professores na solução final (E2)............................................ 98 18 - Distribuição de horas de ensino final por professor (E2) ...................................... 100 19 - Enquadramento dos professores na solução final (E3).......................................... 103 20 - Distribuição de horas de ensino final por professor (E3) ...................................... 104 21 - Enquadramento dos professores na solução final (E4).......................................... 108 22 - Distribuição de horas de ensino final por professor .............................................. 109 23 - Avaliação dos Exemplos...................................................................................... 112 24 - Instâncias da primeira bateria de testes ................................................................ 118 25 - Resultados computacionais da primeira bateria de testes...................................... 118 26 - Resultados dos indicadores do processo de alocação de professores da primeira bateria de testes ................................................................................................... 119 27 - Instâncias da segunda bateria de testes................................................................. 121 28 - Resultados computacionais da segunda bateria de testes ...................................... 122 29 - Resultados dos indicadores do processo de alocação de professores da segunda bateria de testes ................................................................................................... 123 30 - Instâncias da terceira bateria de testes.................................................................. 125 31 - Resultados computacionais da terceira bateria de testes ....................................... 126 32 - Resultados dos indicadores do processo de alocação de professores da terceira bateria de testes ................................................................................................... 127 vii Sumário Capítulo 1 - Introdução ....................................................................................................... 9 Capítulo 2 - Contextualização ........................................................................................... 11 2.1 - A Lei de Diretrizes e Bases da Educação Nacional (LDB)........................................ 13 2.2 - Avaliação no Ensino Superior.................................................................................. 15 2.2.1 - Evolução dos Processos Avaliativos .................................................................. 15 2.2.2 - SINAES ............................................................................................................ 18 2.2.3 - Avaliação Externa ............................................................................................. 20 2.2.4 - Cálculo de Indicadores ...................................................................................... 22 Indicador Titulação .................................................................................................. 22 Indicador Regime de Trabalho.................................................................................. 23 Indicador Publicações/Produções.............................................................................. 24 2.3 - Normas Regionais.................................................................................................... 26 2.4 - Organização e Normas Institucionais....................................................................... 27 2.5 - Competitividade e Custos em IES Particulares......................................................... 30 2.5.1 - Custos x Horário ............................................................................................... 32 2.6 - Conclusão................................................................................................................ 36 Capítulo 3 - Revisão Bibliográfica..................................................................................... 37 3.1 - O Problema ............................................................................................................. 37 3.2 - Viabilidade versus Otimalidade ............................................................................... 41 3.3 - Métodos de Resolução.............................................................................................. 42 3.4 - Modelos Timetabling................................................................................................ 43 3.4.1 - Problema de Escalonamento Turma-Professor (PET) ........................................ 43 3.4.2 - Problema de Escalonamento de Disciplinas (PED) ............................................ 45 3.4.3 - Problema de Escalonamento de Exames (PEE).................................................. 47 3.4.4 - Problema de Alocação de Professores (PAP) ..................................................... 48 3.4.5 - Problema de Alocação de Salas de Aula (PASA)............................................... 50 3.5 - O modelo APRAC .................................................................................................... 52 3.5.1 - Indicadores Referenciais do APRAC................................................................. 54 3.5.2 - Análises sobre os Indicadores Referenciais........................................................ 55 Capítulo 4 - Modelagem do Problema............................................................................... 61 4.1 - Processo de Elaboração de um Quadro de Horários................................................ 61 4.2 - Alocação de Professores .......................................................................................... 64 4.3 - Objetivo a otimizar .................................................................................................. 67 viii 4.4 - Formulação Matemática – Único Campus (Modelo APU)........................................ 71 4.5 - Formulação Matemática – Multicampi (Modelo APM) ............................................ 75 4.6 - Processo Exemplo.................................................................................................... 77 4.6.1 - Fase 1 – Elaboração do Plano de Oferta............................................................. 77 4.6.2 - Fase 2 – Elaboração do Quadro de Oferta.......................................................... 80 4.6.3 - Fase 3 – Alocação de Professores no Quadro de Horários.................................. 82 4.6.4 - Interação entre Fases ......................................................................................... 93 4.7 - Extensões ao exemplo - análises em outros cenários ................................................ 94 4.7.1 - Exemplo E1 - Instituições com vários campi ..................................................... 94 4.7.2 - Exemplo E2 - Evolução no Quadro Docente...................................................... 98 4.7.3 - Exemplo E3 - Professores pré-alocados em atividades complementares........... 102 4.7.4 - Exemplo E4 - Aumento na disponibilidade dos professores ............................. 106 4.8 - Indicadores do Processo de Alocação de Professores ............................................ 111 4.8.1 - Avaliação dos Exemplos ................................................................................. 112 4.9 - Método de Resolução ............................................................................................. 114 4.10 - Testes Realizados ................................................................................................. 115 4.11 - Formulação Alternativa – Fluxo de Custo Mínimo Multiproduto ......................... 129 Capítulo 5 - Conclusões ................................................................................................... 136 Capítulo 6 - Bibliografia .................................................................................................. 138 9 Capítulo 1 - Introdução A elaboração de quadros de horários é uma atividade comum a toda instituição de ensino. A alocação de professores às disciplinas a serem ofertadas em uma turma de alunos em uma determinada sala de aula é uma tarefa difícil e em muitos casos é feita manualmente por uma equipe administrativo-acadêmica antes do início do período letivo. Segundo Bloomfield e McShare [5], “dependendo do tamanho de um departamento e da diversidade da oferta de cursos, o tempo necessário para produzir um escalonamento de turmas pode variar de uma tarde a um mês de trabalho”. Essa atividade, conhecida como construção de quadro de horários, (em inglês, timetabling) tem características comuns nos diversos modelos de ensino. No entanto, cada Instituição, dependendo do seu contexto, possui características ou peculiaridades que influenciam na construção dos seus quadros de horários. Existe uma grande variedade de problemas de timetabling descritos na literatura [50] bem como caminhos diferentes para obtenção da solução. Essa grande variedade ocorre devido à customização dos modelos de acordo com o tipo de escola e seu sistema educacional. Dessa forma, não é possível o estabelecimento de um modelo único que seja capaz de atender todas as situações. Um problema de timetabling é um problema de aspecto combinatório que consiste em construir quadros de horários para uma série de atividades atendendo a um determinado conjunto de restrições. Na maioria dos casos, a confecção de um quadro de horários se baseia em criar uma solução viável dentro do conjunto de restrições do problema [15][50]. Em se tratando de Instituições de Ensino Superior (IES) brasileiras, as quais estão sujeitas a um mecanismo de avaliação oficializado pelo Ministério da Educação (MEC), uma solução de um quadro de horários pode implicar em arranjos melhores ou piores quanto aos conceitos obtidos nas Avaliações Institucionais [37]. Isso porque o plano de disciplinas a serem ofertadas e conseqüentemente o quadro de horários, estão na base estrutural da organização de uma IES e mesmo com um quadro de horários que atenda todas as restrições e satisfaça as necessidades de professores e alunos, pode ser insuficiente para que uma IES atenda aos padrões mínimos de qualidade exigidos nas avaliações e legislação do ensino superior ([6],[7],[10],[11]). Uma vez com um conceito abaixo do máximo, uma IES, com o intuito de melhorar seus resultados, pode vir a atuar de forma ineficiente no problema. Acabam onerando seus 10 custos sem de fato atacar o problema a partir da confecção de um quadro de horários mais adequado. A partir dessa situação, surge a necessidade da criação de quadros de horários mais eficientes em termos da Avaliação Institucional em paralelo com a gestão de custos [37]. Deste modo, além do trabalho para obter um quadro de horários viável segundo as restrições convencionais dos problemas de quadro de horários, deseja-se obter um quadro de horários que seja mais adequado diante do ponto de vista da instituição. Essa dissertação está organizada da seguinte forma: o Capítulo 2 apresenta a contextualização do problema, o cenário da legislação e avaliação institucional, os aspectos de custos e o impacto no horário. No Capítulo 3 é apresentada uma revisão bibliográfica sobre o assunto. No Capítulo 4 são apresentados o processo de construção de quadros de horários bem como os modelos a serem utilizados. Por fim, no Capítulo 5 é feita uma conclusão sobre o trabalho. 11 Capítulo 2 - Contextualização Esse trabalho tem como escopo o estudo da construção de quadros de horários nas Instituições de Ensino Superior Privadas Brasileiras. A limitação do escopo quanto ao contexto das instituições privadas se dá pelo fato de as mesmas seguirem uma linha de atuação calcada em princípios econômicos e financeiros que não estão presentes nas instituições públicas. As instituições privadas têm como característica fundamental a auto sustentabilidade, ou seja, elas se mantém com recursos próprios. Já as instituições públicas são custeadas pelo Estado e a dinâmica utilizada para a captação dos recursos é feita de modo específico. Apesar de praticamente todos os requisitos de qualidade exigidos legalmente aplicarem-se às instituições privadas e públicas, os aspectos econômicos a serem abordados estão presentes apenas nos contextos privados, que são maioria. De acordo com dados divulgados pelo MEC referente ao Censo [36] da Educação Superior 2004, o Sistema de Ensino Superior Brasileiro conta mais de 2000 instituições. Desse total, 88%, aproximadamente, são particulares e essas são responsáveis por mais de 80% de todas as vagas disponibilizadas à população. A TAB. 1 apresenta a evolução do número de IES no Brasil. TABELA 1 Evolução das IES no Brasil – 1998-2004 Ano Públicas % Privadas % Total 1998 209 21,5 764 78,5 973 1999 192 17,5 905 82,5 1.097 2000 176 14,9 1.004 85,1 1.180 2001 183 13,2 1.208 86,8 1.391 2002 195 11,9 1.442 88,1 1.637 2003 207 11,1 1.652 88,9 1.859 2004 224 11,1 1.789 88,9 2.013 Fonte: MEC/INEP Segundo dados divulgados pelo INEP1, houve um aumento de 12,41% no número de cursos ofertados pelas IES Brasileiras comparando 2004 com 2003. Essa grande expansão do ensino superior privado trouxe conseqüências óbvias como, por exemplo, a grande concorrência institucional a partir da crescente oferta de vagas. 1 Disponível em: http://www.inep.gov.br/imprensa/noticias/censo/superior/news06_01.htm Acesso em 12/01/2006 12 Diante desse cenário, surge a necessidade, cada vez mais presente, do aperfeiçoamento das estruturas administrativas e acadêmicas em prol da redução de custos e viabilidade orçamentária. Como conseqüência desse fenômeno, conhecido como mercantilização do ensino [35], a qualidade acadêmica vem sendo ameaçada. A fim de manter o padrão e garantir a qualidade de oferta de educação para a população, o Governo tem criado ações contínuas para o acompanhamento e fiscalização das IES. Então, mecanismos foram criados para formatar as exigências dos níveis de qualidade. Esses níveis são avaliados em escalas que no final do processo resultam em conceitos. Esses conceitos motivam a corrida pela excelência e automaticamente o aumento da qualidade das instituições. No entanto, todo esse aumento implica diretamente em elevação de custos. Nesse cenário competitivo, o aumento de custos pode implicar em perda de mercado, pois a fim de garantir a viabilidade orçamentária, uma instituição pode decidir não operar com excelência, tornando-se uma instituição de segundo nível, ou pode optar por aumentar preços. Seguindo as leis básicas da economia e a atual situação econômica do país, é sabido que os estudantes são sensíveis às variações de preços, pois o custo médio de uma mensalidade de um curso superior tem impacto significativo no orçamento familiar. Com preços elevados, uma instituição pode perder mercado e conseqüentemente reduzir seus recursos, tornando, em alguns casos, o seu orçamento inviável. Por outro lado, com um conceito ruim nas avaliações do MEC, a instituição poderá perder prestígio, reputação e conseqüentemente mercado. A saída que resta está na busca da eficiência e eficácia das estruturas institucionais a fim de que a instituição tenha qualidade e excelência, e ao mesmo tempo, seja financeiramente viável. Estendendo as abordagens propostas na literatura, o objetivo desse trabalho é propor uma metodologia para a construção do quadro de horários tendo como norteador os índices de avaliação institucional e buscando a minimização dos custos operacionais. Exigências legais, convenções ou acordos coletivos e restrições regimentais também deverão ser consideradas. 13 2.1 - A Lei de Diretrizes e Bases da Educação Nacional (LDB) A Lei nº 9.394, de 20 de dezembro de 1996, estabelece as diretrizes e bases da educação nacional. A LDB [6] abrange aspectos desde a educação básica até a educação superior e é considerada, portanto, o pilar central das políticas educacionais brasileiras. A LDB estabelece em seu texto a organização da educação superior bem como a classificação das instituições quanto sua categoria administrativa. Com o intuito de regulamentar alguns artigos da LDB, o Decreto 5.773, de 9 de maio de 2006, dispõe sobre a organização do ensino superior, a avaliação de cursos e instituições. Segundo a legislação supra citada, as instituições educacionais são classificadas quanto à organização administrativa e quanto à organização acadêmica. Quanto à organização administrativa, as instituições podem ser classificadas como públicas, administradas pelo poder público podendo ser federais, estaduais ou municipais, e as privadas. As instituições privadas são mantidas e administradas por pessoas físicas ou jurídicas de direito privado e dividem-se entre instituições com ou sem fins lucrativos. Quanto à organização acadêmica, as instituições são subdivididas entre dois grupos: instituições universitárias e não universitárias. O grupo de instituições universitárias é formado pelas universidades, as universidades especializadas e os centros universitários. As universidades são instituições pluridisciplinares, com formação de quadros profissionais de nível superior, que desenvolvem atividades regulares de ensino, pesquisa e extensão. As universidades especializadas são instituições de educação superior especializadas em um campo do saber, no qual são desenvolvidas atividades de ensino e pesquisa e extensão, em áreas básicas e/ou aplicadas. Já os centros universitários são instituições de educação superior pluricurriculares que devem oferecer ensino de excelência e oportunidades de qualificação ao corpo docente e condições de trabalho à comunidade escolar. De forma similar, os centros universitários especializados são instituições que atuam numa área de conhecimento específica ou de formação profissional. Entre as instituições não universitárias, estão as faculdades, os institutos superiores ou escolas superiores, os centros de educação tecnológica. As faculdades são instituições de educação superior com propostas curriculares em uma ou mais áreas do conhecimento, organizadas sob o mesmo comando e regimento comum, com a finalidade de formar profissionais de nível superior, podendo ministrar cursos nos vários níveis e modalidades do ensino. Já os Institutos Superiores ou Escolas Superiores são instituições de educação superior com finalidade de ministrar cursos nos vários níveis. Por fim, os Centros de Educação 14 Tecnológica são instituições especializadas de educação profissional com a finalidade de qualificar profissionais em cursos superiores de educação tecnológica. De acordo com o art. 12 e 13 do Decreto 5.773 [10], a criação de cursos superiores em instituições credenciadas como faculdades depende de prévia autorização do Poder Executivo. Já as universidades, centros universitários e centros de educação tecnológica, gozam de autonomia didático-pedagógica para a criação de cursos de acordo com seus respectivos regimentos. A qualidade do ensino praticada nas instituições é supervisionada pelos processos avaliativos do poder público [10], sendo que, em caso de desempenho insuficiente nas avaliações, as IES poderão ter suas prerrogativas de autonomia cassadas nos termos da lei. Dessa forma, é exigido pela legislação, um bom desempenho nas avaliações. O texto da LDB já trazia em seu art. 52 algumas metas de qualidade do corpo docente a serem aplicadas às universidades, exigindo das mesmas, pelo menos um terço do corpo docente com titulação acadêmica de mestrado ou doutorado e pelo menos um terço do corpo docente em regime de trabalho tempo integral. Em 24 de maio de 2006, foi editado o Decreto 5.786, que dispõe sobre as metas sobre regime de trabalho e titulação no âmbito dos centros universitários. A TAB. 2 sintetiza as metas para o corpo docente definidas na legislação. No entanto, os conceitos sobre níveis de qualidade são definidos por meio dos processos avaliativos. A avaliação no ensino superior será explorada na próxima seção. TABELA 2 Metas sobre titulação e regime de trabalho para o corpo docente % em Regime Integral % com título de mestre ou doutor Universidades 33% 33% Centros Universitários 20% 33% Fonte: LDB [6] e Decreto 5.786/2006 [11] 15 2.2 - Avaliação no Ensino Superior 2.2.1 - Evolução dos Processos Avaliativos Os processos de avaliação e regulação da educação superior têm como motivação desde a necessidade da garantia de qualidade, a necessidade dos controles, a fundamentação de políticas, distribuição de recursos, até mesmo a necessidade de fornecer informações públicas sobre o quadro educacional. Como resultado desses esforços, podem ser citados o aumento do aparato normativo, a ênfase nos resultados ou produtos, e o uso de instrumentos que produzam informações objetivas e que permitam a comparação e a ampla divulgação para os públicos interessados. A mais antiga e duradoura experiência brasileira em aspectos de avaliação da educação superior é a elaborada e desenvolvida pela Capes desde 1976 junto aos cursos de Pós-Graduação [35]. Desde lá, vários esforços têm sido empenhados na elaboração e implementação de diferentes propostas de avaliação da educação superior abrangendo os demais níveis de formação. A primeira proposta de avaliação da educação superior no país foi o Programa de Avaliação da Reforma Universitária (Paru) de 1983. O Paru tratou basicamente de dois temas: gestão e produção/disseminação de conhecimento. Em 1993 surgiu o Programa de Avaliação Institucional das Universidades Brasileiras (Paiub). O Paiub concebeu a auto-avaliação como etapa inicial de um processo que tinha como etapa final, a avaliação externa. Diante de mudanças políticas significativas no período, o Paiub perdeu sua força e acabou sendo incorporado apenas como um processo de avaliação interno das instituições. A partir da LDB, foram criados novos mecanismos de avaliação: • Exame Nacional de Cursos; • Avaliação das Condições de Oferta; • Avaliação das Condições de Ensino; • Avaliação Institucional. O Exame Nacional de Cursos (ENC), também chamado de Provão, foi concebido como um instrumento de avaliação necessário para subsidiar o MEC de informações para orientar suas ações. Sua primeira edição foi em 1996, avaliando 616 cursos em três áreas, e chegando em 2003 (última edição) avaliando 5.890 cursos em 24 áreas. O ENC basicamente 16 era composto por um teste de conhecimento aplicado aos concluintes dos cursos de graduação e por um conjunto de questionários submetidos aos estudantes. O ENC tinha como filosofia básica o mapeamento do conceito dos cursos a partir da visão dos seus concluintes. A partir dos resultados obtidos e observando as médias nacionais, os cursos avaliados obtinham uma classificação de “A” até “E”. O ENC foi objeto de severas criticas da comunidade acadêmica, pois foi rotulado com um instrumento de avaliação desarticulado e com resultados não confiáveis sobre a real qualidade acadêmica. Já a Avaliação das Condições de Oferta (ACO) visava avaliar in loco cada um dos cursos de graduação submetidos ao Exame Nacional de Cursos. A avaliação era organizada em três dimensões e abrangia aspectos quanto à qualificação do corpo docente, à organização didático-pedagógica e às instalações, tanto as físicas em geral, quanto as especiais, tais como laboratórios, equipamentos e bibliotecas. Cada uma das três dimensões era classificada com um dos conceitos obtidos a partir das ponderações das pontuações obtidas entre os vários aspectos avaliados e seus respectivos pesos: • CMB: Condições Muito Boas; • CB: Condições Boas; • CR: Condições Regulares; • CI: Condições Insuficientes. A Avaliação das Condições de Ensino (ACE) introduziu modificações no sistema de avaliação com o objetivo de suprimir algumas das deficiências apontadas nos mecanismos da ACO. Os instrumentos de avaliação criados para compor a ACE foram balizados nas experiências anteriores com a ACO e o ENC. Foram criados o Manual Geral de Avaliação das Condições de Ensino e os Manuais Específicos por Curso. Esses instrumentos também estão organizados de acordo com as três dimensões, da mesma forma que na ACO, as quais recebem seus conceitos finais a partir da ponderação da pontuação obtida nos aspectos avaliados dentro de cada uma das dimensões. São elas: • Dimensão 1: Organização Didático Pedagógica; • Dimensão 2: Corpo Docente; • Dimensão 3: Instalações. Por fim, a Avaliação Institucional, é o processo que aborda o aspecto institucional, de modo generalista, sem o detalhamento ou captação de informações específicas de cursos. O Manual de Avaliação Institucional é organizado em três dimensões similarmente aos manuais ACE: 17 • Dimensão 1: Organização Institucional • Dimensão 2: Corpo Docente • Dimensão 3: Instalações O cálculo dos conceitos das dimensões é feito de forma semelhante ao cálculo nos manuais ACE. Os resultados obtidos por um curso ou por uma instituição nas avaliações, subsidiam o MEC na homologação de reconhecimentos de cursos e recredenciamento de IES. Outra característica importante do processo avaliativo implantado é a presença do Formulário Eletrônico. Esse sistema, acessível via internet, reúne as informações que subsidiam a avaliação sendo que a pontuação de diversos aspectos (principalmente os relativos ao corpo docente) era calculada automaticamente pelo programa a partir dos dados cadastrados. Os conceitos finais da avaliação também eram calculados pelo sistema a partir das notas atribuídas a cada um dos aspectos pelos avaliadores in loco. Além disso, o formulário eletrônico possibilitou a integração com outras informações captadas em outros sistemas do MEC como, por exemplo, o Censo da Educação Superior e o Cadastro de IES. Os mecanismos então criados estavam voltados para o resultado quantitativo obtido a partir da avaliação dos aspectos de acordo com um manual. Esse modelo acaba tendo características apenas de supervisão ou averiguação, desconsiderando a diversidade de instituições e suas peculiaridades, visto que a definição dos parâmetros é feita de forma unilateral pelo MEC. A partir daí surgiu a necessidade da criação de um sistema nacional de avaliação da educação superior que articulasse regulação com avaliação educativa, aspectos qualitativos em paralelo com os quantitativos. O Sistema Nacional de Avaliação da Educação Superior (SINAES) foi instituído pela Lei Nº 10.861, de 14 de abril de 2004 e tem como propósito articular, de forma coerente, concepções, objetivos, metodologias, práticas, agentes da comunidade acadêmica e de instâncias do governo, resguardando as especificidades, as competências e as autoridades. O SINAES reformula a estruturação dos instrumentos de avaliação segundo a nova filosofia proposta, aperfeiçoando os mecanismos existentes. Mais detalhes do SINAES são explorados a seguir. 18 2.2.2 - SINAES O Sistema Nacional de Avaliação da Educação Superior (SINAES) foi instituído pela Lei Nº 10.861, de 14 de abril de 2004, sendo o sistema de avaliação vigente, e sua sistemática de avaliação é construída com base em três processos: • Avaliação Institucional; • Avaliação do Desempenho dos Estudantes (por meio do Exame Nacional de Desempenho dos Estudantes – ENADE); • Avaliação dos Cursos de Graduação. A Avaliação Institucional (AI) tem por objetivo verificar as condições gerais de funcionamento dos estabelecimentos de educação superior, subsidiando o MEC quanto a credenciamento de IES. A Avaliação Institucional é compreendida por dois processos: a Auto-Avaliação e Avaliação Externa. A Auto-Avaliação é de responsabilidade de cada instituição e deverá ser feita de acordo com o documento Roteiro de Auto-Avaliação Institucional. As informações do Cadastro Institucional, do Censo da Educação Superior e do Paideia2 também servirão de base para nortear a Auto-Avaliação. A periodicidade da auto-avaliação é no máximo de três em três anos. Uma vez concluído o Relatório de Auto-Avaliação, esse é submetido ao MEC e servirá de subsídio para o processo de Avaliação Externa. O processo de Avaliação Externa é realizado por uma comissão externa indicada pelo MEC. Os documentos tomados como base são as Diretrizes e o Instrumento de Avaliação Externa das Instituições de Ensino Superior [7][8]. Enquanto a ACE conceituava separadamente cada uma das suas três dimensões, a Avaliação Externa do SINAES tem seu resultado como um único conceito que é calculado pela ponderação da pontuação de cada uma das dez dimensões e seus respectivos pesos. Já a Avaliação do Desempenho dos Estudantes, feita por meio do ENADE, busca avaliar os alunos dos cursos de graduação, por meio de amostragem. Tem como objetivo geral avaliar o desempenho dos estudantes em relação aos conteúdos programáticos previstos nas diretrizes curriculares, às habilidades e competências para a atualização permanente e aos conhecimentos sobre a realidade brasileira, mundial e sobre outras áreas do conhecimento. Por fim, a Avaliação dos Cursos de Graduação (ACG) [9] é um procedimento utilizado pelo MEC para o reconhecimento ou renovação de reconhecimento dos cursos de 2 O Processo de Avaliação Integrada do Desenvolvimento Educacional e da Inovação da Área (Paideia) é um novo instrumento criado pelo SINAES com o objetivo de mapear o desenvolvimento dos processos formativos e as dinâmicas de cada área do conhecimento. 19 graduação representando uma medida necessária para a emissão de diplomas. O manual da ACG não foi estruturado nos mesmos moldes da Avaliação Externa de Instituições de Educação Superior, trazendo ainda características do modelo da ACE. Uma das diferenças principais são a ausência de parâmetros quantitativos e sua utilização genérica, aplicável a todos os cursos de graduação, diferentemente do modelo da ACE que trazia um manual específico por tipo de curso. Os processos de avaliação acima descritos são realizados pelo Instituto Nacional de Estudos e Pesquisas Educacionais Anísio Teixeira (INEP). No entanto, a avaliação dos cursos de pós-graduação permanece sendo feita pela Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (Capes). Outros detalhes sobre o SINAES podem ser obtidos em www.inep.gov.br. 20 2.2.3 - Avaliação Externa A Avaliação Externa é organizada de acordo com as dez dimensões definidas na Lei Nº 10.861, de 14 de abril de 2004, que instituiu o SINAES. Cada uma das dimensões é composta por indicadores, os quais são pontuados de 1 a 5, de acordo com os padrões e referencias estabelecidos nas normas. Para se chegar no conceito da dimensão, é calculada a média aritmética das pontuações dos indicadores. Com o intuito de minimizar erros no processo e possibilitando uma atribuição de conceitos de maior qualidade, quando a média aritmética dos indicadores (MAI) estiver entre dois valores inteiros (decimais de 0,4 a 0,7), cabe ao avaliador decidir, de acordo com as suas observações, a atribuição da nota da dimensão como sendo o primeiro número inteiro maior que a MAI ou o primeiro menor. Com o conceito de cada uma das dimensões, é feita uma média ponderada por pesos para finalmente definir o conceito final da avaliação. O conceito final também é definido em uma escala de 1 a 5, sendo os critérios de arredondamento similares aos aplicados na conceituação das dimensões. A TAB. 3 discrimina as dimensões e seus respectivos pesos. TABELA 3 Distribuição dos Pesos nas Dimensões do SINAES Dimensão Peso Dimensão 1: Missão e Plano de Desenvolvimento Institucional 5 Dimensão 2: Perspectiva Científica e Pedagógica Formadora: políticas, normas e estímulos para o ensino, a pesquisa e a extensão 30 Dimensão 3: Responsabilidade Social da IES 10 Dimensão 4: Comunicação com a sociedade 5 Dimensão 5: Políticas de pessoal, de carreira, de aperfeiçoamento, de condições de trabalho 20 Dimensão 6: Organização e Gestão da Instituição 5 Dimensão 7: Infra-estrutura física e recursos de apoio 10 Dimensão 8: Planejamento e Avaliação 5 Dimensão 9: Políticas de Atendimento aos Estudantes 5 Dimensão 10: Sustentabilidade financeira 5 Total 100 Fonte: Manual de Avaliação Institucional Externa [7] A pontuação dos indicadores forma a base da avaliação. A conceituação de cada um dos indicadores baseia-se nos critérios indicados pelo instrumento de avaliação. Além disso, alguns dos indicadores são classificados como imprescindíveis ou como não se aplica (NSA). 21 Os indicadores imprescindíveis representam condições obrigatórias para o acesso e a permanência no sistema de educação superior. Esses indicadores, definidos pela legislação em vigor [6][11], exigem no mínimo o conceito 3 para aprovação. Os indicadores NSA são aqueles cujo atendimento é opcional ao Centro Universitário ou à Faculdade, como forma de assegurar o respeito às suas identidades e diversidades. Quando um indicador NSA for descartado na avaliação, ele não entrará no cálculo da média aritmética para a conceituação da dimensão. A maioria dos critérios é de análise qualitativa, ou seja, a partir de uma descrição textual do critério para obtenção de um conceito, o avaliador deverá decidir em qual dos conceitos o aspecto avaliado melhor se enquadra. No entanto, alguns dos indicadores são conceituados de forma automática a partir das informações coletadas sobre o corpo docente. São eles: Titulação, Regime de Trabalho e Publicações/Produções. Todos eles pertencem à dimensão 5 e são calculados diretamente pelo sistema. Uma característica importante no tratamento dos indicadores de cálculo automático é que os parâmetros das faixas de conceitos são diferenciados por tipo de instituição acadêmica (universidades, centros universitários e faculdades). Na seção seguinte serão detalhados os indicadores de cálculo automático da Avaliação Externa que serão utilizados na formulação, bem como as suas fórmulas, parâmetros e faixas de conceitos. 22 2.2.4 - Cálculo de Indicadores Um quadro de horários melhor ou pior em termos de avaliação se resume a um corpo docente mais adequado ao cumprimento das metas. A dimensão que trata assuntos de arranjo do corpo docente é a dimensão 5, a segunda mais significativa no escopo da avaliação. Logo, os indicadores são os que interessam para subsidiar a formulação: • Titulação • Regime de Trabalho • Publicações/Produções Como esses indicadores possuem fórmulas de cálculo bem definidas, torna-se mais fácil representá-los na formulação do modelo matemático para definição dos quadros de horário. A seguir serão descritas as fórmulas de cálculo de cada um dos três indicadores. Indicador Titulação O cálculo do conceito do Indicador Titulação (MT) é dado pela seguinte fórmula: D NPNPNPMT DDMMEE )( ×+×+×= em que: − PE = Peso da Especialização = 10 − NE = Número de Docentes com Especialização − PM = Peso do Mestrado = 30 − NM = Número de Docentes com Mestrado − PD = Peso do Doutorado = 60 − ND = Número de Docentes com Doutorado − D = Total de Docentes De acordo com o tipo de instituição, as metas de qualidade para o conceito variam, de acordo com a TAB. 4. 23 TABELA 4 Conceitos do Indicador Titulação (MT) Conceito Universidades Centros Universitários Faculdades 1 0 ≤ MT < 13 0 ≤ MT < 12 0 ≤ MT < 11 2 13 ≤ MT < 16,6 12 ≤ MT < 14 11 ≤ MT < 12 3 16,6 ≤ MT < 20 14 ≤ MT < 16,6 12 ≤ MT < 14 4 20 ≤ MT < 25 16,6 ≤ MT < 20 14 ≤ MT < 16 5 25 ≤ MT 20 ≤ MT 16 ≤ MT Fonte: Manual de Avaliação Institucional Externa [7] Indicador Regime de Trabalho O cálculo do conceito do Indicador Regime de Trabalho (RT) é dado pela seguinte fórmula: D NPNPNPRT HHPPII )( ×+×+×= em que: − PI = Peso do Regime Integral = 60 − NI = Número de Docentes em Regime Integral − PP = Peso do Regime Parcial = 30 − NP = Número de Docentes em Regime Parcial − PH = Peso do Regime Horista = 10 − NH = Número de Docentes em Regime Horista − D = Total de Docentes Para entendimento do Regime de Trabalho, é necessário definir o que consiste cada um dos tipos. A definição dos regimes de trabalho é apresentada no QUADRO 1. De acordo com o tipo de instituição, as metas de qualidade para o conceito do indicador Regime de Trabalho variam de acordo com a TAB. 5. 24 QUADRO 1 Definição dos tipos de regime de trabalho Tipo Definição Regime Integral Regime cujos docentes são contratados com 40 horas semanais de trabalho na mesma instituição, nelas reservado o tempo de pelo menos 50% da carga horária destinada a atividades complementares3. Regime Parcial Regime cujos docentes são contratados com 12 ou mais horas semanais de trabalho na mesma instituição, nelas reservado pelo menos 25% da carga horária destinada a atividades complementares. Regime Horista Regime cujos docentes são contratados pela instituição exclusivamente para ministrar horas-aula, independentemente da carga horária contratada, ou que não se enquadrem nos outros regimes de trabalho acima definidos. Fonte: Manual de Avaliação Institucional Externa [7] TABELA 5 Conceitos do Indicador Regime de Trabalho (RT) Conceito Universidades Centros Universitários Faculdades 1 0 ≤ RT < 17,5 0 ≤ RT < 15 0 ≤ RT < 12,5 2 17,5 ≤ RT < 26,5 15 ≤ RT < 20 12,5 ≤ RT < 15 3 26,5 ≤ RT < 35 20 ≤ RT < 25 15 ≤ RT < 17,5 4 35 ≤ RT < 40 25 ≤ RT < 30 17,5 ≤ RT < 22,5 5 40 ≤ RT 30 ≤ RT 22,5 ≤ RT Fonte: Manual de Avaliação Institucional Externa [7] Indicador Publicações/Produções O cálculo do conceito do Indicador Publicações/Produções (N) é dado pela seguinte fórmula: DPPPPPPP nPnPnPnPnPnPnP N DPPTPIRTLA dpDPptPTpiPIrRtTlLaA ×++++++ ×+×+×+×+×+×+× = )( )( Onde, − PA = Peso atribuído aos artigos publicados em periódicos científicos indexados = 30 − na = Número de artigos publicados em periódicos científicos indexados, pelo corpo docente da instituição, nos últimos três anos − PL = Peso atribuído aos livros ou capítulos de livros publicados =20 3 Definem-se como atividades complementares àquelas que compreendem atividades de pesquisa, extensão, gestão, planejamento, estudos, avaliação e orientação de alunos. 25 − nl = Número de livros ou capítulos de livros publicados, pelo corpo docente da instituição, nos últimos três anos − PT = Peso atribuído aos trabalhos publicados em anais = 10 − nt = Número de trabalhos completos publicados em anais, pelo corpo docente da instituição, nos últimos três anos − PR = Peso atribuído aos resumos publicados em anais = 05 − nr = Número de resumos publicados em anais, pelo corpo docente da instituição, nos últimos três anos − PPI = Peso atribuído às propriedades intelectuais depositadas ou registradas = 15 − npi = Número de propriedades intelectuais depositadas ou registradas, do corpo docente da instituição, nos últimos três anos − PPT = Peso atribuído aos projetos e/ou produções artísticas, técnicas, culturais e científicos = 10 − npt = Número de projetos e/ou produções artísticas, técnicas, culturais e científicos, do corpo docente da instituição nos últimos três anos − PDP = Peso atribuído às produções didático-pedagógicas relevantes = 10 − ndp = Número de produções didático-pedagógicas relevantes, do corpo docente da instituição, nos últimos três anos; D = Total de Docentes De acordo com o tipo de instituição, as metas de qualidade para o conceito variam, de acordo com a TAB. 6. TABELA 6 Conceitos do Indicador Publicações/Produções (N) Conceito Universidades Centros Universitários Faculdades 1 0 ≤ N < 0,007145 0 ≤ N < 0,004287 0 ≤ N < 0,0021435 2 0,007145 ≤ N < 0,012861 0,004287 ≤ N < 0,007145 0,0021435 ≤ N < 0,004287 3 0,012861 ≤ N < 0,1429 0,007145 ≤ N < 0,07145 0,004287 ≤ N < 0,04287 4 0,1429 ≤ N < 0,2858 0,07145 ≤ N < 0,1429 0,04287 ≤ N < 0,08574 5 0,2858 ≤ N 0,1429 ≤ N 0,08574 ≤ N Fonte: Manual de Avaliação Institucional Externa [7] 26 2.3 - Normas Regionais Os sindicatos regionais de professores, periodicamente realizam o acordo, convenção ou dissídio coletivo que estabelecem várias cláusulas que regulamentam as relações trabalhistas do exercício profissional dos docentes. Entre aspectos relevantes à formação de um quadro de horários, estão a determinação quanto à duração máxima de uma aula, como 50 (cinqüenta) minutos no ensino superior4; a obrigatoriedade da concessão de descanso, mediante intervalo não remunerado, com duração mínima de 15 (quinze) minutos, após duas ou três aulas consecutivas; e a indenização das janelas entre aulas do mesmo turno quando resultante de alterações no horário de aulas após 30 (trinta) dias do início do período letivo. Outra situação importante está na realocação de professores a disciplinas. Não pode o empregador transferir o docente de uma disciplina para outra sem consentimento expresso do mesmo. Além disso, caso uma disciplina seja removida do currículo, o docente já contratado tem prioridade para reaproveitamento em outra disciplina, observada sua habilitação, em que haja vaga. Dependendo da unidade da Federação, podem ser definidos adicionais para atividades extra-classe, qualificação docente, entre outros. Esses adicionais podem implicar em custos para a instituição e que devem ser considerados ao dimensionar a distribuição de atividades aos professores. Os documentos relativos ao acordo, convenção ou dissídio são disponibilizados pelo sindicatos regionais dos professores. 4 Exemplos relativos ao contexto do Estado de Minas Gerais 27 2.4 - Organização e Normas Institucionais As peculiaridades de cada instituição motivam a adequação de restrições específicas para a elaboração de um quadro de horários. A partir de diferentes visões, as instituições podem ser classificadas em grupos, de acordo com as suas características: • Tipo de Instituição: as instituições podem ser classificadas como Universidades, Centros Universitários, Faculdades, etc. de acordo com a Legislação Brasileira em vigor; • Tipo de Currículo: as instituições podem adotar estratégias de currículos fixos, flexíveis ou semi-flexíveis; • Organização Espacial: geograficamente, as instituições podem estar organizadas em um único ou vários campus, que em muitos casos podem estar localizados até mesmo em outra cidade; • Disponibilidade de Recursos Específicos: de acordo com a disponibilidade de recursos específicos, uma instituição pode demandar a elaboração de quadros de horários que racionalizem o uso de laboratórios, auditórios ou qualquer outro recurso específico; • Políticas Pedagógicas: normas internas da instituição podem exigir diretrizes de alocação de disciplinas, diretrizes para alocação de professores e etc.; • Níveis de Formação: uma instituição pode ofertar cursos nos diversos níveis de ensino de acordo com a organização da educação superior; • Áreas de Formação dos Cursos: de acordo com a(s) área(s) de atuação de cada instituição, uma instituição poderá demandar características específicas para a criação de quadros de horários dos seus cursos. Conforme citado na seção Avaliação Institucional Externa, dependendo do tipo de instituição, os parâmetros de qualidade do corpo docente são diferentes. Quanto ao tipo de currículo, uma instituição poderá se organizar de forma diferente na estratégia de construção do quadro de horários. Em instituições que adotam currículo flexível, é mais comum a tentativa de se obter quadros de horários que maximizem o atendimento dos alunos nas escolhas pelas disciplinas ofertadas. Esse tipo de abordagem é conhecido na literatura como o problema de escalonamento de disciplinas (PED). Quando o currículo é fixo, ou seja, todos alunos de um determinado período deverão seguir o mesmo conjunto de 28 disciplinas ofertadas, a construção do quadro de horários se resume ao atendimento das ofertas de cada uma das turmas. Esse tipo de problema é conhecido na literatura como o problema de escalonamento turma-professor (PET). O currículo semi-flexível ocorre quando uma parte do curso, normalmente no final, pode ser selecionada pelo estudante a partir de um rol de opções. Essa situação é bem representada pelas disciplinas optativas e eletivas. Quanto à organização espacial, uma instituição pode estar organizada em diversos campi. Logo, considerando que exista uma distância significativa entre esses locais, torna-se inviável alocar professores para aulas consecutivas em diferentes campi, afetando dessa forma o quadro de restrições para a alocação de professores. Além disso, uma instituição necessita que seu quadro de horários racionalize a utilização de laboratórios, auditórios ou qualquer outro recurso específico, visto que sua disponibilidade normalmente é escassa. Quanto às políticas pedagógicas, registradas por meio de regimentos, portarias ou outras normas internas, a instituição poderá definir uma série de restrições ao problema de construção de um quadro de horários. Podem ser definidas restrições quanto à alocação de disciplinas visando a qualidade didático-pedagógica como, por exemplo, a proibição que duas disciplinas de alto grau de complexidade sejam escalonadas sucessivamente no mesmo dia, a fim de melhorar o rendimento dos alunos, assim como restrições quanto a carga horária máxima para duração de aulas geminadas; ou por exemplo que disciplinas com alto nível de repetência sempre fiquem escalonadas no mesmo horário da sua antecessora em termos de pré-requisito, tal que um repetente tenha como cursar novamente a disciplina do semestre anterior sem ser prejudicado para fazer as demais disciplinas do período seguinte. Quanto aos níveis de formação, de acordo com a legislação brasileira (FIG. 1), uma instituição poderá exigir a formação de quadros de horário que contemplem todas as situações específicas não gerando conflitos de escalonamento. Como por exemplo, se uma instituição possui cursos de graduação, pós-graduação lato sensu e de extensão, seu quadro de horários deverá contemplar que os cursos de graduação são em regime semestral, os de pós-graduação lato sensu em regime modular (cada disciplina corresponde um módulo cujo início e fim podem não coincidir com um semestre letivo) e os cursos de extensão podendo ter duração de semanas ou meses. 29 FIGURA 1 - Níveis de Formação da Educação Superior Brasileira Fonte: MEC Quanto à área de formação dos cursos, muitas características específicas de uma determinada área podem levar a criação de outras restrições na elaboração de um quadro de horários. Por exemplo, um curso da área de saúde exige um número máximo de alunos em aulas práticas. Enquanto isso, um curso de licenciatura exige um cumprimento de atividades de estágio curricular que devem ser desenvolvidas ao longo do semestre, impedindo portanto, a alocação de aulas nos horários correspondentes. Muitas dessas normas são regulamentadas pelas Diretrizes Curriculares Nacionais (DCN), emitidas pelo Conselho Nacional de Educação (CNE), que dispõem sobre os currículos e atividades específicas dos cursos. 30 2.5 - Competitividade e Custos em IES Particulares Com a atual competitividade de IES particulares, uma gestão de custos eficiente e eficaz, pode gerar vantagem perante a concorrência e principalmente subsidiar o investimento em outras atividades acadêmicas. O grande crescimento das IES particulares no Brasil se deu a partir da nova LDB. A partir de lá, o número de instituições cresceu de forma acelerada e atualmente, alguns reflexos dessa expansão são observados: • aumento no número de vagas ofertadas no ensino superior, • aumento da concorrência, • aumento da demanda por professores universitários especializados, • aumento das metas de qualidade no ensino superior. Com o aumento do número de vagas ofertadas e conseqüentemente a concorrência, as instituições de ensino superiores privadas tiveram que se deparar com a pressão pela redução dos preços dos cursos, o que implica diretamente em redução de receita. Além disso, outros problemas como inadimplência, evasão e vagas ociosas, tem assombrado o planejamento orçamentário das IES particulares. Com uma receita reduzida, cada vez mais se faz necessário o estabelecimento de uma gestão de custos eficiente tal que a instituição seja viável financeiramente e dessa forma, garanta a continuidade do projeto educacional. No entanto, a questão elementar está em como cortar despesas. Os custos de uma IES podem ser divididos em dois grandes grupos: diretos e indiretos. Os custos diretos estão vinculados a atividade de ensino, nos cursos ofertados, ou seja, na atividade fim. Já os custos indiretos são os custos da atividade meio, ou seja, responsáveis pelo funcionamento da estrutura de apoio à execução das atividades docentes. A maior parte dos gastos de uma IES está em sua folha de pagamento que compromete grande parte de seus recursos (mais que 50%). Na folha de pagamento também existe a distinção de custos diretos e indiretos. Os custos diretos são as despesas com pessoal docente em “sala de aula” executando atividades de ensino. Atividades de extensão, pesquisa ou de gestão são consideradas como custos indiretos, pois são atividades meio e não geram resultados diretamente. A redução de custos pode e deve se dar em todos os âmbitos institucionais a fim de garantir a viabilidade financeira desejada. No caso da redução de custos em folha de 31 pagamento, a possibilidade de remanejamento de gastos somente pode ser feita no âmbito dos custos indiretos, visto que os diretos estão associados à realização operacional dos cursos ofertados. Contrapondo aos esforços de contenção de gastos, estão as normas e exigências avaliativas que exigem patamares mínimos de qualidade, que por sua vez, possuem custos para implementação. Logo, deseja-se saber qual é o mínimo custo de operacionalização de todas as políticas institucionais, o atendimento a todas exigências de qualidade e o cumprimento de toda a oferta de cursos feita à sociedade. Portanto, a elaboração de um quadro de horários que minimize os custos indiretos docentes de uma instituição é de grande valia. Visto que o quadro de horários aborda apenas os custos diretos docentes (docentes atendendo a demanda de disciplinas), a otimização dos custos indiretos se dá pela análise das metas de qualidade exigidas do corpo docente por meio dos instrumentos de avaliação e legislação específica, associados aos reflexos que o quadro de horários gera na distribuição final de carga horária ao corpo docente, a qual abrange além das atividades de ensino, todas as demais atividades docentes. Na seção seguinte será descrito um cenário para exemplificar tal situação. 32 2.5.1 - Custos x Horário Suponha uma instituição do tipo universidade composta por um curso em implantação que deverá apenas ofertar as disciplinas de um período em dois turnos (matutino e noturno). A TAB. 7 relaciona as disciplinas que deverão ser ofertadas. TABELA 7 Carga horária por disciplina a ser ofertada Disciplina CH Semanal Demanda Manhã Demanda Noite Total CH Semanal Cálculo 4 4 4 8 Geometria Analítica 4 4 4 8 Algoritmos 4 4 4 8 Introdução 4 4 4 8 Metodologia 4 4 4 8 Total 20 20 40 Após analisar a habilitação dos docentes disponíveis, os docentes são atribuídos para executar a demanda de disciplinas previamente planejada. O QUADRO 2 exibe um quadro de horários que atende a demanda com 3 (três) professores. QUADRO 2 Um quadro de horários solução Segunda Terça Quarta Quinta Sexta Turno Horário Disciplina Prof. Disciplina Prof. Disciplina Prof. Disciplina Prof. Disciplina Prof. 1º H or ár io (7h 00 - 8h 40 ) Cálculo Adão Algoritmos Beto Cálculo Adão Algoritmos Beto Geometria Adão M an hã 2º Ho rá rio (9h 00 - 10 h4 0) Introdução Beto Metodologia Maria Geometria Adão Metodologia Maria Introdução Beto 1º Ho rá rio (19 h0 0 - 20 h4 0) Cálculo Adão Algoritmos Beto Cálculo Adão Algoritmos Beto Geometria Adão No ite 2º Ho rá rio (21 h0 0 - 22 h4 0) Introdução Beto Metodologia Maria Geometria Adão Metodologia Maria Introdução Beto 33 Considerando que exista também uma demanda por 8 horas semanais para uma atividade administrativa a ser cumprida pelo Prof. Adão, o quadro de distribuição de carga horária fica de acordo o QUADRO 3 e com um custo operacional 48 horas/semana5. QUADRO 3 Distribuição de carga horária semanal dos professores (1) Professor Carga Horária Cálculo Carga Horária Geometria Carga Horária Algoritmos Carga Horária Introdução Carga Horária Metodologia Total C.H. Ensino Total Comple mentar Carga Horária Total Regime de Trabalho Adão 8 8 - - - 16 8 24 Parcial Beto - - 8 8 - 16 0 16 Horista Maria - - - - 8 8 0 8 Horista TOTAL 8 8 8 8 8 40 8 48 Mesmo tendo atendido a demanda, a distribuição final dos professores não foi adequada, visto que o indicador Regime de Trabalho da Avaliação Institucional Externa [7] teria o valor 16,7. De acordo com as faixas de valor para definição do conceito para o indicador Regime de Trabalho em Universidades, o conceito final obtido seria 1, ou seja, muito fraco. De acordo com o modelo de otimização de Aplicação de Recursos Acadêmicos (APRAC), descrito nas próximas seções, a melhor composição do corpo docente a fim de atender a demanda com o mínimo custo operacional, seria ter um professor em regime integral e dois em regime parcial tal que o conceito seria máximo e o custo mínimo. O QUADRO 4 mostra uma possibilidade para a distribuição de horas dos professores tal que o conceito seja máximo. QUADRO 4 Distribuição de carga horária semanal dos professores (2) Professor Carga Horária Cálculo Carga Horária Geometria Carga Horária Algoritmos Carga Horária Introdução Carga Horária Metodologia Total C.H. Ensino Total Comple mentar Carga Horária Total Regime de Trabalho Adão 8 8 - - - 16 24 40 Integral Beto - - 8 4 - 12 4 16 Parcial Maria - - - 4 8 12 4 16 Parcial TOTAL 8 8 8 8 8 40 32 72 5 Para efeitos de simulação, considera-se que o custo de uma hora docente é o mesmo para qualquer situação, sendo que o custo monetário final é diretamente proporcional ao total de horas distribuídas. 34 Nessa nova proposta foi considerado que a Prof.ª Maria assumiu as aulas de Introdução no turno da manhã. Sendo assim, tanto a Prof.ª Maria quanto o Prof. Beto ficaram com 12 (doze) horas de ensino e 4 (quatro) horas complementares cada um no novo quadro de horários. O Prof. Adão foi enquadrado em regime integral. Portanto, como o indicador Regime de Trabalho da Avaliação Institucional Externa [7] assumiu o valor de 40, a distribuição final dos professores foi adequada, visto que o conceito final obtido foi 5, ou seja, o máximo. O custo operacional da nova proposta foi de 72 horas/semana que é mínimo. No entanto, supondo que existam restrições que impeçam que a Prof.ª Maria assuma as aulas de Introdução às segundas e sextas feiras no turno da manhã, sejam restrições de habilitação ou restrições de tempo, surge a necessidade da confecção de um novo quadro de horários. Supondo que o Prof. Beto não pode reassumir as aulas de Introdução no turno da manhã, e que a Prof.ª Maria fique apenas com suas aulas de Metodologia, surgiria a necessidade da contratação de um novo professor. Esse novo professor, o Prof. Paulo, seria um professor horista, o que faria com que o indicador Regime de Trabalho da Avaliação Institucional tivesse o valor 32,5, o que implica em um conceito final igual a 3, ou seja, regular. O QUADRO 5 mostra a nova distribuição de aulas obtida. QUADRO 5 Distribuição de carga horária semanal dos professores (3) Professor Carga Horária Cálculo Carga Horária Geometria Carga Horária Algoritmos Carga Horária Introdução Carga Horária Metodologia Total C.H. Ensino Total Comple mentar Carga Horária Total Regime de Trabalho Adão 8 8 - - - 16 24 40 Integral Beto - - 8 4 - 12 4 16 Parcial Maria - - - - 8 8 4 12 Parcial Paulo - - - 4 - 4 0 4 Horista TOTAL 8 8 8 8 8 40 32 72 É importante observar que mesmo não tendo havido modificação no custo total do quadro distribuição, o conceito no indicador regime de trabalho decresceu. Observando, ainda, que cada professor possui uma titulação, a entrada do novo docente impacta também nos conceitos dos indicadores titulação e publicações/produções da avaliação. 35 Portanto, ao designar professores a cumprir a demanda do quadro de horários, deve-se levar em consideração o arranjo final da alocação tal que seja possível trabalhar com o menor custo operacional, mas ao mesmo tempo obtendo conceitos de qualidade máximos. 36 2.6 - Conclusão A partir da definição do contexto, deve-se elaborar um modelo para a construção de um quadro de horários que seja capaz de trabalhar com um custo mínimo e indicadores de qualidade máximos. Para isso, a percepção do quadro de horários deverá extrapolar a fronteira da alocação de disciplinas e atingir os níveis de averiguação de outras atividades docentes responsáveis pela composição do quadro final de distribuição de aulas. Apenas a partir do quadro final é possível o cálculo dos indicadores automáticos da avaliação institucional. Apesar do problema de criação de quadros de horários ser um problema que pertencente à classe NP [23][29], o modelo a ser trabalhado deverá contemplar os aspectos de custos e avaliação tal que uma vez obtida uma solução, por meio de um método exato, ela seja ótima, nos aspectos de custos e avaliação, e tenha como garantia o atendimento de toda a demanda sem conflitos na alocação dos recursos docentes. 37 Capítulo 3 - Revisão Bibliográfica 3.1 - O Problema O problema de criação de quadro de horários, conhecido como timetabling, é um problema que consiste em escalonar uma seqüência de aulas entre professores e estudantes em um período de tempo pré-fixado (normalmente uma semana), atendendo a um conjunto de restrições de diversos tipos [50]. O problema de timetabling é um tipo especial de problemas do tipo scheduling [47], o qual vem sendo estudado há muitos anos. Existem muitas variações nas formulações dos problemas de quadros de horários devido às especificidades de cada Instituição e seu respectivo sistema educacional [15]. Da mesma forma, existem vários métodos utilizados para a resolução do problema. Schaerf [50] categorizou os problemas de timetabling em três categorias: • School Timetabling: conhecido também como Problema de Escalonamento Turma-Professor [58] (Class-Teacher Problem); • University Course Timetabling, conhecido também como Problema de Escalonamento de Disciplinas [58] (Course Scheduling Problem); • Examination Timetabling, conhecido também como Problema de Escalonamento de Exames (Exam Scheduling Problem). A primeira categoria consiste no escalonamento semanal de todas as turmas evitando conflitos de horários de professores e de turmas. Conforme frisado por Souza [54], esse problema “diz respeito à alocação das aulas de uma instituição com as características de uma escola secundária típica”. Logo, existem conjuntos disjuntos de turmas, os quais seguem um mesmo currículo, e um conjunto de professores e horários disponíveis para a realização das aulas. Deseja-se obter um quadro de horários tal que todas as turmas tenham todas as aulas devidas com os respectivos professores dentro do tempo definido. No entanto, em faculdades que adotam a estratégia de currículos rígidos, esse tipo de problema também é aplicável. Já a segunda categoria, refere-se aos problemas mais comumente encontrados nas universidades, as quais normalmente adotam sistemas de currículo flexível. Esse problema consiste no escalonamento de disciplinas no tempo tal que ocorram o mínimo de conflitos nas escolhas dos alunos. Para exemplificar a aplicação do problema, cada aluno pode se 38 matricular em disciplinas que compõem seu currículo. Essas disciplinas podem ser ofertadas em diversas turmas, em seus respectivos departamentos ou cursos, e cada uma delas pode estar sendo freqüentada por diversos alunos de currículos diferentes. Portanto, deseja-se criar um quadro de horários que atenda ao máximo a demanda dos alunos, respeitando as restrições de disponibilidade dos professores e salas. Por fim, a terceira categoria, corresponde ao problema do escalonamento de exames. Segundo Souza [54], “o objetivo primário é alocar cada exame a um horário, de forma que nenhum estudante tenha que fazer dois ou mais exames simultaneamente”. É também desejável que os exames fiquem o máximo distribuídos ao longo do seu período de realização tal que os alunos não fiquem sobrecarregados. Segundo Schaerf [50], alguns problemas podem ser classificados em dois grupos de acordo com suas características específicas. No mesmo período, Carter e Laporte [17] também propuseram categorias para os problemas de timetabling. No entanto, foram propostas cinco categorias. Três são equivalentes àquelas propostas Schaerf [50]. As outras duas categorias são: • Teacher Assignment, conhecido também como Problema de Alocação de Professores; • Classroom Assignment, conhecido também como Problema de Escalonamento de Salas; Mais tarde, Reis e Oliveira [43] definiram oito categorias de sub-problemas inter- relacionados com timetabling: • CTT – Class-Teacher Timetabling: corresponde à categoria School Timetabling definida por Schaerf [50]. Nesse tipo de problema, considera-se que a alocação dos professores e disciplinas às turmas já fora feita, restando portanto definir o local e horário de cada uma das aulas. • CT – Course Timetabling: corresponde à categoria University Course Timetabling definida por Schaerf [50]. Nesse tipo de problema, considera-se que a alocação dos professores às disciplinas ocorre previamente (embora seja necessária alguma flexibilidade). Em alguns casos, os estudantes ainda não estão alocados antes da realização do escalonamento. Essa questão é importante, pois segundo Reis e Oliveira [43], embora normalmente os estudantes já estão associados às disciplinas, isso não se aplica a todas as universidades. 39 • ET – Examination Timetabling: corresponde à categoria Examination Timetabling definida por Schaerf [50]. A alocação de salas ou de fiscais podem ser feitas antes ou depois de concluído o escalonamento. • SD – Section Definition: problema que ocorre em qualquer timetabling. Consiste em definir, para cada atividade, o número de seções ofertadas (como por exemplo, uma mesma disciplina dada a diferentes grupos de estudantes). • SS – Student Scheduling: este problema ocorre quando módulos são dados em múltiplas partes. Uma vez que os estudantes selecionaram seus módulos, eles deverão ser escalonados, sem conflitos e com um certo balanceamento da carga. • SA – Staff Allocation (Teacher Assignment): alocação de professores aos diferentes módulos de acordo com suas preferências, distribuição da carga ao longo do tempo. Em alguns casos, o escalonamento de professores é finalizado após dois ou três passos consecutivos. O primeiro passo consiste em selecionar os professores que serão responsáveis para cada um dos módulos. No segundo passo, são selecionados os professores que irão lecionar cada um dos módulos (de acordo com suas cargas horárias). Por fim, o terceiro passo consiste em associar cada uma das seções individuais a cada um dos professores. Em alguns casos, isso pode ficar em aberto (de forma flexível) até o final da geração do quadro de horários. • IA – Invigilator Assignment: esse problema é comum e está associado ao problema de escalonamento de exames. Consiste em alocar fiscais para a realização dos exames. Normalmente, o número de fiscais está relacionado ao número de estudantes e salas. • RA – Room Assignment: normalmente, todo problema de timetabling possui, em alguma fase, o escalonamento de salas. Basicamente, deve-se satisfazer restrições sobre tamanho, recursos especiais (como por exemplo: laboratórios, auditórios) e em alguns casos a localização. Segundo Reis e Oliveira [43], outras categorias de subproblemas podem ser definidas, no entanto, tratar-se-ia de problemas menos usuais ou importantes. Os problemas de timetabling possuem uma estrutura básica de acordo com os tipos de restrição. Segundo Burke [15], essas restrições são divididas em dois conjuntos: 40 • Restrições rígidas (Hard-constraints): nunca podem ser violadas para garantir a integridade de um quadro de horários. • Restrições flexíveis (Soft-constraints): são desejáveis, mas não absolutamente essenciais. De acordo com Braz Júnior [12], restrições flexíveis “nem sempre são menos importantes que restrições rígidas”, mas dificilmente levariam um quadro de horários ser descartado caso alguma fosse violada. Elas devem ser atendidas sempre que possível e pode- se considerar que existam prioridades entre elas. As restrições rígidas são aquelas que não permitem colisões, ou seja, um estudante não pode ser escalonado para duas ou mais disciplinas ao mesmo tempo, um professor não pode ser escalonado para duas ou mais atividades ao mesmo tempo, uma sala não pode ser ocupada simultaneamente para duas disciplinas, não se pode designar dois professores para mesma atividade na mesma turma e todos os envolvidos no quadro de horários devem estar adequadamente escalonados. As restrições flexíveis são desejáveis e como exemplo podem ser citadas as preferências do corpo docente, a não ocorrência de janelas entre as aulas e a não necessidade de trocas de sala entre aulas. 41 3.2 - Viabilidade versus Otimalidade Outra questão importante sobre o problema de timetabling é a abordagem dada para a obtenção da solução. Quando se deseja apenas obter uma solução viável a partir do conjunto de restrições que definem o problema, trata-se de um problema de busca ou de viabilidade, no qual o objetivo se limita a obter uma solução viável. Esse problema é demonstrado ser NP- Completo em [23], [26] e [59]. Algumas implementações trazem abordagens interativas, ou seja, permite a intervenção do usuário durante a construção do quadro de horários. Exemplos de implementações interativas podem ser encontradas em [60] e [19]. Quando o problema de timetabling é formulado como um problema de otimização, além de obter uma solução viável, deseja-se obter a solução ótima. Nesse caso, o problema é NP-Difícil [29] [25]. De acordo com Souza [54], nesses casos, algumas restrições flexíveis são incorporadas no objetivo a ser minimizado, tal que as restrições flexíveis sejam atendidas ao máximo, ou seja, minimizando a distância de viabilidade. Existe uma grande dificuldade em se definir o objetivo a ser otimizado em problemas de timetabling. Uma vez definida a função objetivo, a definição dos coeficientes continua sendo um problema. Conforme colocado por Daskalaki et al. [24], se todos os coeficientes da função objetivo forem iguais, o problema fica degenerado e todas as soluções viáveis serão ótimas. Logo, devido à volatilidade da função, ou seja, muitas soluções têm o mesmo valor de objetivo, o uso de métodos exatos é dificultado. Com um objetivo pouco explícito, diversas soluções devem ser exploradas antes de concluir que um resultado é ótimo, dificultando a convergência para a solução ótima. 42 3.3 - Métodos de Resolução Segundo Schaerf [50], as primeiras técnicas utilizadas para resolução dos problemas de timetabling foram heurísticas. Em seguida, começaram a ser trabalhadas outras técnicas baseadas em Programação Linear Inteira, Fluxos em Redes e Coloração de Grafos. Mais recentemente, abordagens baseadas em técnicas de busca, utilizadas na área de Inteligência Artificial, como por exemplo, Simulated Annealing, Busca Tabu, Algoritmos Genéticos, Programação Lógica Restrita. Diversos trabalhos foram reportados na literatura. Na linha de coloração de grafos está o trabalho de Werra [58] entre outros ([13],[20],[41],[55]). Na linha da Programação Linear Inteira, vários autores resolveram o problema de timetabling. Entre eles, destaca-se o trabalho de Tripathy [57], o qual utilizou a técnica de relaxação lagrangeana na resolução do problema. Outros trabalhos são encontrados em [24] e [42]. Nas linhas de Busca Tabu e Simulated Annealing, temos [1], [48], [49] e [51]. Na linha da Programação Lógica Restrita, temos [30][32][39][46]. Na linha de algoritmos genéticos, temos [2], [21], [22], [44] e [45]. Outras abordagens podem ser vistas na literatura, como por exemplo a utilização de redes neurais [52] e outras técnicas de Inteligência Artificial [53]. Akkoyunlu [3] apresenta um modelo linear para o escalonamento de disciplinas. Em seu survey, Schaerf [50] descreve algumas das técnicas acima citadas. 43 3.4 - Modelos Timetabling Nesta seção são apresentadas as formulações que definem cada uma das cinco classes de problemas timetabling enumeradas nas seções anteriores 3.4.1 - Problema de Escalonamento Turma-Professor (PET) A formulação abaixo é apresentada por Schaerf [50] e é baseada no trabalho de Werra [58]. O problema consiste em atribuir aulas aos períodos de modo que nenhum professor ou turma esteja envolvido em mais de uma aula ao mesmo tempo. Então, considerando: − C = conjunto de turmas, sendo ci ∈ C e i = 1..m; − T = conjunto de professores, sendo tj ∈ T e j = 1..n; − P = conjunto de períodos, sendo pk ∈ P e k = 1..p. As seguintes informações devem ser consideradas no modelo: − rij = número de aulas que o professor j deve dar à turma i. − dijk = desejo do professor j para ser designado para a turma i no período k, sendo 0 quando desejar muito. Seja a seguinte variável de decisão: − xijk = 1 se o professor j foi designado para a turma i no período k, 0 caso contrário. Então, o seguinte modelo de otimização é proposto: ∑∑∑ = = = m i n j p k ijkijk xd 1 1 1 min sujeito a: ij p k ijk rx =∑ =1 ∀ i=1..m, j=1..n (1) 1 1 ≤∑ = n j ijkx ∀ i=1..m, k=1..p (2) 1 1 ≤∑ = m i ijkx ∀ j=1..n, k=1..p (3) { }1,0∈ijkx ∀ i=1..m, j=1..n, k=1..p (4) 44 As restrições (1) garantem que cada professor leciona o número correto de aulas para cada turma. As restrições (2) garantem que cada professor está envolvido em no máximo uma aula por período. As restrições (3) garantem que cada turma está envolvida em no máximo uma aula por período. Esse é um modelo simplificado, que pode ser resolvido em tempo polinomial. Ele não contempla indisponibilidades de professores e nem pré-alocações. A seguir, apresenta-se um modelo PET com uma abordagem mais completa. Então, deverão também ser consideradas as seguintes informações: cik = 1 se a turma i estiver disponível no período k, 0 caso contrário. tjk = 1 se o professor j estiver disponível no período k, 0 caso contrário. pijk = 1 se o professor j estiver pré-alocado para a turma i no período k, 0 caso contrário. ∑∑∑ = = = m i n j p k ijkijk xd 1 1 1 min sujeito a: ij p k ijk rx =∑ =1 ∀ i=1..m, j=1..n (5) ik n j ijk cx ≤∑ =1 ∀ i=1..m, k=1..p (6) jk m i ijk tx ≤∑ =1 ∀ j=1..n, k=1..p (7) ijkijk px ≥ ∀ i=1..m, j=1..n, k=1..p (8) { }1,0∈ijkx ∀ i=1..m, j=1..n, k=1..p (9) As restrições (5) garantem que cada professor leciona o número correto de aulas para cada turma. As restrições (6) garantem que cada professor está envolvido em no máximo uma aula por período, mas condicionado a disponibilidade do professor naquele período. As restrições (7), de forma análoga, garantem que cada turma está envolvida em no máximo uma aula por período caso a mesma tenha disponibilidade. Por fim, as restrições (8) exigem que todas as pré-alocações sejam atendidas. A obtenção de um quadro de horários utilizando o modelo PET apresentado é geralmente um problema NP-Difícil [29]. 45 3.4.2 - Problema de Escalonamento de Disciplinas (PED) A formulação abaixo é apresentada por Schaerf [50] e é também baseada no trabalho de Werra [58]. O problema consiste em escalonar um conjunto de disciplinas para cada curso dado um número de salas e de períodos. Então, considerando: − D = conjunto de disciplinas, sendo Ki ∈ D e i = 1..q; − ki = número de aulas da disciplina Ki ; − G = conjunto de currículos, sendo Sl ∈ G e l = 1..r . Pode-se entender um currículo como sendo um conjunto de disciplinas que possuem estudantes comuns, implicando na impossibilidade de escalonar disciplinas de um mesmo currículo em um mesmo período; − p = número de períodos; As seguintes informações devem ser consideradas no modelo: − lk = número máximo de disciplinas que podem ser escalonadas no período k (pode estar relacionado ao número de salas disponíveis); − dik = desejo de que uma aula da disciplina Ki seja escalonada no período k. Seja a seguinte variável de decisão: − yik = 1 se uma aula da disciplina Ki for escalonada no período k, 0 caso contrário. Então, o seguinte modelo de otimização é proposto: ∑∑ = = q i p k ikik yd 1 1 max sujeito a: i p k ik ky =∑ =1 ∀ i=1..q (10) k q i ik ly ≤∑ =1 ∀ k=1..p (11) 1≤∑ ∈ lSi iky ∀ l=1..r, k=1..p (12) { }1,0∈iky ∀ i=1..q, k=1..p (13) As restrições (10) garantem que cada disciplina tem o número correto de aulas. As restrições (11) garantem que a cada período, o número de aulas não é maior que o número de 46 salas. As restrições (12) garantem não haver conflitos de disciplinas de um mesmo currículo, ou seja, que as mesmas não sejam escalonadas no mesmo período visto que possuem alunos em comum. A obtenção de um quadro de horários utilizando o modelo PED proposto é geralmente um problema NP-Difícil [29]. 47 3.4.3 - Problema de Escalonamento de Exames (PEE) A formulação abaixo é apresentada por Schaerf [50]. O problema consiste em escalonar um conjunto de exames, correspondentes às disciplinas ofertadas em um determinado tempo. Nesse problema, a função objetivo tenta evitar que um estudante faça dois exames em períodos consecutivos. Então, considerando: − D = conjunto de disciplinas, com Ki ∈ D e i = 1..q, sendo que a cada disciplina está associado um exame; − E = conjunto de grupos de exames, sendo Sl ∈ E e l = 1..r . Para cada Sl, existem estudantes que devem fazer todos os exames de Sl ; − p = número de períodos; As seguintes informações devem ser consideradas no modelo: − lk = número máximo de exames que podem ser escalonados no período k. Seja a seguinte variável de decisão: − yik = 1 se o exame da disciplina Ki for escalonado no período k, 0 caso contrário. Então, o seguinte modelo de otimização é proposto: ∑∑∑ − = = ∈ + 1 1 1 )1(min p k r l Sj kjik l yy sujeito a: 1 1 =∑ = p k iky ∀ i=1..q (14) k q i ik ly ≤∑ =1 ∀ k=1..p (15) 1≤∑ ∈ lSi iky ∀ l=1..r, k=1..p (16) { }1,0∈iky ∀ i=1..q, k=1..p (17) As restrições do PEE desempenham as mesmas condições no PED. A obtenção de um escalonamento de exames utilizando o modelo PEE é geralmente um problema NP-Difícil [29]. 48 3.4.4 - Problema de Alocação de Professores (PAP) A formulação abaixo é adaptada a partir da apresentada por McClure e Wells [38]. O problema consiste em escalonar professores a fim de atender a todas as disciplinas, maximizando a preferência docente. Seja: − T = conjunto de professores, sendo tj ∈ T e j = 1..n; − D = conjunto de disciplinas, sendo Ki ∈ D e i = 1..q; − ki = número de aulas da disciplina Ki ; − E = conjunto de escalonamentos, sendo m ∈ E; − Ej = conjunto de escalonamentos viáveis para o professor j, sendo Ej ⊆ E, obtido a partir do conjunto de todas as combinações possíveis para as disciplinas que o professor pode lecionar, observando a carga docente e tempos para preparação de aulas. Seja a seguinte variável de decisão: − xjm = 1 se o professor j for alocado no escalonamento m, 0 caso contrário. Devem ser consideradas ainda, as seguintes informações: − ujm = medida de utilidade relativa ao professor j ser alocado no escalonamento m; − cjmi = número de vezes que a disciplina i aparece no escalonamento m para o professor j. Logo, tem-se o seguinte modelo matemático: ∑ ∑ = ∈ n j Em jmjm j xu 1 max sujeito a: 1=∑ ∈ jEm jmx ∀ j=1..n (18) i n j Em jmjmi kxc j =∑∑ = ∈1 ∀ i=1..q (19) { }1,0∈jmx ∀ j=1..n, m∈ Ej (20) As restrições (18) exigem que cada professor esteja associado a apenas um escalonamento. As restrições (19) exigem que os escalonamentos associados aos professores atendam ao número correto de aulas para cada disciplina. Afim de reduzir o número de 49 variáveis, o número total de escalonamentos possíveis para cada professor é reduzido. Segundo McClure e Wells [38], apenas os escalonamentos com maior valor de utilidade são considerados. 50 3.4.5 - Problema de Alocação de Salas de Aula (PASA) A formulação abaixo é adaptada a partir da apresentada por Gosselin e Truchon [31]. O problema consiste em alocar salas de aula de acordo com uma determinada demanda. Nesse problema, deseja-se minimizar uma função de penalidades. Então, considerando: − H = conjunto de horários considerados em um dia, sendo Hh ∈ H e h = 1..NH; − R = conjunto de tipos de requisições, sendo Rd ∈ R e d = 1..ND; − Ed = conjunto de requisições do tipo Rd; − S = conjunto de categorias de salas, sendo Ss ∈ S e s = 1..NS; − Fs = conjunto de salas da categoria Ss; − Pd = conjunto de categorias de salas que podem atender requisições do tipo Rd. Para qualquer conjunto finito E, define-se n(E) como sendo a cardinalidade do conjunto. A fim de nunca se obter inviabilidade na solução, define-se que a categoria de sala SNS é composta por salas fictícias, as quais podem atender qualquer requisição, e que ( ) ( )∑≥ d dS EnFn NS . O uso de salas fictícias tem uma elevada penalidade associada à função objetivo. Seja então a seguinte variável de decisão: − xsd denota o número de requisições do tipo Rd que serão atendidas com salas do tipo Ss, sendo Ss ∈Pd . As seguintes informações devem ser consideradas no modelo: − csd = penalidade associada a cada xsd . − adh = igual a 1 se o horário Hh está envolvido em requisições do tipo Rd, sendo 0 caso contrário. Então, o seguinte modelo de otimização é proposto: ∑ ∑ = ∈ ND d PS sdsd ds xc 1 min sujeito a: )( 1 sS ND d sddh Fnxa ≤∑ = ∀ h=1..NH , s = 1..NS (21) )( d PS sd Enx ds =∑ ∈ ∀ d=1..ND (22) 51 +Ζ∈sdx ∀ d=1..ND, Ss ∈PD (23) As restrições (21) garantem que em um dado horário, não são alocadas mais salas do que a disponibilidade correspondente de acordo com as categorias. As restrições (22) garantem que todas as solicitações são atendidas. Em uma segunda fase, as salas específicas são alocadas a cada uma das solicitações, de acordo com suas categorias. Segundo Gosselin e Truchon [31], esta formulação pode ser resolvida em tempo polinomial, mas, no entanto, em geral, conforme colocado por Carter e Tovey [16], o problema é NP-Difícil. 52 3.5 - O modelo APRAC O modelo de Aplicação de Recursos Acadêmicos (APRAC), é um modelo de programação linear destinado a computar o mínimo de carga horária necessária para atender uma demanda de ensino de acordo com as exigências dos indicadores de regime de trabalho definidos no processo de avaliação institucional [7]. O modelo foi proposto primeiramente em [37] e seu propósito era municiar de informações gerenciais os gestores de IES para estimar a quantidade mínima de carga horária complementar que deveria ser alocada ao corpo docente. Logo, o modelo é capaz de informar o limite inferior para os custos de alocação docente a partir de dada demanda, visto que ele trabalha informações sobre carga horária de ensino e carga horária complementar. A carga horária de ensino deve atender a demanda planejada e a carga horária complementar é indiretamente minimizada atendendo as restrições de qualidade definidas. O modelo pode ser aplicado com ou sem as restrições de integralidade às variáveis de decisão. Quando o modelo é tratado como um problema de programação linear puro, é possível identificar os custos marginais associados a cada uma das variáveis. No entanto, no mundo real, as variáveis somente podem assumir valores inteiros. Logo, o modelo deve ser descrito como um problema de programação linear inteira. Segue abaixo a formulação matemática do modelo APRAC. Seja: − J = conjunto de regimes de trabalho nos quais um docente pode estar enquadrado. − I = subconjunto de regimes de trabalho do tipo tempo integral => I ⊂ J. − pj = variável de decisão, indicando quantos professores serão alocados no regime de trabalho j. − ej = total de horas destinadas a atividades de ensino de cada regime de trabalho j. − ch = carga horária semanal total de ensino demandada. − pesoj = peso que o regime de trabalho j possui na avaliação institucional. − MRT = meta de qualidade do indicador regime de trabalho para atingir o conceito máximo na avaliação institucional. − MTI = meta de docentes em regime de trabalho tempo integral com vistas ao atendimento da LDB e do Decreto nº 5.786, dependendo do tipo de organização acadêmica. 53 − cj = custo mensal de um docente alocado no regime de trabalho j. O custo é proporcional à quantidade de carga horária alocada ao docente. Logo, tem-se a seguinte formulação para o APRAC: ∑ ∈Jj jjcpmin sujeito a: chep Jj jj ≥∑ ∈ (1) ∑∑ ∈∈ ≥ Jj j Jj jj pMRTpesop (2) ∑∑ ∈∈ ≥ Jj j Ij j pMTIp (3) 0≥jp ∀ j ∈J (4) Ζ∈jp ∀ j ∈J (5) A restrição (1) garante o atendimento da demanda de carga horária. A restrição (2) garante o conceito máximo na avaliação do indicador Regime de Trabalho. Já a restrição (3) garante os percentuais de docentes em tempo integral estabelecidos na legislação de acordo com o tipo de instituição. As restrições (4) garantem a não negatividade das variáveis de decisão e quando o modelo é resolvido com as restrições de integralidade, as restrições (5) são consideradas. A partir dos resultados obtidos no processo de otimização do modelo APRAC, ou seja, os custos marginais associados a cada pj e a combinação ótima do número de professores em cada regime de trabalho a fim de atender toda a demanda de carga horária de atividades de ensino, é possível saber os limites inferiores para a alocação de recursos acadêmicos para uma instância, assim como também, compreender em nível macro quais são as direções que devem ser tomadas para a redução de custos operacionais. 54 3.5.1 - Indicadores Referenciais do APRAC O modelo APRAC define limites inferiores referenciais para a alocação de recursos acadêmicos. Esses limites são expressos por meio de alguns indicadores referenciais definidos a seguir: 1. CHTM – Carga Horária Total Mínima: é a carga horária total alocada aos professores na solução ótima do APRAC para uma determinada instância; 2. CPLM – Carga Horária Complementar Mínima: é a carga horária complementar total alocada aos professores na solução ótima do APRAC para uma determinada instância; 3. NPM – Número Total Mínimo de Professores: é o número de professores alocados na solução ótima do APRAC para uma determinada instância; 4. NTIM – Número Total Mínimo de Professores em Regime Integral: é o número de professores alocados em regime de trabalho integral na solução ótima do APRAC para uma determinada instância; Os indicadores referenciais deverão ser utilizados para a definição de índices de avaliação do grau de eficiência de uma alocação de professores. 55 3.5.2 - Análises sobre os Indicadores Referenciais A partir da análise de sucessivas execuções do modelo APRAC, pode-se observar o comportamento dos indicadores referenciais à medida que a carga horária a ser atendida cresce. O GRAF. 1 demonstra que o crescimento da carga horária total mínima (CHTM) é linear em relação à carga horária de ensino (CHE) demandada. Como era de se esperar, a CHTM para as universidades é maior que para os centros universitários, que por sua vez é maior que para as faculdades, visto que a comparação foi realizada utilizando um mesmo conceito no indicador Regime de Trabalho da Avaliação Institucional. CHTM por tipo IES (Conceito 5) 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária de Ensino Semanal CH T - Ca rg a H o rá ria To ta l S e m a n a l U5 C5 F5 GRÁFICO 1 - Carga Horária Total Mínima por tipo de IES Legenda: U5 – Universidade (Conceito 5) C5 – Centro Universitário (Conceito 5) F5 – Faculdade (Conceito 5) Essa linearidade do GRAF. 1 pode ser comprovada analisando a proporção entre a CHTM e a CHE (GRAF. 2), ou seja, quão maior a CHTM é em relação a CHE percentualmente. Esse valor tende a ser constante à medida que a CHE cresce, demonstrando que a carga horária total fica diretamente proporcional a demanda de carga horária de ensino. Logo, é possível estimar a CHTM a partir da CHE sem mesmo instanciar o modelo APRAC. Por meio dos gráficos que demonstram a proporção entre CHTM e CHE (GRAF. 2, 3, 4 e 5), pode-se perceber também a variação da quantidade de recursos hora percentuais são necessários para mudar de um conceito para outro ou de uma modalidade de Instituição para outra. 56 Proporção CHTM/CHE (Conceito 5) 0,00% 10,00% 20,00% 30,00% 40,00% 50,00% 60,00% 70,00% 80,00% 90,00% 100,00% 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária Ensino Semanal U5 C5 F5 GRÁFICO 2 – Proporção CHTM/CHE por tipo de IES Legenda: U5 – Universidade (Conceito 5) C5 – Centro Universitário (Conceito 5) F5 – Faculdade (Conceito 5) Proporção CHTM/CHE (Universidades) 0,00% 10,00% 20,00% 30,00% 40,00% 50,00% 60,00% 70,00% 80,00% 90,00% 100,00% 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária Ensino Semanal U5 U4 U3 GRÁFICO 3 – Proporção CHTM/CHE nas Universidades Legenda: U5 – Universidade (Conceito 5) U4 – Universidade (Conceito 4) U3 – Universidade (Conceito 3) 57 Proporção CHTM/CHE (Centros Universitários) 0,00% 10,00% 20,00% 30,00% 40,00% 50,00% 60,00% 70,00% 80,00% 90,00% 100,00% 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária Ensino Semanal C5 C4 C3 GRÁFICO 4 – Proporção CHTM/CHE nos Centros Universitários Legenda: C5 – Centros Universitários (Conceito 5) C4 – Centros Universitários (Conceito 4) C3 – Centros Universitários (Conceito 3) Proporção CHTM/CHE (Faculdades) 0,00% 5,00% 10,00% 15,00% 20,00% 25,00% 30,00% 35,00% 40,00% 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária Ensino Semanal F5 F4 F3 F2 F1 GRÁFICO 5 – Proporção CHTM/CHE nas Faculdades Legenda: F5 – Faculdade (Conceito 5) F4 – Faculdade (Conceito 4) F3 – Faculdade (Conceito 3) F2 – Faculdade (Conceito 2) F1 – Faculdade (Conceito 1) 58 Uma observação interessante sobre os gráficos anteriormente apresentados é que como as universidades devem cumprir um mínimo de 33% do corpo docente em tempo integral e os centros universitários 20% (TAB. 2), os conceitos 4 e 5 são coincidentes aos valores do conceito 3. Isso não acontece para as faculdades, que no caso de trabalharem com o conceito 1, a CHTM é igual a CHE, ou seja, não existe a necessidade de carga horária complementar (a curva F1 toca o eixo no GRAF. 5). Quanto ao número de professores mínimo (NPM) pode-se observar que o número mínimo de professores em um centro universitário é menor que em uma universidade. No entanto, para as faculdades, o número mínimo se apresentou maior que para os demais tipos de IES, como pode ser observado no GRAF. 6. Isso ocorre devido ao fato de que para as faculdades não existe exigência quanto o número de professores em tempo integral e as metas para o indicador regime de trabalho são baixas. Visto isso, o número de professores pouco interfere na alocação de recursos complementares, exigidos por meio dos regimes de trabalho tempo integral, permitindo, portanto, se trabalhar com um número maior de docentes. Essa característica pode inclusive facilitar a montagem de quadros de horários nas faculdades pois pode-se ter mais professores disponíveis para a alocação. NPM - Número Professores Mínimo 0 50 100 150 200 250 300 350 400 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária de Ensino Semanal N º Pr o fe ss o re s F5 U5 C5 GRÁFICO 6 - Número de Professores Mínimo por tipo de IES Legenda: U5 – Universidade (Conceito 5) C5 – Centro Universitário (Conceito 5) F5 – Faculdade (Conceito 5) 59 Quanto ao número de professores em tempo integral, pode-se observar que o percentual se estabiliza a partir de uma determinada quantidade de CHE a ser atendida. O percentual para as universidades é maior que o percentual dos centros universitários, que por sua vez é maior que o percentual para as faculdades, o qual é praticamente zero (GRAF. 7, 8 e 9). % Professores em Tempo Integral (NTIM/NPM) 0,0% 10,0% 20,0% 30,0% 40,0% 50,0% 60,0% 70,0% 80,0% 90,0% 100,0% 0 1000 2000 3000 4000 5000 6000 7000 8000 CHE - Carga Horária de Ensino Semanal U5 C5 F5 GRÁFICO 7 - Percentual de Professores em Tempo Integral por tipo de IES Legenda: U5 – Universidade (Conceito 5) C5 – Centro Universitário (Conceito 5) F5 – Faculdade (Conceito 5) 60 % Professores em Tempo Integral (NTIM/NPM) por Conceito - Universidades 0,0% 10,0% 20,0% 30,0% 40,0% 50,0% 60,0% 70,0% 80,0% 90,0% 100,0% 0 2000 4000 6000 8000 CHE - Carga Horária de Ensino Semanal U5 U4 U3 Lei GRÁFICO 8 - Percentual de Professores em Tempo Integral nas Universidades Legenda: U5 – Universidade (Conceito 5) U4 – Universidade (Conceito 4) U3 – Universidade (Conceito 3) Lei – Limite definido na legislação (Vide TAB. 2) % Professores em Tempo Integral (NTIM/NPM) por Conceito - Centros Universitários 0,0% 10,0% 20,0% 30,0% 40,0% 50,0% 60,0% 70,0% 80,0% 90,0% 100,0% 0 2000 4000 6000 8000 CHE - Carga Horária de Ensino Semanal C5 C4 C3 Lei GRÁFICO 9 - Percentual de Professores em Tempo Integral nos Centros Universitários Legenda: C5 – Centro Universitário (Conceito 5) C4 – Centro Universitário (Conceito 4) C3 – Centro Universitário (Conceito 3) Lei – Limite definido na legislação (Vide TAB. 2) 61 Capítulo 4 - Modelagem do Problema Com base no cenário do Sistema de Ensino Superior Brasileiro, busca-se a definição de um modelo, associado a um processo, para definir um quadro de horários eficiente. O escopo é limitado, ou melhor, focado, para as IES particulares, visto que essas instituições devem se manter com recursos próprios e por isso, a gestão de custos eficiente é um requisito primordial. Quanto à legislação a ser atendida, são abordados requisitos apontados no SINAES, aplicáveis às IES brasileiras de modo geral, tanto públicas quanto privadas. 4.1 - Processo de Elaboração de um Quadro de Horários Toda a estrutura de uma instituição se organiza em prol da realização de um conjunto de atividades, as quais são escalonadas em um quadro de horários. Por isso, o processo de elaboração de um quadro de horários pode ser dito como estrutural em uma IES. Esse processo é realizado em fases compreendidas em um período de tempo. Para o caso das IES particulares, que na maioria dos casos adotam a estratégia de currículos rígidos, ou seja, o aluno é obrigado a seguir uma seqüência de disciplinas obrigatórias, com pré-requisitos, até sua formação, toda a modelagem do processo assume que existem currículos a serem cumpridos pelos alunos ingressantes nas instituições, com pouca flexibilidade para disciplinas do tipo optativas ou eletivas. Na primeira fase do processo, denominada elaboração do plano de oferta, está o gerenciamento das grades curriculares dos cursos a serem ofertadas. Não é viável pensar que os cursos possuem grades imutáveis ao longo do tempo. Dessa forma, o dinamismo da evolução das grades curriculares dos cursos é um fator que impacta diretamente no processo da construção do quadro de horários, tal que o processo seja aplicável ao dia a dia das IES. As grades curriculares definem temporalmente, o conjunto de disciplinas que deverão ser ofertadas no período letivo seguinte, de acordo com as turmas de alunos ingressantes em cada processo seletivo realizado e seu respectivo currículo. Nessa fase, devem ser abordadas também situações específicas como, por exemplo, o de oferta de turmas especiais e de disciplinas optativas. Como resultado da primeira fase, define-se o plano de ofertas de disciplinas. Pode-se observar que o plano de ofertas já pode delinear programações de custos 62 visto que independente de quando e onde elas ocorrerão, o custo hora para a realização das atividades já está definido. Na segunda fase, a partir do plano de ofertas, começa uma nova etapa que se resume a definir o quadro de ofertas, ou seja, definir o posicionamento de cada uma das disciplinas na grade de horários semanal. A definição do quadro de ofertas subsidia o planejamento institucional, não somente o do aluno, mas como também dos setores administrativos e do corpo docente. A FIG 2 mostra a seqüência das fases. FIGURA 2 - Fases do Processo Essa abordagem permite que as informações sobre a oferta já sejam divulgadas sem mesmo haver a designação dos professores às disciplinas. Na prática é o que ocorre visto que um docente pode ser contratado até poucos dias antes do início de um período letivo enquanto a matrícula dos alunos ocorre com uma certa antecedência. Além disso, entre o período de divulgação das disciplinas ofertadas e a matrícula dos alunos até o início das aulas, podem ocorrer mudanças nas disponibilidades dos professores, o que faria com que a alocação tivesse que ser alterada. Uma vez que o quadro de ofertas está disponível com antecedência, é possível que o aluno programe suas disciplinas, faça seu plano orçamentário, e por fim, decida em quais unidades de oferta de disciplinas irá se matricular. Essa organização de fases traz também benefícios ao corpo docente. A tarefa de planejamento das disciplinas pretendidas pelo professor é facilitada visto que os horários nas quais cada uma das ofertas ocorrerá são divulgados com antecedência. Logo, em instituições onde existem vários professores que não trabalham em regime integral, torna-se mais fácil planejar a alocação. Um docente, sabendo exatamente o horário das disciplinas, pode, por exemplo, buscar outras aulas em outros locais com a segurança de que não será surpreendido 63 minutos antes de começar o trabalho com a informação que seus horários estão sendo modificados. Na parte administrativa, os benefícios são obtidos a partir da antecedência para a realização das ações. Por exemplo, uma equipe de infra-estrutura tem mais tempo para a preparação de salas de aula para receber os alunos matriculados nas unidades de oferta. Uma equipe de informática poderá organizar com antecedência sua matrícula on-line, assim como também a secretaria na divulgação do que será ofertado etc. Essa fase de elaboração do quadro de oferta pode ser auxiliada por um modelo matemático, buscando, por exemplo, uma organização das unidades de oferta de disciplinas tal que sejam minimizadas as janelas, que disciplinas que necessitem de recursos especiais não sejam escalonadas nos mesmos horários, ou que disciplinas que devam ser ofertadas em dias diferentes sejam devidamente escalonadas. Outros critérios didático-pedagógicos também podem ser utilizados para a construção do quadro de ofertas. Para isso, vários modelos e métodos propostos na literatura podem ser adaptados e utilizados, tanto com propostas interativas como propostas do tipo automáticas. Como exemplo, tem-se o trabalho proposto por Chaves [19], que permite a criação de quadros de horários interativos. White e Wong [60] também propuseram um sistema interativo para a definição de um quadro de horários. A principal diferença é que nesse caso ainda não existe a restrição de que “um determinado professor é quem leciona a disciplina”. Parte-se do pressuposto que o resultado do processo da segunda fase, ou seja, o quadro de ofertas consolidado foi construído de alguma forma, seja manual, automática ou interativa, e, portanto, será considerado como dado de entrada para a execução da terceira fase. Por fim, a terceira fase, denominada alocação de professores, consiste na elaboração final do quadro de horários, ou seja, acoplar ao quadro de oferta os recursos docentes para a realização das atividades. Consiste em alocar o corpo docente de uma forma eficiente para cumprir o quadro de ofertas. Na terceira fase existem dois processos macro: a otimização do modelo APRAC e a alocação de professores (FIG. 3). Nessa fase entram os aspectos para a definição de uma alocação eficiente. No contexto proposto das IES particulares, a alocação tem duas componentes principais: o custo e o conceito de avaliação. 64 4.2 - Alocação de Professores Segundo Carter e Laporte [17], os problemas de quadros de horários podem ser vistos como um problema de alocação multidimensional onde estudantes e professores são alocados em cursos que são alocados em salas e horários. Reis e Oliveira [43] lembraram que essa multidimensionalidade do problema indica que não temos um problema único de quadros de horários, conforme indicado nas seções anteriores. No entanto, os problemas de quadros de horários abordados na literatura tem se especializado nos problemas de escalonamento turma- professor, escalonamento de disciplinas e escalonamento de exames. Outra questão é a definição do objetivo, que normalmente está associada à preferência docente, diminuição de janelas de tempo etc. Na área de alocação de professores, são encontrados menos trabalhos. Entre eles, vale destacar o de Hultberg e Cardoso [33], que tem como objetivo minimizar o número de disciplinas distintas alocadas a um professor. Teixeira et al [55] propuseram um trabalho de alocação de professores para atendimento de carências diante a expansão de demanda. De acordo com o modelo APRAC, existem formas mais eficientes de se alocar o corpo docente tal que seja possível obter um custo operacional mínimo com garantia de níveis de qualidade máximo nos indicadores de avaliação institucional. Essa abordagem deverá ser acoplada ao problema de quadro de horários, definindo então um novo objetivo para a alocação. Portanto, para a definição do objetivo para resolução da terceira fase do processo, deverão ser abordados os seguintes pontos a respeito dos professores: • status da alocação, • disponibilidade de tempo, • formação acadêmica e área de atuação, • disponibilidade nos horários, • titulação, • publicações e produções acadêmicas, • experiência profissional, • carreira institucional. O status da alocação do professor destina-se a avaliar o tipo de regime de trabalho que o docente está alocado. Conforme abordado por Carvalho [18], sempre que ocorre uma redução de jornada, gera-se uma rescisão parcial do contrato de trabalho do professor, a qual 65 gera custos para a Instituição. Sendo assim, é importante evitar reduções parciais, preferindo alocar prioritariamente aqueles docentes que já fazem parte do quadro efetivo. Observando também o disposto nos acordos coletivos, uma vez que um professor já atua em determinada disciplina, deve-se preferencialmente mantê-lo na mesma. A disponibilidade de tempo do professor é importante, pois quanto mais disponível (mais próximo de quarenta horas semanais), mais fácil é alocar atividades ao docente. Uma observação que pode ser feita a partir de simulações do modelo APRAC é que o modelo, ao minimizar os custos operacionais, reduz ao máximo o número de professores necessários para atender a demanda. Visto isso, deve-se observar que cada vez mais, o corpo docente deve ser menor, mas com mais envolvimento nas atividades institucionais (menos professores com carga horária maior). Portanto, é importante ter professores com disponibilidade de tempo para serem alocados. Quanto à formação acadêmica e área de atuação, os professores que tem afinidade com o conjunto de disciplinas ofertadas tem prioridade de alocação. Afinal, a formação didático- pedagógica do professor é fundamental para o bom andamento da relação ensino- aprendizagem em todas as disciplinas. Como o quadro de ofertas é pré-estabelecido, é importante que o professor tenha disponibilidade nos horários nos quais as ofertas de disciplinas de sua área ocorrem. Estendendo a formação acadêmica por área, quanto maior for a qualificação docente, melhor para a Instituição. Logo, docentes com melhores titulações, índices de publicações e produções acadêmicas e mais tempo de experiência profissional, são mais indicados para serem alocados. Por fim, respeitando aspectos regimentais e de planos de carreira institucionais, aqueles professores que já estão mais avançados em termos de carreira institucional, a critério de cada instituição, devem ser prioritariamente alocados. Todos os aspectos acima descritos deverão ser contemplados para a elaboração do objetivo, além das informações sobre custo de alocação e informações sobre alocação mínima apontadas pela resolução do modelo APRAC. A FIG. 3 mostra o diagrama da modelagem de processo da construção do quadro de horários. A próxima seção explica como é definida a função objetivo. 66 FIGURA 3 - Diagrama de processo para construção do quadro de horários 67 4.3 - Objetivo a otimizar O objetivo do modelo a ser proposto é alocar os professores de forma eficiente. Para isso, aspectos sobre o corpo docente, sobre os custos de alocação e sobre as informações para a alocação de custo mínimo são consideradas. Para uma determinada instância, deve-se decidir: • Se o docente deverá ou não ser alocado no quadro de horários; • Se for alocado, em qual regime de trabalho o docente deverá atuar; • Se for alocado, em quais unidades de oferta o docente deverá lecionar. Considerando: − I = conjunto de docentes disponíveis para serem alocados; − J = conjunto de regimes de trabalho; − K = conjunto de unidades de oferta de disciplinas. Então, as variáveis de decisão para o problema são: − Yij = 0 ou 1, sendo 1 caso o docente i seja atribuído ao regime de trabalho j e 0 caso contrário. − Xik = 0 ou 1, sendo 1 caso o docente i seja designado a atender a oferta de disciplina k. O objetivo a ser otimizado pode então ser descrito da seguinte forma: ∑∑∑∑ ∈ ∈∈ ∈ + Ii Kk ikik Ii Jj ijij XCYFmin A definição dos coeficientes F e C devem ser balizadas nos aspectos enumerados anteriormente. O coeficiente F está relacionado à ativação do professor em um regime de trabalho. O coeficiente C está relacionado à designação do professor para atender uma determinada oferta de disciplina. Um professor somente poderá ser alocado para uma determinada oferta de disciplina caso ele tenha sido previamente alocado em um regime de trabalho. Além disso, cada regime de trabalho tem uma faixa de horas que podem ser alocadas para o docente. Portanto, a alocação do docente a ofertas de disciplinas está limitada a disponibilidade do regime no qual o docente fora atribuído. 68 O coeficiente F é calculado para cada docente em cada regime de trabalho. Em um primeiro momento, é definida uma função f(i), denominada função de penalidade, que retorna uma penalidade para cada professor i disponível para participar da alocação. A rigor, ∑ ∑ ∈ ∈ = Aa a Aa aa p np if )( onde: − A = conjunto de aspectos; − pa é o peso do aspecto a; − na é a nota do aspecto a. A função f(i) é uma média ponderada dos aspectos docentes considerados. O conjunto A é formado por: 1) Regime: penalidade igual a 0 (zero) caso o professor se encontre atualmente em regime de trabalho integral e igual a 100 caso o professor não pertença ao quadro efetivo. 2) Disponibilidade: penalidade igual a 0 (zero) quando o professor tiver a disponibilidade total de carga horária (40 horas semanais), crescendo quanto menos disponível. 3) Titulação: penalidade igual a 0 (zero) quando a maior titulação do professor Doutorado, crescendo quanto menor for a titulação. 4) Publicações/Produções: penalidade igual a 0 (zero) quando a média de publicações do professor for maior que uma publicação por ano, considerando os últimos três anos, devendo a penalidade máxima ocorrer para o docente sem produção acadêmica. 5) Experiência: penalidade igual a 0 (zero) quando o professor possuir 5 (cinco) anos ou mais de experiência, crescendo quanto menor for a experiência. 6) Carreira: penalidade igual a 0 (zero) para professores com mais que 5 (cinco) anos de docência na Instituição, crescendo quanto menor for o tempo de trabalho na Instituição. A lista de aspectos pode ser ampliada, visto que a definição dos pesos de cada um deverá ser orientada pelos interesses institucionais, que podem inclusive ser norteadas pelos pesos e relevância de cada um dos aspectos dentro da Avaliação Institucional no SINAES. Sendo assim, uma instituição a fim de melhorar algum quesito para obter uma melhor avaliação, pode definir uma forma diferente para atribuir pesos aos aspectos considerados no 69 cálculo de f(i). A função f(i) retorna a penalidade do docente de acordo com os parâmetros definidos. O propósito é que os docentes com a menor penalidade terão preferência para a alocação. Após executar o modelo APRAC para a instância correspondente, duas informações principais são obtidas. A primeira é o número de professores por regime de trabalho na solução ótima6. A segunda é o custo marginal de cada um dos regimes de trabalho. A definição de cada Fij é dada pelo seguinte algoritmo: Para cada docente i ∈ I, sendo i ordenado crescentemente de acordo com f(i), faça Para cada regime j ∈ J, sendo j ordenado decrescentemente por peso na avaliação faça Fij recebe a soma do custo marginal de j com o valor de f(i) Se o número de professores analisados até o regime j for maior que o número total de docentes até o regime j da solução ótima, então Fij recebe Fij mais o custo operacional efetivo de j Analisa o próximo j Analisa o próximo i Após ter executado o procedimento acima, o valor de cada um dos coeficientes Fij indica ao modelo quais recursos deverão ser priorizados na alocação, facilitando a convergência dos métodos de solução exatos. Assim como o coeficiente F, o coeficiente C está associado a uma penalidade para que o professor i seja alocado para atender a oferta de disciplina k. A definição de Cik é balisada nos seguintes aspectos: 1) Preferência pela disciplina. 2) Histórico de Alocação. 3) Adequação da Formação. 4) Status contratação. De forma análoga, outros aspectos podem ser definidos de acordo com as necessidades específicas de uma determinada instituição. Seja g(i,k) uma função que retorna um valor de penalidade para que o professor i seja alocado na oferta de disciplina k. A função g(i,k) é a soma das penalidades avaliadas em cada um dos aspectos. Abaixo, define-se um critério para obter o valor de g(i,k). 6 O modelo APRAC deve ser executado duas vezes: uma para obter solução inteira para o número de professores em cada regime de trabalho e outra para obter os custos marginais associados aos regimes de trabalho na solução linear. Uma opção é armazenar dados de execução do APRAC a fim de evitar sucessivas resoluções de instâncias iguais. 70 Para o primeiro aspecto, a penalidade é 0 (zero) caso a disciplina seja altamente desejada. Quanto menos se deseja aquela disciplina, maior a penalidade. Para disciplinas que não se deseja em hipótese nenhuma, deve-se associar uma penalidade infinita, indicando que aquela disciplina nunca deverá ser alocada para aquele docente. Quanto ao segundo aspecto, a penalidade é 0 (zero) caso o docente já estiver lecionando a disciplina e 20 (por exemplo) caso contrário. Quanto ao terceiro aspecto, a penalidade é 0 (zero) caso o docente tenha formação adequada para lecionar aquela disciplina. Caso não tenha formação adequada, deve-se associar uma penalidade alta. Quanto ao quarto e último aspecto, a penalidade é 0 (zero) caso o docente faça parte do quadro efetivo e 100 (por exemplo) caso contrário. Ao final da avaliação para cada professor i e para cada oferta de disciplina k, Cik recebe o valor de g(i,k) + f(i). Conforme colocado anteriormente, os valores dos coeficientes F e C podem ser alterados de acordo com a especificidade de cada instituição, tornando determinados critérios mais relevantes em termos de otimização. Além disso, a definição desses valores depende fortemente de uma base de informações para permitir o cálculo dos coeficientes. Uma vez encontrada uma solução de custo mínimo, de acordo com os coeficientes definidos por F e C, pode-se afirmar que o quadro de horários resultante apresentará as características como: 1) Custo operacional baixo. 2) Atendimento da oferta de disciplinas de forma eficiente. 3) Concentração de atividades em número menor de professores. 4) Equipe acadêmica com um melhor nível de qualidade. A seguir são enunciados os modelos matemáticos completos para a solução do problema de alocação de professores. 71 4.4 - Formulação Matemática – Único Campus (Modelo APU) O problema a ser resolvido é a elaboração de um quadro de custo mínimo tal que sejam mantidos níveis de qualidade máximos. Parte-se do pressuposto que o quadro de ofertas de disciplinas já exista e a atividade está em alocar o corpo docente para executar tal oferta. O modelo de Alocação de Professores para um Único Campus (APU) proposto é descrito da seguinte forma: Seja: − I = conjunto de docentes. − J = conjunto de regimes de trabalho. (Tipicamente: de acordo com o QUADRO 1, RI – Regime Integral –, RP – Regime Parcial –, e RH – Regime Horista. − K = conjunto de unidades de oferta de disciplinas. (Obs: uma disciplina pode estar sendo ofertada várias vezes). − H = conjunto de horários de um turno. (Tipicamente: 1 a 4). − T = conjunto de turnos. (Tipicamente: Manhã, Tarde e Noite). − D = conjunto de dias da semana (Tipicamente: Segunda a Sexta). Deve-se considerar como dados de entrada do modelo as seguintes informações: − Fij = custo de ativação de um docente i ao regime de trabalho j. − Cik = custo de alocação de um professor i a uma oferta de disciplina k. Pode representar preferências docentes a designação do conjunto de oferta de disciplinas. − Tamk = tamanho, em horas, de uma oferta de disciplina k. − THj = total de horas do regime de trabalho j. − Ej = disponibilidade de horas do regime de trabalho j para alocação em atividades de ensino, ou seja, atividades que vão atender a oferta de disciplinas. − Emj = limite inferior de horas do regime de trabalho j para alocação em atividades de ensino, ou seja, atividades que vão atender a oferta de disciplinas. − Qdkhtd = quadro de oferta das disciplinas, especificando que a oferta de disciplina k ocorrerá no horário h, do turno t, do dia d, sendo Qdkhtd igual a 1 quando existe a oferta e 0 caso contrário. 72 − PRTj = peso do regime de trabalho na avaliação institucional do MEC. − MRT = Meta do Indicador Regime de Trabalho na Avaliação Institucional. − RTIj = Igual a 1 caso o regime de trabalho seja do tipo tempo integral. − MTI = Meta de docentes em regime de trabalho tempo integral de acordo com o tipo de organização acadêmica. − Dispihtd = quadro de disponibilidade do docente i, sendo 1 caso o docente i tem disponibilidade para ser alocado no horário h, do turno t, do dia d, sendo 0 caso contrário. − Compli = Carga horária pré-alocada para o docente i em atividades complementares7. As variáveis de decisão do modelo são: − Yij = 0 ou 1, sendo 1 caso o docente i seja atribuído ao regime de trabalho j e 0 caso contrário. − Xik = 0 ou 1, sendo 1 caso o docente i seja designado a atender a oferta de disciplina k. O objetivo do modelo é alocar os docentes tal que todas as unidades de oferta sejam atendidas com o mínimo custo operacional, atendendo também aos requisitos de qualidade da avaliação institucional e demais restrições de um quadro de horários. As restrições serão explicadas a partir da formulação matemática do modelo descrita abaixo: ∑∑∑∑ ∈ ∈∈ ∈ + Ii Kk ikik Ii Jj ijij XCYFmin sujeito a: 1≤∑ ∈Jj ijY ∀ i ∈I (1) 1=∑ ∈Ii ikX ∀ k ∈K (2) ∑∑ ∈∈ ≤ Jj jijk Kk ik EYTamX ∀ i ∈I (3) ∑∑ ∈∈ ≥ Jj jijk Kk ik EmYTamX ∀ i ∈I (4) 7 A pré-alocação em atividades complementares permite informar ao modelo que determinado professor já se encontra alocado em atividades de gestão, projetos de pesquisa e demais atividades complementares. 73 ∑∑ ∈∈ −≤ Jj ijijk Kk ik ComplTHYTamX ∀ i ∈I (5) ∑ ∈ ≥− Jj ijjij ComplETHY )( ∀ i ∈I (6) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj jij YMRTPRTY (7) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj jij YMTIRTIY (8) ihtdkhtdik DispQdX ≤ ∀ i ∈I, k ∈K, h ∈H, t ∈T, d ∈D (9) 1≤∑ ∈Kk khtdikQdX ∀ i ∈I, h ∈H, t ∈T, d ∈D (10) { }1,0∈ikX ∀ i ∈I, k ∈K (11) { }1,0∈ijY ∀ i ∈I, j ∈J (12) As restrições (1) garantem que um docente i estará alocado em apenas um regime de trabalho j. Caso não esteja associado a nenhum significa que ele não está alocado no quadro de horários final. Já as restrições (2) garantem que toda a oferta de disciplina k será exclusivamente atendida por um docente i. As restrições (3), (4), (5) e (6) servem para limitar a quantidade de carga horária alocada a um docente de acordo com seu regime de trabalho. As restrições (3) garantem que a quantidade de horas alocadas a um docente i para atender ofertas de disciplinas não é superior a quantidade de horas disponíveis para atividades de ensino de acordo com o regime de trabalho j. Da mesma forma, as restrições (4) definem um limite inferior para o número de horas de ensino do regime de trabalho j. As restrições (5) garantem que a quantidade de horas alocadas a um docente i para atender ofertas de disciplinas não sobreponha à carga horária complementar (Compli) pré-alocada ao docente i. Já as restrições (6) garantem que o total de carga horária complementar pré-alocado seja sempre enquadrado no montante destinado a esse tipo de atividade para cada regime de trabalho j, ou seja, no saldo de THj - Ej . A restrição (7) garante que o conceito do indicador regime de trabalho da avaliação institucional seja atendido no nível máximo, enquanto a restrição (8) garante o atendimento do percentual de professores em regime de trabalho tempo integral, de acordo com o estabelecido na legislação. As restrições (9) garantem que nenhum docente será alocado caso esteja indisponível em um determinado horário. As restrições (10) garantem que um docente i nunca está alocado 74 mais de uma vez em um mesmo horário. Por fim, as restrições (11) e (12) definem os domínios das variáveis de decisão X e Y, respectivamente. A fim de incrementar o modelo, podem ser adicionadas duas outras restrições, apesar de que seu atendimento está embutido na função objetivo. ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj iij YMTITPTITY (13) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj iij YMPUBPPUBY (14) PTITi corresponde ao peso da titulação e PPUBi corresponde ao peso da publicação do professor i de acordo com o Manual de Avaliação Externa [7]. MTIT e MPUB são as metas para o indicador Titulação e Publicação/Produção respectivamente, de acordo com o tipo de IES. A restrição (13) garante o atendimento do indicador titulação e a restrição (14) garante o atendimento do indicador Publicação/Produção. Como o atendimento dessas restrições está embutido na função objetivo, essas restrições podem ser consideradas desejáveis e por isso não serem utilizadas. Outra observação importante é que as restrições de indisponibilidade dos professores também podem ser relaxadas visto que como o quadro de ofertas está pré-definido, caso um professor esteja indisponível durante o horário de determinada oferta, pode-se simplesmente desabilitá-lo a atender tal oferta. Essa situação corresponde à associar um custo elevado ao coeficiente Cik sempre que o professor estiver indisponível no horário de realização da oferta de disciplina. Nesse caso, as restrições (9) seriam desconsideradas do modelo. Por fim, com o intuito de evitar a criação de variáveis que jamais serão solução do problema, ou seja, aquelas que possuem um custo muito elevado (infinito), pode-se incrementar o modelo tal que apenas as variáveis que podem vir a participar da solução sejam instanciadas e que variáveis de folga sejam inseridas para evitar a inviabilidade na resolução do modelo. Dessa forma é possível trabalhar com instâncias maiores. 75 4.5 - Formulação Matemática – Multicampi (Modelo APM) O modelo anteriormente proposto não é aplicável em instituições que trabalham com seus cursos distribuídos em mais de um campus. Isso porque o modelo permite que em um mesmo turno t, de um mesmo dia d, o professor seja alocado em ofertas de disciplinas que ocorrerão em campus diferentes. Normalmente, devido à necessidade de um deslocamento significativo entre essas unidades, torna-se inviável permitir que um professor seja designado a atender a demanda em campus diferentes, no mesmo turno, no mesmo dia. A fim de comportar o problema multicampi, o modelo anteriormente proposto necessita de restrições e variáveis adicionais. Então, seja: − L = conjunto de campus ou locais que exigem deslocamento significativo do docente. − NH = número de horários de um turno. − Qdkhtdl = quadro de oferta das disciplinas, especificando que a oferta de disciplina k será dada no horário h, do turno t, do dia d, no campus l, sendo Qdkhtdl igual a 1 quando existe a oferta e 0 caso contrário. − Dispihtdl = quadro de disponibilidade do docente i, sendo 1 caso o docente i tem disponibilidade para ser alocado no horário h, do turno t, do dia d, no campus l, sendo 0 caso contrário. − Vitdl = variável auxiliar que representa que um docente i foi alocado para lecionar no turno t do dia d no campus l, sendo 1 quando o docente foi alocado e 0 caso contrário. Reescrevendo as restrições (9) e (10) e adicionando quatro novos conjuntos de restrições, temos o modelo de Alocação de Professores Multicampi (APM): ihtdlkhtdlik DispQdX ≤ ∀ i ∈I, k ∈K, h ∈H, t ∈T, d ∈D, l ∈L (15) 1≤∑ ∈Kk khtdlikQdX ∀ i ∈I, h ∈H, t ∈T, d ∈D, l ∈L (16) 1≤∑ ∈Ll itdlV ∀ i ∈I, t ∈T, d ∈D (17) 111 −≥−∑∑ ∈ ∈ NH VQdX NH itdlKk Hh khtdlik ∀ i ∈I, t ∈T, d ∈D, l ∈L (18) 01 ≤−∑∑ ∈ ∈ itdl Kk Hh khtdlik VQdXNH ∀ i ∈I, t ∈T, d ∈D, l ∈L (19) 76 { }1,0∈itdlV ∀ i ∈I, t ∈T, d ∈D, l ∈L (20) As restrições (17) garantem que um professor nunca é alocado dentro de um mesmo turno em dois campi diferentes. As restrições (18) e (19) são responsáveis por atribuir 0 ou 1 à variável Vitdl., que de acordo com as restrições (20), é binária. Quando um docente i foi alocado em um turno t do dia d no campus l, a variável Vitdl assume 1. As restrições (15) e (16) correspondem às restrições (9) e (10) do modelo para um único campus. Da mesma forma, no caso de não se utilizar as restrições de disponibilidade de professores, conforme explicado na seção anterior, as restrições (15) seriam desconsideradas do modelo. 77 4.6 - Processo Exemplo Para exemplificar o funcionamento do processo proposto, será demonstrado um fluxo do início ao fim abrangendo as três fases da construção de um quadro de horários. As informações aqui apresentadas são meramente ilustrativas. 4.6.1 - Fase 1 – Elaboração do Plano de Oferta Uma determinada instituição possui três cursos em implantação: ciência da computação, engenharia elétrica e matemática, sendo que os três cursos funcionam nos turnos da manhã e da noite. No período letivo seguinte, o qual está sendo planejado, o curso de ciência da computação terá 3 (três) períodos implantados e os demais 2 (dois) períodos. Com base na grade curricular de cada um dos cursos, chega-se a uma lista de disciplinas que deverão ser ofertadas. O QUADRO 6 mostra o conjunto de disciplinas que deverão ser ofertadas nos dois turnos. QUADRO 6 Conjunto de disciplinas a serem ofertadas de acordo com a grade curricular Curso Período Disciplina CH Cálculo I 4 Geometria Analítica e Álgebra Linear I 4 Algoritmos e Estruturas de Dados I 6 Introdução à Ciência da Computação 2 1 Metodologia Científica 4 Cálculo II 4 Álgebra Linear 4 Algoritmos e Estruturas de Dados II 4 Física para Computação 4 2 Leitura e Produção de Textos 4 Cálculo III 4 Matemática Discreta 4 Algoritmos e Estruturas de Dados III 4 Introdução aos Sistemas Lógicos 4 Ciência da Computação 3 Teoria Geral da Administração 4 Curso Período Disciplina CH Curso Período Disciplina CH Cálculo I 4 Introdução à Aritmética e Álgebra 4 Química Geral 4 Introdução à Geometria Plana 4 Geometria Analítica 4 Leitura e Produção de Textos 4 Algoritmos e Estruturas de Dados 4 Matemática e Informática 4 1 Leitura e Produção de Textos 4 1 Tópicos Especiais 4 Cálculo II 4 Estudo de Funções 6 Física I 4 Filosofia 2 Álgebra Linear 4 Geometria Analítica I 4 Circuitos Elétricos I 6 Matemática e Educação I 4 Engenharia Elétrica 2 Introdução ao Pensamento Científico 2 Matemática 2 Trigonometria 4 78 Com a lista de disciplinas que devem ser ofertadas, a coordenação pedagógica da instituição deverá avaliar o número de turnos que cada disciplina deverá ser ofertada, o número de alunos previstos de acordo com as vagas do curso, as necessidades de turmas especiais oriundas de adaptações e ou repetências, além da necessidade de divisão de turmas em caso de aulas práticas ou outras exigências legais. Neste exemplo, foi decidido que a disciplina Cálculo I deverá ser ofertada em uma turma especial pois existe uma demanda grande para a disciplina, visto que vários alunos foram reprovados e todos os ingressantes na Instituição são obrigados a se matricularem na mesma. Como resultado da primeira fase, obtêm-se o plano de ofertas de disciplinas que deverá ser oferecido aos alunos no semestre seguinte com suas respectivas cargas horárias. A lista é apresentada na TAB. 8. TABELA 8 Plano de oferta de disciplinas (Continua) Código Oferta Disciplina Turma CH OF001 Cálculo I 1º Período Ciência da Computação - Manhã 4 OF002 Geometria Analítica e Álgebra Linear I 1º Período Ciência da Computação - Manhã 4 OF003 Algoritmos e Estruturas de Dados I 1º Período Ciência da Computação - Manhã 6 OF004 Introdução à Ciência da Computação 1º Período Ciência da Computação - Manhã 2 OF005 Metodologia Científica 1º Período Ciência da Computação - Manhã 4 OF006 Cálculo II 2º Período Ciência da Computação - Manhã 4 OF007 Álgebra Linear 2º Período Ciência da Computação - Manhã 4 OF008 Algoritmos e Estruturas de Dados II 2º Período Ciência da Computação - Manhã 4 OF009 Física para Computação 2º Período Ciência da Computação - Manhã 4 OF010 Leitura e Produção de Textos 2º Período Ciência da Computação - Manhã 4 OF011 Cálculo III 3º Período Ciência da Computação - Manhã 4 OF012 Matemática Discreta 3º Período Ciência da Computação - Manhã 4 OF013 Algoritmos e Estruturas de Dados III 3º Período Ciência da Computação - Manhã 4 OF014 Introdução aos Sistemas Lógicos 3º Período Ciência da Computação - Manhã 4 OF015 Teoria Geral da Administração 3º Período Ciência da Computação - Manhã 4 OF016 Cálculo I 1º Período Ciência da Computação - Noite 4 OF017 Cálculo I 1º Período Ciência da Computação - Noite (T. Especial) 4 OF018 Geometria Analítica e Álgebra Linear I 1º Período Ciência da Computação - Noite 4 OF019 Algoritmos e Estruturas de Dados I 1º Período Ciência da Computação - Noite 6 OF020 Introdução à Ciência da Computação 1º Período Ciência da Computação - Noite 2 OF021 Metodologia Científica 1º Período Ciência da Computação - Noite 4 OF022 Cálculo II 2º Período Ciência da Computação - Noite 4 OF023 Álgebra Linear 2º Período Ciência da Computação - Noite 4 OF024 Algoritmos e Estruturas de Dados II 2º Período Ciência da Computação - Noite 4 OF025 Física para Computação 2º Período Ciência da Computação - Noite 4 OF026 Leitura e Produção de Textos 2º Período Ciência da Computação - Noite 4 OF027 Cálculo III 3º Período Ciência da Computação - Noite 4 OF028 Matemática Discreta 3º Período Ciência da Computação - Noite 4 OF029 Algoritmos e Estruturas de Dados III 3º Período Ciência da Computação - Noite 4 OF030 Introdução aos Sistemas Lógicos 3º Período Ciência da Computação - Noite 4 OF031 Teoria Geral da Administração 3º Período Ciência da Computação - Noite 4 79 TABELA 8 Plano de oferta de disciplinas (Conclusão) Código Oferta Disciplina Turma CH OF032 Cálculo I 1º Período Engenharia Elétrica - Manhã 4 OF033 Química Geral 1º Período Engenharia Elétrica - Manhã 4 OF034 Geometria Analítica 1º Período Engenharia Elétrica - Manhã 4 OF035 Algoritmos e Estruturas de Dados 1º Período Engenharia Elétrica - Manhã 4 OF036 Leitura e Produção de Textos 1º Período Engenharia Elétrica - Manhã 4 OF037 Cálculo II 2º Período Engenharia Elétrica - Manhã 4 OF038 Física I 2º Período Engenharia Elétrica - Manhã 4 OF039 Álgebra Linear 2º Período Engenharia Elétrica - Manhã 4 OF040 Circuitos Elétricos I 2º Período Engenharia Elétrica - Manhã 6 OF041 Introdução ao Pensamento Científico 2º Período Engenharia Elétrica - Manhã 2 OF042 Cálculo I 1º Período Engenharia Elétrica - Noite 4 OF043 Química Geral 1º Período Engenharia Elétrica - Noite 4 OF044 Geometria Analítica 1º Período Engenharia Elétrica - Noite 4 OF045 Algoritmos e Estruturas de Dados 1º Período Engenharia Elétrica - Noite 4 OF046 Leitura e Produção de Textos 1º Período Engenharia Elétrica - Noite 4 OF047 Cálculo II 2º Período Engenharia Elétrica - Noite 4 OF048 Física I 2º Período Engenharia Elétrica - Noite 4 OF049 Álgebra Linear 2º Período Engenharia Elétrica - Noite 4 OF050 Circuitos Elétricos I 2º Período Engenharia Elétrica - Noite 6 OF051 Introdução ao Pensamento Científico 2º Período Engenharia Elétrica - Noite 2 OF052 Introdução à Aritmética e Álgebra 1º Período Matemática - Manhã 4 OF053 Introdução à Geometria Plana 1º Período Matemática - Manhã 4 OF054 Leitura e Produção de Textos 1º Período Matemática - Manhã 4 OF055 Matemática e Informática 1º Período Matemática - Manhã 4 OF056 Tópicos Especiais 1º Período Matemática - Manhã 4 OF057 Estudo de Funções 2º Período Matemática - Manhã 6 OF058 Filosofia 2º Período Matemática - Manhã 2 OF059 Geometria Analítica I 2º Período Matemática - Manhã 4 OF060 Matemática e Educação I 2º Período Matemática - Manhã 4 OF061 Trigonometria 2º Período Matemática - Manhã 4 OF062 Introdução à Aritmética e Álgebra 1º Período Matemática - Noite 4 OF063 Introdução à Geometria Plana 1º Período Matemática - Noite 4 OF064 Leitura e Produção de Textos 1º Período Matemática - Noite 4 OF065 Matemática e Informática 1º Período Matemática - Noite 4 OF066 Tópicos Especiais 1º Período Matemática - Noite 4 OF067 Estudo de Funções 2º Período Matemática - Noite 6 OF068 Filosofia 2º Período Matemática - Noite 2 OF069 Geometria Analítica I 2º Período Matemática - Noite 4 OF070 Matemática e Educação I 2º Período Matemática - Noite 4 OF071 Trigonometria 2º Período Matemática - Noite 4 Total 284 80 4.6.2 - Fase 2 – Elaboração do Quadro de Oferta A segunda fase, a qual destina-se a escalonar cada uma das ofertas no quadro de horários, tem como entrada o plano de ofertas. Esse processo pode ser auxiliado por um sistema especialista ou pode até mesmo ser feito manualmente. Independente de como o plano de ofertas foi montado, o objetivo da segunda fase é definir onde (local e sala) e quando (horário de realização) cada oferta de disciplina será realizada, ou seja, definir o quadro de oferta. Um quadro é uma planilha de alocação de atividades ao longo do tempo. É composto por períodos de tempo, denominados horários (i.e. timeslots), que são unidades mínimas de alocação e que possuem um tamanho pré-definido em horas. Nesse exemplo, um horário corresponde à duas aulas de 50 min., ou seja, 1:40 h de duração. O QUADRO 7 é um quadro de oferta. O posicionamento das disciplinas obedeceu a alguns critérios pedagógicos definidos tal como disciplinas pré-requisito deverão ocorrer em um mesmo horário, implicando na necessidade de professores distintos. É importante frisar que o quadro de ofertas pode trazer uma característica evolutiva, ou seja, recuperar informações de quadros de horários anteriores para subsidiar a elaboração do quadro de ofertas seguinte. Segundo Barraclough [4], o processo de construção de um quadro de horários deverá verificar o quadro do período anterior e os novos requisitos exigidos para a definição do novo quadro de horários. 81 QUADRO 7 Quadro de oferta de disciplinas Turno Horário Segunda Terça Quarta Quinta Sexta OF003 OF001 OF003 OF001 OF003 OF008 OF006 OF008 OF006 OF010 OF013 OF011 OF013 OF011 OF014 OF033 OF034 OF036 OF034 OF033 OF039 OF038 OF039 OF040 OF038 OF052 OF055 OF052 OF055 OF054 1º Ho rá rio (7h 00 - 8h 40 ) OF057 OF059 OF057 OF060 OF059 OF002 OF005 OF002 OF005 OF004 OF007 OF009 OF007 OF010 OF009 OF012 OF014 OF012 OF015 OF015 OF035 OF032 OF035 OF032 OF036 OF040 OF037 OF040 OF037 OF041 OF053 OF054 OF056 OF053 OF056 M an hã 2º H or ár io (9h 00 - 10 h4 0) OF058 OF060 OF061 OF057 OF061 OF016 OF016 OF019 OF017 OF019 OF017 OF019 OF024 OF022 OF024 OF022 OF026 OF029 OF027 OF029 OF027 OF030 OF043 OF044 OF046 OF044 OF043 OF049 OF048 OF049 OF050 OF048 OF062 OF065 OF062 OF065 OF064 1º H or ár io (19 h0 0 - 20 h4 0) OF067 OF069 OF067 OF070 OF069 OF018 OF021 OF018 OF021 OF020 OF023 OF025 OF023 OF026 OF025 OF028 OF030 OF028 OF031 OF031 OF045 OF042 OF045 OF042 OF046 OF050 OF047 OF050 OF047 OF051 OF063 OF064 OF066 OF063 OF066 N oi te 2º H or ár io (21 h0 0 - 22 h4 0) OF068 OF070 OF071 OF067 OF071 O quadro de oferta pode ser divulgado mesmo antes da conclusão do quadro de horários. Isso porque a informação necessária para os alunos e para outros setores, como por exemplo infra-estrutura, já está definida. Para a finalização do quadro de horários, deve-se definir por fim a alocação dos professores às ofertas de disciplina. 82 4.6.3 - Fase 3 – Alocação de Professores no Quadro de Horários Considerando que todos os cursos funcionam em um mesmo local, para efetivar a conclusão do processo, deverá ser utilizado o modelo de Alocação de Professores para um Único Campus. Considerando o plano de ofertas apresentado (TAB. 8), o primeiro passo é instanciar o modelo APRAC para conhecer as condições de mínimo operacional. Portanto, as seguintes informações devem ser passadas ao modelo: a quantidade de horas demandadas e os parâmetros sobre as metas de avaliação e características dos regimes de trabalho. Com base no Manual de Avaliação Institucional Externa [7], afim de permitir uma melhor percepção das alocações em regimes de trabalho, deve-se primeiramente discretizar as possibilidades de enquadramento docente, criando um detalhamento de cada classificação em regimes de trabalho. Considerando a quantidade de horas alocadas para atividades de ensino e a quantidade de horas alocadas para atividades complementares, sendo que o total de horas deve ser sempre menor que 40 horas semanais, chega-se a um conjunto de regimes de trabalho resultante das diversas combinações para o enquadramento docente (QUADRO 8). QUADRO 8 Discretização dos regimes de trabalho Horas Destinadas a Atividades de Ensino CH 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 0 - H H H H H H H H H H H H H H H H H H H H 2 H H H H H H H H H H H H H H H H H H H H - 4 H H H H P P P H H H H H H H H H H H H - - 6 H H H P P P P P P P H H H H H H H H - - - 8 H H P P P P P P P P P P P H H H H - - - - 10 H P P P P P P P P P P P P P P P - - - - - 12 P P P P P P P P P P P P P P P - - - - - - 14 P P P P P P P P P P P P P P - - - - - - - 16 P P P P P P P P P P P P P - - - - - - - - 18 P P P P P P P P P P P P - - - - - - - - - 20 P P P P P P P P P P I - - - - - - - - - - 22 P P P P P P P P P I - - - - - - - - - - - 24 P P P P P P P P I - - - - - - - - - - - - 26 P P P P P P P I - - - - - - - - - - - - - 28 P P P P P P I - - - - - - - - - - - - - - 30 P P P P P I - - - - - - - - - - - - - - - 32 P P P P I - - - - - - - - - - - - - - - - 34 P P P I - - - - - - - - - - - - - - - - - 36 P P I - - - - - - - - - - - - - - - - - - 38 P I - - - - - - - - - - - - - - - - - - - H or a s De st in ad as a At iv id a de s Co m pl em e n ta re s 40 I - - - - - - - - - - - - - - - - - - - - Legenda: H = Regime Horista; P = Regime Parcial; I = Regime Integral, de acordo com o QUADRO 1 83 Para o exemplo proposto, apenas um subconjunto das possibilidades para arranjo de um regime de trabalho foi considerado. A TAB. 9 apresenta os regimes de trabalho considerados, bem como os parâmetros de cada um, utilizados no modelo. TABELA 9 Regimes de trabalho considerados e seus parâmetros Código Regime Tipo TH E Em Compl Código Regime Tipo TH E Em Compl H02 Horista 2 2 1 0 H38 Horista 38 38 37 0 H04 Horista 4 4 3 0 H40 Horista 40 40 39 0 H06 Horista 6 6 5 0 I08 Integral 40 8 7 32 H08 Horista 8 8 7 0 I12 Integral 40 12 11 28 H10 Horista 10 10 9 0 I16 Integral 40 16 15 24 H12 Horista 12 12 11 0 I20 Integral 40 20 19 20 H14 Horista 14 14 13 0 P12 Parcial 12 8 7 4 H16 Horista 16 16 15 0 P14 Parcial 14 10 9 4 H18 Horista 18 18 17 0 P16 Parcial 16 12 11 4 H20 Horista 20 20 19 0 P19 Parcial 19 14 13 5 H22 Horista 22 22 21 0 P22 Parcial 22 16 15 6 H24 Horista 24 24 23 0 P24 Parcial 24 18 17 6 H26 Horista 26 26 25 0 P27 Parcial 27 20 19 7 H28 Horista 28 28 27 0 P30 Parcial 30 22 21 8 H30 Horista 30 30 29 0 P32 Parcial 32 24 23 8 H32 Horista 32 32 31 0 P35 Parcial 35 26 25 9 H34 Horista 34 34 33 0 P38 Parcial 38 28 27 10 H36 Horista 36 36 35 0 P40 Parcial 40 30 29 10 Legenda: Tipo = Tipo do regime de trabalho TH = Total de Horas E = Carga horária destinada a ensino Em = Carga horária mínima destinada a ensino Compl = Carga horária complementar De acordo com o plano de ofertas (TAB. 8), a demanda de horas a serem atendidas é de 284 horas semanais. Com base nas informações apresentadas, a solução ótima do modelo APRAC indica que a situação de custo mínimo operacional é de 364 horas, utilizando dez professores (TAB. 10). TABELA 10 Solução ótima (inteira) do modelo APRAC Código Regime de Trabalho Nº Prof. Horas de Ensino do Regime de Trabalho Horas de Ensino Atendidas Total Horas do Regime de Trabalho Custo Total em Horas/ Semana H10 1 10 10 10 10 H36 1 36 36 36 36 H38 1 38 38 38 38 H40 3 40 120 40 120 I20 4 20 80 40 160 TOTAL 10 284 364 84 A solução do modelo APRAC pode ser entendida como um limite inferior para a alocação do quadro de horários para a instância correspondente. De fato, o APRAC não contempla restrições de indisponibilidade, área de atuação docente, distribuição de atividades e outras restrições típicas dos quadros de horários. No entanto, conforme apresentado (TAB. 10), se fosse possível escalonar dez professores nos regimes de trabalho correspondentes, cobrindo toda a demanda do quadro de ofertas, a solução para a alocação de professores seria ótima no ponto de vista custo e avaliação. Para exemplificar o oposto, suponha que fosse decidido cobrir o quadro de horários apenas com professores em tempo integral (ex. I20) com o propósito de facilitar a alocação. Nesse caso, o custo operacional seria 600 horas (15 professores com 40 horas semanais), que representaria um acréscimo de aproximadamente 65% além do custo mínimo operacional. TABELA 11 Custos marginais dos regimes de trabalho - solução linear do APRAC Código Regime de Trabalho Custos Marginais Código Regime de Trabalho Custos Marginais Código Regime de Trabalho Custos Marginais Código Regime de Trabalho Custos Marginais H02 1.758,86 H20 925,71 H38 92,57 P19 644,14 H04 1.666,29 H22 833,14 H40 - P22 686,57 H06 1.573,71 H24 740,57 I08 2.499,43 P24 594,00 H08 1.481,14 H26 648,00 I12 1.666,29 P27 636,43 H10 1.388,57 H28 555,43 I16 833,14 P30 678,86 H12 1.296,00 H30 462,86 I20 - P32 586,29 H14 1.203,43 H32 370,29 P12 786,86 P35 628,71 H16 1.110,86 H34 277,71 P14 694,29 P38 536,14 H18 1.018,29 H36 185,14 P16 601,71 P40 578,57 Sendo assim, com base nas informações retornadas pela solução do modelo, mais os custos marginais8 associados a cada um dos regimes de trabalho (TAB. 11), dá-se então a criação da instância para ser resolvida pelo modelo de Alocação de Professores proposto. Pressupõe-se que algum sistema armazene informações diversas sobre professores e informações acadêmicas em geral, para que, a partir desse repositório, os dados sejam extraídos e dessa forma a instância do modelo seja gerada. As informações utilizadas para a geração das instâncias foi utilizada do modelo de dados apresentado na FIG. 4. Foram considerados 24 professores capazes de cobrir as ofertas de disciplinas relacionadas no plano de oferta. Após serem verificadas as informações sobre o regime de trabalho atual do docente, a disponibilidade, a titulação, as publicações e produções 8 Custos marginais podem ser entendidos como o aumento do custo total quando diante do aumento de uma unidade do fator em questão. 85 acadêmicas, a experiência profissional e o enquadramento na carreira institucional, foi definido o valor da função de penalidade f(i) para cada um dos professores. A TAB. 12 apresenta os valores para cada um dos professores em ordem crescente de penalidade. FIGURA 4 - Modelo de dados utilizado TABELA 12 Penalidade calculada para cada professor Professor f(i) Professor f(i) Professor f(i) P02 0 P09 14 P24 37 P08 2 P10 14 P16 38 P06 3 P20 30 P18 38 P01 6 P19 30 P12 39 P05 8 P15 32 P21 39 P07 10 P17 32 P13 40 P04 11 P11 36 P23 40 P03 14 P14 37 P22 41 86 Quanto menor a penalidade, mais chances o professor tem de participar da alocação. Teoricamente, se todos os professores fossem aptos a lecionar qualquer disciplina e estivessem disponíveis em todos os horários, os dez primeiros, de acordo com o resultado do APRAC, seriam certamente alocados. No entanto, trata-se de uma situação irreal. O QUADRO 9 mostra as informações de quais professores podem atender cada uma das ofertas de disciplinas. QUADRO 9 Relação de ofertas de disciplinas afins aos professores Prof. Ofertas de Disciplinas Total P01 OF001; OF002; OF006; OF007; OF011; OF016; OF017; OF018; OF022; OF023; OF027; OF032; OF037; OF039; OF042; OF047; OF049; OF052; OF062; 19 P02 OF003; OF004; OF008; OF012; OF013; OF019; OF020; OF024; OF028; OF029; OF035; OF045; OF055; OF065; 14 P03 OF002; OF007; OF018; OF023; OF034; OF039; OF044; OF049; OF052; OF053; OF059; OF062; OF063; OF069; 14 P04 OF005; OF021; OF041; OF051; 4 P05 OF009; OF014; OF025; OF030; OF038; OF040; OF048; OF050; 8 P06 OF012; OF014; OF028; OF030; 4 P07 OF033; OF043; 2 P08 OF015; OF031; OF055; OF065; 4 P09 OF010; OF026; OF036; OF046; OF054; OF064; 6 P10 OF003; OF008; OF013; OF019; OF024; OF029; OF035; OF045; OF055; OF056; OF065; OF066; 12 P11 OF057; OF059; OF061; OF067; OF069; OF071; 6 P12 OF041; OF051; OF058; OF068; 4 P13 OF001; OF016; OF017; OF032; OF042; OF052; OF060; OF061; OF062; OF070; OF071; 11 P14 OF001; OF006; OF011; OF012; OF016; OF017; OF022; OF027; OF028; OF032; OF037; OF042; OF047; 13 P15 OF001; OF006; OF011; OF016; OF017; OF022; OF027; OF032; OF037; OF042; OF047; OF060; OF070; 13 P16 OF005; OF021; OF041; OF051; OF058; OF068; 6 P17 OF003; OF008; OF013; OF019; OF024; OF029; OF035; OF045; OF055; OF065; 10 P18 OF002; OF004; OF018; OF034; OF044; OF053; OF059; OF063; OF069; 9 P19 OF010; OF026; OF036; OF046; OF054; OF064; 6 P20 OF009; OF014; OF020; OF025; OF030; OF038; OF040; OF048; OF050; 9 P21 OF056; OF057; OF061; OF064; OF066; OF067; OF071; 7 P22 OF015; OF031; 2 P23 OF009; OF025; OF033; OF038; OF040; OF043; OF046; OF048; OF050; 9 P24 OF004; OF014; OF015; OF020; OF030; OF031; OF060; OF070; 8 Total 200 Além disso, os professores podem possuir períodos de indisponibilidade para serem alocados no quadro de horários. O QUADRO 10 mostra a indisponibilidade dos professores que poderão ser alocados. 87 QUADRO 10 Períodos de indisponibilidade dos professores Professor Período(s) de indisponibilidade P01 as 6ª-feiras P02 P03 P04 as 2ª-feiras P05 as 4ª-feiras e no 2º Horário Turno da Noite de 5ª-feira P06 as 5ª-feiras P07 as 4ª e 5ª-feiras e no 2º Horário Turno da Noite de 6ª-feira P08 as 2ª e 4ª-feiras e no 1º Horário Turno da Manhã de 6ª-feira P09 as 2ª-feiras P10 P11 as 5ª-feiras P12 as 3ª-feiras e no 1º Horário Turno da Manhã de 4ª-feira P13 no 2º Horário Turno da Noite de 2ª e 5ª-feiras P14 as 6ª-feiras P15 as 2ª, 4ª e 6ª-feiras P16 P17 no 2º Horário Turno da Noite de 3ª, 5ª e 6ª-feiras P18 P19 as 2ª-feiras P20 as 4ª-feiras P21 as 5ª-feiras e no 2º Horário Turno da Noite de 2ª-feira P22 as 2ª, 3ª e 4ª-feiras P23 P24 as 2ª e 4ª-feiras A partir dos dados, o modelo APU é instanciado e após ser resolvido por um software de otimização, obtém-se a solução final. A solução final utilizou 19 dos 24 professores disponíveis, os quais atenderam às 284 horas semanais demandadas. O total de horas utilizado na alocação foi de 436 horas semanais, que representa um acréscimo de aproximadamente 19,8% em relação à carga horária total mínima apontada pelo APRAC. Outra observação importante é quanto ao atendimento do indicador regime de trabalho da avaliação institucional, obtendo conceito máximo e garantindo todas as exigências legais. O enquadramento de cada um dos professores pode ser visto na TAB. 13. 88 TABELA 13 Enquadramento dos professores na solução final Professor Regime de Trabalho Horas Ensino Total de Horas P01 P38 28 38 P02 I20 20 40 P03 P32 24 32 P04 I12 12 40 P05 P38 28 38 P06 I16 16 40 P08 I16 16 40 P09 P22 16 22 P10 H18 18 18 P11 H16 16 16 P12 H04 4 4 P13 H08 8 8 P14 P16 12 16 P15 H16 16 16 P17 P14 10 14 P18 P22 16 22 P19 P12 8 12 P23 H08 8 8 P24 P12 8 12 Total 284 436 O quadro de distribuição de horas de ensino para cada um dos professores (TAB. 14) exibe as informações da composição da carga horária total de cada professor de acordo com as ofertas de disciplina alocadas para o professor. Por fim, basta gerar o quadro de horários final, no formato adequado para divulgação para a comunidade acadêmica, como por exemplo, o leiaute apresentado no QUADRO 11. 89 TABELA 14 Distribuição de horas de ensino final por professor (Continua) P01 P02 P03 P04 P05 P06 P08 P09 P10 P11 P12 P13 P14 P15 P17 P18 P19 P23 P24 OF001 4 - - - - - - - - - - - - - - - - - - 4 OF002 4 - - - - - - - - - - - - - - - - - - 4 OF003 - - - - - - - - 6 - - - - - - - - - - 6 OF004 - 2 - - - - - - - - - - - - - - - - - 2 OF005 - - - 4 - - - - - - - - - - - - - - - 4 OF006 - - - - - - - - - - - - - 4 - - - - - 4 OF007 - - 4 - - - - - - - - - - - - - - - - 4 OF008 - - - - - - - - - - - - - - 4 - - - - 4 OF009 - - - - 4 - - - - - - - - - - - - - - 4 OF010 - - - - - - - 4 - - - - - - - - - - - 4 OF011 - - - - - - - - - - - - 4 - - - - - - 4 OF012 - - - - - 4 - - - - - - - - - - - - - 4 OF013 - 4 - - - - - - - - - - - - - - - - - 4 OF014 - - - - - 4 - - - - - - - - - - - - - 4 OF015 - - - - - - 4 - - - - - - - - - - - - 4 OF016 - - - - - - - - - - - 4 - - - - - - - 4 OF017 - - - - - - - - - - - - 4 - - - - - - 4 OF018 - - 4 - - - - - - - - - - - - - - - - 4 OF019 - - - - - - - - - - - - - - 6 - - - - 6 OF020 - 2 - - - - - - - - - - - - - - - - - 2 OF021 - - - 4 - - - - - - - - - - - - - - - 4 OF022 4 - - - - - - - - - - - - - - - - - - 4 OF023 4 - - - - - - - - - - - - - - - - - - 4 OF024 - 4 - - - - - - - - - - - - - - - - - 4 OF025 - - - - 4 - - - - - - - - - - - - - - 4 OF026 - - - - - - - 4 - - - - - - - - - - - 4 OF027 - - - - - - - - - - - - - 4 - - - - - 4 OF028 - - - - - 4 - - - - - - - - - - - - - 4 OF029 - - - - - - - - 4 - - - - - - - - - - 4 OF030 - - - - - 4 - - - - - - - - - - - - - 4 OF031 - - - - - - 4 - - - - - - - - - - - - 4 OF032 - - - - - - - - - - - - - 4 - - - - - 4 OF033 - - - - - - - - - - - - - - - - - 4 - 4 OF034 - - - - - - - - - - - - - - - 4 - - - 4 OF035 - 4 - - - - - - - - - - - - - - - - - 4 OF036 - - - - - - - 4 - - - - - - - - - - - 4 OF037 - - - - - - - - - - - - 4 - - - - - - 4 OF038 - - - - 4 - - - - - - - - - - - - - - 4 OF039 - - 4 - - - - - - - - - - - - - - - - 4 OF040 - - - - 6 - - - - - - - - - - - - - - 6 OF041 - - - 2 - - - - - - - - - - - - - - - 2 OF042 - - - - - - - - - - - - - 4 - - - - - 4 OF043 - - - - - - - - - - - - - - - - - 4 - 4 OF044 - - 4 - - - - - - - - - - - - - - - - 4 Professores Oferta Total 90 TABELA 14 Distribuição de horas de ensino final por professor (Conclusão) P01 P02 P03 P04 P05 P06 P08 P09 P10 P11 P12 P13 P14 P15 P17 P18 P19 P23 P24 OF045 - 4 - - - - - - - - - - - - - - - - - 4 OF046 - - - - - - - 4 - - - - - - - - - - - 4 OF047 4 - - - - - - - - - - - - - - - - - - 4 OF048 - - - - 4 - - - - - - - - - - - - - - 4 OF049 - - 4 - - - - - - - - - - - - - - - - 4 OF050 - - - - 6 - - - - - - - - - - - - - - 6 OF051 - - - 2 - - - - - - - - - - - - - - - 2 OF052 4 - - - - - - - - - - - - - - - - - - 4 OF053 - - - - - - - - - - - - - - - 4 - - - 4 OF054 - - - - - - - - - - - - - - - - 4 - - 4 OF055 - - - - - - 4 - - - - - - - - - - - - 4 OF056 - - - - - - - - 4 - - - - - - - - - - 4 OF057 - - - - - - - - - 6 - - - - - - - - - 6 OF058 - - - - - - - - - - 2 - - - - - - - - 2 OF059 - - 4 - - - - - - - - - - - - - - - - 4 OF060 - - - - - - - - - - - - - - - - - - 4 4 OF061 - - - - - - - - - 4 - - - - - - - - - 4 OF062 4 - - - - - - - - - - - - - - - - - - 4 OF063 - - - - - - - - - - - - - - - 4 - - - 4 OF064 - - - - - - - - - - - - - - - - 4 - - 4 OF065 - - - - - - 4 - - - - - - - - - - - - 4 OF066 - - - - - - - - 4 - - - - - - - - - - 4 OF067 - - - - - - - - - 6 - - - - - - - - - 6 OF068 - - - - - - - - - - 2 - - - - - - - - 2 OF069 - - - - - - - - - - - - - - - 4 - - - 4 OF070 - - - - - - - - - - - - - - - - - - 4 4 OF071 - - - - - - - - - - - 4 - - - - - - - 4 Total 28 20 24 12 28 16 16 16 18 16 4 8 12 16 10 16 8 8 8 284 Oferta Professores Total 91 QUADRO 11 Quadro de horários final (Continua) Segunda Terça Quarta Quinta Sexta Turno Horário Oferta Detalhe Oferta Detalhe Oferta Detalhe Oferta Detalhe Oferta Detalhe OF003 D: AEDS I T: 1º P. C.Computação(M) Prof: P10 - Sala: 101 OF001 D: Cálculo I T: 1º P. C.Computação(M) Prof: P01 - Sala: 101 OF003 D: AEDS I T: 1º P. C.Computação(M) Prof: P10 - Sala: 101 OF001 D: Cálculo I T: 1º P. C.Computação(M) Prof: P01 - Sala: 101 OF003 D: AEDS I T: 1º P. C.Computação(M) Prof: P10 - Sala: 101 OF008 D: AEDS II T: 2º P. C.Computação(M) Prof: P17 - Sala: 102 OF006 D: Cálculo II T: 2º P. C.Computação(M) Prof: P15 - Sala: 102 OF008 D: AEDS II T: 2º P. C.Computação(M) Prof: P17 - Sala: 102 OF006 D: Cálculo II T: 2º P. C.Computação(M) Prof: P15 - Sala: 102 OF010 D: Leitura e Prod. de Textos T: 2º P. C.Computação(M) Prof: P09 - Sala: 102 OF013 D: AEDS III T: 3º P. C.Computação(M) Prof: P02 - Sala: 103 OF011 D: Cálculo III T: 3º P. C.Computação(M) Prof: P14 - Sala: 103 OF013 D: AEDS III T: 3º P. C.Computação(M) Prof: P02 - Sala: 103 OF011 D: Cálculo III T: 3º P. C.Computação(M) Prof: P14 - Sala: 103 OF014 D: Intr. aos Sistemas Lógicos T: 3º P. C.Computação(M) Prof: P06 - Sala: 103 OF033 D: Química Geral T: 1º P. Eng. Elétrica(M) Prof: P23 - Sala: 104 OF034 D: Geometria Analítica T: 1º P. Eng. Elétrica(M) Prof: P18 - Sala: 104 OF036 D: Leitura e Prod. de Textos T: 1º P. Eng. Elétrica(M) Prof: P09 - Sala: 104 OF034 D: Geometria Analítica T: 1º P. Eng. Elétrica(M) Prof: P18 - Sala: 104 OF033 D: Química Geral T: 1º P. Eng. Elétrica(M) Prof: P23 - Sala: 104 OF039 D: Álgebra Linear T: 2º P. Eng. Elétrica(M) Prof: P03 - Sala: 105 OF038 D: Física I T: 2º P. Eng. Elétrica(M) Prof: P05 - Sala: 105 OF039 D: Álgebra Linear T: 2º P. Eng. Elétrica(M) Prof: P03 - Sala: 105 OF040 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(M) Prof: P05 - Sala: 105 OF038 D: Física I T: 2º P. Eng. Elétrica(M) Prof: P05 - Sala: 105 OF052 D: Intr. à Aritmética e Álgebra T: 1º P. Matemática(M) Prof: P01 - Sala: 106 OF055 D: Matemática e Informática T: 1º P. Matemática(M) Prof: P08 - Sala: 106 OF052 D: Intr. à Aritmética e Álgebra T: 1º P. Matemática(M) Prof: P01 - Sala: 106 OF055 D: Matemática e Informática T: 1º P. Matemática(M) Prof: P08 - Sala: 106 OF054 D: Leitura e Prod. de Textos T: 1º P. Matemática(M) Prof: P19 - Sala: 106 1 º H o r á r i o ( 7 h 0 0 - 8 h 4 0 ) OF057 D: Estudo de Funções T: 2º P. Matemática(M) Prof: P11 - Sala: 107 OF059 D: Geometria Analítica I T: 2º P. Matemática(M) Prof: P03 - Sala: 107 OF057 D: Estudo de Funções T: 2º P. Matemática(M) Prof: P11 - Sala: 107 OF060 D: Matemática e Educação I T: 2º P. Matemática(M) Prof: P24 - Sala: 107 OF059 D: Geometria Analítica I T: 2º P. Matemática(M) Prof: P03 - Sala: 107 OF002 D: GAAL I T: 1º P. C.Computação(M) Prof: P01 - Sala: 101 OF005 D: Metodologia Científica T: 1º P. C.Computação(M) Prof: P04 - Sala: 101 OF002 D: GAAL I T: 1º P. C.Computação(M) Prof: P01 - Sala: 101 OF005 D: Metodologia Científica T: 1º P. C.Computação(M) Prof: P04 - Sala: 101 OF004 D: Intr. à C.Computação T: 1º P. C.Computação(M) Prof: P02 - Sala: 101 OF007 D: Álgebra Linear T: 2º P. C.Computação(M) Prof: P03 - Sala: 102 OF009 D: Física para Computação T: 2º P. C.Computação(M) Prof: P05 - Sala: 102 OF007 D: Álgebra Linear T: 2º P. C.Computação(M) Prof: P03 - Sala: 102 OF010 D: Leitura e Prod. de Textos T: 2º P. C.Computação(M) Prof: P09 - Sala: 102 OF009 D: Física para Computação T: 2º P. C.Computação(M) Prof: P05 - Sala: 102 OF012 D: Matemática Discreta T: 3º P. C.Computação(M) Prof: P06 - Sala: 103 OF014 D: Intr. aos Sistemas Lógicos T: 3º P. C.Computação(M) Prof: P06 - Sala: 103 OF012 D: Matemática Discreta T: 3º P. C.Computação(M) Prof: P06 - Sala: 103 OF015 D: TGA T: 3º P. C.Computação(M) Prof: P08 - Sala: 103 OF015 D: TGA T: 3º P. C.Computação(M) Prof: P08 - Sala: 103 OF035 D: AEDS T: 1º P. Eng. Elétrica(M) Prof: P02 - Sala: 104 OF032 D: Cálculo I T: 1º P. Eng. Elétrica(M) Prof: P15 - Sala: 104 OF035 D: AEDS T: 1º P. Eng. Elétrica(M) Prof: P02 - Sala: 104 OF032 D: Cálculo I T: 1º P. Eng. Elétrica(M) Prof: P15 - Sala: 104 OF036 D: Leitura e Prod. de Textos T: 1º P. Eng. Elétrica(M) Prof: P09 - Sala: 104 OF040 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(M) Prof: P05 - Sala: 105 OF037 D: Cálculo II T: 2º P. Eng. Elétrica(M) Prof: P14 - Sala: 105 OF040 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(M) Prof: P05 - Sala: 105 OF037 D: Cálculo II T: 2º P. Eng. Elétrica(M) Prof: P14 - Sala: 105 OF041 D: Intr. ao Pens. Científico T: 2º P. Eng. Elétrica(M) Prof: P04 - Sala: 105 OF053 D: Intr. à Geometria Plana T: 1º P. Matemática(M) Prof: P18 - Sala: 106 OF054 D: Leitura e Prod. de Textos T: 1º P. Matemática(M) Prof: P19 - Sala: 106 OF056 D: Tópicos Especiais T: 1º P. Matemática(M) Prof: P10 - Sala: 106 OF053 D: Intr. à Geometria Plana T: 1º P. Matemática(M) Prof: P18 - Sala: 106 OF056 D: Tópicos Especiais T: 1º P. Matemática(M) Prof: P10 - Sala: 106 M a n h ã 2 º H o r á r i o ( 9 h 0 0 - 1 0 h 4 0 ) OF058 D: Filosofia T: 2º P. Matemática(M) Prof: P12 - Sala: 107 OF060 D: Matemática e Educação I T: 2º P. Matemática(M) Prof: P24 - Sala: 107 OF061 D: Trigonometria T: 2º P. Matemática(M) Prof: P11 - Sala: 107 OF057 D: Estudo de Funções T: 2º P. Matemática(M) Prof: P11 - Sala: 107 OF061 D: Trigonometria T: 2º P. Matemática(M) Prof: P11 - Sala: 107 92 QUADRO 11 Quadro de horários final (Conclusão) Segunda Terça Quarta Quinta Sexta Turno Horário Oferta Detalhe Oferta Detalhe Oferta Detalhe Oferta Detalhe Oferta Detalhe OF016 D: Cálculo I T: 1º P. C.Computação(N) Prof: P13 - Sala: 101 OF016 D: Cálculo I T: 1º P. C.Computação(N) Prof: P13 - Sala: 101 OF019 D: AEDS I T: 1º P. C.Computação(N) Prof: P17 - Sala: 101 OF017 D: Cálculo I T: 1º P. C.Computação(N) (T. Esp.) Prof: P14 - Sala: 108 OF019 D: AEDS I T: 1º P. C.Computação(N) Prof: P17 - Sala: 101 OF017 D: Cálculo I T: 1º P. C.Computação(N) (T. Esp.) Prof: P14 - Sala: 108 OF019 D: AEDS I T: 1º P. C.Computação(N) Prof: P17 - Sala: 101 OF024 D: AEDS II T: 2º P. C.Computação(N) Prof: P02 - Sala: 102 OF022 D: Cálculo II T: 2º P. C.Computação(N) Prof: P01 - Sala: 102 OF024 D: AEDS II T: 2º P. C.Computação(N) Prof: P02 - Sala: 102 OF022 D: Cálculo II T: 2º P. C.Computação(N) Prof: P01 - Sala: 102 OF026 D: Leitura e Prod. de Textos T: 2º P. C.Computação(N) Prof: P09 - Sala: 102 OF029 D: AEDS III T: 3º P. C.Computação(N) Prof: P10 - Sala: 103 OF027 D: Cálculo III T: 3º P. C.Computação(N) Prof: P15 - Sala: 103 OF029 D: AEDS III T: 3º P. C.Computação(N) Prof: P10 - Sala: 103 OF027 D: Cálculo III T: 3º P. C.Computação(N) Prof: P15 - Sala: 103 OF030 D: Intr. aos Sistemas Lógicos T: 3º P. C.Computação(N) Prof: P06 - Sala: 103 OF043 D: Química Geral T: 1º P. Eng. Elétrica(N) Prof: P23 - Sala: 104 OF044 D: Geometria Analítica T: 1º P. Eng. Elétrica(N) Prof: P03 - Sala: 104 OF046 D: Leitura e Prod. de Textos T: 1º P. Eng. Elétrica(N) Prof: P09 - Sala: 104 OF044 D: Geometria Analítica T: 1º P. Eng. Elétrica(N) Prof: P03 - Sala: 104 OF043 D: Química Geral T: 1º P. Eng. Elétrica(N) Prof: P23 - Sala: 104 OF049 D: Álgebra Linear T: 2º P. Eng. Elétrica(N) Prof: P03 - Sala: 105 OF048 D: Física I T: 2º P. Eng. Elétrica(N) Prof: P05 - Sala: 105 OF049 D: Álgebra Linear T: 2º P. Eng. Elétrica(N) Prof: P03 - Sala: 105 OF050 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(N) Prof: P05 - Sala: 105 OF048 D: Física I T: 2º P. Eng. Elétrica(N) Prof: P05 - Sala: 105 OF062 D: Intr. à Aritmética e Álgebra T: 1º P. Matemática(N) Prof: P01 - Sala: 106 OF065 D: Matemática e Informática T: 1º P. Matemática(N) Prof: P08 - Sala: 106 OF062 D: Intr. à Aritmética e Álgebra T: 1º P. Matemática(N) Prof: P01 - Sala: 106 OF065 D: Matemática e Informática T: 1º P. Matemática(N) Prof: P08 - Sala: 106 OF064 D: Leitura e Prod. de Textos T: 1º P. Matemática(N) Prof: P19 - Sala: 106 1 º H o r á r i o ( 1 9 h 0 0 - 2 0 h 4 0 ) OF067 D: Estudo de Funções T: 2º P. Matemática(N) Prof: P11 - Sala: 107 OF069 D: Geometria Analítica I T: 2º P. Matemática(N) Prof: P18 - Sala: 107 OF067 D: Estudo de Funções T: 2º P. Matemática(N) Prof: P11 - Sala: 107 OF070 D: Matemática e Educação I T: 2º P. Matemática(N) Prof: P24 - Sala: 107 OF069 D: Geometria Analítica I T: 2º P. Matemática(N) Prof: P18 - Sala: 107 OF018 D: GAAL I T: 1º P. C.Computação(N) Prof: P03 - Sala: 101 OF021 D: Metodologia Científica T: 1º P. C.Computação(N) Prof: P04 - Sala: 101 OF018 D: GAAL I T: 1º P. C.Computação(N) Prof: P03 - Sala: 101 OF021 D: Metodologia Científica T: 1º P. C.Computação(N) Prof: P04 - Sala: 101 OF020 D: Intr. à C.Computação T: 1º P. C.Computação(N) Prof: P02 - Sala: 101 OF023 D: Álgebra Linear T: 2º P. C.Computação(N) Prof: P01 - Sala: 102 OF025 D: Física para Computação T: 2º P. C.Computação(N) Prof: P05 - Sala: 102 OF023 D: Álgebra Linear T: 2º P. C.Computação(N) Prof: P01 - Sala: 102 OF026 D: Leitura e Prod. de Textos T: 2º P. C.Computação(N) Prof: P09 - Sala: 102 OF025 D: Física para Computação T: 2º P. C.Computação(N) Prof: P05 - Sala: 102 OF028 D: Matemática Discreta T: 3º P. C.Computação(N) Prof: P06 - Sala: 103 OF030 D: Intr. aos Sistemas Lógicos T: 3º P. C.Computação(N) Prof: P06 - Sala: 103 OF028 D: Matemática Discreta T: 3º P. C.Computação(N) Prof: P06 - Sala: 103 OF031 D: TGA T: 3º P. C.Computação(N) Prof: P08 - Sala: 103 OF031 D: TGA T: 3º P. C.Computação(N) Prof: P08 - Sala: 103 OF045 D: AEDS T: 1º P. Eng. Elétrica(N) Prof: P02 - Sala: 104 OF042 D: Cálculo I T: 1º P. Eng. Elétrica(N) Prof: P15 - Sala: 104 OF045 D: AEDS T: 1º P. Eng. Elétrica(N) Prof: P02 - Sala: 104 OF042 D: Cálculo I T: 1º P. Eng. Elétrica(N) Prof: P15 - Sala: 104 OF046 D: Leitura e Prod. de Textos T: 1º P. Eng. Elétrica(N) Prof: P09 - Sala: 104 OF050 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(N) Prof: P05 - Sala: 105 OF047 D: Cálculo II T: 2º P. Eng. Elétrica(N) Prof: P01 - Sala: 105 OF050 D: Circuitos Elétricos I T: 2º P. Eng. Elétrica(N) Prof: P05 - Sala: 105 OF047 D: Cálculo II T: 2º P. Eng. Elétrica(N) Prof: P01 - Sala: 105 OF051 D: Intr. ao Pens. Científico T: 2º P. Eng. Elétrica(N) Prof: P04 - Sala: 105 OF063 D: Intr. à Geometria Plana T: 1º P. Matemática(N) Prof: P18 - Sala: 106 OF064 D: Leitura e Prod. de Textos T: 1º P. Matemática(N) Prof: P19 - Sala: 106 OF066 D: Tópicos Especiais T: 1º P. Matemática(N) Prof: P10 - Sala: 106 OF063 D: Intr. à Geometria Plana T: 1º P. Matemática(N) Prof: P18 - Sala: 106 OF066 D: Tópicos Especiais T: 1º P. Matemática(N) Prof: P10 - Sala: 106 N o i t e 2 º H o r á r i o ( 2 1 h 0 0 - 2 2 h 4 0 ) OF068 D: Filosofia T: 2º P. Matemática(N) Prof: P12 - Sala: 107 OF070 D: Matemática e Educação I T: 2º P. Matemática(N) Prof: P24 - Sala: 107 OF071 D: Trigonometria T: 2º P. Matemática(N) Prof: P13 - Sala: 107 OF067 D: Estudo de Funções T: 2º P. Matemática(N) Prof: P11 - Sala: 107 OF071 D: Trigonometria T: 2º P. Matemática(N) Prof: P13 - Sala: 107 93 4.6.4 - Interação entre Fases As fases do processo ocorrem sequencialmente e periodicamente (por exemplo em um semestre). No entanto, pode-se assumir que existe uma interação entre as fases, visto que o problema de elaboração de quadros de horários tem um comportamento dinâmico. Como por exemplo, após ter sido definido o plano de ofertas na primeira fase, por algum motivo, foi observado, na segunda fase, na construção do quadro de ofertas que uma determinada turma, se dividida, viabilizaria a utilização de um determinado laboratório de capacidade reduzida, evitando um conflito de horário em um laboratório maior que tem uso compartilhado, não necessitando portanto, construir outro. Nesse caso, a primeira fase foi revista e a divisão de tal turma foi considerada. Outras situações podem ser observadas, por exemplo, entre a segunda e terceira fase. Suponha que apenas um professor entre todos os disponíveis para a alocação, na terceira fase, seja capaz de atender uma determinada oferta de disciplina. Sendo assim, considerando que o mesmo tem uma disponibilidade limitada, a definição do quadro de ofertas na segunda fase será influenciada por essa informação, restringindo, portanto, as possibilidades de posicionamento de tal oferta de disciplina no quadro de horários. O aprendizado armazenado após iterações do processo, pode inclusive aprimorar as técnicas de realização das atividades. Apesar de existirem momentos de reavaliação dos resultados, o processo é seqüencial e assume que existe um produto final de cada fase, sendo que o mesmo é utilizado como informação para o início da fase seguinte. 94 4.7 - Extensões ao exemplo - análises em outros cenários Modificações no cenário dos dados de entrada podem implicar em mudanças nas soluções para as alocações nos quadros de horários. Abaixo são apresentadas situações hipotéticas para avaliar o impacto sobre a solução final, todas baseadas nos dados do exemplo anteriormente descrito, denominado EP (exemplo principal). O exemplo E1 considera que existem 2 (dois) campus distintos onde as ofertas de disciplinas são realizadas. O exemplo E2 considera uma situação de evolução do corpo docente e conseqüente modificação nos parâmetros de entrada para a função objetivo a ser otimizada. O exemplo E3, mostra a situação que um professor possui pré-alocação em atividades complementares. Por fim, o exemplo E4 mostra o efeito de se ter uma maior disponibilidade dos professores para atendimento das ofertas de disciplinas. 4.7.1 - Exemplo E1 - Instituições com vários campi De acordo com o QUADRO 11, o professor P01 atende, entre outras, as ofertas de disciplina OF002 e OF052. Ambas ocorrem nas segundas e quartas-feiras, no turno da manhã. A OF052 ocorre no 1º horário e a OF002 ocorre no 2º horário. Considerando que a OF002, pertencente ao curso de Ciência da Computação, ocorre no campus C1 e que OF052, pertencente ao curso de Matemática, ocorre no campus C2, ocorre uma situação indesejada visto que o professor terá que deslocar entre dois campi dentro de um mesmo turno para lecionar as aulas correspondentes. No caso de uma IES possuir diversos campi, deve-se realizar a alocação de professores ao quadro de horários utilizando o modelo APM. Considerando que os cursos de Ciência da Computação e Engenharia Elétrica estão no campus C1 e que o curso de Matemática está no campus C2, a partir das informações apresentadas no exemplo, obtêm-se a solução apresentada na TAB. 15. 95 TABELA 15 Enquadramento dos professores na solução final (E1) Professor Regime de Trabalho Horas Ensino Total de Horas P01 P38 28 38 P02 I20 20 40 P03 P32 24 32 P04 I12 12 40 P05 P38 28 38 P06 I16 16 40 P08 I08 8 40 P09 P22 16 22 P10 H18 18 18 P12 H04 4 4 P13 P16 12 16 P14 H12 12 12 P15 H16 16 16 P17 P12 8 12 P18 P22 16 22 P19 P12 8 12 P21 H20 20 20 P23 H08 8 8 P24 P14 10 14 Total 284 444 A solução obtida tem mais horas no total (444 horas) que se o modelo fosse tratado com um único campus (436 horas). A TAB. 16 apresenta a alocação final das disciplinas. A partir das informações obtidas na solução, o quadro de horários final (QUADRO 11) deverá ser remontado com os novos dados. 96 TABELA 16 Distribuição de horas de ensino final por professor (E1) (Continua) P01 P02 P03 P04 P05 P06 P08 P09 P10 P12 P13 P14 P15 P17 P18 P19 P21 P23 P24 OF001 - - - - - - - - - - - 4 - - - - - - - 4 OF002 - - - - - - - - - - - - - - 4 - - - - 4 OF003 - - - - - - - - 6 - - - - - - - - - - 6 OF004 - - - - - - - - - - - - - - - - - - 2 2 OF005 - - - 4 - - - - - - - - - - - - - - - 4 OF006 4 - - - - - - - - - - - - - - - - - - 4 OF007 4 - - - - - - - - - - - - - - - - - - 4 OF008 - - - - - - - - - - - - - 4 - - - - - 4 OF009 - - - - 4 - - - - - - - - - - - - - - 4 OF010 - - - - - - - 4 - - - - - - - - - - - 4 OF011 - - - - - - - - - - - - 4 - - - - - - 4 OF012 - - - - - 4 - - - - - - - - - - - - - 4 OF013 - 4 - - - - - - - - - - - - - - - - - 4 OF014 - - - - - 4 - - - - - - - - - - - - - 4 OF015 - - - - - - 4 - - - - - - - - - - - - 4 OF016 - - - - - - - - - - - 4 - - - - - - - 4 OF017 - - - - - - - - - - 4 - - - - - - - - 4 OF018 - - - - - - - - - - - - - - 4 - - - - 4 OF019 - 6 - - - - - - - - - - - - - - - - - 6 OF020 - 2 - - - - - - - - - - - - - - - - - 2 OF021 - - - 4 - - - - - - - - - - - - - - - 4 OF022 4 - - - - - - - - - - - - - - - - - - 4 OF023 4 - - - - - - - - - - - - - - - - - - 4 OF024 - - - - - - - - - - - - - 4 - - - - - 4 OF025 - - - - 4 - - - - - - - - - - - - - - 4 OF026 - - - - - - - 4 - - - - - - - - - - - 4 OF027 - - - - - - - - - - - - 4 - - - - - - 4 OF028 - - - - - 4 - - - - - - - - - - - - - 4 OF029 - - - - - - - - 4 - - - - - - - - - - 4 OF030 - - - - - 4 - - - - - - - - - - - - - 4 OF031 - - - - - - 4 - - - - - - - - - - - - 4 OF032 - - - - - - - - - - - - 4 - - - - - - 4 OF033 - - - - - - - - - - - - - - - - - 4 - 4 OF034 - - - - - - - - - - - - - - 4 - - - - 4 OF035 - 4 - - - - - - - - - - - - - - - - - 4 OF036 - - - - - - - 4 - - - - - - - - - - - 4 OF037 4 - - - - - - - - - - - - - - - - - - 4 OF038 - - - - 4 - - - - - - - - - - - - - - 4 OF039 4 - - - - - - - - - - - - - - - - - - 4 OF040 - - - - 6 - - - - - - - - - - - - - - 6 OF041 - - - 2 - - - - - - - - - - - - - - - 2 OF042 - - - - - - - - - - - 4 - - - - - - - 4 OF043 - - - - - - - - - - - - - - - - - 4 - 4 OF044 - - - - - - - - - - - - - - 4 - - - - 4 Professores Oferta Total 97 TABELA 16 Distribuição de horas de ensino final por professor (E1) (Conclusão) P01 P02 P03 P04 P05 P06 P08 P09 P10 P12 P13 P14 P15 P17 P18 P19 P21 P23 P24 OF045 - 4 - - - - - - - - - - - - - - - - - 4 OF046 - - - - - - - 4 - - - - - - - - - - - 4 OF047 - - - - - - - - - - - - 4 - - - - - - 4 OF048 - - - - 4 - - - - - - - - - - - - - - 4 OF049 4 - - - - - - - - - - - - - - - - - - 4 OF050 - - - - 6 - - - - - - - - - - - - - - 6 OF051 - - - 2 - - - - - - - - - - - - - - - 2 OF052 - - 4 - - - - - - - - - - - - - - - - 4 OF053 - - 4 - - - - - - - - - - - - - - - - 4 OF054 - - - - - - - - - - - - - - - 4 - - - 4 OF055 - - - - - - - - 4 - - - - - - - - - - 4 OF056 - - - - - - - - - - - - - - - - 4 - - 4 OF057 - - - - - - - - - - - - - - - - 6 - - 6 OF058 - - - - - - - - - 2 - - - - - - - - - 2 OF059 - - 4 - - - - - - - - - - - - - - - - 4 OF060 - - - - - - - - - - - - - - - - - - 4 4 OF061 - - - - - - - - - - 4 - - - - - - - - 4 OF062 - - 4 - - - - - - - - - - - - - - - - 4 OF063 - - 4 - - - - - - - - - - - - - - - - 4 OF064 - - - - - - - - - - - - - - - 4 - - - 4 OF065 - - - - - - - - 4 - - - - - - - - - - 4 OF066 - - - - - - - - - - - - - - - - 4 - - 4 OF067 - - - - - - - - - - - - - - - - 6 - - 6 OF068 - - - - - - - - - 2 - - - - - - - - - 2 OF069 - - 4 - - - - - - - - - - - - - - - - 4 OF070 - - - - - - - - - - - - - - - - - - 4 4 OF071 - - - - - - - - - - 4 - - - - - - - - 4 Total 28 20 24 12 28 16 8 16 18 4 12 12 16 8 16 8 20 8 10 284 Oferta Professores Total 98 4.7.2 - Exemplo E2 - Evolução no Quadro Docente De acordo com a evolução do corpo docente, novos cenários vão se construindo tal que os coeficientes da função objetivo do modelo para alocação de professores também vão se alterando. Uma nova qualificação do professor, uma nova contratação, uma expansão de cursos e outros eventos vão implicar em novas características do quadro docente. Supondo que o professor P07 tenha terminado o doutorado, deixando, portanto, de ser um especialista. Logo, seu f(i) que era 10 (TAB. 12) foi para 4. O professor P07 era o sexto na lista das menores penalidades f(i). Com esse novo título acadêmico, o professor passou a ser o quarto. Com essas novas informações a solução para o modelo APU é alterada e então o professor P07 passou a participar da alocação (TAB. 17). TABELA 17 Enquadramento dos professores na solução final (E2) Professor Regime de Trabalho Horas Ensino Total de Horas P01 P38 28 38 P02 I20 20 40 P03 H24 24 24 P04 I12 12 40 P05 P38 28 38 P06 I16 16 40 P07 I08 8 40 P08 I16 16 40 P09 P22 16 22 P10 H18 18 18 P12 H04 4 4 P13 H08 8 8 P14 H12 12 12 P15 H16 16 16 P17 P14 10 14 P18 P22 16 22 P19 P12 8 12 P21 H16 16 16 P24 P12 8 12 Total 284 456 O total de horas utilizados na solução foi de 456 que é maior que a solução obtida no primeiro cenário (436 horas). Esse crescimento se deu ao fato que a prioridade para alocação do professor P07 aumentou, mas, no entanto, sua capacidade de atendimento das ofertas de 99 disciplinas não. O professor P07 pode apenas atender as ofertas de disciplina OF033 e OF043 (QUADRO 9). Sendo assim, o modelo alocou o professor, mas, no entanto, a carga horária complementar do mesmo foi maior, implicando em um aumento da carga horária total resultante. Por outro lado, a solução conta com mais um professor doutor, o que implica em um conceito no indicador titulação melhor. Obviamente, os pesos relativos a cada uma das características docentes podem ser alterados a fim de refletir os diversos interesses e particularidades das instituições. A alocação final dos professores às disciplinas é apresentado na TAB. 18. A partir das informações obtidas na solução, o quadro de horários final (QUADRO 11) deverá ser remontado com os novos dados. 100 TABELA 18 Distribuição de horas de ensino final por professor (E2) (Continua) P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P12 P13 P14 P15 P17 P18 P19 P21 P24 OF001 4 - - - - - - - - - - - - - - - - - - 4 OF002 - - 4 - - - - - - - - - - - - - - - - 4 OF003 - - - - - - - - - - - - - - 6 - - - - 6 OF004 - 2 - - - - - - - - - - - - - - - - - 2 OF005 - - - 4 - - - - - - - - - - - - - - - 4 OF006 - - - - - - - - - - - - 4 - - - - - - 4 OF007 4 - - - - - - - - - - - - - - - - - - 4 OF008 - - - - - - - - - 4 - - - - - - - - - 4 OF009 - - - - 4 - - - - - - - - - - - - - - 4 OF010 - - - - - - - - 4 - - - - - - - - - - 4 OF011 - - - - - - - - - - - - - 4 - - - - - 4 OF012 - - - - - 4 - - - - - - - - - - - - - 4 OF013 - 4 - - - - - - - - - - - - - - - - - 4 OF014 - - - - - 4 - - - - - - - - - - - - - 4 OF015 - - - - - - - 4 - - - - - - - - - - - 4 OF016 - - - - - - - - - - - 4 - - - - - - - 4 OF017 - - - - - - - - - - - - 4 - - - - - - 4 OF018 - - 4 - - - - - - - - - - - - - - - - 4 OF019 - - - - - - - - - 6 - - - - - - - - - 6 OF020 - 2 - - - - - - - - - - - - - - - - - 2 OF021 - - - 4 - - - - - - - - - - - - - - - 4 OF022 - - - - - - - - - - - - - 4 - - - - - 4 OF023 4 - - - - - - - - - - - - - - - - - - 4 OF024 - 4 - - - - - - - - - - - - - - - - - 4 OF025 - - - - 4 - - - - - - - - - - - - - - 4 OF026 - - - - - - - - - - - - - - - - 4 - - 4 OF027 4 - - - - - - - - - - - - - - - - - - 4 OF028 - - - - - 4 - - - - - - - - - - - - - 4 OF029 - - - - - - - - - - - - - - 4 - - - - 4 OF030 - - - - - 4 - - - - - - - - - - - - - 4 OF031 - - - - - - - 4 - - - - - - - - - - - 4 OF032 - - - - - - - - - - - - 4 - - - - - - 4 OF033 - - - - - - 4 - - - - - - - - - - - - 4 OF034 - - - - - - - - - - - - - - - 4 - - - 4 OF035 - 4 - - - - - - - - - - - - - - - - - 4 OF036 - - - - - - - - 4 - - - - - - - - - - 4 OF037 - - - - - - - - - - - - - 4 - - - - - 4 OF038 - - - - 4 - - - - - - - - - - - - - - 4 OF039 - - 4 - - - - - - - - - - - - - - - - 4 OF040 - - - - 6 - - - - - - - - - - - - - - 6 OF041 - - - 2 - - - - - - - - - - - - - - - 2 OF042 - - - - - - - - - - - - - 4 - - - - - 4 OF043 - - - - - - 4 - - - - - - - - - - - - 4 OF044 - - - - - - - - - - - - - - - 4 - - - 4 Professores Oferta Total 101 TABELA 18 Distribuição de horas de ensino final por professor (E2) (Conclusão) P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P12 P13 P14 P15 P17 P18 P19 P21 P24 OF045 - 4 - - - - - - - - - - - - - - - - - 4 OF046 - - - - - - - - 4 - - - - - - - - - - 4 OF047 4 - - - - - - - - - - - - - - - - - - 4 OF048 - - - - 4 - - - - - - - - - - - - - - 4 OF049 - - 4 - - - - - - - - - - - - - - - - 4 OF050 - - - - 6 - - - - - - - - - - - - - - 6 OF051 - - - 2 - - - - - - - - - - - - - - - 2 OF052 4 - - - - - - - - - - - - - - - - - - 4 OF053 - - - - - - - - - - - - - - - 4 - - - 4 OF054 - - - - - - - - - - - - - - - - 4 - - 4 OF055 - - - - - - - 4 - - - - - - - - - - - 4 OF056 - - - - - - - - - 4 - - - - - - - - - 4 OF057 - - - - - - - - - - - - - - - - - 6 - 6 OF058 - - - - - - - - - - 2 - - - - - - - - 2 OF059 - - 4 - - - - - - - - - - - - - - - - 4 OF060 - - - - - - - - - - - - - - - - - - 4 4 OF061 - - - - - - - - - - - 4 - - - - - - - 4 OF062 4 - - - - - - - - - - - - - - - - - - 4 OF063 - - - - - - - - - - - - - - - 4 - - - 4 OF064 - - - - - - - - 4 - - - - - - - - - - 4 OF065 - - - - - - - 4 - - - - - - - - - - - 4 OF066 - - - - - - - - - 4 - - - - - - - - - 4 OF067 - - - - - - - - - - - - - - - - - 6 - 6 OF068 - - - - - - - - - - 2 - - - - - - - - 2 OF069 - - 4 - - - - - - - - - - - - - - - - 4 OF070 - - - - - - - - - - - - - - - - - - 4 4 OF071 - - - - - - - - - - - - - - - - - 4 - 4 Total 28 20 24 12 28 16 8 16 16 18 4 8 12 16 10 16 8 16 8 284 Oferta Professores Total 102 4.7.3 - Exemplo E3 - Professores pré-alocados em atividades complementares Suponha que o professor P01 foi indicado para participar de um projeto de pesquisa que vai alocá-lo por 16 horas semanais. Além disso, o professor foi também nomeado para assumir uma atividade administrativo-acadêmica de supervisão de laboratórios específicos, a qual irá alocá-lo por mais 8 horas semanais. Sendo assim, o professor P01 possui 24 horas semanais complementares pré-alocadas. Na solução do EP (exemplo principal), o professor P01 foi alocado para atender a 7 (sete) ofertas de disciplina, totalizando 28 horas semanais envolvido em atividades de ensino. Visto que ele está pré-alocado em 24 horas semanais, o modelo APU poderá alocá-lo para até 16 horas semanais (aproximadamente 4 ofertas de disciplina) pois o limite máximo de carga horária semanal de um professor é 40 (quarenta). Sendo assim, algumas das ofertas que o professor atendia deverão ser alocadas para outros professores, de acordo o modelo. Portanto, a partir do novo cenário, obtêm-se a solução apresentada na TAB. 19 e a alocação final dos professores às disciplinas é apresentado na TAB. 20. 103 TABELA 19 Enquadramento dos professores na solução final (E3) Professor Regime de Trabalho Horas Ensino Total de Horas P01 I16 16 40 P02 I20 20 40 P03 H24 24 24 P04 I12 12 40 P05 P38 22 38 P06 I16 16 40 P08 I16 16 40 P09 P22 16 22 P10 H18 18 18 P11 P16 12 16 P12 H04 4 4 P13 H24 24 24 P14 H12 12 12 P15 H16 16 16 P17 P14 10 14 P18 P22 22 22 P19 P12 8 12 P23 H08 8 8 P24 P12 8 12 Total 284 442 O total de horas utilizados foi de 442 horas, maior que o valor da solução do primeiro cenário apresentado (436 horas). Esse aumento indica o custo associado à decisão de se alocar o professor P01 para as atividades complementares. Ao observar o resultado, um gestor poderia, por exemplo, alocar o professor apenas para a atividade de pesquisa (16 horas) e alocar um outro docente para a atividade de supervisão de laboratório. Então uma nova simulação poderia ser feita com o intuito de verificar os resultados obtidos, antes de homologar a alocação final a ser utilizada pela instituição. A partir das informações obtidas na solução, o quadro de horários final (QUADRO 11) deverá ser remontado com os novos dados. 104 TABELA 20 Distribuição de horas de ensino final por professor (E3) (Continua) P01 P02 P03 P04 P05 P06 P08 P09 P10 P11 P12 P13 P14 P15 P17 P18 P19 P23 P24 OF001 - - - - - - - - - - - 4 - - - - - - - 4 OF002 - - 4 - - - - - - - - - - - - - - - - 4 OF003 - - - - - - - - - - - - - - 6 - - - - 6 OF004 - 2 - - - - - - - - - - - - - - - - - 2 OF005 - - - 4 - - - - - - - - - - - - - - - 4 OF006 - - - - - - - - - - - - 4 - - - - - - 4 OF007 4 - - - - - - - - - - - - - - - - - - 4 OF008 - 4 - - - - - - - - - - - - - - - - - 4 OF009 - - - - 4 - - - - - - - - - - - - - - 4 OF010 - - - - - - - - - - - - - - - - 4 - - 4 OF011 - - - - - - - - - - - - - 4 - - - - - 4 OF012 - - - - - 4 - - - - - - - - - - - - - 4 OF013 - - - - - - - - 4 - - - - - - - - - - 4 OF014 - - - - - 4 - - - - - - - - - - - - - 4 OF015 - - - - - - 4 - - - - - - - - - - - - 4 OF016 - - - - - - - - - - - - - 4 - - - - - 4 OF017 - - - - - - - - - - - 4 - - - - - - - 4 OF018 - - 4 - - - - - - - - - - - - - - - - 4 OF019 - - - - - - - - 6 - - - - - - - - - - 6 OF020 - 2 - - - - - - - - - - - - - - - - - 2 OF021 - - - 4 - - - - - - - - - - - - - - - 4 OF022 - - - - - - - - - - - - 4 - - - - - - 4 OF023 4 - - - - - - - - - - - - - - - - - - 4 OF024 - - - - - - - - - - - - - - 4 - - - - 4 OF025 - - - - 4 - - - - - - - - - - - - - - 4 OF026 - - - - - - - 4 - - - - - - - - - - - 4 OF027 4 - - - - - - - - - - - - - - - - - - 4 OF028 - - - - - 4 - - - - - - - - - - - - - 4 OF029 - 4 - - - - - - - - - - - - - - - - - 4 OF030 - - - - - 4 - - - - - - - - - - - - - 4 OF031 - - - - - - 4 - - - - - - - - - - - - 4 OF032 - - - - - - - - - - - - - 4 - - - - - 4 OF033 - - - - - - - - - - - - - - - - - 4 - 4 OF034 - - 4 - - - - - - - - - - - - - - - - 4 OF035 - 4 - - - - - - - - - - - - - - - - - 4 OF036 - - - - - - - 4 - - - - - - - - - - - 4 OF037 - - - - - - - - - - - - 4 - - - - - - 4 OF038 - - - - 4 - - - - - - - - - - - - - - 4 OF039 - - 4 - - - - - - - - - - - - - - - - 4 OF040 - - - - 6 - - - - - - - - - - - - - - 6 OF041 - - - 2 - - - - - - - - - - - - - - - 2 OF042 4 - - - - - - - - - - - - - - - - - - 4 OF043 - - - - - - - - - - - - - - - - - 4 - 4 OF044 - - - - - - - - - - - - - - - 4 - - - 4 Professores Oferta Total 105 TABELA 20 Distribuição de horas de ensino final por professor (E3) (Conclusão) P01 P02 P03 P04 P05 P06 P08 P09 P10 P11 P12 P13 P14 P15 P17 P18 P19 P23 P24 OF045 - 4 - - - - - - - - - - - - - - - - - 4 OF046 - - - - - - - 4 - - - - - - - - - - - 4 OF047 - - - - - - - - - - - - - 4 - - - - - 4 OF048 - - - - 4 - - - - - - - - - - - - - - 4 OF049 - - 4 - - - - - - - - - - - - - - - - 4 OF050 - - - - 6 - - - - - - - - - - - - - - 6 OF051 - - - 2 - - - - - - - - - - - - - - - 2 OF052 - - - - - - - - - - - 4 - - - - - - - 4 OF053 - - - - - - - - - - - - - - - 4 - - - 4 OF054 - - - - - - - 4 - - - - - - - - - - - 4 OF055 - - - - - - 4 - - - - - - - - - - - - 4 OF056 - - - - - - - - 4 - - - - - - - - - - 4 OF057 - - - - - - - - - 6 - - - - - - - - - 6 OF058 - - - - - - - - - - 2 - - - - - - - - 2 OF059 - - - - - - - - - - - - - - - 4 - - - 4 OF060 - - - - - - - - - - - - - - - - - - 4 4 OF061 - - - - - - - - - - - 4 - - - - - - - 4 OF062 - - - - - - - - - - - 4 - - - - - - - 4 OF063 - - - - - - - - - - - - - - - 4 - - - 4 OF064 - - - - - - - - - - - - - - - - 4 - - 4 OF065 - - - - - - 4 - - - - - - - - - - - - 4 OF066 - - - - - - - - 4 - - - - - - - - - - 4 OF067 - - - - - - - - - 6 - - - - - - - - - 6 OF068 - - - - - - - - - - 2 - - - - - - - - 2 OF069 - - 4 - - - - - - - - - - - - - - - - 4 OF070 - - - - - - - - - - - - - - - - - - 4 4 OF071 - - - - - - - - - - - 4 - - - - - - - 4 Total 16 20 24 12 28 16 16 16 18 12 4 24 12 16 10 16 8 8 8 284 Oferta Professores Total 106 4.7.4 - Exemplo E4 - Aumento na disponibilidade dos professores Considerando a hipótese de que todo professor poderia atender qualquer disciplina, a solução da alocação de professores ocorreria de acordo com a solução apontada pelo modelo APRAC. No entanto, essa situação é irreal e não condiz com nenhuma diretriz de qualidade acadêmica aplicável na prática. Normalmente, os professores possuem formação em áreas do conhecimento específicas e dessa forma, lecionam disciplinas específicas que normalmente possuem certa proximidade temática. Observando o modelo, quanto mais ofertas de disciplinas os professores puderem em média atender, melhor será o resultado da alocação, visto que as atividades estarão concentradas em menos professores os quais terão uma maior carga horária. Quando o número de ofertas de disciplinas de um determinado tipo (mesma ementa) é pequeno, o aumento de carga horária de um determinado professor automaticamente implicará em muitos tipos de disciplinas sendo lecionadas pelo mesmo. Essa situação não é desejável observando aspectos de qualidade didático-pedagógica. Por outro lado, existem disciplinas que são ofertadas diversas vezes, e em alguns casos, em diversos cursos. Nesse caso, o professor poderia atender mais disciplinas, pois todas seriam do mesmo tipo. Logo, considerando hipoteticamente um aumento de 300 novas disponibilidades dos 24 professores para atenderem outras ofertas, obtêm-se uma nova solução para o problema de alocação. As novas disponibilidades de oferta são apresentadas no QUADRO 12 (são 300 a mais que o QUADRO 9). A partir dos novos dados, a solução da alocação de professores pelo modelo APU é apresentada na TAB. 21 e a alocação final dos professores às disciplinas é apresentada na TAB. 22. A partir das informações obtidas na solução, o quadro de horários final (QUADRO 11) deverá ser remontado com os novos dados. 107 QUADRO 12 Relação de ofertas de disciplinas afins aos professores (E4) Prof. Ofertas de Disciplinas Total P01 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF059; OF060; OF061; OF062; OF063; OF069; OF070; OF071; 31 P02 OF002; OF003; OF004; OF007; OF008; OF012; OF013; OF014; OF018; OF019; OF020; OF023; OF024; OF028; OF029; OF030; OF035; OF039; OF045; OF049; OF052; OF055; OF056; OF057; OF062; OF065; OF066; OF067; 28 P03 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF055; OF059; OF060; OF061; OF062; OF063; OF065; OF069; OF070; OF071; 33 P04 OF005; OF010; OF021; OF026; OF036; OF041; OF046; OF051; OF054; OF058; OF064; OF068; 12 P05 OF003; OF008; OF009; OF013; OF014; OF019; OF024; OF025; OF029; OF030; OF033; OF035; OF038; OF040; OF043; OF045; OF048; OF050; 18 P06 OF002; OF003; OF007; OF008; OF012; OF013; OF014; OF018; OF019; OF023; OF024; OF028; OF029; OF030; OF035; OF039; OF045; OF049; OF052; OF057; OF062; OF067; 22 P07 OF009; OF025; OF033; OF038; OF040; OF043; OF048; OF050; 8 P08 OF015; OF031; OF055; OF065; OF070; 5 P09 OF005; OF010; OF021; OF026; OF036; OF041; OF046; OF051; OF054; OF058; OF064; OF068; 12 P10 OF003; OF004; OF008; OF009; OF013; OF014; OF019; OF020; OF024; OF025; OF029; OF030; OF033; OF035; OF038; OF040; OF043; OF045; OF048; OF050; OF055; OF056; OF065; OF066; 24 P11 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF057; OF059; OF061; OF062; OF063; OF067; OF069; OF071; 31 P12 OF005; OF010; OF015; OF021; OF026; OF031; OF036; OF041; OF046; OF051; OF054; OF058; OF064; OF068; 14 P13 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF059; OF060; OF061; OF062; OF063; OF069; OF070; OF071; 31 P14 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF056; OF057; OF059; OF062; OF063; OF066; OF067; OF069; 31 P15 OF001; OF002; OF006; OF007; OF011; OF012; OF016; OF017; OF018; OF022; OF023; OF027; OF028; OF032; OF034; OF037; OF039; OF042; OF044; OF047; OF049; OF052; OF053; OF056; OF059; OF060; OF062; OF063; OF066; OF069; OF070; 31 P16 OF005; OF010; OF021; OF026; OF036; OF041; OF046; OF051; OF054; OF058; OF064; OF068; 12 P17 OF003; OF004; OF008; OF013; OF019; OF020; OF024; OF029; OF035; OF045; OF055; OF065; 12 P18 OF001; OF002; OF003; OF004; OF006; OF007; OF008; OF011; OF012; OF013; OF016; OF017; OF018; OF019; OF020; OF022; OF023; OF024; OF027; OF028; OF029; OF032; OF034; OF035; OF037; OF039; OF042; OF044; OF045; OF047; OF049; OF052; OF053; OF059; OF062; OF063; OF069; 37 P19 OF005; OF010; OF015; OF021; OF026; OF031; OF036; OF041; OF046; OF051; OF054; OF058; OF064; OF068; 14 P20 OF003; OF008; OF009; OF013; OF014; OF019; OF020; OF024; OF025; OF029; OF030; OF033; OF035; OF038; OF040; OF043; OF045; OF048; OF050; 19 P21 OF002; OF005; OF007; OF010; OF012; OF018; OF021; OF023; OF026; OF028; OF036; OF039; OF041; OF046; OF049; OF051; OF052; OF054; OF056; OF057; OF058; OF061; OF062; OF064; OF066; OF067; OF068; OF071; 28 P22 OF015; OF031; 2 P23 OF005; OF009; OF010; OF021; OF025; OF026; OF033; OF036; OF038; OF040; OF041; OF043; OF046; OF048; OF050; OF051; OF054; OF058; OF064; OF068; 20 P24 OF003; OF004; OF008; OF009; OF013; OF014; OF015; OF019; OF020; OF024; OF025; OF029; OF030; OF031; OF033; OF035; OF038; OF043; OF045; OF048; OF050; OF056; OF060; OF066; OF070; 25 Total 500 108 TABELA 21 Enquadramento dos professores na solução final (E4) Professor Regime de Trabalho Horas Ensino Total de Horas P01 H40 40 40 P02 P40 30 40 P03 H32 32 32 P04 I16 16 40 P05 P38 28 38 P06 I20 20 40 P07 I20 20 40 P08 I16 16 40 P09 P19 14 19 P11 H08 8 8 P13 H08 8 8 P14 P16 12 16 P18 H30 30 30 P21 H10 10 10 Total 284 401 109 TABELA 22 Distribuição de horas de ensino final por professor (Continua) P01 P02 P03 P04 P05 P06 P07 P08 P09 P11 P13 P14 P18 P21 OF001 - - 4 - - - - - - - - - - - 4 OF002 - - - - - - - - - - - - 4 - 4 OF003 - - - - - 6 - - - - - - - - 6 OF004 - 2 - - - - - - - - - - - - 2 OF005 - - - 4 - - - - - - - - - - 4 OF006 - - - - - - - - - - - - 4 - 4 OF007 - - - - - 4 - - - - - - - - 4 OF008 - - - - - - - - - - - - 4 - 4 OF009 - - - - 4 - - - - - - - - - 4 OF010 - - - - - - - - 4 - - - - - 4 OF011 - - - - - - - - - 4 - - - - 4 OF012 - - 4 - - - - - - - - - - - 4 OF013 - - - - 4 - - - - - - - - - 4 OF014 - 4 - - - - - - - - - - - - 4 OF015 - - - - - - - 4 - - - - - - 4 OF016 - - - - - - - - - - - 4 - - 4 OF017 - - - - - - - - - - - - 4 - 4 OF018 - 4 - - - - - - - - - - - - 4 OF019 - - - - - - - - - - - - 6 - 6 OF020 - 2 - - - - - - - - - - - - 2 OF021 - - - - - - - - 4 - - - - - 4 OF022 - - - - - - - - - 4 - - - - 4 OF023 - - 4 - - - - - - - - - - - 4 OF024 - 4 - - - - - - - - - - - - 4 OF025 - - - - 4 - - - - - - - - - 4 OF026 - - - - - - - - - - - - - 4 4 OF027 - - 4 - - - - - - - - - - - 4 OF028 - - - - - 4 - - - - - - - - 4 OF029 - - - - 4 - - - - - - - - - 4 OF030 - 4 - - - - - - - - - - - - 4 OF031 - - - - - - - 4 - - - - - - 4 OF032 - - - - - - - - - - - - 4 - 4 OF033 - - - - - - 4 - - - - - - - 4 OF034 - - - - - - - - - - 4 - - - 4 OF035 - 4 - - - - - - - - - - - - 4 OF036 - - - - - - - - 4 - - - - - 4 OF037 - - 4 - - - - - - - - - - - 4 OF038 - - - - 4 - - - - - - - - - 4 OF039 - - 4 - - - - - - - - - - - 4 OF040 - - - - - - 6 - - - - - - - 6 OF041 - - - 2 - - - - - - - - - - 2 OF042 - - - - - - - - - - - - 4 - 4 OF043 - - - - - - 4 - - - - - - - 4 OF044 - - - - - - - - - - 4 - - - 4 Professores Oferta Total 110 TABELA 22 Distribuição de horas de ensino final por professor (Conclusão) P01 P02 P03 P04 P05 P06 P07 P08 P09 P10 P12 P13 P14 P15 OF045 - - - - 4 - - - - - - - - - 4 OF046 - - - 4 - - - - - - - - - - 4 OF047 - - 4 - - - - - - - - - - - 4 OF048 - - - - 4 - - - - - - - - - 4 OF049 - - 4 - - - - - - - - - - - 4 OF050 - - - - - - 6 - - - - - - - 6 OF051 - - - - - - - - 2 - - - - - 2 OF052 4 - - - - - - - - - - - - - 4 OF053 4 - - - - - - - - - - - - - 4 OF054 - - - - - - - - - - - - - 4 4 OF055 - - - - - - - 4 - - - - - - 4 OF056 - - - - - - - - - - - 4 - - 4 OF057 - 6 - - - - - - - - - - - - 6 OF058 - - - - - - - - - - - - - 2 2 OF059 4 - - - - - - - - - - - - - 4 OF060 4 - - - - - - - - - - - - - 4 OF061 4 - - - - - - - - - - - - - 4 OF062 4 - - - - - - - - - - - - - 4 OF063 4 - - - - - - - - - - - - - 4 OF064 - - - 4 - - - - - - - - - - 4 OF065 - - - - - - - 4 - - - - - - 4 OF066 - - - - - - - - - - - 4 - - 4 OF067 - - - - - 6 - - - - - - - - 6 OF068 - - - 2 - - - - - - - - - - 2 OF069 4 - - - - - - - - - - - - - 4 OF070 4 - - - - - - - - - - - - - 4 OF071 4 - - - - - - - - - - - - - 4 Total 40 30 32 16 28 20 20 16 14 8 8 12 30 10 284 Oferta Professores Total 111 4.8 - Indicadores do Processo de Alocação de Professores Para facilitar a análise do resultado final da alocação de professores, deverão ser considerados alguns indicadores que permitem avaliar a eficiência de uma solução em relação aos indicadores referenciais apresentados pelo APRAC. São eles: 1. CHT – Carga Horária Total da Alocação: é a carga horária total da alocação, sendo que CHT é a soma da carga horária de ensino (CHE) e da carga horária complementar (CPL), para cada um dos professores alocados, onde o total de carga horária de ensino semanal é a soma de todas as ofertas de disciplinas a serem atendidas; 2. CPL – Carga Horária Complementar da Alocação: é a carga horária complementar total de acordo com o enquadramento nos regimes de trabalho de cada um dos professores alocados; 3. NP – Número de Professores Alocados: número total de professores participantes da alocação; 4. NTI – Número de Professores em Regime Tempo Integral: número total de professores participantes da alocação em regime de trabalho tempo integral. Para avaliar uma alocação, define-se o índice IEA (Índice de Eficiência da Alocação). O IEA é definido como a distância percentual que uma alocação está em relação à alocação ótima definida no APRAC, por meio do indicador CHTM (carga horária total mínima), apresentado na seção 3.5.1. A rigor, %100−= CHTM CHTIEA Quanto menor for o índice IEA do quadro final de alocação, mais eficiente é a alocação. Se o IEA for zero, significa que a instituição consegue ter sua alocação exatamente atingindo o valor de CHTM. Apesar de apontar eficiência, o IEA não pode ser considerado simplesmente o objetivo a ser minimizado. Isso porque existem diversos outros aspectos associados ao problema que não podem ser ignorados e que não se relacionam diretamente com o indicador CHTM. No entanto, a função objetivo para os modelos apresentados traz informações sobre a solução ótima do APRAC, o que tenta aproximar a solução do limite inferior definido pelo mesmo. 112 4.8.1 - Avaliação dos Exemplos A TAB. 23 apresenta um quadro comparativo dos indicadores do processo de alocação de professores e dos indicadores referenciais obtidos com o modelo APRAC. TABELA 23 Avaliação dos Exemplos EXEMPLO Indicador Valor Referência EP E1 E2 E3 E4 CHE 284 284 284 284 284 284 CPL 80 152 160 172 158 117 %CPL/CHT 22,0% 34,9% 36,0% 37,7% 35,7% 29,2% CHT 364 436 444 456 442 401 IEA 0,0% 19,8% 22,0% 25,3% 21,4% 10,2% NP 10 19 19 19 19 14 CHE/NP 28,4 14,9 14,9 14,9 14,9 20,3 CHT/NP 36,4 22,9 23,4 24,0 23,3 28,6 NTI 4 4 4 5 5 4 %NTI/NP 20% 21% 21% 26% 26% 29% NRT 30 30 30 30,53 30,53 30 Legenda: CHE – Carga Horária de Ensino CPL – Carga Horária Complementar CHT – Carga Horária Total IEA – Índice de Eficiência da Alocação NP – Número de Professores NTI – Número de Professores em Tempo Integral NRT – Nota do Indicador Regime de Trabalho [7] A partir dos dados observados pode ser percebido que quanto maior é a média de carga horária por professor melhor é o índice IEA da solução. No caso, o melhor IEA obtido foi para o exemplo E4, visto que foi possível alocar mais ofertas de disciplinas aos professores de um modo geral. Em um ambiente prático, pode ser que não seja possível atingir a média de 20,3 horas de ensino por professor (CHE/NP) devido a configuração das disponibilidades dos professores, as áreas de conhecimento relacionadas a cada um e em alguns casos, as diretrizes pedagógicas definidas. No entanto, esse valor está fortemente relacionado a um baixo IEA. Outra observação interessante sobre os resultados é que o número de professores não variou para os primeiros exemplos. Isso porque a disponibilidade dos professores não havia modificado. Sendo assim o modelo realizou a alocação de forma que as alterações ocorridas 113 se concentraram no enquadramento do regime de trabalho, mantendo a média de carga horária de ensino por professor (CHE/NP) inalterada. Analisando o indicador NRT e o indicador %NTI/NP, os quais correspondem as restrições do modelo, pode-se observar que as soluções foram limitadas pela restrição correspondente ao indicador Regime de Trabalho, como esperado (GRAF. 9). Para os centros universitários, a exigência legal define um mínimo de 20% de professores em tempo integral. Essa restrição foi em todos os casos atendida com folga. Já para o indicador Regime de Trabalho, observando NRT, pode-se perceber que a restrição foi atendida sem folga na maioria dos casos. No ambiente prático, a alocação final dos professores dependerá do cenário de cada instituição. As prioridades, metas e objetivos vão alterar as referências para atuação do modelo de alocação proposto. Instituições que tenham como objetivo apenas atender a demanda com baixa qualidade e com custos reduzidos, podem ignorar o desejo por conceitos melhores assim como também não selecionarem professores especialistas, preferindo professores generalistas que tem a possibilidade de atender diversas disciplinas. Nesse caso, o IEA do seu quadro de alocação de professores deveria ser o mínimo. Por outro lado, instituições que pleiteiam altos níveis de qualidade, assumindo custos e investimentos correspondentes, podem se balizar em uma reputação no meio acadêmico que irá garantir, mesmo em longo prazo, uma demanda de alunos capaz de manter sua estrutura. Portanto, a solução final da alocação dos professores dependerá do contexto de cada instituição, a qual irá definir critérios pedagógicos para a possibilidade de alocação de professores, a definição dos critérios para a formação da função objetivo e as metas de qualidade e custo que se deseja alcançar. 114 4.9 - Método de Resolução Existem vários métodos para resolução de modelos de programação linear inteira. Baseados em programação linear, os diversos métodos são aplicáveis a situações específicas, dependendo de como o conjunto de restrições do problema está disposto. O conjunto de restrições define uma região viável, chamada de poliedro. Os pontos extremos desse poliedro são as soluções para o problema. Cabe ao método encontrar os pontos extremos que correspondem à solução ótima. O algoritmo branch-and-bound consiste em um método exato para a resolução de problemas de programação linear inteira. O método consegue realizar podas na árvore de soluções, evitando explorar nodos desnecessários. Por isso, mesmo para instâncias relativamente grandes o método é capaz de encontrar a solução ótima para o problema. O branch-and-bound, assim como o método Simplex, é implementado em diversos pacotes de otimização comerciais. Nesse estudo, foi usado o pacote comercial CPLEX [34], em conjunto com a linguagem de programação matemática AMPL [28]. A partir do ambiente AMPL, é feita uma chamada ao resolvedor CPLEX, o qual resolve o problema e retorna a solução ótima. Para se gerar instâncias para o problema, foi criado um repositório de dados, utilizando o banco de dados MS Acess. Além disso, foram criados programas desenvolvidos na linguagem de programação Visual Basic que a partir dos dados armazenados no banco, geram instâncias do problema. 115 4.10 - Testes Realizados Os testes foram realizados em instâncias de diversos tamanhos. Foram utilizados computadores Pentium IV com 1 Gb de memória RAM. A partir de observações realizadas durante a execução do branch-and-bound do CPLEX, pode-se constatar que o problema tende a convergir para o valor mínimo da função objetivo com uma certa rapidez, mas o gap, que é a distância da melhor solução obtida para o limite inferior computado pelo algoritmo, converge lentamente a partir de um certo ponto. Para instâncias menores, o algoritmo encontra a solução ótima (gap igual a zero) em um tempo baixo, com poucas iterações. O GRAF. 10 demonstra a evolução do gap para uma instância com 225 professores e 128 ofertas de disciplina (APU = 3.958 variáveis e 1.289 restrições; APM = 5.074 variáveis e 3.521 restrições). Como o APM é maior, o algoritmo precisa de mais iterações para computar a solução ótima, mas para os dois modelos, o comportamento é muito parecido. Evolução do Gap para uma Instância com 225 Professores e 128 Ofertas de Disciplina 0,00% 5,00% 10,00% 15,00% 20,00% 25,00% 30,00% 0 500 1000 1500 2000 2500 3000 3500 Nº Iterações APU APM GRÁFICO 10 - Evolução do gap para uma instância pequena Legenda: APU – Modelo de Alocação de Professores Único Campus APM – Modelo de Alocação de Professores Multicampi 116 Evolução da Função Objetivo e do Limite Inferior para uma Instância com 225 Professores e 128 Ofertas de Disciplina 80000 90000 100000 110000 120000 130000 0 500 1000 1500 2000 2500 3000 3500 Nº Iterações Sol.Int.APU Lim.Inf.APU Sol.Int.APM Lim.Inf.APM GRÁFICO 11 - Evolução da função objetivo e do limite inferior para uma instância pequena Legenda: APU – Modelo de Alocação de Professores Único Campus APM – Modelo de Alocação de Professores Multicampi Sol.Int. – Melhor Solução Inteira Lim.Inf – Limite Inferior No entanto, para uma instância maior, o gap diminui lentamente, sem melhorias no valor da função objetivo, ou seja, apenas com o aumento do limite inferior. Por essa característica, e por ser um problema combinatório, a execução do modelo com um gap positivo não prejudica o método exato, sendo que a solução final tem uma garantia de aproximação da solução ótima, que para essa abordagem, é satisfatório. O GRAF. 12 demonstra a evolução do gap para uma instância com 358 professores e 614 ofertas de disciplina (9.754 variáveis e 2.790 restrições) executando o modelo APU. Pode-se observar que a partir de cerca de 10.000.000 iterações, o valor da função objetivo (GRAF. 13) não teve melhora e a diminuição do gap se deu a partir do aumento do limite inferior, resultado da exploração exaustiva de nós da árvore branch-and-bound no espaço de soluções do problema. Sendo assim, a execução dos modelos utilizando um gap positivo, pode ser útil pois permite diminuir o esforço computacional e conseqüentemente o tempo de resolução do problema. Dessa forma, é possível resolver o modelo em tempos aceitáveis (limitado a um dia) sem prejuízos na qualidade da solução, tornando essa tarefa viável no ambiente prático. 117 Evolução do Gap para uma Instância com 358 Professores e 614 Ofertas de Disciplinas 0,00% 0,50% 1,00% 1,50% 2,00% 2,50% 3,00% 3,50% 4,00% - 10.000.00 0 20.000.00 0 30.000.00 0 40.000.00 0 50.000.00 0 60.000.00 0 Nº Iterações GRÁFICO 12 - Evolução do gap para uma instância maior Evolução da Função Objetivo e do Limite Inferior para uma Instância com 358 Professores e 614 Ofertas de Disciplina 296.000,00 297.000,00 298.000,00 299.000,00 300.000,00 301.000,00 302.000,00 - 10.000.000 20.000.000 30.000.000 40.000.000 50.000.000 60.000.000 Nº Iterações Sol.Int. Lim.Inf. GRÁFICO 13 - Evolução da função objetivo e do limite inferior para uma instância maior Legenda: Sol.Int. – Melhor Solução Inteira Lim.Inf – Limite Inferior 118 Para os testes realizados foi considerado um gap de 0,01% para todas as simulações. Os testes foram divididos em três baterias. A primeira bateria foi realizada afim de comparar os resultados dos modelos APM e APU em instâncias iguais, de uma instituição do tipo centro universitário, atuando com o conceito 5. A TAB. 24 exibe as instâncias utilizadas na primeira bateria de testes e a TAB. 25 exibe os resultados computacionais. TABELA 24 Instâncias da primeira bateria de testes Instância C P O NV NR NVP NRP 1.01 1 68 20 2.591 2.402 537 303 1.02 2 225 128 9.189 8.005 3.958 1.289 1.03 3 291 188 11.957 10.375 5.156 1.640 1.04 4 330 457 14.142 12.009 7.603 2.133 1.05 5 358 614 16.192 13.146 9.754 2.790 1.06 6 404 697 18.478 14.839 11.398 3.173 1.07 7 421 830 19.544 15.567 12.695 3.499 1.08 8 456 912 21.068 16.874 13.630 3.731 1.09 9 463 981 21.905 17.188 14.557 4.072 1.10 10 473 1.010 22.341 17.567 14.682 4.116 1.11 11 507 1.082 23.969 18.829 16.299 4.504 Legenda: C – Número de cursos abrangidos (referência) P – Número de professores disponíveis para a alocação O – Número de ofertas de disciplinas a serem alocadas NV – Número de variáveis da instância NR – Número de restrições da instância NVP – Número de variáveis após pré-processamento NRP – Número de restrições após pré-processamento TABELA 25 Resultados computacionais da primeira bateria de testes Solução # Iterações MIP Simplex # Nós B&B Instância APU APM APU APM APU APM 1.01 G G 70 89 - - 1.02 G G 2.486 2.956 10 - 1.03 G G 1.319.957 5.265 142.375 180 1.04 G G 9.553.020 7.332 490.218 160 1.05 G G 254.136 966.872 16.960 36.000 1.06 T G 25.194.943 27.377 692.070 960 1.07 T G 25.833.540 12.831.563 756.171 592.941 1.08 G G 11.686.462 70.770 661.875 4.000 1.09 G T 412.895 22.055.477 21.000 295.427 1.10 G T 316.156 14.232.067 9.000 212.952 1.11 G T 703.010 22.718.477 38.000 316.168 Legenda: G – Processamento com solução ótima com gap de 0,01% T – Processamento com solução inteira após tempo limite de 36.000 segundos B&B – Branch-and-bound 119 TABELA 26 Resultados dos indicadores do processo de alocação de professores da primeira bateria de testes CHT %CPL/CHT IEA NP CHE/NP CHT/NP NTI %NTI/NP NRT Instância CHE APU APM APU APM CHTM APU APM APU APM NPM APU APM APU APM APU APM NTIM APU APM APU APM 1.01 78 194 194 59,8% 59,8% 107 81,3% 81,3% 12 12 3 6,5 6,5 16,17 16,17 3 3 1 25,0% 25,0% 30,8 30,8 1.02 492 786 790 37,4% 37,7% 627 25,4% 26,0% 39 39 16 12,62 12,62 20,15 20,26 9 9 6 23,0% 23,0% 30,3 30,3 1.03 668 1.069 1.047 37,5% 36,2% 854 25,2% 22,6% 55 55 22 12,15 12,15 19,44 19,04 12 11 8 22,0% 20,0% 30,0 30,2 1.04 1.380 2.055 2.054 32,9% 32,8% 1.734 18,5% 18,5% 99 99 44 13,94 13,94 20,76 20,75 20 20 17 20,0% 20,0% 30,0 30,0 1.05 1.796 2.641 2.640 32,0% 32,0% 2.254 17,2% 17,1% 121 121 57 14,84 14,84 21,83 21,82 25 25 22 21,0% 21,0% 30,1 30,1 1.06 1.980 3.022 3.005 34,5% 34,1% 2.480 21,9% 21,2% 144 144 62 13,75 13,75 20,99 20,87 32 31 25 22,0% 22,0% 30,0 30,1 1.07 2.370 3.519 3.515 32,7% 32,6% 2.980 18,1% 18,0% 167 167 75 14,19 14,19 21,07 21,05 34 34 30 20,0% 20,0% 30,0 30,0 1.08 2.690 4.007 4.013 32,9% 33,0% 3.380 18,6% 18,7% 188 189 85 14,31 14,23 21,31 21,23 40 40 34 21,0% 21,0% 30,0 30,0 1.09 2.958 4.371 4.410 32,3% 32,9% 3.707 17,9% 19,0% 200 203 93 14,79 14,57 21,86 21,72 44 44 37 22,0% 22,0% 30,0 30,0 1.10 3.058 4.575 4.593 33,2% 33,4% 3.827 19,5% 20,0% 213 217 96 14,36 14,09 21,48 21,17 46 48 38 22,0% 22,0% 30,0 30,0 1.11 3.342 4.999 5.006 33,2% 33,2% 4.200 19,0% 19,2% 236 236 105 14,16 14,16 21,18 21,21 50 52 42 21,0% 22,0% 30,0 30,0 Legenda: APU – Modelo de Alocação de Professores Único Campus APM – Modelo de Alocação de Professores Multicampi CHE – Carga Horária de Ensino CPL – Carga Horária Complementar CHT – Carga Horária Total IEA – Índice de Eficiência da Alocação NP – Número de Professores NTI – Número de Professores em Tempo Integral NRT – Nota do Indicador Regime de Trabalho [7] 120 A TAB. 26 traz comparações dos resultados com alguns indicadores do processo de alocação de professores. Analisando os dados apresentados pode-se observar que o IEA decresce à medida que a dimensão da instância cresce. Isso se deve ao fato de existirem mais professores aptos a assumir as ofertas de disciplinas a serem alocadas, propiciando uma melhor alocação de professores. No entanto, a carga horária de ensino por professor (CHE/NP) não passou de 15, o que significa que o corpo docente tem pouca disponibilidade para atendimento de ofertas de disciplinas. Um possível aumento da carga horária de ensino média por professor, bem como a carga horária total média por professor, implicaria em um melhor IEA para a alocação. Outra observação é que quando o problema foi tratado como multicampi, pouco se alterou o número de professores utilizados na solução, ou seja, o resultado da alocação praticamente não foi alterado. A segunda bateria de testes foi realizada com objetivo de analisar as variações na solução para tipos diferentes de instituição. Então foi utilizado o modelo APU para as modalidades universidade, centro universitário e faculdade. Foi considerado que o conceito deveria ser máximo, ou seja, conceito 5. A TAB. 27 exibe as instâncias utilizadas na segunda bateria de testes e a TAB. 28 exibe os resultados computacionais. 121 TABELA 27 Instâncias da segunda bateria de testes Instância C P O NV NR NVP NRP 2.01 1 198 108 8.074 7.040 3.471 1.158 2.02 2 214 104 8.715 7.596 4.141 1.205 2.03 3 260 212 11.317 9.314 7.633 1.935 2.04 4 288 223 12.430 10.305 7.864 2.058 2.05 5 298 258 13.208 10.690 9.104 2.419 2.06 6 422 605 19.613 15.377 14.402 4.156 2.07 7 441 722 24.241 16.159 18.650 5.101 2.08 8 478 782 25.965 17.514 19.800 5.375 2.09 9 568 1.051 30.688 20.933 23.506 6.388 2.10 10 609 1.208 33.461 22.525 25.739 7.161 2.11 11 632 1.322 35.151 23.444 27.101 7.556 2.12 12 687 1.405 37.890 25.452 28.782 8.041 2.13 13 713 1.538 39.490 26.495 30.198 8.498 2.14 14 767 1.620 41.826 28.467 31.249 8.916 2.15 15 799 1.757 43.731 29.724 32.934 9.463 2.16 17 834 1.855 45.816 31.047 34.114 9.954 2.17 18 864 2.015 47.993 32.257 35.923 10.490 2.18 19 890 2.110 49.393 33.262 36.883 10.757 2.19 20 904 2.150 50.231 33.792 37.279 10.912 2.20 21 929 2.222 51.649 34.739 38.142 11.197 Legenda: C – Número de cursos abrangidos (referência) P – Número de professores disponíveis para a alocação O – Número de ofertas de disciplinas a serem alocadas NV – Número de variáveis da instância NR – Número de restrições da instância NVP – Número de variáveis após pré-processamento NRP – Número de restrições após pré-processamento 122 TABELA 28 Resultados computacionais da segunda bateria de testes Solução # Iterações MIP Simplex # Nós B&B Instância U5 C5 F5 U5 C5 F5 U5 C5 F5 2.01 G G G 2.104 2.009 166.429 - 10 19.007 2.02 G G G 6.227.449 24.201.004 1.078.114 525.162 2.211.023 120.929 2.03 G G G 29.123.131 11.286.603 7.134.331 1.206.408 509.978 1.266.110 2.04 T G G 18.575.873 14.746.250 10.231.490 1.033.294 1.199.918 1.264.382 2.05 G G G 7.742.229 18.482.775 7.722.237 1.171.536 1.092.955 1.142.196 2.06 G G G 1.738.545 2.998.524 10.852.889 158.000 169.000 772.917 2.07 G G G 496.162 15.441.441 49.601 25.000 293.000 640 2.08 G G G 52.794 1.761.650 99.357 2.000 41.150 2.160 2.09 G E G 1.365.142 - 59.678 59.000 - 880 2.10 G G G 4.048.603 1.455.612 244.744 142.400 47.910 6.440 2.11 G E G 498.653 - 775.386 24.400 - 27.200 2.12 G E G 166.122 - 351.891 6.080 - 15.680 2.13 G G G 2.890.951 4.075.383 655.709 199.000 99.450 25.333 2.14 E G G - 12.554.331 4.640.976 - 320.000 164.610 2.15 G G E 2.073.579 6.924.915 - 137.000 177.990 - 2.16 G E G 9.557.324 - 442.838 300.531 - 13.520 2.17 G E G 4.044.434 - 2.561.705 157.530 - 61.030 2.18 G G G 1.682.610 7.373.308 3.086.945 80.030 176.882 69.000 2.19 E E G - - 1.805.745 - - 73.152 2.20 G E G 4.834.821 - 5.061.204 239.940 - 162.000 Legenda: G – Processamento com solução ótima com gap de 0,01% T – Processamento com solução inteira após tempo limite de 36.000 segundos E – Processamento interrrompido com erro do resolvedor B&B – Branch-and-bound U5 – Universidade (Conceito 5) C5 – Centro Universitário (Conceito 5) F5 – Faculdade (Conceito 5) 123 TABELA 29 Resultados dos indicadores do processo de alocação de professores da segunda bateria de testes (Continua) CHT %CPL/CHT CHTM IEA NP NPM Instância CHE U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 2.01 414 760 618 625 45,5% 33,0% 33,8% 600 534 468 26,7% 15,7% 33,5% 29 28 28 15 14 19 2.02 398 806 638 588 50,6% 37,6% 32,3% 580 507 448 39,0% 25,8% 31,3% 35 34 35 15 13 19 2.03 812 1.497 1.217 1.202 45,8% 33,3% 32,5% 1.180 1.027 920 26,9% 18,5% 30,7% 60 60 60 30 26 32 2.04 834 1.563 1.280 1.222 46,6% 34,8% 31,8% 1.200 1.054 940 30,3% 21,4% 30,0% 64 64 63 30 27 36 2.05 972 1.891 1.540 1.436 48,6% 36,9% 32,3% 1.400 1.227 1.100 35,1% 25,5% 30,5% 77 76 75 35 31 40 2.06 2.472 4.351 3.673 3.408 43,2% 32,7% 27,5% 3.547 3.107 2.760 22,7% 18,2% 23,5% 163 164 162 89 78 108 2.07 2.864 5.061 4.192 3.961 43,4% 31,7% 27,7% 4.094 3.580 3.180 23,6% 17,1% 24,6% 190 184 179 103 90 128 2.08 3.040 5.405 4.514 4.259 43,8% 32,7% 28,6% 4.347 3.800 3.380 24,3% 18,8% 26,0% 203 201 197 109 95 136 2.09 3.752 6.679 - 5.347 43,8% - 29,8% 5.380 - 4.180 24,1% - 27,9% 249 - 242 135 - 168 2.10 4.168 7.470 6.072 6.012 44,2% 31,4% 30,7% 5.947 5.200 4.628 25,6% 16,8% 29,9% 281 267 264 149 130 183 2.11 4.552 8.238 - 6.524 44,7% - 30,2% 6.520 - 5.068 26,3% - 28,7% 306 - 286 163 - 203 2.12 4.736 8.574 - 6.746 44,8% - 29,8% 6.780 - 5.268 26,5% - 28,1% 320 - 304 170 - 211 2.13 5.126 9.177 7.570 7.460 44,1% 32,3% 31,3% 7.320 6.400 5.700 25,4% 18,3% 30,9% 341 339 329 183 160 224 2.14 5.446 - 8.013 7.967 - 32,0% 31,6% - 6.800 6.048 - 17,8% 31,7% - 354 350 - 170 243 2.15 5.876 10.501 8.575 - 44,0% 31,5% - 8.400 7.360 - 25,0% 16,5% - 390 381 - 210 184 - 2.16 6.244 11.050 - 8.967 43,5% - 30,4% 8.920 - 6.940 23,9% - 29,2% 410 - 395 223 - 276 2.17 6.598 11.780 - 9.351 44,0% - 29,4% 9.440 - 7.340 24,8% - 27,4% 431 - 415 236 - 292 2.18 6.970 12.372 10.112 9.943 43,7% 31,1% 29,9% 9.947 8.707 7.740 24,4% 16,1% 28,5% 451 442 435 249 218 308 2.19 7.114 - - 10.041 - - 29,2% - - 7.920 - - 26,8% - - 445 - - 312 2.20 7.398 13.058 - 10.652 43,4% - 30,6% 10.580 - 8.228 23,4% - 29,5% 477 - 461 265 - 327 124 TABELA 29 Resultados dos indicadores do processo de alocação de professores da segunda bateria de testes (Conclusão) CHE/NP CHT/NP NTI NTIM %NTI/NP NRT Instância U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 U5 C5 F5 2.01 14,3 14,8 14,8 26,2 22,1 22,3 13 6 7 9 5 0 44,8% 21,4% 25,0% 40,0 30,0 28,2 2.02 11,4 11,7 11,4 23,0 18,8 16,8 15 8 6 9 5 0 42,9% 23,5% 17,1% 40,0 30,0 26,0 2.03 13,5 13,5 13,5 25,0 20,3 20,0 26 12 16 18 10 2 43,3% 20,0% 26,7% 40,0 30,0 26,3 2.04 13,0 13,0 13,2 24,4 20,0 19,4 28 14 15 18 10 1 43,8% 21,9% 23,8% 40,0 30,0 26,0 2.05 12,6 12,8 13,0 24,6 20,3 19,2 35 18 18 21 12 2 45,5% 23,7% 24,0% 40,0 30,0 26,5 2.06 15,2 15,1 15,3 26,7 22,4 21,0 75 40 33 53 31 1 46,0% 24,4% 20,4% 40,0 30,0 26,5 2.07 15,1 15,6 16,0 26,6 22,8 22,1 88 46 41 61 36 0 46,3% 25,0% 22,9% 40,0 30,0 27,2 2.08 15,0 15,1 15,4 26,6 22,5 21,6 92 47 45 65 38 0 45,3% 23,4% 22,8% 40,1 30,1 27,0 2.09 15,1 - 15,5 26,8 - 22,1 113 - 60 81 - 0 45,4% - 24,8% 40,0 - 28,2 2.10 14,8 15,6 15,8 26,6 22,7 22,8 126 63 71 89 52 1 44,8% 23,6% 26,9% 40,0 30,0 29,4 2.11 14,9 - 15,9 26,9 - 22,8 142 - 76 98 - 0 46,4% - 26,6% 40,0 - 28,8 2.12 14,8 - 15,6 26,8 - 22,2 150 - 75 102 - 0 46,9% - 24,7% 40,0 - 28,1 2.13 15,0 15,1 15,6 26,9 22,3 22,7 156 78 90 110 64 2 45,7% 23,0% 27,4% 40,0 30,0 29,4 2.14 - 15,4 15,6 - 22,6 22,8 - 84 97 - 68 0 - 23,7% 27,7% - 30,0 29,5 2.15 15,1 15,4 - 26,9 22,5 - 180 83 - 126 74 - 46,2% 21,8% - 40,0 30,0 - 2.16 15,2 - 15,8 27,0 - 22,7 186 - 106 134 - 1 45,4% - 26,8% 40,0 - 28,8 2.17 15,3 - 15,9 27,3 - 22,5 199 - 102 142 - 1 46,2% - 24,6% 40,0 - 28,4 2.18 15,5 15,8 16,0 27,4 22,9 22,9 206 98 115 149 87 1 45,7% 22,2% 26,4% 40,0 30,0 28,6 2.19 - - 16,0 - - 22,6 - - 110 - - 2 - - 24,7% - - 28,0 2.20 15,5 - 16,1 27,4 - 23,1 211 - 128 159 - 1 44,2% - 27,8% 40,0 - 29,1 Legenda: APU – Modelo de Alocação de Professores Único Campus APM – Modelo de Alocação de Professores Multicampi CHE – Carga Horária de Ensino CPL – Carga Horária Complementar CHT – Carga Horária Total IEA – Índice de Eficiência da Alocação NP – Número de Professores NTI – Número de Professores em Tempo Integral NRT – Nota do Indicador Regime de Trabalho [7] 125 A TAB. 29 exibe as informações sobre alguns indicadores do processo de alocação de professores da segunda bateria de testes. Pode-se observar houve pouca variação na carga horária de ensino média por professor. Para a carga horária total média por professor, como era de se esperar, o valor para as universidades foi maior que os centros universitários que possua vez foram maiores que os das faculdades. No entanto, analisando apenas centros universitários e faculdades, pode-se observar que os valores ficaram próximos devido a disponibilidade dos professores não ter variado de uma instância para outra. Como as metas para o conceito do indicador Regime de Trabalho da Avaliação Institucional são menores para as faculdades, o índice IEA se apresentou com um resultado pior que os demais. Por fim, a terceira bateria de testes foi realizada com o intuito de avaliar as variações dos conceitos da Avaliação Institucional dentro de um mesmo tipo de instituição. A TAB. 30 exibe as instâncias utilizadas e a TAB. 31 exibe os resultados computacionais. TABELA 30 Instâncias da terceira bateria de testes Instância C P O NV NR NVP NRP 3.01 5 298 258 13.208 10.690 9.104 2.419 3.02 10 609 1.208 33.461 22.525 25.739 7.161 3.03 15 799 1.757 43.731 29.724 32.934 9.463 3.04 20 904 2.150 50.231 33.792 37.279 10.912 Legenda: C – Número de cursos abrangidos (referência) P – Número de professores disponíveis para a alocação O – Número de ofertas de disciplinas a serem alocadas NV – Número de variáveis da instância NR – Número de restrições da instância NVP – Número de variáveis após pré-processamento NRP – Número de restrições após pré-processamento 126 TABELA 31 Resultados computacionais da terceira bateria de testes Instância Tipo IES 3.01 3.02 3.03 3.04 U5 G G G E U4 G E G E U3 G G G G C5 G G G E C4 G G G G C3 G G G G F5 G G E G F4 G G G G Solução F3 G G G G U5 7.742.229 4.048.603 2.073.579 - U4 12.663.575 - 5.957.915 - U3 6.643.756 287.674 363.547 1.166.930 C5 18.482.775 1.455.612 6.924.915 - C4 6.546.955 243.897 397.340 583.058 C3 46.048.960 97.900 526.774 635.312 F5 7.722.237 244.744 - 1.805.745 F4 8.464.981 424.057 80.430 386.545 # Iterações MIP Simplex F3 5.866.498 66.632 52.816 92.059 U5 1.171.536 142.400 137.000 - U4 1.147.006 - 182.520 - U3 1.096.257 9.320 15.970 54.080 C5 1.092.955 47.910 177.990 - C4 1.150.963 21.120 14.710 23.000 C3 1.095.686 3.830 18.000 26.000 F5 1.142.196 6.440 - 73.152 F4 1.174.200 21.930 2.400 14.404 # Nós B&B F3 1.129.118 3.580 1.669 4.060 Legenda: G – Processamento com solução ótima com gap de 0,01% T – Processamento com solução inteira após tempo limite de 36.000 segundos E – Processamento interrrompido com erro do resolvedor B&B – Branch-and-bound U5 – Universidade (Conceito 5) U4 – Universidade (Conceito 4) U3– Universidade (Conceito 3) C5 – Centro Universitário (Conceito 5) C4 – Centro Universitário (Conceito 4) C3 – Centro Universitário (Conceito 3) F5 – Faculdade (Conceito 5) F4 – Faculdade (Conceito 4) F3 – Faculdade (Conceito 3) 127 TABELA 32 Resultados dos indicadores do processo de alocação de professores da terceira bateria de testes Instância Instância Instância Instância Tipo IES 3.01 3.02 3.03 3.04 Tipo IES 3.01 3.02 3.03 3.04 Tipo IES 3.01 3.02 3.03 3.04 Tipo IES 3.01 3.02 3.03 3.04 CHE 972 4168 5876 7114 CHE 972 4168 5876 7114 CHE 972 4168 5876 7114 CHE 972 4168 5876 7114 U5 1891 7470 10501 - U5 35,1% 25,6% 25,0% - U5 12,62 14,83 15,07 - U5 21 89 126 - U4 1707 - 9642 - U4 29,3% - 23,0% - U4 12,96 - 15,07 - U4 17 - 98 - U3 1628 6281 8977 10875 U3 38,0% 25,6% 27,2% 27,3% U3 12,62 15,49 15,3 15,57 U3 10 42 59 71 C5 1540 6072 8575 - C5 25,5% 16,8% 16,5% - C5 12,79 15,61 15,42 - C5 12 52 74 - C4 1414 5674 8039 9697 C4 22,7% 15,9% 16,2% 15,8% C4 12,96 15,79 15,71 16,02 C4 7 36 52 62 C3 1374 5485 7762 9442 C3 24,9% 18,2% 18,7% 19,2% C3 12,96 16,03 15,88 15,99 C3 6 24 33 40 F5 1436 6012 - 10041 F5 30,5% 29,9% - 26,8% F5 12,96 15,79 - 15,99 F5 2 1 0 2 F4 1258 4899 6972 8376 F4 21,9% 12,0% 12,8% 11,9% F4 13,14 16,03 15,92 16,32 F4 0 0 0 0 CHT F3 1234 4719 6735 8203 IEA F3 21,9% 10,1% 11,1% 11,8% CHE/ NP F3 13,14 16,09 15,97 16,28 NTIM F3 0 0 0 0 U5 48,6 44,2 44,04 - U5 77 281 390 - U5 24,56 26,58 26,93 - U5 45,5% 44,8% 46,2% - U4 43,06 - 39,06 - U4 75 - 390 - U4 22,76 - 24,72 - U4 34,7% - 34,6% - U3 40,29 33,64 34,54 34,58 U3 77 269 384 457 U3 21,14 23,35 23,38 23,8 U3 33,8% 33,1% 33,1% 33,0% C5 36,88 31,36 31,48 - C5 76 267 381 - C5 20,26 22,74 22,51 - C5 23,7% 23,6% 21,8% - C4 31,26 26,54 26,91 26,64 C4 75 264 374 444 C4 18,85 21,49 21,49 21,84 C4 20,0% 20,1% 20,1% 20,0% C3 29,26 24,01 24,3 24,66 C3 75 260 370 445 C3 18,32 21,1 20,98 21,22 C3 20,0% 20,0% 20,0% 20,0% F5 32,31 30,67 - 29,15 F5 75 264 - 445 F5 19,15 22,77 - 22,56 F5 24,0% 26,9% - 24,7% F4 22,73 14,92 15,72 15,07 F4 74 260 369 436 F4 17 18,84 18,89 19,21 F4 12,2% 5,4% 5,7% 6,0% %CPL/ CHT F3 21,23 11,68 12,75 13,28 NP F3 74 259 368 437 CHT/ NP F3 16,68 18,22 18,3 18,77 %NTI/ NP F3 10,8% 4,2% 5,4% 5,7% U5 1400 5947 8400 - U5 35 149 210 - U5 35 126 180 - U5 40,0 40,0 40,0 0,0 U4 1320 - 7840 - U4 33 - 196 - U4 26 - 135 - U4 35,1 0,0 35,0 0,0 U3 1180 5000 7060 8540 U3 30 125 177 214 U3 26 89 127 151 U3 28,2 27,8 28,3 28,8 C5 1227 5200 7360 - C5 31 130 184 - C5 18 63 83 - C5 30,0 30,0 30,0 0,0 C4 1152 4894 6920 8376 C4 34 124 173 212 C4 15 53 75 89 C4 25,9 25,2 25,3 25,8 C3 1100 4640 6540 7920 C3 28 116 165 198 C3 15 52 74 89 C3 23,7 22,0 22,2 22,5 F5 1100 4628 - 7920 F5 40 183 - 312 F5 18 71 - 110 F5 26,5 29,4 0,0 28,0 F4 1032 4374 6180 7484 F4 34 141 200 242 F4 9 14 21 26 F4 20,1 18,3 18,7 18,8 CHTM F3 1012 4288 6060 7336 NPM F3 32 128 180 216 NTI F3 8 11 20 25 NRT F3 19,2 15,8 16,1 17,0 Legenda: Vide legenda da TABELA 29. 128 A TAB. 32 exibe as informações sobre alguns indicadores do processo de alocação de professores para a terceira bateria de testes. Pode-se observar que assim como nos outros testes, houve pouca variação na carga horária de ensino média por professor. Devido à disponibilidade dos professores não ter variado, quando o conceito foi sendo diminuído, a carga horária total média por professor reduziu mas o índice IEA não. Em vários casos, o índice aumentou quando a carga horária total estava diminuindo. Isso porque as metas dos conceitos diminuíram relativamente mais que a carga horária alocada para cada docente. Portanto, a partir da observação de todas as instâncias, pode-se afirmar que quanto maior for a disponibilidade docente para o atendimento das demandas de disciplina, melhor tende a ser o índice IEA da alocação de professores. Pois, a partir de um determinado ponto, as restrições de disponibilidade não permitem uma melhora no objetivo, alocando os professores de modo a cumprir todas as exigências e restrições, mas afastando cada vez mais dos referenciais limite apontados pelo modelo APRAC. 129 4.11 - Formulação Alternativa – Fluxo de Custo Mínimo Multiproduto O objetivo de se propor uma formulação alternativa é exibir o problema de alocação de professores por outro ângulo, por meio da formulação de fluxos em redes. Esse tipo de formulação pode ser mais intuitivo para o entendimento. O problema de alocação de professores pode ser modelado como uma rede multifluxo de custo mínimo com restrições adicionais de controle. O fluxo de produtos na rede é simbolizado por carga horária docente, sendo que cada oferta de disciplina denota um produto. No nodo inicial, tem-se a disponibilidade de carga horária total que deverá ser alocada para os diversos professores. Nos nodos terminais, têm-se a demanda por carga horária para cada uma das disciplinas. Deseja-se obter o fluxo de menor custo que atenda toda a demanda de carga horária a partir da origem sujeito às restrições de limites nos arcos que ligam cada um dos nodos. A rede pode ser modelada como um grafo G=(V,E) , k-partido, onde: − V é o conjunto de vértices, sendo CTIJOV ∪∪∪∪= e O, J, I, T e C são conjuntos disjuntos. − E é o conjunto de arestas, sendo ICCJITJIOJE ∪∪∪∪= e OJ, JI, IT, CJ e IC são conjuntos disjuntos. A definição dos conjuntos O, J, I, T e C será apresentada adiante nas próximas páginas. Em cada aresta de OJ, JI e IT podem ser passadas k ofertas de disciplinas sendo Kk ∈ . Deseja-se atender todas as demandas pela oferta de disciplina k em cada um dos horários (i.e. timeslots). O nodo origem o, { }oO = , é o nodo que possui a disponibilidade de carga horária para cada uma das k ofertas de disciplinas. O conjunto J é conjunto de tipos de regime de trabalho nos quais um professor pode estar enquadrado. Tipicamente, { }RHRPRIJ ,,= , de acordo com o disposto na legislação educacional citada anteriormente (QUADRO 1). O conjunto de arcos JOOJ ×= realiza a distribuição do fluxo para os diversos tipos de regime de trabalho que um professor poderá estar alocado. Já o conjunto de arcos JI indica a alocação do professor i, Ii ∈ , ao regime de trabalho j, Jj ∈ . Então, IJJI ×= .O fluxo de carga horária que passa por um nodo i poderá se originar apenas em um único nodo j, pois um professor pode estar associado a apenas um regime de trabalho. 130 Já o conjunto de arcos IT, determina a disponibilidade de um professor i ser alocado ao horário t, sendo Tt ∈ . O conjunto T pode variar de uma instituição para outra. Tipicamente é formado pelos horários disponíveis em cada turno e em cada dia da semana. Como exemplo, o 1º horário do turno da noite na terça-feira é um elemento do conjunto T. Haverá arco de um professor i para um horário t, caso o professor tenha disponibilidade para atender a alguma oferta de disciplina naquela hora. Cada nodo t tem a informação de quais são as ofertas de disciplinas que deverão se realizar naquele horário (timeslot), assim como a carga horária demandada naquele horário. De acordo com o enunciado, na definição do problema, a especificação de quais horários cada oferta de disciplina irá ocorrer é obtido na fase 2 do processo. Portanto, para o modelo proposto, essa informação é parâmetro de entrada. A FIG. 5 exibe um grafo exemplo para o problema de alocação de professores. FIGURA 5 - Modelo da rede multifluxo Uma característica importante do modelo é que nos arcos CJ, IC e JI, existe a possibilidade de um fluxo específico denominado carga horária complementar. Logo, o subgrafo G’ =(V’, E’) implementa um modelo de circulação de fluxo a partir da definição de limites superiores e inferiores para o fluxo nos arcos do conjunto JI em função do fluxo das k ofertas de disciplinas na rede do grafo G, onde V’ é o conjunto de vértices, sendo IJCV ∪∪=' e E’ é o conjunto de arestas, sendo ICJICJE ∪∪=' . Define-se JCCJ ×= 131 e CIIC ×= . O nodo auxiliar c, { }cC = , é o nodo que denota a carga horária complementar alocada para um docente de acordo com seu fluxo de carga horária e o regime de trabalho no qual um professor estará enquadrado. Portanto, seja: − O = conjunto origem para a disponibilidade de carga horária de oferta de disciplinas. − C = conjunto auxiliar para carga horária complementar. − J = conjunto de regimes de trabalho. − I = conjunto de professores. − T = conjunto de horários (timeslots). − K = conjunto de oferta de disciplinas. − OJ = conjunto de arcos de O para J. − JI = conjunto de arcos de J para I. − IT = conjunto de arcos de I para T. − CJ = conjunto de arcos que ligam o nodo de CH complementar aos regimes de trabalho. − IC = conjunto de arcos que ligam os professores ao nodo de CH complementar. − OCHok = oferta de carga horária para cada oferta de disciplina k que deverá ser transportada na rede. − DCHtk = demanda de carga horária para cada oferta de disciplina k que deverá ser atendida. − CHEj = carga horária máxima para atividades de ensino no regime de trabalho j. − CHTj = carga horária total máxima de um regime de trabalho j. − CHMj = carga horária total mínima de um regime de trabalho j. − EC = percentual mínimo de atividade extra-classe, que um tipo de atividade complementar, de acordo com convenções ou acordos coletivos de classe. − v = valor hora da atividade docente. − Fij = custo de ativação do docente i no regime de trabalho j. − Dispi = disponibilidade de carga horária de um professor i para alocação. − CHMaxik = carga horária máxima que o professor i pode ser alocado para a oferta de disciplina k. − Tamt = tamanho em horas de um timeslot. 132 − eit = penalidade associada a um docente i a lecionar no timeslot t, sendo 0 quando o professor preferir o horário t. − Cik = custo de alocação de um professor i a uma disciplina k. − CHCompli = carga horária pré-alocada para o professor i em atividades complementares. − RTIj = regimes de trabalho do tipo Integral. − PRTj = peso de cada um dos regimes de trabalho j de acordo com [7]. − PTITi = Peso da titulação do professor i de acordo com [7]. − PPUBi = Peso da publicação professor i de acordo com [7]. − MRT = Meta para o indicador Regime de Trabalho de acordo com o tipo de IES, estabelecido em [7]. − MTI = Meta para professores em Tempo Integral de acordo com [6][11]. − MTIT = Meta para o indicador Titulação de acordo com o tipo de IES, estabelecido em [7]. − MPUB = Meta para o indicador Publicação de acordo com o tipo de IES, estabelecido em [7]. Os fluxos nos arcos são representados pelas seguintes variáveis: − dojk que representa o fluxo de carga horária do nodo o para o nodo de regime de trabalho j para a oferta de disciplina k. − rjik que representa o fluxo de carga horária do nodo de regime de trabalho j para o nodo de professor i para a oferta de disciplina k. − pitk que representa o fluxo de carga horária do nodo de professor i para o nodo de timeslot t para a oferta de disciplina k. − gcj que representa o fluxo de carga horária complementar do nodo c para o nodo de regime de trabalho j. − aji que representa o fluxo de carga horária complementar do nodo de regime de trabalho j para o nodo de professor i. − hcj que representa o fluxo de carga horária complementar do nodo c para o nodo de regime de trabalho j, sendo +Ζ∈cjh . − Yji que representa se o professor i está alocado no regime de trabalho j, sendo { }1,0∈jiY . 133 − Xik que representa se o professor i está alocado para lecionar a oferta de disciplina k, sendo { }1,0∈ikX . A partir do enunciado, define-se o seguinte modelo matemático: ∑∑∑∑ ∈ ∈ ∈ ∈∈ ∈ ∈ +++           += Kk ITti ikititk Kk JIij ijjik ICci ic Kk OJjo ojk CepFrhdvz ),(),(),(),( )(5,4min (1) sujeito a: ok OJjo ojk OCHd =∑ ∈),( ∀ k ∈K (2) 0 ),(),( =− ∑∑ ∈∈ JIij jik OJjo ojk rd ∀ k ∈K (3) 0 ),(),( =− ∑∑ ∈∈ ITti itk JIij jik pr ∀ k ∈K (4) tk ITti itk DCHp =∑ ∈),( ∀ t ∈T, k ∈K (5) 0 ),(),( =− ∑∑ ∈∈ CJjc cj ICci ic gh ∀ c ∈C (6) 0 ),(),( =− ∑∑ ∈∈ JIij ji CJjc cj ag ∀ j ∈J (7) 0 ),(),( =− ∑∑ ∈∈ ICci ic JIij ji ha ∀ i ∈I (8) jijji Kk jik YCHTar ≤+∑ ∈ ∀ (j,i) ∈JI (9) jijji Kk jik YCHMar ≥+∑ ∈ ∀ (j,i) ∈JI (10) jij Kk jik YCHEr ≤∑ ∈ ∀ (j,i) ∈JI (11)         −×      +≥ ∑ ∈ j j Kk jijikji CHT CHE ara 1 ∀ (j,i) ∈JI (12) ∑ ∈ ≥ Kk jikji rECa ∀ (j,i) ∈JI (13) iji Kk jik Dispar ≤+∑ ∈ ∀ (j,i) ∈JI (14) jiikjik YCHMaxr ≤ ∀ (j,i) ∈JI, k ∈K (15) 134 iic CHComplh ≥ ∀ (i,c) ∈IC (16) t Kk itk Tamp ≤∑ ∈ ∀ (i,t) ∈IT (17) tikitk TamXp ≤ ∀ (i,t) ∈IT , k ∈K (18) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj jij YMRTPRTY (19) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj jij YMTIRTIY (20) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj iij YMTITPTITY (21) ∑∑∑∑ ∈ ∈∈ ∈ ≥ Ii Jj ij Ii Jj iij YMPUBPPUBY (22) 1≤∑ ∈Jj ijY ∀ i ∈I (23) 1=∑ ∈Ii ikX ∀ k ∈K (24) { }1,0∈ikX ∀ i ∈I , k ∈K (25) { }1,0∈jiY ∀ j ∈J, i ∈I (26) O objetivo do modelo é atender a demanda de carga horária alocando os professores com o um custo mínimo. A função objetivo (1) demonstra as três fases da rede. A primeira parcela da função trás o custo operacional da alocação, abordando a carga horária total alocada ao professor e o custo hora da alocação. Já a segunda fase, representada pela segunda parcela, corresponde aos custos de realocação dos docentes e seu peso institucional, representados por exemplo por um plano de carreira. Já a terceira parcela demonstra uma suposta preferência por determinados horários de trabalho além da afinidade com a disciplina a ser alocada. Pode-se atribuir pesos a cada uma das parcelas caso deseje-se enfatizar mais um ou outro critério. Observando o modelo, pode-se perceber que as restrições (2) a (5) implementam as restrições de conservação de fluxo e atendimento da demanda pela oferta de carga horária. Já as restrições (6) a (8) implementam o modelo de circulação de fluxo para o controle da carga horária complementar (representado em cinza na FIG. 5). As restrições (9) determinam que a carga horária total alocada a um professor não pode extrapolar a carga horária máxima para um regime de trabalho. Já as restrições (10) determinam o contrário: que a carga horária total alocada a um professor deve ser maior ou igual a carga horária mínima para um regime de 135 trabalho. As restrições (11) determinam que a carga horária alocada para atividades de ensino de um professor não extrapola o limite de carga horária de ensino de um regime de trabalho. As restrições (12) e (13) definem um limite inferior para a carga horária complementar do professor, sendo a primeira de acordo com o regime de trabalho e a segunda de acordo com as exigências dos sindicatos de classe que definem um limite mínimo de carga horária complementar para a realização de atividades extra-classe. As restrições (14) definem um limite para a quantidade de horas podem ser alocadas para um professor devido a sua disponibilidade. As restrições (15) definem que um professor poderá conduzir o fluxo se e somente se ele estiver alocado em um determinado regime de trabalho, por meio da variável Yji., e do limite de carga horária do professor para assumir atividades. As restrições (16) exigem que a carga horária complementar pré-alocada seja atendida. As restrições (17) garantem que o fluxo total de um professor para um determinado horário (timeslot) seja sempre restrito ao tamanho do mesmo. As restrições (18) definem que um professor poderá conduzir o fluxo de uma determinada oferta de disciplina se e somente se ele estiver designado a ela, por meio da variável Xik., e do limite de carga horária do horário (timeslot). As restrições (19) a (22) implementam as validações das metas de qualidade propostas na Avaliação Institucional. As restrições (23) e (24) definem que um professor pode estar associado a apenas um regime de trabalho e que uma oferta de disciplina pode ser associada a apenas um professor. Por fim, as restrições (25) e (26) definem os domínios das variáveis X e Y, respectivamente. 136 Capítulo 5 - Conclusões A construção de um quadro de horários eficiente permite a alocação racionalizada dos recursos docentes de uma instituição de ensino superior. Por ser considerado estrutural, as características de um quadro de horários vão interferir diretamente na gestão administrativa e acadêmica, o que justifica a utilização da metodologia proposta. A abordagem do problema apresentada cria uma nova visão a respeito dos problemas de quadros de horários. Os aspectos considerados, presentes no cenário brasileiro, tornam-se uma extensão aos problemas clássicos de timetabling. Logo, novos estudos podem ser conduzidos nessa área, conjugando a multidimensionalidade do problema com as necessidades específicas de gestão e qualidade acadêmica. A utilização de métodos exatos de resolução para o problema de alocação de professores foi facilitada pela definição da função objetivo. Com um objetivo mais específico, torna-se mais fácil entender o problema como um problema de otimização em si, e não como um simples problema de busca, que se limita a obtenção de uma solução viável. Por outro lado, a utilização de pacotes comerciais de otimização se apresenta como um limitador para a execução de instâncias maiores, pois esses programas são desenvolvidos para uso genérico. Então, a fim de aumentar o desempenho dos procedimentos de alocação de professores e a construção do quadro de horários como um todo, como trabalhos futuros, podem ser desenvolvidos algoritmos especialistas que sejam capazes de aproveitar a estrutura do problema para se tornarem mais eficientes na prática. Essa eficiência pode estar relacionada à escalabilidade (capacidade de processar maiores instâncias) e desempenho (tempo e recursos utilizados). No entanto, mesmo em grandes instituições, com grandes instâncias, dependendo dos recursos e investimentos empregados, o uso de pacotes comerciais de otimização pode se apresentar satisfatório. A apresentação de uma formulação alternativa também pode ser útil para o desenvolvimento de trabalhos futuros, pois como seu entendimento é mais intuitivo (fluxos em redes), novos procedimentos podem ser formulados a partir de tal estrutura. Por fim, a metodologia proposta pode ser acoplada a um sistema ERP (Enterprise Resource Planning), a fim de promover um ambiente de gestão administrativo-acadêmico integrado que permita ao gestor implantar efetivamente o processo, definindo parâmetros e 137 metas, e dessa forma, controlar de forma efetiva todas as atividades e recursos envolvidos na vida de uma instituição de ensino superior. 138 Capítulo 6 - Bibliografia [1] ABRAMSON, D., Constructing School Timetables using Simulated Annealing: Sequential and Parallel Algorithms. Management Science, v. 37, n. 1, p. 98-113, 1991. [2] ABRAMSON, D.; ABELA, J.; A Parallel Genetic Algorithm for Solving the School Timetabling Problem. Technical report, Division of Information Technology, C.S.I.R.O, 1991. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [3] AKKOYUNLU, E. A., A linear algorithm for computing the optimum university timetable. Computer Journal, v. 16, n. 4, p. 347-350, 1973. [4] BARRACLOUGH, Elizabeth D., The application of a digital computer to the construction of timetables. The Computer Journal, v. 8, n. 2, p. 136-146, 1965. [5] BLOOMFIELD, S. D.; MCSHARRY, M. M., Preferencial Course Scheduling System. Interfaces, v. 9, n. 4, p. 24-31, 1979. [6] BRASIL. Congresso Nacional. Lei n. 9.394 de 20 de dezembro de 1996. Estabelece as diretrizes e bases da educação nacional. Diário Oficial da União, Poder Executivo, Brasília, DF, 23 dez. 1996. Seção 1. p. 27833. Disponível em: http://www.camara.gov.br. Acesso em: 25 mai. 2006. [7] BRASIL. Ministério da Educação. Manual de Avaliação Externa de Instituições de Educação Superior: Diretrizes e Instrumento. Brasília, fev. 2006. Disponível em http://www.inep.gov.br. Acesso em: 25 mai. 2006. [8] BRASIL. Ministério da Educação. Portaria n. 300 de 30 de janeiro de 2006. Aprova, em extrato, o Instrumento de Avaliação Externa de Instituições de Educação Superior do Sistema Nacional de Avaliação da Educação Superior – SINAES. Diário Oficial da União, Poder Executivo, Brasília, DF, 31 jan. 2006. Seção 1. p. 5. Disponível em: www.inep.gov.br. Acesso em: 25 mai. 2006. [9] BRASIL. Ministério da Educação. Portaria n. 563 de 21 de fevereiro de 2006. Aprova, em extrato, o Instrumento de Avaliação de Cursos de Graduação do Sistema Nacional de Avaliação da Educação Superior – SINAES. Diário Oficial da União, Poder Executivo, Brasília, DF, 22 fev. 2006. Seção 1. p. 6. Disponível em: www.inep.gov.br. Acesso em: 25 mai. 2006. [10] BRASIL. Presidência da República. Decreto n. 5.773 de 9 de maio de 2006. Dispõe sobre o exercício das funções de regulação, supervisão e avaliação de instituições de educação superior e cursos superiores de graduação e seqüenciais no sistema federal de ensino. Diário Oficial da União, Poder Executivo, Brasília, DF, 10 mai. 2006. Seção 1. p. 6. Disponível em: http://www.camara.gov.br. Acesso em: 25 mai. 2006. [11] BRASIL. Presidência da República. Decreto n. 5.786 de 24 de maio de 2006. Dispõe sobre os centros universitários e dá outras providências. Diário Oficial da União, Poder Executivo, Brasília, DF, 25 mai. 2006. Seção 1. p. 9. Disponível em: http://www.camara.gov.br. Acesso em: 25 mai. 2006. [12] BRAZ JÚNIOR, Osmar de Oliveira, Otimização de Horários em Instituições de Ensino Superior Através de Algoritmos Genéticos. 2000. 131 f. Dissertação (Mestrado em Engenharia de Produção) – Departamento de Engenharia de Produção, Universidade Federal de Santa Catarina, Florianópolis, 2000. 139 [13] BURKE, E. K., ELLIMAN, D. G., WEARE, R., A University Timetabling System based on Graph Colouring and Constraint Manipulation. Journal of Research on Computing in Education, v. 27, n. 1, p. 1-18, 1994. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [14] BURKE, E. K.; KINGSTON, J. H.; JACKSON, K.; WEARE, R., Automated University Timetabling: the state of the art. The Computer Journal, v. 40, n. 9, p. 565-571, 1997. [15] BURKE, E. K.; PETROVIC, S., Recent research directions in automated timetabling. European Journal of Operational Research, v. 140, n. 2, p. 266-280, 2002. [16] CARTER, M. W.; TOVEY, C. A.; When is the classroom assignment problem hard? Operations Research, v. 40, n. 1, p. 28-39, 1989 apud [50]. [17] CARTER, Michael W., LAPORTE, Gilbert, Recent developments in practical course timetabling. Lecture Notes in Computer Science, v. 1408, p. 3-19, 1997. [18] CARVALHO, Mário T. P., Confecção de Horários de Aulas em Instituições de Ensino Privadas de 3º Grau no Brasil, 2002. 101 f. Dissertação (Mestrado em Engenharia de Produção). Departamento de Engenharia de Produção, Universidade Federal de Minas Gerais, Belo Horizonte, 2002. [19] CHAVES, Thiago F., Um Sistema de Apoio à Construção de Quadros de Horários, 2005. 77 f. Dissertação. Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, 2006. No prelo. [20] CHIARANDINI, Marco; STÜTZLE, Thomas; An Application of Iterated Local Search to Graph Coloring. In: COMPUTATIONAL SYMPOSIUM ON GRAPH COLORING AND ITS GENERALIZATIONS, 2002, New York [Proceedings…], Ithaca, New York, 2002. p. 112-125. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [21] CISCON, Leonardo A. et al. O Problema da Geração de Horários: um foco na eliminação de janelas e aulas isoladas. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 37, 2005, Gramado. [Anais eletrônicos...] Gramado: UFRGS, 2005. 1 CD-ROM. p. 1724-1732. [22] COLORNI, Alberto; DORIGO, Marco; MANIEZZO, Vittorio; A Genetic Algorithm to Solve the Timetable Problem. Technical Report, v. 90, n. 60, Politecnico di Milano, Italy, 1992. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [23] COOPER, Tim B.; KINGSTON, Jeffrey H., The Complexity of Timetable Construction Problems. In: INTERNATIONAL CONFERENCE ON THE PRACTICE AND THEORY OF AUTOMATED TIMETABLING, 1., 1995, Edingburgh. [Proceedings…] Edingburgh: ICPTAT, 1995. p. 511-522. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 2 out. 2005. [24] DASKALAKI, S.; BIRBAS, T.; HOUSOS, E.; An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, v.153, p. 117-135. 2004. [25] EIKELDER, H.; WILLEMEN, R. J.; Some complexity aspects of secondary school timetables problems. Lecture Notes in Computer Science, v. 2079, p. 18-27, 2001. 140 [26] EVEN, S.; ITAI, A.; SHAMIR, A.; On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, v. 5, n. 4, p. 691-703, 1976. [27] FERLAND, Jacques A.; ROY, Serge; Timetabling Problem for University as Assignment of Activities to Resources. Computers and Operation Research, v. 12, n. 2, p. 207-218, 1985. [28] FOURER, R.; GAY, D.; KERNIGHAN, B., AMPL: a modeling language for mathematical programming, 2 ed. Toronto: Thomson, 2003. [29] GAREY, M.; JOHNSON, D., Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979. 340 p. [30] GOLTZ, Hans-Joachim, MATZKE, Dirk, University Timetabling Using Constraint Logic Programming. Lecture Notes in Computer Science, v. 1551, p. 320-334, 1999. [31] GOSSELIN, Karl; TRUCHON, Michel; Allocation of classrooms by linear programming. Journal of Operational Research Society, v. 37, n. 6, p. 561-569, 1986. [32] GUÉRET, Christelle; JUSSIEN, Narendra; BOIZUMAULT, Patrice, PRINS, Christian; Building University Timetables using constraint logic programming. In: INTERNATIONAL CONFERENCE ON THE PRACTICE AND THEORY OF AUTOMATED TIMETABLING, 1., 1995, Edingburgh. [Proceedings…] Edingburgh: ICPTAT, 1995. p. 393-408. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [33] HULTBERG, Tim H.; CARDOSO, Domingos M.; The teacher assignment problem: a especial case of the fixed charge transportation problem. European Journal of Operational Research, v. 101, n. 3, p. 463-473, 1997. [34] ILOG, ILOG AMPL CPLEX System User´s Guide, V. 9.0, Gentilly: ILOG, 2003. Disponível em: www.ampl.com. Acesso em: 2 fev. 2006. [35] INSTITUTO NACIONAL DE ESTUDOS E PESQUISAS EDUCACIONAIS ANÍSIO TEIXEIRA. SINAES – Sistema Nacional de Avaliação da Educação Superior: da concepção à regulamentação. 2º ed. Brasília: INEP, 2004. [36] INSTITUTO NACIONAL DE ESTUDOS E PESQUISAS EDUCACIONAIS ANÍSIO TEIXEIRA. Censo da Educação Superior 2004: Resumo Técnico. Brasília: INEP, 2005. Disponível em www.inep.gov.br. Acesso em: 25 mai. 2006. [37] LARA, Braulio A. S., Um Modelo de Programação Linear para Solução do Problema da Aplicação de Recursos em Atividades Complementares em Instituições de Ensino Superior. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 36., 2004, São João Del Rei. [Anais eletrônicos...] São João Del Rei: UFSJ, 2004. 1 CD-ROM. p. 381-387. [38] MCCLURE, Richard H.; WELLS, Charles E.; A Mathematical Programming Model for Faculty Course Assignments. Decision Sciences, v. 15, n. 3, p. 409-420, 1984. [39] MEISELS, Amnon, ELL-SANA, Jihad, GUDES, Ehud, Decomposing and Solving Timetabling Constraint Networks. Computational Intelligence, v. 13, n. 4, p. 486- 505, 1997. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [40] MICROSOFT CORP. Visual Basic: guia do programador. v. 5.0, [New York]: Microsoft Press, 1997. 141 [41] MINER, Sara K.; ELMOHAMED, Saleh; YAU, Hon W.; Optimizing Timetabling Solutions Using Graph Coloring. NPAC REU program, NPAC, Syracuse University, Syracuse, NY, 1995. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [42] MUSHI, A. R. Mathematical Programming Formulations for the Examinations Timetabling Problem: The Case of the University of Dar Es Salaam. African Journal of Science and Technology: Science and Engineering Series, v. 5, n. 2, p. 34-40, 2004. [43] REIS, Luís Paulo, OLIVEIRA, Eugênio. A Language for Specifying Complete Timetabling Problems. Lecture Notes in Computer Science, v. 2079, p. 322-337, 2001. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 2 jun. 2006. [44] RIBEIRO FILHO, Geraldo; LORENA, Luiz A. N.; A Constructive Evolutionary Approach to School Timetabling. Lecture Notes in Computer Science, v. 2037, p. 130-139, 2001. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [45] ROSS, Peter, CORNE, Dave, FANG, Hsiao-Lan, Successful Lecture Timetabling with Evolutionary Algorithms. In: EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, 11., 1994, Amsterdam. [Proceedings…] Amsterdam: ECAI, 1994. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [46] RUDOVA, Hana, MURRAY, Keith. University Course Timetabling with Soft Constraints. In: INTERNATIONAL CONFERENCE ON THE PRACTICE AND THEORY OF AUTOMATED TIMETABLING, 4., 2002, Gent. [Proceedings…] Gent: ICPTAT, 2002. p. 73-89. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [47] SANDHU, Kuldeep Singh., Automating Class Schedule Generation in the Context of a University Timetabling Information System, 2001. 200 f. These. (Doctor of Philosophy in Managment) School of Management, Griffith University, Nathan, Australia, 2003. Disponível em: http://www4.gu.edu.au:8080/adt-root/public/adt- QGU20030825.121338/ . Acesso em: 22 jun. 2006. [48] SANTOS, Haroldo G.; OCHI, Luiz S.; SOUZA, Marcone J. F.; A Tabu Search Heuristic with Efficient Diversification Strategies for the Class/Teacher Timetabling Problem. In: INTERNATIONAL CONFERENCE ON THE PRACTICE AND THEORY OF AUTOMATED TIMETABLING, 5., 2004, Pittsburgh. [Proceedings…] Pittsburgh: ICPTAT, 2004. p. 343-359. Disponível em: www.asap.cs.nott.ac.uk. Acesso em: 26 jun. 2006. [49] SANTOS, Haroldo G.; OCHI, Luiz S.; SOUZA, Marcone J. F.; An Efficient Tabu Search Heuristic for the School Timetabling Problem. Lecture Notes in Computer Science, v. 3059, p. 468-481, 2004. [50] SCHAERF, A., A Survey of Automated Timetabling. Artificial Intelligence Review, v.13, n. 2, apr. 1999, p. 87-127. [51] SCHAERF, Andrea; DI GASPERO, Luca; Local Search Techniques for Educational Timetabling Problems. In: INTERNATIONAL SYMPOSIUM ON OPERATIONS RESEARCH, 6., 2001, Slovenia. [Proceedings…] Slovenia: SOR, 2001. p. 13-23. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. 142 [52] SMITH, Kate A.; ABRAMSON, David; DUKE, David; Hopfield neural networks for timetabling: formulations, methods and comparative results. Computers and Industrial Engineering, v. 44, p. 283-305, 2003. [53] SOCHA, Krzysztof; KNOWLES, Joshua; SAMPELS, Michael; A Max-Min Ant System for the University Course Timetabling Problem. Lecture Notes in Computer Science, v. 2463, p. 1-13, 2002. Disponível em: www.citeseer.ist.psu.edu. Acesso em: 26 jun. 2006. [54] SOUZA, Marcone J. F., Programação de horários em escolas: uma aproximação por metaheurísticas. 2000. 149 f. Tese (Doutorado em Engenharia de Sistemas e Computação) – COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, 2000. [55] TEIXEIRA, P. J. M., MELO, Valdir A., BOAVENTURA NETTO, P. O., Alocação de Docentes a Disciplinas em um Departamento: Uma Aplicação do Problema do B- acoplamento. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 36., 2004, São João Del Rei. [Anais eletrônicos...] São João Del Rei: UFSJ, 2004. 1 CD- ROM. p. 2239-2250. [56] TERRA, Ivone P., Uma Solução para a Confecção do Horário Acadêmico, 2001. 59 f. Dissertação. (Mestrado em Ciência da Computação) Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, 2001. [57] TRIPATHY, Arabinda. School Timetabling: a case in large binary integer linear programming. Management Science, v. 30, n. 12, p.1473-1489, 1984. [58] WERRA, D., An Introduction to Timetabling, European Journal of Operational Research, Amsterdam, v. 19, n. 2, p. 151-162, feb. 1985. [59] WERRA, D., The combinatorics of timetabling. European Journal of Operational Research, v. 96, p. 504-513, 1997. [60] WHITE, George M.; WONG, Simon K. S., Interactive Timetabling in Universities. Computers in Education, v.12, n. 4, p. 521-529, 1988.