****************************************************
Modelo Flowshop para planilha eletrônica no gnumeric
2019s1: Cid C. de Souza (IC-Unicamp)
****************************************************

* Parâmetros:

.. N: conjunto de tarefas {1,...,n} (n=|N|}
.. d_{kj}, k \in {1,2}, j \in N: duração do processamento da 
                                 tarefa j na máquina k;
.. M: valor grande, no caso escolhido como:
      M=\sum_{j \in N} d_{1j}
      (soma dos tempos de processamento na máquina 1)

.. MM: valor grande, no caso escolhido como:
       MM = M + \sum_{j \in N} d_{2j} 
       (soma de todos tempos de processamento)

* variáveis:

- f_{1j}: instante de término da tarefa j na máquina 1
          (variável inteira)

- f_{2j}: instante de término da tarefa j na máquina 2
          (variável inteira)

- x_{ij}=1  <==>  tarefa i é o predecessor imediato da tarefa j 
                  na permutação ótima (variável binária)

* FO: z = min_{j \in N} f_{2j}

* Restrições:

.. R1:  tempo de término da  tarefa j na  máquina 1 deve ser  maior ou
       igual à  soma do  tempo de  término da tarefa  i quando  esta a
       precede com a sua própria duração  na máquina 1.  A restrição é
       redundante se i não precede j.

       f_{1j} >= f_{1i} + x_{ij}*(d_{1j}+M) - M, para todo par (i,j) \in NxN
 
.. R2:  tempo de término da  tarefa j na  máquina 1 deve ser  menor ou
       igual ao  tempo de término menos  a duração da tarefa  i quando
       esta a sucede na máquina 1.   A restrição é redundante se i não
       sucede j.

       f_{1j} <= f_{1i} - x_{ji}*(d_{1i}+M) + M, para todo par (i,j) \in NxN

       Esta restrição se vale do fato  de que existe uma solução ótima
       que, além de ser um  permutation schedule, também não apresenta
       ociosidade na máquina 1.

.. R3:  tempo de término da  tarefa j na  máquina 2 deve ser  maior ou
       igual ao  tempo de término  da tarefa  i quando esta  a precede
       mais  a  sua  própria  duração  na máquina  2.  A  restrição  é
       redundante se i não sucede j.

       f_{2j} >= f_{2i} + x_{ij}*(d_{2j}+MM) - MM, para todo par (i,j) \in NxN

.. R4:  tempo de término da  tarefa j na  máquina 2 deve ser  maior ou
       igual ao seu  tempo de término na máquina 1  mais a sua duração
       na máquina 2.

      f_{2j} >= f_{1j} + d_{2j}, para todo j \in N

.. R5: as tarefas i e j não podem preceder uma à outra simultaneamente:

      x_{ij} + x_{ji}  <= 1, para todo par (i,j) \in NxN com i<>j

.. R6: redundante, mas no gnumeric  tem que tomar cuidado como trata o
       caso x_{ii}=0.
       
       x_{ij} <= 1, para todo par (i,j) \in NxN

.. R7: f_{1j} <= M e f_{2j} <= MM, para todo j\in N

.. R8: toda tarefa só pode ter no máximo uma antecessora imediata 
       \sum_{i \in N\{j}} x_{ij} <= 1, para todo j \in N

.. R9: toda tarefa só pode ter no máximo uma sucessora imediata 
       \sum_{i \in N\{j}} x_{ji} <= 1, para todo j \in N

.. R10:  o número total  de relações de  precedência será o  número de
        tarefas menos 1.

        \sum_{i \in N} \sum_{j \in N} x_{ij} = n-1.

.. R11: para todo j \in N, o tempo de término de j na máquina 1
        deve ser maior que o seu tempo de processamento naquela 
        máquina

        f_{1j} >= d_{1j}.

        Esta desigualdade podia ser reforçada para

        f_{1j} >= d_{1j} + \sum{i \in N\{j}} d_{1i}*x{ij},

        mas isto não está implmentado na planilha.