# Multi-Criteria Optimization in Operations Scheduling Applying Selected Priority Rules
## 3 Multi-Criteria Optimization in Scheduling
### Multi-Criteria Optimization Problem  
In general, we consider a MOP (2) with \(n\) decision variables and \(k\) objectives (\(k>1\)). Solving MOP is a procedure of simultaneous optimization of a set of \(k\) individual objective functions \(Fi\) (\(\mathbf{x}\)) subjected to constraints given by the system of inequalities and equalities. It can be represented in the form (2):  
\[ \begin{array}{ll}\text{Minimize}&\\ \mathbf{x}\in D&\mathbf{F}(\mathbf{x})=[F_{1}(\mathbf{x}),\;F_{2}(\mathbf{x}),\;\ldots,\;F_{k}( \mathbf{x})]^{T};\;k>1\\ \text{subject to}&g_{s}(\mathbf{x})\leq 0,s=1,2,\ldots,\;m;\;m\geq 0,\\ &h_{l}(\mathbf{x})=0,l=1,2,\ldots,\;r;\;r\geq 0.\end{array}  \tag{2}\]  
Vector \(\mathbf{x}\) is the decision vector in the feasible region \(D\) in \(n\)-dimensional design (decision) space, constrained by inequalities \(\mathbf{x}_{L}\leq\mathbf{x}\leq\mathbf{x}_{\mathbf{U}}\). In case of a combinatorial problem, the \(D\) region is discrete. Vector \(\mathbf{F}(\mathbf{x})\;\in E_{k}\) consists of \(k\) objective functions \(F_{i}(\mathbf{x})\): \(E_{n}\to\;E_{1}\) in the feasible objective (criterion) space \(Z\), \(Z\subset E_{k}\). As a result of solving MOP, if the objectives \(F_{i}(\mathbf{x})\) are conflicting, one cannot be able to find one single solution as the best one, rather a set of trade-offs, all with a compromising nature. Due to the absence of an absolute ordering in the vector space, the way how to identify MOP solution is via the preference relationship of partial preorder based on Pareto relation. It is built on the following associated definitions:  
Pareto dominance: A decision vector \(\mathbf{x}\) (\(\mathbf{x}\in D\)) (Pareto) dominates a decision vector \(\mathbf{y}\) (denoted \(\mathbf{x}\prec\mathbf{y}\)) if and only if \(F_{i}(\mathbf{x})\leq F_{i}(\mathbf{y})\;\forall\;i\;\in\{1,2,\ldots,k\}\;\wedge\;F_{ i}(\mathbf{x})<F_{i}(\mathbf{y})\) for at least one \(i\in\{1,2,\ldots,k\},\;k\geq 2\). Pareto optimality: A solution \(\mathbf{x}\in D\) is Pareto optimal if does not exists any other \(\mathbf{x}^{\prime}\in D\) that dominates \(\mathbf{x}\)[34]. The set of Pareto optimal solutions is called the Pareto optimal set. Its image in the objective space is referred to as the Pareto optimal front [38]. Pareto optima correspond to \"best trade-off\" solutions between different conflicting criteria\" [39]. From a geometric perspective, the Pareto front represents a hypersurface in \(k\)-dimensional space of objective functions, where all non-dominated solutions are located. The optimal solution of MOP can be also characterized by terms of efficient solution and non-dominated solution according to space where the MOP solutions are located. Typically, efficiency refers to a vector of design variables in the design space, whereas dominance refers to a vector of functions in objective space [24]. These basic terms are explained by the following definitions, adopted from [PERSON] and [PERSON] [24]:  
A feasible solution \(x^{*}\) situated in design (decision) space \(D\) is efficient if and only if there does not exist any other \(x\in D\) such that \(\mathbf{F}(\mathbf{x})\leq\mathbf{F}(\mathbf{x}^{*})\) with at least one \(F_{i}(\mathbf{x})<F_{i}(\mathbf{x}^{*})\). With relation to the objective space, a corresponding vector \(\mathbf{F}(\mathbf{x}^{*})\) in the objective space is non-dominated if and only if there does not exist another vector \(\mathbf{F}(\mathbf{x})\in Z\) such that \(\mathbf{F}(\mathbf{x})\leq\mathbf{F}(\mathbf{x}^{*})\) with at least one \(F_{i}(\mathbf{x})<F_{i}(\mathbf{x}^{*})\). That means all non-dominated solutions dominate the others, but do not dominate themselves. Both introduced definitions represent a similar idea and \"a recipe\" for how to identify Pareto-optimal solutions via a vector's coordinates comparison. We will use the term Pareto-optimal solution in the sense of non-dominated solution yielded by solving MOP throughout the following text. For an excellent survey of multicriteria scheduling, we refer to the book by [PERSON] and [PERSON] [39].