## 2 Scheduling Problem Definition  
The scheduling problem is a combinatorial optimization problem subject to constraints, with a dynamic nature, and its solution poses challenges. [PERSON] [11] pointed out that scheduling can be defined as the allocation of resources to tasks over time, and that it is a decision making process in order to optimize one or more objectives.  
The main elements of a production scheduling problem are: machines, tasks, operations and plans. A machine is characterized by its qualitative (or functional) characteristics and its quantitative capabilities. A task is composed by a set of operations that may either be sequential or concurrent. Each task is associated with a precedence graph of operations. An operation is processed on a machine. Each operation can be associated with a processing time in a machine, plus the set-up, transport and waiting times on that machine. A scheduling plan is a task execution program, with clear identification of the tasks' processing sequence on the machines, and the start and completion times of task operations. A plan is said to be admissible or feasible if it is possible to be totally fulfilled while obeying the imposed constraints. In practice, scheduling problems are discrete, distributed, dynamic and non-deterministic. Those are quite different from theoretical problems [11].  
This paper considers scheduling problems based on job-shop [11] with some additional constraints, which are important for a more realistic representation of the manufacturing process. These problems are known as extended job-shop scheduling problems [12]. Additional constraints considered for this type of problem are: different release and due dates for each task; priorities associated with the tasks; the possibility that not all machines are used for all tasks; a job can have more than one operation to be performed on the same machine; the possibility of simultaneous processing operations belonging to the same task; the existence of alternative machines, whether identical or not, for processing operations.  
It is also important to note that no task starts its processing before the respective release date, and its completion shall not exceed the due date (although it can be possible, usually with some penalization).  
In this work, solutions are encoded by a direct representation, where the schedule is described as a sequence of operations. Therefore, each position represents an operation index with initial and final processing times. Each operation is characterized by the index \((i,j,k,l)\), which contains natural numbers, where \(i\) defines the machine in which the operation \(k\) is processed, \(j\) the job (task) it belongs to and \(l\) the graph precedence level. Level 1 corresponds to initial operations, without precedents [8; 13].  
The minimization of total completion time, also known as the makespan [11], is:  
\[\begin{split}&\text{Min }C_{max}=\max(F_{j}),\ \forall j=1,\ldots,n,\\ &\text{subject to}\\ & ST_{ijkl}+p_{ijkl}\leq ST_{ij^{\prime}k^{\prime}l^{\prime}}\\ &\forall j=1,\ldots,n,\ \forall(O_{ijkl},O_{ij^{\prime}k^{\prime}l^{ \prime}})\end{split} \tag{1}\]  
The constraints from Equation (1) represents the precedent relationship between two operations \(k\) e \(k^{\prime}(k\
eq k^{\prime}\), \(k<k^{\prime}\) and \(l\leq l^{\prime})\) of the same job \(j\), which can be executed on different machines \(k\) and \(k^{\prime}\), and at different levels \(l\) and \(l^{\prime}\).  
\[ST_{ijkl}\geq t_{ijkl+1}\,\quad\forall O_{ijkl} \tag{2}\]  
This constraint on (2) represents that the processing time to start operation \(O_{ijkl}\) must be larger or equal to the earliest starting time for the same operation.