Em grande parte dos campi universitários, os departamentos acadêmicos contratam alunos para prestar pequenos serviços, como atender telefone e fazer trabalhos de digitação. A necessidade desse tipo de serviço varia durante o horário normal de trabalho ( 8 h às 17h). No departamento de Engenharia Industrial, o número mínimo necessário de estudantes é dois entre Sh e 10 h , três entre 10 h 01 e 11 h , quatro entre 11 h 01 e 13 h , e três entre 13h01 e 17h. Cada estudante trabalha por três horas consecutivas (exceto os que começam às 15 h 01 , que trabalham duas horas, e os que começam às 16 h 01 , que trabalham uma hora). Devido a seu horário flexível, de modo geral os estudantes podem se apresentar para o trabalho a qualquer hora durante o horário normal de trabalho, mas nenhum deles quer começar a trabalhar na hora do almoço (meio-dia). Determine o número mínimo de estudantes que o Departamento de Engenharia Industrial deve contratar e especifique a que hora do dia cada um deve se apresentar para trabalhar.
Passo 1
O enunciado pede achar o número mínimo de estudantes e os horários de início de turno, de forma que em cada momento do dia (8 h–17 h) o número de estudantes em serviço atenda à demanda mínima:
– de 8 h até 10 h: 2 estudantes;
– de 10 h01 até 11 h: 3 estudantes;
– de 11 h01 até 13 h: 4 estudantes;
– de 13 h01 até 17 h: 3 estudantes.
Cada estudante trabalha três horas consecutivas (exceto quem começa às 15 h 01, que trabalha 2 h, e às 16 h 01, que trabalha 1 h), e ninguém pode iniciar exatamente ao meio-dia. Vamos modelar turnos discretos iniciando nos instantes-chaves 8 h, 9 h, 10 h, 11 h, 13 h, 14 h, 15 h 01 e 16 h 01, escrever as restrições de cobertura e resolver por otimização inteira.
– de 8 h até 10 h: 2 estudantes;
– de 10 h01 até 11 h: 3 estudantes;
– de 11 h01 até 13 h: 4 estudantes;
– de 13 h01 até 17 h: 3 estudantes.
Cada estudante trabalha três horas consecutivas (exceto quem começa às 15 h 01, que trabalha 2 h, e às 16 h 01, que trabalha 1 h), e ninguém pode iniciar exatamente ao meio-dia. Vamos modelar turnos discretos iniciando nos instantes-chaves 8 h, 9 h, 10 h, 11 h, 13 h, 14 h, 15 h 01 e 16 h 01, escrever as restrições de cobertura e resolver por otimização inteira.
Passo 2
Definimos variáveis inteiras não negativas
, onde
Passo 3
Para cada sub-intervalo de demanda, escrevemos a soma dos turnos que o cobrem. Como alguns turnos não cobrem períodos finais, dividimos 11 h01–13 h e 13 h01–17 h em sub-intervalos menores. As restrições são:
Passo 4
O objetivo é minimizar
sujeito às oito desigualdades acima e
.
Passo 5
Ao resolver essa programação inteira por inspeção, nota-se que as duas observações chave são:
- Para cobrir 12–13 (C2) precisamos de
. - Para cobrir 14–15 h01 (D2) e adiante basta usar três turnos iniciando às 14 h
, o que resolverá automaticamente (D3) e (D4) com .
Escolhendo
satisfaz
. Para as duas primeiras demandas, toma-se
(mínimo para (A)) e ajusta-se para (B) e (C1). Basta pôr
. Finalmente, para D selecionamos
Esse vetor
totaliza
estudantes e satisfaz todas as coberturas.
Resposta
O número mínimo de estudantes é 9, distribuídos assim nos horários de início:
– 2 estudantes às 8 h,
– 1 estudante às 10 h,
– 3 estudantes às 11 h,
– 3 estudantes às 14 h.
– 2 estudantes às 8 h,
– 1 estudante às 10 h,
– 3 estudantes às 11 h,
– 3 estudantes às 14 h.