Task Scheduler

Script em python (com alternativa em Julia), que faz a organização de datas de entrega de tarefas. O script foi desenvolvido com o intuito de facilitar minha organização para estudos para provas e desenvolvimento de trabalhos. Publicado no GitHub após pedidos de meus colegas.

O que preciso saber para utilizar?

O algoritmo se baseia em duas listas, a lista E (Entregas) e a lista F ("Fins de semana"). F não precisa ser necessariamente fins de semana, mas recebeu esse nome devido a uma limitação minha quando fiz o algoritmo. Assim, para utilizar o programa, basta preencher as listas E e F e rodar o script. O script supõe que existe uma solução válida para a organização.

Lista E

Os valores de E são os dias de entrega de atividades que levam 1 turno para serem realizadas. O dia é definido por um número inteiro não negativo, que pode ser considerado o número de dias a partir de algum ponto. Se 1 fosse o dia 01/03, 2 seria o dia 02/03, 31 seria o dia 31/03 e 32 seria o dia 01/04. 1 turno é definido como metade de um dia, significando que se você possui 1 dia livre, você possui 2 turnos livres, podendo assim realizar duas atividades nesse dia. Atividades que levariam mais de um turno podem ser simplesmente duplicadas na lista e são indistinguíveis de outras atividades com a mesma data de entrega. Atividades podem ser datas de provas para as quais se pretende estudar em um dia em F.

Lista F

Os valores de F são os dias livres que se têm disponíveis para realização das atividades. Os dias são sempre compostos de 2 turnos, atualmente não se tem flexibilidade para dias com apenas 1 turno disponível.

O que o script faz

O script utilizará as atividades da lista E e os dias da lista F para informar quais são as melhores escolhas de dias para se fazer cada atividade de modo a minimizar o intervalo de tempo entre quando a atividade foi feita e seu prazo. Essa minimização foi feita tendo em mente diminuir a margem entre o dia em que se estuda para uma prova e o dia em que se faz a prova, e evitar que fossem feitos trabalhos antes que o professor passasse o conteúdo necessário para se realizar tal trabalho.

Como funciona

O algoritmo é baseado nos princípios de programação linear em inteiros aprendidos durante a cadeira de Otimização Combinatória na UFRGS. A primeira versão do problema foi escrita em Julia utilizando algoritmos do professor como base e foi reescrito em python para facilitar adição de outras implementações que podem vir a serem úteis.

Variáveis x

Considera-se que existem n atividades para serem entregues (n = |E|) e que existem m dias para que sejam feitas (m = |F|). Então gera-se n⋅m variáveis binárias x, sendo x_ij∈B ∀i∈[n],j∈[m], de modo que x_ij é 1 se a i-ésima tarefa em E será feita no j-ésimo dia em F e 0 caso contrário.

Função objetivo

O objetivo é minimizar o tempo entre as atividades serem feitas e a data em que precisam estar prontas, desse modo, minimizamos a soma de todos os E[i] - F[j] para todos as combinações de atividades i que foram feitas em dias j. Com as variáveis que temos, podemos dizer que a função objetivo é Min Σ_i∈[n]Σ_j∈[m] x_ij⋅(E[i] - F[j]), fazendo com que a soma seja somente entre as combinações de i e j que foram utilizadas.

Restrições

As restrições do problema são que:

Todas as atividades devem ser feitas exatamente uma vez

Como seria irracional fazer uma atividade mais de uma vez, já que isso apenas faria com que mais um valor fosse somado na função objetivo, piorando o valor otimizado, podemos reformular essa restrição como "Todas as atividades devem ser feitas" e sua formulação matemática seria: Σ_j∈[m] x_ij ≥ 1 ∀i∈[n]. Pode-se interpretar como "Para toda atividade i, deve-se somar 1 ou mais dias j em que ela foi feita"

Só se pode fazer até duas atividades por dia

Sua formulação matemática seria: Σ_i∈[n] x_ij ≤ 2 ∀j∈[m]. Pode-se interpretar como "Para todo dia j, deve-se somar 2 ou menos atividades i feitas nesse dia"

Uma atividade deve ser feita em um fim de semana anterior à data de entrega.

Aqui, precisamos pensar que E[i] deve ser maior que F[j] para todas as combinações de atividades i que foram feitas em dias j. Como x_ij diz se uma atividade i foi feita no dia j, podemos representar isso como x_ij → E[i] ≥ F[j] ∀i∈[n],j∈[m]. Isso pode ser alcançado na restrição por meio de: E[i] ≥ x_ij⋅F[j] ∀i∈[n],j∈[m].

Solução

A solução, então, consiste em descobrir quais atividades i fazer em quais dias j. Portanto, basta exibir quais x_ij são 1.