Normalization of Regular Scheduling Criteria with Dynamic Constraint

Normalization is a pre-processing stage for multi-criteria optimization problems used in several fields ranging from computing, material selection, medical and biological application, financing, industrial and project management among others [8]. Numerous researchers in various fields have explored the process within different context. For an instance, in the field of synthetic biology, Degasperi et al. [9] compared objective functions that use data-driven normalisation of the simulations with those that use scaling factors. According to Ersoy [10], normalization for multicriteria optimization problems can be classified into various ways; the need for normalization of objective functions, selection of suitable normalization techniques, studying the effects of different normalization techniques among others. Jain et al. [11] proposed a method for dynamic selection (DS) of optimal normalization technique using data complexity measures. The work evaluates 14 popular learning algorithms for designing dynamic selection model for the selection of optimal normalization technique. In order to design this dynamic selection model, 12 different data complexity measures are extracted for 48 different benchmark datasets. Akande [12] studied the need for normalization techniques in multicriteria scheduling problems. The studies of suitable normalization techniques for simple weighting method of solving multicriteria problem as well as hierarchy solution method was explored by Vafaei et al. [7, 13] respectively. The comparative analysis of linear and vector normalization methods in decision making for learning quota assistance was studied by Budiman and Hairah [14]. Ranking of solution based on normalization techniques was also discussed by Lakshmi and Venkatesan [15].

According to Vafaei et al. [7], it was stated that the linear min max method is the suitable normalization techniques for simple weighting method of solving multicriteria problem. The method is a subset of orientation dependent normalization techniques which is either benefit orientation or cost orientation. For this class, the normalization equation changes for different criteria as well as the imposed constraints. There are numerous multicriteria scheduling problems with release dates found in the literature that requires normalization in order to explore simultaneous optimization by computing the LCOF. These include Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time by Lin and Yin [16], Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness by Huo et al. [17], minimization of total tardiness and total flowtime on single machine with non-zero release dates [4]

However, there are literature that established normalization equations for different objective function with the imposed constraints. Establishing the normalization equations for different regular criteria with unavailability constraints (non zero release date) is the purpose of this work. Though, Oyetunji and Oluleye [18] established the equations for the extreme parameters for completion time using only the benefit orientation. The corresponding equations for other regular performance measures are missing.

This normalization technique performs a linear transformation of the objective function value obtained by a given solution method to a dimensionless and scaled data (0, 1). Two different orientations of linear min-max techniques are usually employed; the benefit and the cost orientation.

4.1 Benefit and cost orientation

The benefit optimization orientation implies that the increase in the performance values of the alternatives evaluated in criterion j is preferred to the decrease while the cost optimization orientation implies that the reduction in the performance values of the alternatives in criterion j is preferred to the increase [8]. The general equations for the two orientations are given in Eqs. (9) and (10).

$Y_B=\frac{Y_{S M}-Y_{\min }}{Y_{\max }-Y_{\min }}$                 （9）

$Y_c=\frac{Y_{\max }-Y_{S M}}{Y_{\max }-Y_{\min }}$          （10）

where:

$Y_b$ is the benefit orientation normalized value of the objective function, X.

$Y_c$ is the cost orientation normalized value of the objective function, X.

$Y_{S M}$ is the objective function value obtained from a given solution method.

$Y_{\min }$ is the minimum value of the objective function.

$Y_{\max }$ is the maximum value of the objective function.

The $Y_{\min }$ and $Y_{\max }$ are called the extreme parameters. The equations for these parameters are functions of objective function of interest as well as the imposed constraints.

Determination of extreme values

Regular performance measures are functions of completion time. Therefore, the equation for the extreme parameters for completion time will be determine and use for other performance measures.

Given a set of N jobs to be scheduled on a single machine with distinct release dates, randomly generated from $R_{\min }$ to $R_{\max }$.

The minimum values (best case scenario) occur when

1. The first schedule job (i=1) is schedule at minimum $R_{\min }$
2. the waiting time, ($W_i$) of all the jobs is zero. This is possible if $R_{i+1}$= $C_i$

The Gantt chart under this condition is represented in Figure 1.

tu_pian_1.png

Figure 1. The Gantt chart for the best case scenario

$\begin{gathered}C_{t o t}=\sum_i^n C_t=C_1+C_2+C_3+\ldots+C_n \\ C_1=P_1+R_{\min }=\sum_{i=1}^1 P_i+R_{\min } \\ C_2=C_1+P_2=\sum_{i=1}^2 P_i+R_{\min } \\ C_3=C_2+P_3=\sum_i^3 P_i+R_{\min } \\...\\ C_n=C_{n-1}+P_n=\sum_i^n P_i+R_{\min } \\ C_{\text {tot }}^{\min }=\sum_{i=1}^1 P_i+R_{\min }+\sum_{i=1}^2 P_i+R_{\min }+ \\ \sum_i^3 P_i+R_{\min }+\ldots+\sum_i^n P_i+R_{\min } \\ C_{\text {tot }}^{\min }=\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+ n R_{\min }\end{gathered}$             （11)

The maximum values (worst case scenario) occurs when the waiting time, ($w_i$) of the first schedule job is maximum. The Gantt chart under this condition is represented in Figure 2.

tu_pian_2.png

Figure 2. The Gantt chart for the worst case scenario

Therefore,

$\begin{gathered}C_{\text {tot }}=\sum_i^n C_t=C_1+C_2+C_3+\ldots+C_n \\ C_1=P_1+R_{\max }=\sum_i^1 P_i+R_{\max } \\ C_2=C_1+P_2=P_1+R_{\max }+P_2=\sum_i^2 P_i+ \\ R_{\max } \\ C_3=C_2+P_3=\sum_i^2 P_i+R_{\max }+P_3=\sum_i^3 P_i+ R_{\max } \\ ... \\ C_n=C_{n-1}+P_n=\sum_i^{n-1} P_i+R_{\max }+P_n= \sum_i^n P_i+m R_{\max } \\ C_{\text {tot }}^{\max }=\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+ n R_{\max }\end{gathered}$            (12)

The benefit and cost orientation equations can be determined from the extreme values.

Benefit orientation

$\begin{gathered}C_N=\frac{C_{S M}-C_{\min }}{X_{\max }-X_{\min }} \\ X_{\max }-X_{\min }=\left(n R_{\max }+P_1+\sum_i^2 P_i+\right. \left.\sum_i^3 P_i+\ldots+\sum_i^n P_i\right)-\left(P_1+\sum_i^2 P_i+\sum_i^3 P_i+\ldots+\right. \left.\sum_i^n P_i+n R_{\min }\right)=n R_{\max }-n R_{\min } \\ C_N=\frac{C_{S M}-\left(P_1+\sum_i^2 P_i+\sum_i^3 P_i+\ldots+\sum_i^n P_i+R_{\min }\right)}{n R_{\max }} \\ C_N=\frac{C_{S M}-\left(P_1+\sum_i^2 P_i+\sum_i^3 P_i+\ldots+\sum_i^n P_i+n R_{\min }\right)}{n R_{\max }-n R_{\min }}\end{gathered}$            (13)

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\ C_N=\frac{\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_i^3 P_i \ldots \sum_i^n P_i+n R_{\max }-C_{S M}}{n R_{\max }-n R_{\min }}\end{gathered}$          (14)

Makespan (maximum completion time)

The maximum completion time, called the makespan is the completion time of the last job in a system.

$C_{\max }=\max \left(C_1, C_2, \ldots, C_3\right)$             (15)

The minimum values of $C_{\max }$ is possible when all the jobs has zero waiting time and the first scheduled job has the minimum possible value of release date.

The Gantt chart under this condition is represented in Figure 3.

tu_pian_3.png

Figure 3. The Gantt chart for computing minimum $C_{\max }$

Thus, the completion time of the last job is the summation of all the completion time.

$\begin{gathered}C_{\max }^{\min }=\max \left(P_1, \sum_i^2 P_i, \sum_i^3 P_i, \ldots, \sum_i^n P_i+R_{\min }\right) \\ C_{\max }^{\min }=\sum_i^n P_i+R_{\min }\end{gathered}$            (16)

The maximum values (worst case scenario) occurs when the waiting time, ($W_i$) of the first schedule job is maximum. The Gantt chart is represented in Figure 4.

tu_pian_4.png

Figure 4. The Gantt chart for computing maximum $C_{\max }$

Therefore,

$\begin{gathered}C_{\max }^{\max }=\max \left(\mathrm{P}_1+R_{\max }, \sum_i^2 P_i+R_{\max }, \sum_{\mathrm{i}}^3 \mathrm{P}_{\mathrm{i}}+R_{\max },\right.\left.+\ldots \sum_i^n P_i+R_{\max }\right)\end{gathered}$

$C_{\max }^{\max }=\sum_i^n P_i+R_{\max }$ 

Benefit orientation

$\begin{gathered}C_N=\frac{C_{S M}-C_{\min }}{C_{\max }-C X_{\min }} \\ C_{\max }-C_{\min }=\left(R_{\max }+\sum_i^n P_i\right)-\left(\sum_i^n P_i+R_{\min }\right)= C_N=\frac{C_{S M}-\left(\sum_i^n P_i+R_{\min }\right)}{R_{\max }-R_{\min }}\end{gathered}$            (17)

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\ C_N=\frac{\sum_i^n P_i+R_{\max }-C_{S M}}{n R_{\max }-n R_{\min }}\end{gathered}$              (18)

Total flow time

The flow time is the time a job spent in the shop after its availability. It is computed as the differences between the completions time of job i and its release date.

$F_i=C_i-r_i$           (19)

It is also the sum of job processing time and the waiting time.

$F_i=P_i+W_i$           (20)

$F_{\text {tot }}=\sum_i^n F_{t o t}=F_1+F_2+F_3+\ldots+F_n$        (21)

Just like the completion time, the extreme values for flowtime are also computed from the waiting time. The waiting time is computed as:

$W_{i+1}=C_i-r_{i+1}$             (22)

When $C_{i+1}>r_i$,

$W_i$ is called the waiting time of job i.

When $C_{i+1}<r_i$,

$W_i$ is the machine or processor waiting time, called the idle time.

When $C_i=r_{i+1}$,

$W_{i+1}=0$, then $F_{i+1}$ is minimum, thus $F_{i+1}=P_{i+1}$.

Given a set of N jobs to be scheduled on a single machine with distinct release dates, randomly generated from $R_{\min }-R_{\max }$.

The minimum values (best case scenario) occurs when the waiting time, (w_i) of all the jobs is zero. The Gantt chart is represented in Figure 5.

tu_pian_5.png

Figure 5. The Gantt chart for computing minimum $F_{\text {tot }}$

$\begin{gathered}F_{\text {tot }}^{\text {min }}=\sum_i^n F_i^{\text {min }}=F_1^{\text {min }}+F_2^{\text {min }}+F_3^{\text {min }}+\ldots+ F_{\text {tot }}^{\text {min }} \\ F_{\text {tot }}^{\text {min }}=\sum_i^n F_i^{\text {min }}=P_1+P_2+P_3+\ldots+P_n \\ F_{\text {tot }}^{\text {min }}=\sum_i^n P_i\end{gathered}$        (23)

The flow time is maximum, when

1. $W_i$ is maximum.
2. $C_i$ or $C_{i+1}$) is maximum and $r_i$ is minimum.

$\begin{gathered}F_i=C_i-r_i \\ F_i=P_i+W_i \\ F_{\text {tot }}^{\max }=\sum_i^n F_{\text {tot }}^{\max }=\left(C_1-r_1+C_2-r_2+C_3-\right. \left.r_3+\ldots+C_n-r_n\right) \\ F_{\text {tot }}^{\max }=\sum_i^n F_{\text {tot }}^{\max }=\sum_i^n\left(C_{\text {tot }}^{\max }-R_i^{\min }\right) \\ F_{\text {tot }}^{\max }=n R_{\max }+P_1+\sum_i^2 P_i++\sum_i^3 P_i+\ldots+\sum_i^n P_i-n R_{\min }\end{gathered}$         (24)

Benefit orientation

$\begin{gathered}F_N=\frac{X-X_{\min }}{X_{\max }-X_{\min }} \\ X_{\max }-X_{\min }=\left(n R_{\max }+P_1+\sum_i^2 P_i+\cdots\right. \left.\sum_i^3 P_i+\ldots+\sum_i^n P_i-n R_{\min }\right)-\sum_i^n P_i  \left(n R_{\max }+P_1+\sum_i^2 P_i++\sum_i^3 P_i+\ldots+\right.  \left.\sum_i^{n-1} P_i-n R_{\min }\right) \\ F_N=\frac{F_{S M}-\sum_i^n P_i}{P_1+\sum_i^2 P_i++\sum_i^3 P_i+\ldots+\sum_i^{n-1} P_i+n R_{\max }-n R_{\min }}\end{gathered}$                (25)

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\ X_N=\frac{n R_{\max }+P_1+\sum_i^2 P_i+\sum_i^3 P_i+\ldots+\sum_i^n P_i-n R_{\min }-X}{P_1+\sum_i^2 P_i+\sum_i^3 P_i+\ldots+\sum_i^{n-1} P_i+n R_{\max }-n R_{\min }}\end{gathered}$            （26）

Maximum flow time

The maximum flow time is defined as:

$F_{\text {max }}=\max \left(F_1, F_2, F_3, \ldots, F_n\right)$         （27）

From Eq. (23), $F_i=P_i$,

$\begin{aligned} F_{\max }^{\min }= & \max \left(P_1, P_2, P_3, \ldots, P_n\right) \\ & F_{\max }^{\min }=\max \left(P_i\right)\end{aligned}$            （28）

The flow time is maximum when,

1. $W_i$ is maximum.
2. $C_i\left(\right.$ or $\left.C_{i+1}\right)$ is maximum and $r_i$ is minimum.

$F_i=C_i-r_i$

$F_i=P_i+W_i$

$F_{\max }^{\max }=\max \left(C_1-r_1, C_2-r_2, C_3-r_3, \ldots C_n-r_n\right)$

The maximum value of $F_{\max }$ is achieve when the completion time is maximum (makespan) and the release date is minimum.

$F_{\max }^{\max }=C_{\max }-r_{\min }$         （29）

Benefit orientation

$\begin{gathered}N F_{\max }=\frac{X-X_{\min }}{X_{\max }-X_{\min }} \\ N F_{\max }=\frac{F_{S M}-\max \left(P_i\right)}{\left(C_{\max }-R_{\min }\right)-\max \left(P_i\right)}\end{gathered}$             （30）

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\X_N=\frac{\left(C_{\max }-R_{\min }\right)-X}{\left(C_{\max }-R_{\min }\right)-\max \left(P_i\right)}\end{gathered}$            (31)

The total tardiness

This is the sum of tardiness of all the jobs. The tardiness of job i is defined as:

$\begin{gathered}T_i=\max \left\{0,\left(C_i-d_i\right)\right\} \\ \left(T_{t o t}\right): \sum_{i=1}^n T_i=\sum_{i=1}^n \max \left\{0,\left(C_i-d_i\right)\right\}\end{gathered}$

The minimum value of total tardiness s zero,

$T_{t o t}^{\min }=0$          （32）

The due date of job i, can never be 0 or negative, it implies that the total tardiness is maximum when the completion time is maximum.

The maximum value of total tardiness is given by:

$\begin{gathered}T_{\text {tot }}^{\max }=\left(C_{\text {tot }}^{\max }-\sum_{i=1}^n d_i\right)\\ T_{\text {tot }}^{\max }=\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_i^3 P_i \cdots \sum_i^n P_i+ n R_{\max }-\sum_{i=1}^n d\end{gathered}$       (33)

Benefit orientation

$\begin{gathered}T_N=\frac{T_{S M}-T_{\min }}{T_{\max }-T_{\min }}=\frac{T_{S M}}{T_{\max }} \\ T_N=\frac{T_{S M}}{\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_i^3 P_i \ldots \sum_i^n P_i+n R_{\max }-\sum_{i=1}^n d}\end{gathered}$                               （34）

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\ X_N=\frac{\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_i^3 P_i \ldots \sum_i^n P_i+n R_{\max }-\sum_{i=1}^n d-T_{S M}}{\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_i^3 P_i \ldots \sum_i^n P_i+n R_{\max }-\sum_{i=1}^n d}\end{gathered}$                                 （35）

The maximum tardiness

Maximum tardiness ($T_{\max }$) is given by:

$T_{\max }=\max \left(\max \left\{0,\left(C_i-d_i\right)\right\}\right.$          

The minimum possible value of maximum tardiness is zero

$T_{m x n}^{m i x}=0$                  （36）

The maximum value of maximum total tardiness

$T_{\text {tot }}^{\max }=\left(C_{\max }-d_{\min }\right)$

Benefit orientation

$\begin{gathered}N T_{\max }=\frac{T_{S M}-T_{\min }}{T_{\max }-T_{\min }}=\frac{T_{S M}}{C_{\max }-d_{\min }} \\ N T_{\max }=\frac{T_{S M}}{C_{\max }-d_{\min }}\end{gathered}$                  （37）

Cost orientation

$X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }}, X_N=\frac{C_{\max }-d_{\min }-X_{S M}}{C_{\max }-d_{\min }}$           （38）

The total lateness

Lateness is measure as the difference between the completion time and the due date.

The lateness is given by:

$\begin{gathered}\mathrm{L}_{\mathrm{i}}=\left(\mathrm{C}_{\mathrm{i}}-\mathrm{d}_{\mathrm{i}}\right) \\ L_{\text {tot }}=\sum_{i=1}^n L_i=\sum_{i=1}^n\left(\mathrm{C}_{\mathrm{i}}-\mathrm{d}_{\mathrm{i}}\right)\end{gathered}$      

Minimum total lateness

$\begin{gathered}\left(L_{\text {tot }}^{\min }\right)=\sum_{i=1}^n \mathrm{~L}_{\mathrm{i}}=\left(C_{\text {tot }}^{\min }-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}\right) \\ L_{\text {tot }}^{\min }=\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+ n R_{\text {min }}-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}\end{gathered}$               （39）

Maximum total lateness

$\begin{gathered}\left(L_{\text {tot }}^{\max }\right)=\sum_{i=1}^n \mathrm{~L}_{\mathrm{i}}=\left(C_{\text {tot }}^{\max }-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}\right) \\ L_{\text {tot }}^{\max }=\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \cdots \sum_{i=1}^n P_i+ n R_{\max }-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}\end{gathered}$               （40）

Benefit orientation

$\begin{gathered}

L_N=\frac{L_{S M}-L_{\min }}{L_{\max }-L_{\min }}, L_N=\frac{L_{S M}-L_{\min }}{L_{\max }-L_{\min }} \\

L_N= \frac{L_{S M}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\min }-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}}{\left(n R_{\max }-n R_{\min }\right)}

\end{gathered}$ (41)

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X_{S M}}{X_{\max }-X_{\min }} \\ X_N=  \frac{\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\min }-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-X_{S M}}{\left(n R_{\max }-n R_{\min }\right)}\end{gathered}$                    （42）

The maximum lateness

The maximum lateness is given by,

$\mathrm{L}_{\text {max }}=\max \left(\mathrm{C}_{\mathrm{i}}-\mathrm{d}_{\mathrm{i}}\right)$

The $L_{\max }^{\min }=0$             （43）

This occurs when $d_i \geq C_i$ for all i.

The $L_{\max }^{\max }$ occurs when the completion time is maximum and the due date is minimum.

$L_{\max }^{\max }=\left(C_{\max }-d_{\min }\right)$            （44）

Benefit orientation

$N L_{\max }=\frac{L_{S M}-L_{\min }}{L_{\max }-L_{\min }}=\frac{L_{\max }}{\mathrm{C}_{\max }-\mathrm{d}_{\min }}$                     （45）

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X_{S M}}{X_{\max }-X_{\min }} \\ X_N=\frac{C_{\max }-d_{\min }-X_{S M}}{C_{\max }-d_{\min }}\end{gathered}$                    （46）

The total earliness

The job earliness has been expressed in two different ways in the literature; the classical definition and the opposite of lateness definition.

Earliness, defined as the opposite of lateness is express as $E_i=\left(d_i-C_i\right)$.

Total earliness $\left(E_{t o t}\right)=\sum_{i=1}^n E_i=\sum_{i=1}^n\left(d_i-C_i\right)=\left(-L_i\right)$

With this definition, the earliness based performance measure is a maximization problem.

The extreme values

The $E_{\text {tot }}$ is minimum when the completion time is maximum.

Minimum total earliness

$\begin{gathered}\left(E_{\text {tot }}^{\min }\right)=\sum_{i=1}^n E_i=\left(\sum_{i=1}^n d_i-C_{\text {tot }}^{\max }\right) \\ E_{\text {tot }}^{\text {min }}=\sum_{i=1}^n d_i-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+ \sum_{i=1}^3 P_i \cdots \sum_{i=1}^n P_i+n R_{\max }\end{gathered}$               （47）

Maximum total earliness

$\begin{gathered}\left(E_{\text {tot }}^{\max }\right)=\sum_{i=1}^n E_i=\left(\sum_{i=1}^n d_i-C_{\text {tot }}^{\min }\right) \\ E_{\text {tot }}^{\max }=\sum_{i=1}^n d_i-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+ \sum_{i=1}^3 P_i \cdots \sum_{i=1}^n P_i+n R_{\min }\end{gathered}$              （48）

Benefit orientation

$\begin{gathered}N E_{t o t}=\frac{E_{S M}-E_{\min }}{E_{\max }-E_{\min }} \\ N E_{\text {tot }}= \frac{E_{S M}-\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\max }}{n R_{\max }-n R_{\min }}\end{gathered}$                  （49）

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X_{S M}}{X_{\max }-X_{\min }} \\ N E_{\max }= \frac{\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\min }-E_{S M}}{n R_{\max }-n R_{\min }}\end{gathered}$             （50）

Maximum earliness

$\left(\mathrm{E}_{\max }\right)=\max \left(\mathrm{d}_{\mathrm{i}}-\mathrm{C}_{\mathrm{i}}\right)=\max \left(-\mathrm{L}_{\mathrm{i}}\right), E_{\max }^{\min }=0$                      （51）

This occurs when $d_i \leq C_i$.

The $E_{\max }^{\max }$ is when the completion time is minimum and the due date is maximum.

$E_{\max }^{\max }=\left(d_{\max }-C_{\min }\right)$                              （52）

Benefit orientation

$X_N=\frac{X-X_{\min }}{X_{\max }-X_{\min }}, X_N=\frac{X}{d_{\max }-C_{\min }}$                        （53）

Cost orientation

$X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }}=\frac{d_{\max }-C_{\min }-X}{\left(d_{\max }-C_{\min }\right)}$           （54）

Classical definition of earliness

The earliness, $E_i$ of job I is defined as:

$\mathrm{E}_{\mathrm{i}}=\max \{-L i, 0\}$.

Total earliness $\left(\mathrm{E}_{\text {tot }}\right)=\sum_{i=1}^n \mathrm{E}_{\mathrm{i}}=\sum_{i=1}^n \max \left(\mathrm{d}_{\mathrm{i}}-\mathrm{C}_{\mathrm{i}}, 0\right)=\sum_{i=1}^n \max \{-L i, 0\}$.

Minimum total earliness

$\left(E_{\text {tot }}^{\min }\right)=0$                 （55）

Maximum total earliness

$\begin{gathered}\left(E_{\text {tot }}^{\max }\right)=\sum_{i=1}^n \mathrm{E}_{\mathrm{i}}=\left(\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-C_{\text {tot }}^{\min }\right) \\ E_{\text {tot }}^{\text {max }}=\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{\mathrm{i}=1}^2 \mathrm{P}_{\mathrm{i}}+ \sum_{i=1}^3 P_i \quad \cdots \sum_{i=1}^n P_i+n R_{\text {min }}\end{gathered}$               （56）

Benefit orientation

$X_N=\frac{X-X_{\min }}{X_{\max }-X_{\min }}$                （57）

$X_N=\frac{X}{\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\text {min }}}$                        （58）

Cost orientation

$\begin{gathered}X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }} \\ X_N=\frac{\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\min }-X}{\sum_{i=1}^n \mathrm{~d}_{\mathrm{i}}-\sum_{i=1}^1 P_i+\sum_{i=1}^2 P_i+\sum_{i=1}^3 P_i \ldots \sum_{i=1}^n P_i+n R_{\min }}\end{gathered}$             （59）

Maximum earliness

$\mathrm{E}_{\mathrm{i}}=\max \{-L i, 0\}$

For i =1: n

$\begin{gathered}E_{\max }=\max \left\{E_I, E_2, E_3, \ldots, E_n\right\} \\ E_{\max }^{\min }=0\end{gathered}$       (60)

This occurs when $d_i \leq C_i$ for all i.

$E_{\max }^{\min }=0, E_{\max }^{\max }=\left(\mathrm{d}_{\max }-\mathrm{C}_{\min }\right)$                     (61)

Benefit orientation

$X_N=\frac{X-X_{\min }}{X_{\max }-X_{\min }}=\frac{X_{S M}}{d_{\max }-C_{\min }}$                  (62)

Cost orientation

$X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }}=\frac{d_{\max }-C_{\min }-X_{S M}}{d_{\max }-C_{\min }}$              (63)

Baker and Trietsch [21] and Akande and Ajisegiri [22] explored the classical definition of earliness.

The Total Number of Tardy/Late Jobs

The minimum number of tardy/late job is zero while the maximum number is the total number of jobs.

Benefit orientation

$\begin{gathered}X_N=\frac{X-X_{\min }}{X_{\max }-X_{\min }}=\frac{X}{X_{\max }} \\ T_N=\frac{N_{t_{S M}}}{N}\end{gathered}$                       (64)

Cost orientation

$X_N=\frac{X_{\max }-X}{X_{\max }-X_{\min }}=\frac{X}{N}$                      (65)

Table 1 shows the summary of the extreme values equations for the considered performance measures.

Table 1. The extreme values of some performance objectives

Table 2. Normalization expression for some multicriteria problems

4.2 Normalized LCOF

The extreme values and the $X_{S M}$ for each of the criteria in a multicriteria problem will be substituted into the LCOF Eq. (3). The normalized LCOF can be used for effective comparison of different solution.

$N_{L C O F}=\alpha N_X+\beta N_Y+\gamma N_z$                          (66)

where:

$N_{L C O F}$ is the normalized total composite function.

$N_X$ is the normalized value of criterion X.

$N_y$ is the normalized value of criterion Y.

$N_z$ is the normalized value of criterion Z.

Table 2 shows the $N_{L C O F}$ equations for some multicriteria scheduling problems found in the literature.