Discrete Fuzzy Multi-Objective Unrelated Parallel Machine Scheduling Problems: A Framework of Modified Artificial Fish Swarm Algorithm

Constructing a framework for solving UPMSP involves five phases of the research methodology as illustrated in Figure 1.

1) Phase 1: Conduct relevant literature review:

Reviewing previous research and frameworks is an important phase in framework development, including an in-depth review of previously published works and established frameworks relevant to the subject. This phase comprehensively covered the existing literature on the use of deterministic and uncertain models to solve single and multi-objective functions in UPMSPs, followed by many related works of literature that use the AFSA in several machine scheduling problems.

1.png

Figure 1. Phases of the conceptual framework

2) Phase 2: Define problem description and formulation:

An optimization technique has been employed to maximize or minimize a singular objective. A common challenge faced by decision-makers is the need to optimize multiple objectives simultaneously, which results in multi-objective optimization. A solution may be optimal for one objective function but not for another, which makes it often vague to define what an optimal solution is [41]. In recent years, much attention has been focused on multi-objective optimization, with nearly half of the publications, particularly in 2019 and 2020, focusing on multi-objectives [42], which must be used in practice to determine a trade-off between them when making scheduling decisions. This phase aims to adapt and extend the linear multi-objective model proposed by Kongsri and Buddhakulsomsiri [43] for UPMSP by minimizing the makespan and total tardiness. This step will be done by simplifying the mathematical model and reducing sequence dependent setup times constraints with the purpose of making them more flexible and expandable.

3) Phase 3: Apply fuzzification process:

The majority of UPMSP work is conducted using the deterministic optimization methodology, where each parameter is assumed to be well-defined. While this assumption may be correct in some situations, it is often incorrect in practical implementations. There is a widespread assumption among researchers regarding the presence of predictable conditions for characteristics such as task processing times, release dates and due dates. However, in addition to the investigations conducted in a deterministic setting, the various parameters associated with UPMSP are often not well-known, resulting in uncertainties in real-world scenarios. Thus, this phase identifies and describes the fuzzification process of the UPMSP research problem model by embedding TFNs for the main parameters processing times and due dates in the proposed mathematical model to make it more realistic. This helps cover unexpected occurrences that are common in practice, such as errors in the estimation of values parameters, the changing weather and the health of the workforce, machine breakdown and human factors making and improving scheduling efficiency and achieving satisfactory results within the constraints of time, cost, and quality. Jobs' processing times and due dates are considered here along with TFNs to deal with the unpredictable nature of parameters in practical settings. The first fuzzy number indicated processing times $\tilde{p}_{i j}=\left(p_{i j}^1, p_{i j}^2, p_{i j}^3\right)$, where $p^1{ }_{i j}$ is the shortest processing time, $p^2{ }_{i j}$ is the most possible processing time and $p^3{ }_{i j}$ is the longest processing time. To represent job processing times, the following triangular fuzzy membership function is used:

$\mu_{\tilde{p}_{i j}}(x)=\left\{\begin{array}{c}0 \quad \text { for } x<p^1{ }_{i j} \\ \frac{x-p^1{ }_{i j}}{p^2{ }_{i j}-p^1{ }_{i j}} \text { for } p^1{ }_{i j} \leq x \leq p_{i j}^2 \\ \frac{p_{i j}^3-x}{p_{i j}^3-p_{i j}^2} \text { for } p_{i j}^2 \leq x \leq p_{i j}^3 \\ 0 \text { for } x>p_{i j}^3\end{array}\right.$                           (1)

The second fuzzy number indicated the due dates $\tilde{d}_j=\left(d^1{ }_j\right.$, $d^2{ }_j, d^3{ }_j$), where, $d^1{ }_j$ is the earliest due date, $d^2{ }_j$ is the most possible due date and $d^3{ }_j$ is the latest due date. The following triangular fuzzy membership function is used to represent job due dates:

$\mu_{\tilde{d}_j}(x)=\left\{\begin{array}{c}0 \quad \text { for } x<d^1{ }_j \\ \frac{x-d^1{ }_j}{d^2{ }_j-d^1{ }_j} \text { for }{d^1}_j \leq x \leq d^2{ }_j \\ \frac{d^3{ }_j-x}{d^3{ }_j-d^2{ }_j} \text { for } d^2{ }_j \leq x \leq d^3{ }_j \\ 0 \quad \text { for } x>d^3{ }_j\end{array}\right.$                   (2)

The fuzzy environment has an impact on the objective functions because the fuzzy completion time of each job will be a TFNs due to the triangular form of the processing times and is defined as a $\tilde{C}_{i j}=\left(C^1{ }_{i j}, C^2{ }_{i j}, C^3{ }_{i j}\right)$, the tardiness of the job $j$ on machine $i$ equals to the $\tilde{T}_{i j}=\left(T^1{ }_{i j}, T^2{ }_{i j}, T^3{ }_{i j}\right)$ where $\tilde{T}_{i j}=\max \left(\tilde{C}_{i j}-\tilde{d}_j, 0\right)$, where, the zero fuzzy number $=(0,0,0)$. The problem can be mathematically presented as follows:

$\operatorname{MinF}=w \widetilde{C_{\max }}+(1-w) \sum_{j=1}^n \sum_{i=1}^m \widetilde{T}_{i j}$       (3)

$\tilde{\mathrm{C}}_0=0$     (4)

$\tilde{C}_{i j}-\tilde{C}_{i k}+v\left(1-X_{i k j}\right) \geq \tilde{p}_{i k} \\  \forall i \in M, \forall k \in N_0, \forall j \in N: j \neq k$     (5)   

$\widetilde{C_{\max }} \geq \tilde{C}_j \quad \forall j \in N$      (6)

$\tilde{T}_{i j}=\max \left(0, \tilde{C}_{i j}-\tilde{d}_j\right) \quad \forall i \in M, \forall \mathrm{j} \in N$       (7)

$\tilde{P}_{i j}, \quad \tilde{C}_{i j}, \quad \tilde{T}_{i j}, \quad \widetilde{C_{\max }} \geq 0$         (8)

$\mathrm{X}_{i k j} \in\{0,1\}$     (9)

Eq. (3) represents the multi-objective functions to reduce the makespan and total tardiness. Constraint (4) sets the dummy job's completion time to zero. Constraint (5) guarantees the completion time of job k equals the previous job's completion time plus the processing time of job k at each machine. Constraint (6) indicates that the makespan is equivalent to the maximum completion time among all machines, Constraint (7) determines the tardiness value for every job. Constraint (8) indicates that all decision variables must assume non-negative values. Constraint (9) clarifies the binary variables.

4) Phase 4: Develop a modified algorithm:

AFSA, described by Li [44] has been effectively applied to solve several optimization problems. Because of its simple principle and excellent features such as robustness and parameter setting tolerance [36], AFSA has grown in importance in swarm intelligence optimization. It is an iterative algorithm that progressively converges to the optimum global solutions. The basic idea is to mimic different environmental behaviors of schooling fish in the water by displaying social search behaviors and moving to regions with greater food availability, where a fish represents a point or fictitious entity of a true fish in a population and swarm movements occur at random [45].

In AFSA, all artificial fish (AF) are trained to react to real-time situations. Each AF learns how to execute four types of basic behaviors: prey, swarm, follow, and random. Figure 2 shows the flowchart of the standard AFSA algorithm.

• Prey behavior is the basis for the algorithm’s convergence,

• Swarm behavior enhances the algorithm's global convergence and stability,

• Follow behavior accelerates the algorithm's convergence,

• Random behavior balances out the conflict between the other three behaviors.

2.png

Figure 2. Flowchart of standard AFSA

3.png

Figure 3. Framework for a proposed modified algorithm

AF behaves in response to current conditions and environmental conditions, and it has an impact on the environment through its own and other AF's activities. Each AF receives two input parameters: visual (perception) and step (moving step length). AFs will collect information and then move using visual and step guidance. AFs' behaviors tend to affect each other's fitness as well.

We propose employing a three-stage framework that effectively modifies the AFSA algorithm. The proposed modified algorithm allows for increasing the effectiveness of traditional AFSA behaviors to make it suitable to the proposed problem. As illustrated in Figure 3, the framework can be divided into three stages: adding new behavior, adopting improved parameters, and using the transformation method. Each stage includes distinct activities as outlined below:

• Add a new behavior

Creating aspiration behavior depends on the best solution reached by AFs of all AFSA behaviors and adopted its position to compare with the current position in order to enhance the search process and help AFs to escape from the local optimums.

The update processes are formulated as: Suppose that $X_{\text {best }}$ represents the potential position of AF in the step range and $\left\|X_{\text {best }}-X_i\right\| \leq$ Step$_2$, which can be stated as:

$X_{\text {Aspiration }}=X_i+\frac{X_{\text {best }}-X_i}{\left\|X_{\text {best }}-X_i\right\|} \times$ Step$_2 \times R(0,1)$         (10)

The aspiration behavior guarantees that the computing time is greatly reduced because AF can determine the best position in just one cycle of calculations. The following illustrates the pseudocode of the proposed aspiration behavior.

Pseudocode of the Aspiration behavior

• Adopted improved parameters

The visual and step parameters in the standard AFSA are fixed through iterative processes. Large visual and step values at the beginning of the algorithm speed up its convergence. However, the large values will result in problems like local optimum or iterative jumps when AFs approach the final position. However, if the values are too low, the effectiveness decreases [46]. As a result, the algorithm has specific requirements about the visual and step at different stages. Therefore, to achieve a balance between convergence rate and global search capability, the algorithm has adopted improved parameters as described in Tan and Mohamad-Saleh [40], and can presented as follows:

visual $^{t+1}=$ visual $^t-$ visual $^t \times \lambda+$ visual $_{\text {min }}$       (11)

step $^{t+1}=$ step $^t-$ step $^t \times \lambda+$ step $_{\min }$     (12)

$\lambda=e^{-\frac{\sigma}{\sqrt[4]{\left(_{\max }\right)^3}} *\left(t_{\text {max }}-t\right)}$      (13)

where, visual$_{\text {min }}$ is the minimum visual value; $\operatorname{step}_{\min }$ is the minimum step value; t=(1, 2, …, $t_{\max }$) is the index number of iterations; $0.5<\sigma<1$ at any stage. Therefore, it improves the algorithm's local search at a later stage.

• Using transformation method

AFSA was initially developed as a continuous algorithm for solving continuous problems, making it challenging to deal with combinatorial optimization problems like UPMSP that have a discrete solution space. Hence, in the optimization algorithm, the process of solution encoding is critical. It is essential to enable the AFSA algorithm to solve discrete UPMSPs and enhance the search capabilities of the original algorithm. The major stage of the proposed algorithm is the use of the transformation method to transform the continuous search space of AFSA into a discrete search space to make it appropriate for discrete optimization problems such as UPMSP. The following illustrates the pseudocode for the transformation method.

Pseudocode of the transformation method

This code uses a trans function to transform the input vector q, which represents the continuous solution, into the output vector a, representing the discrete solution. It starts by:

Step 1: Determine the length of q to find the number of elements in q and store it in n.

Step 2: Initialize s with a random value generated from a uniform distribution in the range [0.1, 0.2]. This value will serve as the starting point for the assignment process.

Step 3: Loop through each element of q. For every element in q, perform the following steps inside the loop:

1. a(q(i))=s;: The current value of s would be assigned to the position in a for which q(i) is specified. This step maps the continuous solution to a discrete position.
2. s=s+random('uniform', 0.1, 0.2, 1, 1);: A new random number from the same uniform distribution is added to update s. By doing this, the solution's randomness is maintained, and every next assignment in a is based on a new random value.

Step 4: Normalize the vector a to ensure its Euclidean norm (length) equals one. This step checks that the final discrete solution is appropriately scaled.

This method is used to compute the best solution in the population according to the value of multi objective function. Subsequently, the pseudocode of the proposed modified AFSA algorithm is presented as below, while Figure 4 represents the flowchart. The yellow color represents the modification steps that have been made in the proposed modified version of AFSA.

Pseudocode of the proposed modified AFSA algorithm:

4.png

Figure 4. Flowchart of the proposed modified AFSA algorithm