## 5 Scheduling Problems  
Scheduling problems are numerous and varied. They arise in diverse areas such as flexible manufacturing systems, production planning, computer design, logistics, timetabling, communication, etc. [14].  
Here we focus on one of them, the Permutation Flow Shop Scheduling Problem (PFSSP), which, like the Assignment problem and the Traveling Salesman Problem, is permutational in nature.  
It can be briefly described as follows: There are a set of \(m\) machines (processors) and a set of \(n\) jobs. Each job comprises a set of \(m\) operations which must be done on different machines. All jobs have the same processing operation order when passing through the machines. There are no precedence constraints among operations of different jobs. Operations cannot be interrupted, and each machine can process only one operation at a time. The problem is to find the job sequences on the machines which minimizes the makespan (i.e., the maximum completion times of all operations).  
Mathematical Model of PFSSP  
Consider three finite sets \(J,\,M,\,O\) where \(J\) is a set of jobs \(1,\,\ldots,\,n,\,M\) is a set of machines \(1,\,\ldots,\,m\), and \(O\) is a set of operations \(1,\,\ldots,\,m\).  
Denote:  
\[\begin{array}{lclcl}J_{i}&\ldots&\mbox{the $i$th job in the permutation of jobs}\\ p_{ik}&\ldots&\mbox{processing time of the job $J_{i}\in J$ on machine $k$}\\ &&\\ (\forall i\in J)(\forall k\in M):&v_{ik}&=&\mbox{waiting time (idle time) on machine $k$}\\ &&\mbox{before starting job $J_{i}$}\\ &&\\ (\forall i\in J)(\forall k\in M):&w_{ik}&=&\mbox{waiting time (idle time) of job $J_{i}$}\\ &&\mbox{after finishing processing on machine $k$}\\ &&\mbox{while waiting for machine $k+1$ to become available}\end{array}\]  
Define the following decision variables:  
\[\forall i,j\in J:\ \ x_{ij}=\left\{\begin{array}{lcl}1,&\mbox{if job $j$ \ is assigned to the $i$th position in the permutation $(J_{i}=j)$}\\ 0,&\mbox{otherwise}\end{array}\right. \tag{83}\]  
Figure 1 illustrates the use of the variables \(v_{ik}\) and \(w_{ik}\) on an example with 5 jobs and 3 machines.  
From Figure 1, we can draw some more general conclusions:  
* The first task in a permutation can always continue the next operation on the next machine without delay because it does not wait for the completion of any other operation.
* It follows from the previous conclusion that waiting times to start the operation of the first task in the permutation on the second and subsequent machines are given by the sum of the durations of the operations of that task on the previous machines.
* Equalities of 3 addition terms in Figure 1 can be generalized into a Gantt chart between all pairs of neighboring machines.
* The duration of the entire schedule (makespan) is given by the sum of the waiting times for the start of operations on the last machine and the duration of these operations.  
All verbal conclusions are expressed formally by the following system of equations:  
\[\forall i\in J:\sum_{j=1}^{n}x_{ij} = 1 \tag{84}\] \[\forall j\in J:\sum_{i=1}^{n}x_{ij} = 1\] (85) \[\forall k\in M-\{m\}:w_{1k} = 0\] (86) \[\forall k\in M-\{1\}:v_{1k} = \sum_{r=1}^{k-1}\sum_{i=1}^{n}p_{ir}x_{1i}\] (87) \[\left(\forall i\in J-\{n\}\right)\left(\forall k\in M-\{m\}\right):\] \[v_{i+1,k}+\sum_{j=1}^{n}p_{jk}x_{i+1,j}+w_{i+1,k} = w_{ik}+\sum_{j=1}^{n}p_{j,k+1}x_{ij}+v_{i+1,k+1}\] (88) \[C_{\max} = \sum_{i=1}^{n}(v_{im}+\sum_{j=1}^{n}p_{jm}x_{ij}) \tag{89}\]