Agendando trabalhos em uma máquina

Esta tarefa consiste em encontrar uma programação ideal para $n$ trabalhos em uma única máquina, se o trabalho $i$ puder ser processada em tempo $t_i$, mas nos $t$ segundos que aguardam antes de processar o trabalho, uma penalidade de $f_i(t)$ deve ser paga.

Assim, a tarefa pede para encontrar essa permutação de trabalhos, de modo que a penalidade total seja mínima. Se denotarmos por $\pi$ a permutação dos trabalhos ($\pi_1$ é o primeiro item processado, $\pi_2$ o segundo etc.), a penalidade total será igual a: $$F(\pi) = f_{\pi_1}(0) + f_{\pi_2}(t_{\pi_1}) + f_{\pi_3}(t_{\pi_1} + t_{\pi_2}) + \dots + f_{\pi_n}\left(\sum_{i=1}^{n-1} t_{\pi_i}\right)$$

Soluções para casos especiais

Funções lineares de penalidade

Primeiro, resolveremos o problema no caso de todas as funções de penalidade $f_i(t)$ serem lineares, ou seja, terem a forma $f_i(t) = c_i \cdot t$, onde $c_i$ é um número não negativo. Observe que essas funções não têm um termo constante. Caso contrário, podemos resumir todos os termos constantes e resolver o problema sem eles.

Vamos fixar uma permutação $\pi$, e tomar um índice $i = 1 \dots n-1$. Deixe a permutação $\pi'$ ser igual à permutação $\pi$ com os elementos $i$ e $i+1$ trocados. Vamos ver o quanto a penalidade mudou. $$F(\pi') - F(\pi) =$$ É fácil ver que as mudanças ocorrem apenas no $i$-ésimo e $(i+1)$-ésimo somando: $$\begin{align} &= c_{\pi_i'} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_{i+1}'} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_{i+1}} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_i} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \end{align}$$

É possível perceber que, se o cronograma/agendamento $\pi$ for ideal, qualquer alteração leva a um aumento da penalidade (ou a uma penalidade idêntica); portanto, para o cronograma ideal, podemos escrever a seguinte condição: $$c \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \ge 0 \quad \forall i = 1 \dots n-1$$ E depois reorganizando, obtemos: $$\frac{c_{\pi_i}}{t_{\pi_i}} \ge \frac{c_{\pi_{i+1}}}{t_{\pi_{i+1}}} \quad \forall i = 1 \dots n-1$$

Assim, obtemos o cronograma ideal simplesmente ordenando os trabalhos pela fração $\frac{c_i}{t_i}$ em ordem não crescente.

Deve-se notar que construímos esse algoritmo pelo chamado "método de permutação": tentamos trocar dois elementos adjacentes, calculamos quanto a penalidade mudou e, em seguida, derivamos o algoritmo para encontrar o método ideal.

Função exponencial de penalidade

Deixe a função de penalidade ter esta forma: $$f_i(t) = c_i \cdot e^{\alpha \cdot t},$$ em que todos os números $c_i$ não são negativos e a constante $\alpha$ é positiva.

Ao aplicar o método da permutação, determinamos que os trabalhos devem ser ordenados em ordem não crescente do valor: $$v_i = \frac{1 - e^{\alpha \cdot t_i}}{c_i}$$

Função monótona idêntica de penalidade

Nesse caso, consideramos o caso em que todos os $f_i(t)$ são iguais e essa função é monótona ascendente.

É óbvio que, nesse caso, a permutação ideal é ordenar os trabalhos(não crescente) pelo tempo de processamento $t_i$.

Teorema de Livshits-Kladov

O teorema de Livshits-Kladov estabelece que o método de permutação é aplicável apenas aos três casos mencionados acima, ou seja:

Em todos os outros casos, o método não pode ser aplicado.

O teorema é comprovado sob a suposição de que as funções de penalidade são suficientemente derivadas (as terceiras derivadas($y'''$) existem).

Nos três casos, aplicamos o método da permutação, através do qual o cronograma ideal desejado pode ser encontrada por ordenações, portanto, em tempo $O(n \log n)$.