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.

Passo 2

Definimos variáveis inteiras não negativas x_1,\dots,x_8, onde
\begin{aligned} x_1&=\text{número de estudantes que começam às 8 h},\\\ x_2&=\text{“ ” às 9 h},\quad x_3\text{ “ ” às 10 h},\quad x_4\text{ “ ” às 11 h},\\\ x_5&=\text{“ ” às 13 h},\quad x_6\text{ “ ” às 14 h},\quad x_7\text{ “ ” às 15 h 01},\quad x_8\text{ “ ” às 16 h 01}. \end{aligned}úçàààààààà

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:
\begin{aligned} &\text{(A) }8\text{–}10:\quad x_{1}+x_{2}\;\ge2,\\\ &\text{(B) }10{:}01\text{–}11:\quad x_{1}+x_{2}+x_{3}\;\ge3,\\\ &\text{(C1) }11{:}01\text{–}12:\quad x_{2}+x_{3}+x_{4}\;\ge4,\\\ &\text{(C2) }12\text{–}13:\quad x_{3}+x_{4}\;\ge4,\\\ &\text{(D1) }13{:}01\text{–}14:\quad x_{4}+x_{5}\;\ge3,\\\ &\text{(D2) }14\text{–}15{:}01:\quad x_{5}+x_{6}\;\ge3,\\\ &\text{(D3) }15{:}01\text{–}16{:}01:\quad x_{5}+x_{6}+x_{7}\;\ge3,\\\ &\text{(D4) }16{:}01\text{–}17:\quad x_{6}+x_{7}+x_{8}\;\ge3. \end{aligned}

Passo 4

O objetivo é minimizar
\min\;X = \sum_{i=1}^{8}x_i
sujeito às oito desigualdades acima e x_i\in\mathbb{Z}_{\ge0}.

Passo 5

Ao resolver essa programação inteira por inspeção, nota-se que as duas observações chave são:
  1. Para cobrir 12–13 (C2) precisamos de x_3+x_4\ge4.
  2. Para cobrir 14–15 h01 (D2) e adiante basta usar três turnos iniciando às 14 h x_6=3, o que resolverá automaticamente (D3) e (D4) com x_7=x_8=0.
Escolhendo
x_3=1,\quad x_4=3
satisfaz x_3+x_4=4. Para as duas primeiras demandas, toma-se x_1+x_2=2 (mínimo para (A)) e ajusta-se para (B) e (C1). Basta pôr x_1=2,x_2=0. Finalmente, para D selecionamos
x_5=0,\quad x_6=3,\quad x_7=0,\quad x_8=0.
Esse vetor (2,0,1,3,0,3,0,0) totaliza 2+0+1+3+0+3+0+0=9 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.

Exercícios relacionados