Numerical solutions for nonlinear Volterra-Fredholm integral equations of the second kind with a phase lag

Gamal A. Mosa; Mohamed A. Abdou; Ahmed S. Rahby; Gamal A. Mosa; Mohamed A. Abdou; Ahmed S. Rahby

doi:10.3934/math.2021495

AIMS Mathematics

2021, Volume 6, Issue 8: 8525-8543. doi: 10.3934/math.2021495

Previous Article Next Article

Research article

Numerical solutions for nonlinear Volterra-Fredholm integral equations of the second kind with a phase lag

1.
Department of Mathematics, Faculty of Science, Benha University, Egypt
2.
Department of Mathematics, Faculty of Education, Alexandria University, Egypt
Correction on: AIMS Mathematics 7: 258-259

Received: 31 December 2020 Accepted: 17 May 2021 Published: 04 June 2021
MSC : 45G10, 46B07, 65R20

This study is focused on the numerical solutions of the nonlinear Volterra-Fredholm integral equations (NV-FIEs) of the second kind, which have several applications in physical mathematics and contact problems. Herein, we develop a new technique that combines the modified Adomian decomposition method and the quadrature (trapezoidal and Weddle) rules that used when the definite integral could be extremely difficult, for approximating the solutions of the NV-FIEs of second kind with a phase lag. Foremost, Picard's method and Banach's fixed point theorem are implemented to discuss the existence and uniqueness of the solution. Furthermore, numerical examples are presented to highlight the proposed method's effectiveness, wherein the results are displayed in group of tables and figures to illustrate the applicability of the theoretical results.

Keywords:

Citation: Gamal A. Mosa, Mohamed A. Abdou, Ahmed S. Rahby. Numerical solutions for nonlinear Volterra-Fredholm integral equations of the second kind with a phase lag[J]. AIMS Mathematics, 2021, 6(8): 8525-8543. doi: 10.3934/math.2021495

Related Papers:

[1]	Hong Li, Keyu Zhang, Hongyan Xu . Solutions for systems of complex Fermat type partial differential-difference equations with two complex variables. AIMS Mathematics, 2021, 6(11): 11796-11814. doi: 10.3934/math.2021685
[2]	Wenjie Hao, Qingcai Zhang . The growth of entire solutions of certain nonlinear differential-difference equations. AIMS Mathematics, 2022, 7(9): 15904-15916. doi: 10.3934/math.2022870
[3]	Fengrong Zhang, Linlin Wu, Jing Yang, Weiran Lü . On entire solutions of certain type of nonlinear differential equations. AIMS Mathematics, 2020, 5(6): 6124-6134. doi: 10.3934/math.2020393
[4]	Yeyang Jiang, Zhihua Liao, Di Qiu . The existence of entire solutions of some systems of the Fermat type differential-difference equations. AIMS Mathematics, 2022, 7(10): 17685-17698. doi: 10.3934/math.2022974
[5]	Zheng Wang, Zhi Gang Huang . On transcendental directions of entire solutions of linear differential equations. AIMS Mathematics, 2022, 7(1): 276-287. doi: 10.3934/math.2022018
[6]	Yong Liu, Chaofeng Gao, Shuai Jiang . On meromorphic solutions of certain differential-difference equations. AIMS Mathematics, 2021, 6(9): 10343-10354. doi: 10.3934/math.2021599
[7]	Jingjing Li, Zhigang Huang . Radial distributions of Julia sets of difference operators of entire solutions of complex differential equations. AIMS Mathematics, 2022, 7(4): 5133-5145. doi: 10.3934/math.2022286
[8]	Minghui Zhang, Jianbin Xiao, Mingliang Fang . Entire solutions for several Fermat type differential difference equations. AIMS Mathematics, 2022, 7(7): 11597-11613. doi: 10.3934/math.2022646
[9]	Wenju Tang, Keyu Zhang, Hongyan Xu . Results on the solutions of several second order mixed type partial differential difference equations. AIMS Mathematics, 2022, 7(2): 1907-1924. doi: 10.3934/math.2022110
[10]	Zhenguang Gao, Lingyun Gao, Manli Liu . Entire solutions of two certain types of quadratic trinomial q-difference differential equations. AIMS Mathematics, 2023, 8(11): 27659-27669. doi: 10.3934/math.20231415

Abstract

1. Introduction

The MS-RCPSP ^[1,2,3,4,5] is a complex scheduling problem widely studied in operations research and project management. It is a type of project scheduling problem that considers the order in which tasks should be performed and the resources required to perform each task, such as labor, equipment and materials. In the MS-RCPSP, resources are considered limited, finite and reused, meaning there are restrictions on the number of renewable resources available at any given time. The goal of solving the MS-RCPSP is to minimize the project's completion time, cost or both (multi-objective) while ensuring that all resource constraints are satisfied. It is a widely studied problem with numerous real-world applications, including construction, software development and manufacturing.

The MS-RCPSP problem has an important constraint: a resource can only perform the task if it possesses the right skill type and the skill level is greater than or equal to the required skill level. This constraint accurately describes reality. Moreover, resources have many skill types and skill levels, so it is necessary to plan for allocating resources to perform practical tasks to improve the efficiency of project implementation. MS-RCPSP is a problem of class NP-Hard, so the optimal solution cannot be found in polynomial time. However, metaheuristic methods can solve the problem to find approximate solutions in less time. In order to find a suitable solution for the MS-RCPSP problem, this paper proposes the MEMINV algorithm developed from the Memetic algorithm ^[6,7,8] integrated with the Inversion method. The solution to the MS-RCPSP problem when applying MEMINV is a schedule that allocates resources to perform project tasks.

The major contributions of this paper involve the following:

● Proposing the Inversion method to detect the local extreme of populations in the evolutionary process over the generations. The local extreme detection is based on examining the number of successive evolutionary generations of a population without changing the total project time.

● Proposing the Adaptive Localserach method to dynamically change the parameters during the algorithm's evolution, including mutation coefficient, crossover coefficient and the number of neighboring individuals used to perform the search.

● Proposing hybrid algorithm MEMINV based on combining the Memetic algorithm and the Inversion method to improve problem-solving efficiency.

● Conduct experiments on the iMOPSE^[4,5] dataset to verify the proposed algorithm.

The remainder of this paper is organized as follows: Part 2 provides an overview of related works in the RCPSP and MS-RCPSP problems and studies existing research on evolutionary methods employed to address these problems. Additionally, this section introduces the Memetic algorithm, known for its effectiveness in solving NP-Hard class problems. Section 3 describes the mathematical formulation of the problem, including the mathematical constraints and their implications. Part 4 presents the MEMINV algorithm, a hybrid approach combining the Memetic algorithm with the Inversion method, aimed at enhancing solution efficiency.

2. Background and Literature review

The MS-RCPSP ^{[2,3,4,5,9,10,11]} is a sub-classification of the Resource-Constrained Project Scheduling Problem (RCPSP), which has been proven to be an NP-Hard class, meaning that their solutions cannot be found in polynomial time. Therefore, it is common to use approximate, evolutionary algorithms to find an acceptable solution quickly.

2.1. Approximate methods to solve the Resource-Constrained Project Scheduling Problem

Numerous scientists have extensively researched and published various methods to discover practical solutions for RCPSP and MS-RCPSP problems. These solutions are primarily based on evolutionary computation algorithms, including Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Differential Evolution (DE) and Cuckoo Search (CS). Table 1 summarizes some outstanding works to solve those problems.

Table 1. Summary of early works.

No.	Based on Algorithm	Problem	References
1	GA	RCPSP	13,14,15,16
2		NPV-RCPSP	12
3		MS-RCPSP	17,18,19,20
4	PSO	RCPSP	21,23
5	PSO	MS-RCPSP	2,22
6	DE	RCPSP	24,25
7	DE	MS-RCPSP	26
8	CS	MS-RCPSP	31,32

| Show Table

DownLoad: CSV

Many authors widely use the GA algorithm to solve the RCPSP family of problems.

In ^[12], the authors use the GA integrated with the Immune to solve the NPV-Based RCPSP problem. The algorithm is also applied with two additional variables to improve efficiency: local search and forward-backward improvement. Mateja Đumíc et al. ^[13] using GA combined with many different methods to determine the feasible schedule of RCPSP. In ^[14], O. Shuvo et al. consider RCPSP by integrating chemical reaction optimization and genetic algorithm (CRO-GA), and the authors have redesigned the basic operators of CRO and GA and the priority-based selection operator to find out the schedules. The authors ^[15] introduce the quantum-inspired genetic algorithm (QIGA), which is an adjusted GA algorithm to solve the RCPSP problem. In this algorithm, the authors improve the initialization and update stages population using quantum gates and superposition. In paper ^[16], the authors employ a combination of GA (Genetic Algorithm) and a two-point crossover operator to tackle the resource-constrained project scheduling problem with transfer times (RCPSPTT).

The GA algorithm is used to solve the MS-RCPSP. In ^[17], the authors proposed the genetic programming hyper-heuristic (GP-HH) algorithm, which has many improvements to improve solution quality, including repair-based decoding of a solution, using ten simple heuristic rules designed to construct a set of low-level heuristics, using GA with a high-level strategy and the design-of-experiment (DOE) method is employed to investigate the effect of parameters setting. The performance of GP-HH is evaluated on the iMOPSE dataset. The authors ^[18] use the breadth and depth methods hybrid with the GA algorithm. In ^[19], the authors proposed the MOGP-HH/D algorithm to find out the multi-objective of MS-RCPSP, which uses many technicals, including NSGA-Ⅱ algorithm, local search... design-of-experiment (DOE) by Taguchi method. In their study ^[20], the authors used several methods to obtain a multi-objective solution for the problem. The first utilized a priority rule for population initialization, followed by applying the NSGA-Ⅱ algorithm to facilitate the search process. Finally, they integrated a local search into the search process to enhance the quality of the results

Particle Swarm Optimization (PSO) is another commonly used metaheuristic for solving scheduling problems. The authors of the paper ^[21] proposed an algorithm that is improved from PSO to solve RCSPS. The new algorithm uses the "Valid Particle Generator" technique to detect feasible solutions and, at the same time, applies more adaptive methods to improve the quality of the solutions. In ^[2], the authors proposed a novel M-PSO algorithm to solve MS-RCPSP. The M-PSO is a hybrid between the PSO algorithm and the Migration method that supports the population escapes from local extrema. D. Q. Huu et al. ^[22] combined PSO with the re-assignment technical to recalculate the resource assigned to execute the task after each generation. The proposed algorithms are conducted with the iMOPSE dataset. In ^[23], the authors used PSO for the resource-constrained project scheduling problem with varying resource levels (RCPSPVRL), an RCPSP extension. In the RCPSPVRL, the total project duration is divided into many periods, each requiring a different quantity of resources.

Additionally, the DE algorithm discovers extensive applications among various research groups for solving scheduling problems. In ^[24], the authors proposed a two-stage multi-operator differential evolution (DE) algorithm to solve RCPSP. The algorithm processes each generation through two stages, including the exploration stage, and based on the diversity of the population and the quality of solutions, this approach dynamically places more importance on the most-suitable DE and then repeats the same process during the exploitation phase. In ^[25], improving DE (IDE) with the mutation technique is used to speed up the algorithm's convergence speed. The author evaluates the new algorithm and compares it with other algorithms, such as HGA and PSO, to demonstrate its effectiveness. The authors ^[26] consider a multi-objective MS-RCPSP problem with priority constraints to find the minimum deviation from the expected time to complete each project and allocate resources. The schedule alternative is found based on the improved DE algorithm.

Researchers have also proposed and developed some variations of the MS-RCPSP problem. In ^[27], the author extended MS-RCPSP to resource scheduling and cooperative multi-robot system problem task allocation. for SAR (RSTA-RSSAR). In RSTA-RSSAR, the skills of multi-robot systems are considered from both depth and breadth. In it, the processing time of activities in RSTA-RSSAR changes with skill ability resources provided. In order to solve the problem effectively, a genetic differential evolution algorithm (PS-GDEA) is proposed. Another variant is Real-RCPSP ^[28], which extends from MS-RCPSP by adding a constraint on task execution time that varies according to resource ability usage instead of a fixed duration. The authors also proposed an algorithm to solve the Real-RCPSP problem based on the Adaptive method combined with the DE algorithm called A-DEM.

Furthermore, numerous research groups have embraced the utilization of the CS algorithm as a valuable tool for addressing scheduling problems effectively. The authors use the Cuckoo Search (CS) ^[29,30] algorithm to solve the scheduling problem. The CS uses Lévy Flight random walk to evolve the population, using two search techniques: Local Search and Global Search. Authors of ^[31,32] use this metaheuristic to solve the MS-RCPSP.

Moreover, many other researchers have also proposed state-of-the-art algorithms that offer practical solutions for finding feasible schedules for the MS-RCPSP problem. The authors ^[33] recommend the multi-objective evolution strategy (MOES) framework to discover multi-objective solutions by focusing on generating and using mutation operators for good scheduling. In ^[34], the authors proposed a discrete oppositional multi-verse optimization (DOMVO) algorithm with many processing steps to get high effective such as using the black/white holes technique combined with the path relinking technique, the opposition-based learning (OBL), a repair-based decoding scheme, and the design-of-experiment (DOE) method.

Usually, to experiment with the proposed algorithms, the authors often use two primary datasets, PSLIB ^[35] and iMOPSE ^[4,5], which was suggested by P. B. Myszkowski.

2.2. Memetic algorithm

Memetic algorithms (MAs) ^[6,7,8] are optimization algorithms that incorporate both evolutionary and local search procedures to solve complex optimization problems. MAs have gained increasing popularity in recent years due to their ability to overcome the limitations of traditional evolutionary algorithms (EAs) by incorporating problem-specific knowledge to guide the search process.

In a memetic algorithm, individuals in the population are encoded as solutions to the optimization problem and evolve through selection, crossover (recombination) and mutation. The genetic algorithm generates new candidate solutions, while the local search method is used to refine the solutions generated by the genetic algorithm.

Using local search methods in memetic algorithms can lead to faster convergence and improved solution quality compared to traditional genetic algorithms. This is because local search methods can exploit the structure of the problem space to find better solutions quickly. Moreover, the genetic algorithm provides a mechanism for exploring the search space and avoids getting trapped in local optima.

The Memetic algorithm performs the following steps:

● Step 1. Initialization: Generate an initial population of candidate solutions, each represented as a chromosome.

● Step 2. Fitness evaluation: Evaluate the fitness of each chromosome in the population using a fitness function.

● Step 3. Selection: Select pre-chromosomes for reproduction based on their fitness values.

● Step 4. Crossover: Combine the selected pre-chromosomes to create offspring chromosomes through crossover (recombination) operation.

● Step 5. Mutation: Introduce random variations into the offspring chromosomes through mutation operation.

● Step 6. Local search: To improve their solutions, perform a local search on some of the offspring chromosomes.

● Step 7. Acceptance: Accept the offspring as the new population if they are better than the current population, otherwise keep the current population.

● Step 8. Termination: Terminate the algorithm if a satisfactory solution is found or a stopping criterion is met.

● Repeat steps 2 to 8 to create the next generation of solutions.

However, there are also some disadvantages to using MAs. One of the main drawbacks is that MAs can be computationally expensive, as they require both global and local search procedures. Another challenge is designing effective, problem-specific and efficient local search procedures can be complex. Furthermore, MAs can also suffer from premature convergence, where the algorithm becomes stuck in a local optimum and cannot escape finding the global optimum.

3. MS-RCPSP problem model

The MS-RCPSP has a wide range of real-world applications, such as in project management, scheduling of manufacturing processes and resource allocation in large-scale engineering projects. The ability to effectively solve the MS-RCPSP has significant implications for the efficiency and success of these real-world applications.

To solve the MS-RCPSP, advanced optimization techniques are required to find the optimal schedule. Solving the MS-RCPSP is to minimize the makespan, or the total time required to complete the project while ensuring that all resource constraints are satisfied. The solution must also consider any dependencies between tasks, meaning that predecessor tasks must be completed before others begin.

3.1. Resource-Constrained Project Scheduling Problem (RCPSP) and MS-RCPSP

RCPSP (Resource-Constrained Project Scheduling Problem) ^{[1,9,10,11,12]} is a problem of finding a schedule to complete project tasks with limited renewable resources (usually smaller than the number of tasks). The RCPSP problem is to find the best schedule to perform the project tasks under resource constraints, and the tasks have a fixed order of execution. The objective function of the RCPSP problem is evaluated based on the execution time (makespan), the cost of implementation (cost) or a combination of both (multi-objective).

In RCPSP, multiple tasks are performed, and each task is described by start and end times with some significant constraints as follows:

● When a task starts, it cannot be stopped until it is finished.

● Tasks are related to each other in order of execution. That is, the predecessors' task needs to be completed before the start of the successor's task.

● Resources are finite and can be reused for other tasks. The number of resources allocated should not exceed the amount available. Although a task can use multiple resources, a resource can be used for only one task concurrently.

Multi-Skill (MS) RCPSP problem ^[2,3,4,5] is extended from the RCPSP. The MS-RCPSP added a new constraint to the resources: each resource has many skills and a certain level. Therefore, each task will require a specific skill type and skill level resource. The MS-RCPSP is a widely studied problem with numerous real-world applications, including construction, software development and manufacturing.

Example 1: A project with 10 tasks and 3 renewable resources.

● Tasks that require resources with the skill level required to perform are shown in Table 2.

Table 2. The task requirement.

Task	W₁	W₂	W₃	W₄	W₅	W₆	W₇	W₈	W₉	W₁₀
Required skill of the resource	S_2.1	S_1.2	S_1.3	S_3.1	S_2.2	S_1.3	S_2.2	S_3.2	S_3.1	S_1.2

| Show Table

DownLoad: CSV

● Resources with complementary skills and skill levels are shown in Table 3.

Table 3. The skills of resources.

Resource	L₁	L₂	L₃	L₄
Skills	S_1.3	S_1.2	S_1.3	S_2.2
Skills	S_2.1	S_3.2	S_3.1	S_3.1

| Show Table

DownLoad: CSV

The notations:

● W_i: Task i, L_j: Resource j

● S_i.j represents a skill type i with a skill level of j.

Based on the resource requirements for execution and the capacity of the given resources, we can build a matrix describing the resource's ability to perform the task, as shown in Figure 1 below.

Figure 1. Resource's ability to perform the tasks.

DownLoad: Full-Size Img PowerPoint

3.2. Problem definitions

The MS-RCPSP problem can be conceptually formulated based on the notations in Table 4.

Table 4. The notations.

Symbol	Description
C_i	The set of tasks need to be completed before task i can be executed
S	The set of all resource's skills Sⁱ: the subset of skills owned by the resource i, Sⁱ ⊆ S;
S_i	The skill i;
t_j	The duration of task j
L	The resources used to execute tasks of the project
L^k	The subset of the resources which can be performed task k; L^k ⊆ L
L_i	The resource i
W	The tasks of the project need to do
W^k	The subset of task which can be executed by the resource k, W^k ⊆ W
W_i	The task i
rⁱ	The subset of the skill required by task i. A resource has the same skill and skill level equal to or greater than the requirement that can be performed.
B_k, E_k	The begin time and end time of the task k
A_{u, v}^t	The variable to identify the resource v is running task u at time t; 1: yes, 0: no;
h_i	The skill level i;
g_i	Type of skill i;
m	Makespan of the schedule
P	The feasible solution
P_all	The set of all solution
f(P):	The function to calculate the makespan of P solution
n	Task number
z	Resource number

| Show Table

DownLoad: CSV

The MS-RCPSP problem could be state as follow:

$f(P) → min$

(1)

Where:

$f\left(P\right) = \underset{{W}_{i}\in W}{\mathit{max}}\left\{{E}_{i}\right\}-\underset{{W}_{k}\in W}{\mathit{min}}\left\{{B}_{k}\right\}$

(2)

Subject to the following constraints:

$● \;\;\;\; S^k \neq \varnothing \quad \forall L_k \in L$

(3)

$● \;\;\;\; t_{j k} \geq 0 \quad \forall W_j \in W, \quad \forall L_k \in L$

(4)

$● \;\;\;\; E_j \geq 0 \quad \forall W_j \in W$

(5)

$● \;\;\;\; E_i \leq E_j-t_j \quad \forall W_j \in W, j \neq 1, W_i \in C_j$

(6)

$● \;\;\;\; {\forall {\mathrm{W}}_{i}\in {W}^{k}\;\exists {S}_{q}\in {S}^{k}:{g}_{{S}_{q}} = {g}_{{r}_{i}}\;\mathrm{a}\mathrm{n}\mathrm{d}\;h}_{{S}_{q}}\ge {h}_{{r}_{i}}$

(7)

$● \;\;\;\; \forall {L}_{k}\in L, \mathrm{ }\forall q\in m:\sum _{i = 1}^{n}{A}_{i, k}^{q}\le 1$

(8)

$● \;\;\;\; \forall {W}_{j}\in W\;\exists !q\in \left[0, m\right], !{L}_{k}\in L:{A}_{j, k}^{q} = 1;\;\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\;{A}_{j, k}^{q}\in \left\{0;1\right\}$

(9)

The above constraints have the following meanings:

● Constraint (3) guarantees that each resource has at least one skill

● Constraints (4, 5) say that the execution time of any task must be at least 0 (in fact, every real task, with a minimum execution time, is always greater than 0, the case is zero to illustrate two dummy tasks representing the start and end of the project)

● Constraint (6) implies that the predecessor task (task i) must end before the successor task (task j) starts. The time when task i ends is denoted E_i, and the time when successor task j starts is E_j - t_j (finish time minus execution time).

● Constraint (7) ensures that for every task i ∈ W_k (set of tasks that resource k can perform), there is always a skill S ∈ S_k (skill set of resource k) such that g_S = g_Si : r's skill type coincides with L_i's skill type that task i requires. h_Sq ≥ h_rⁱ : the skill level of the performing resource is higher or equal to the required skill level.

● Constraint (8) states that at each time (q), each resource can only perform at most one task. If $\sum _{i = 1}^{n}{A}_{i, k}^{q} = 0$ , then resource k is not assigned to any task. If $\sum _{i = 1}^{n}{A}_{i, k}^{q} =$ 1, then resource k is assigned to a single task.

● Constraint (9) ensures that each task is assigned to only one renewable resource and performed by only one resource.

In the MS-RCPSP problem, each task has additional skill requirements of the renewable resource needed to perform. Each resource is also divided into different skill types and skill levels. Figure 1 depicts an example of the resource skill constraints required to complete a task.

4. Proposed algorithm

This section describes the proposed evolutionary algorithm for the MS-RCPSP problem named MEMINV, a variation of the Memetic algorithm ^[6,7,8] enhanced with the Inversion method.

4.1. Individual presentation

In the MS-RCPSP problem, the population is calculated and evolved over several generations to improve the makespan of the project. Representing each individual in the population is a vector whose elements correspond to the total number of project tasks. The value at each vector element denotes the resource index assigned to perform the corresponding task.

Considering the project in example 1, an individual can be represented as a vector as shown in Figure 2 below.

Figure 2. Individual vector.

DownLoad: Full-Size Img PowerPoint

4.2. Adaptive Local Search method

The goal of the adaptive method is to adjust the crossover parameter µCR through each generation to increase the algorithm's efficiency. The adjustment depends on the results of the evolutionary performance of the population. The specific steps are as follows:

● The crossover parameter of the ith individual, denoted CR_i, is calculated by the Cauchy random function of the crossover parameter CR. The CR is calculated based on the number of successful evolution individuals.

● When implementing the MEMINV algorithm, instead of using a fixed number of neighboring individuals at the local search step, the algorithm dynamically calculates and changes the number of neighboring individuals based on the number of individuals that successfully evolve.

● Suppose the population has ten individuals, with the project duration given in Figure 3. It is necessary to find three neighboring individuals with P₅, the algorithm runs through the following steps:

Figure 3. The population to find neighbors.

DownLoad: Full-Size Img PowerPoint

o Step 1: Sort the population in ascending order of the project execution time of each individual (calculated using the objective function); the result is shown in Figure 4.

Figure 4. Finding the neighboring individuals by distance from d₅.

DownLoad: Full-Size Img PowerPoint

o Step 2: Considering the sorted list of Pall to calculate the distance with the P₅ individual, it gets d₅ = 13.

o Step 3: Considering P_all to get three individuals adjacent to P₅. Neighboring individuals obtained include P_S⁵ = {P₂, P₄, P₆}.

The Adaptive local search is shown in the algorithm 1.

Algorithm 1. AdaptiveLocalSearch Input: P_all: the population current: the current individual to find the neighbors µCR: crossover probability (global variable) Output: P_bestⁱ: the best individual gets from the neighboring individuals
Begin 1. P_R = {}; w_min = 3; w_max = 10; 2. fitness ← f(P_all) 3. i = index(current) // the index of current individual in P_all 4. mp = fitness(i) 5. N = sizeOf(P_all) 6. P_all^sort ← sort(P_all, fitness) // sort population by fitness 7. D_i = findDistance(i) 8. For j=1 to N 9. If abs(fitness(j) – mp) ≤ D_i 10. P_S= P_S + {P_j} 11. End if 12. If (sizeOf(P_S) > w) break; 13. End for 14. P_bestⁱ = fbest(P_S) 15. If (P_bestⁱ!= localbest) S_CR = S_CR + {µCR} CR_i = randci (µCR, 0.1) c = rand(0, 1) µCR = (1 - c) × µCR + c × mean(S_CR) //Adaptive factor w = w_max – i/N × (w_max – w_min) 20. Return P_bestⁱ End Function
where: findDistance: function to find the maximum distance from position i (index of the curent individual) to others to be able to get enough number of individuals neighboring of P_i.

| Show Table

DownLoad: CSV

4.3. Catching the local extreme

The traditional memetic algorithm operates by evolving a population over several generations through several steps, including selection, crossover, mutation, local search and recombination to create a new population. However, while evolving, the algorithms may fall into the local extreme and iterate infinitely without leaving, so finding a better result is impossible. Therefore, the Inversion technique moves the population to another solution space far from the local extreme. Integrating the Inversion technique into the memetic algorithm leads to improved results.

In this step, the algorithm uses a marked variable c_fail to count the times the makespan is not changed over generations; if c_fail was more significant than a specified threshold (c_max), then the population has fallen into the local extreme. Equation (10) represents the calculation of c_fail.

${c}_{fail} = \left\{\begin{array}{c}{c}_{fail}+1\;if\;ne{w}_{makespan} = {old}_{makespan}\\ 0\;if\;ne{w}_{makespan}\ne {old}_{makespan}\end{array}\right.$

(10)

4.4. Inversion method

Throughout the algorithm's evolution, upon detection of a local extreme, the Inversion method is invoked to facilitate the population's elimination of the local extreme. This is achieved through the following steps:

Step 1: Repeating with each individual

Step 2: Considering each task i of the individual, get out the Lⁱ of resources to execute the current task, reordering the resources index in Lⁱ.

Step 3: Replacing the current resource with the resource which mirrors in Lⁱ. The formula (11) shows this action.

$L^i = \left\{L_1, L_2, \ldots, L_m\right\}, m \leqslant n \\ \forall {W}_{i}\in W, j\in \left[1, m\right]:{L}_{j}\leftarrow {L}_{m-j}$

(11)

Figure 5 presents the Inversion technical by replacing the execution resource. Primarily, the task being performed by resource L₂ will be changed to L_m-1, and resource L_m does the task will be allocated to L₁.

Figure 5. Replace the resource that performs the task.

DownLoad: Full-Size Img PowerPoint

After applying the Inversion method, the population will be moved to a new location, allowing the algorithm MEMINV to escape the local extreme, continue the evolutionary computation and expand the solution space.

The Inversion method is present in Algorithm 2 below.

Algorithm 2. Inversion

  Input: P_all – the population needs to move
  Output:P_new – the result population
Begin
1. {
2. P_new = {}
3. i = 1
4. p_size = size(P)
5. while(i < p_size) {
6.  P_i ← P_all[i];
7.  j_task = 1
8.  n_task = size(P_i)
9.  for { j_task = 1; j_task < n_task; j_task++)
10.  {
11.    Lⁱ ← the resources matching with L(j_task) requirement
12.    Lⁱ ← Reorder(Lⁱ)
13.    i_current ← current resource index to run task i
14.    i_current = size(Lⁱ) – idx + 1
15.    L_{j_task} = Lⁱ[i_current]
16.  } // j_task
17.  P_new = P_new + {P_i}
18. }
19. Return P_new
20. }

| Show Table

DownLoad: CSV

4.5. MEMINV algorithm

The MEMINV algorithm is a hybrid algorithm from the memetic algorithm and the Inversion method. The steps of the algorithm are detailed in Figure 6.

Figure 6. The MEMINV algorithm diagram.

DownLoad: Full-Size Img PowerPoint

In the Figure 6, ALC is Active Local Search method used to dynamically find the individual in the algorithm's evolution. The improvement of MEMINV is demonstrated in the ALC and "Inversion steps", with the ALC, the algorithm will conduct an individual based on dynamically changing the number of neighboring and the crossover coefficient in the evolutionary process to get the local best and "Inversion steps" will check for local extrema within the population and redirects it to another region if it has fallen into one. This step is executed by applying the Inversion method.

The MEMINV algorithm is present in Algorithm 3.

Algorithm 3. MEMINV
Input: dataset, g_max: number of generation,
  S_CR: global variable, set of crossover coefficients of successful evolution individuals
  µCR: Crossover Probability (global variable)
  µMP: Mutation Probability (global variable)
  w: number of neighbors for local search (global variable)
Output: best individual and makespan

1. Begin
2. {
3.  {Read dataset}.
4.  g = 0, c_fail = 0, c_max = 50, S_CR = {}_; µCR = 0.5; w = 3;
5.  P_all = {population initallation}
6.  {makespan, best, fitness} = {Caculating the fitness of population and the best individual}
7.  while(g < g_max)
8.  {
9.    predecessors = Selection(population); // Select predecessor chromosomes for reproduction based on their fitness values
10.    offspring = Crossover(predecessors, µCR); // Perform crossover on the population
11.    offspring = Mutate(offspring, µMP); // Perform mutation on the offspring
12.    offspring = AdaptiveLocalSearch(P_all, offspring); // Perform local search on some of the offspring
13.    P_all = CombinePopulation(P_all, offspring); // Combine the pre-population and offspring to create the new population
14.    {new_makespan, new_best, fitness} = {Caculating the fitness of population and the best individual from P_all}
15.    if new_makespan!= makespan then
16.        c_fail = 0
17.    else
18.        c_fail += 1
19.    end if
20.    if (c_fail = c_max)
21.       P_all = Inversion(P_all)
22.       c_fail = 0
23.    end if
24.    if (makespan < new_makespan)
25.      makespan = new_makespan;
26.      best = new_best;
27.      S_CR += 1;
28.    end if
29.    g = g+1
30.  } // end while
31.  return {best, makespan }
32. }

| Show Table

DownLoad: CSV

In Algorithm 2, lines 15–19 aim to detect local extremes, while commands in lines 20–23 move the population by calling the Inversion function. After moving the population, the algorithm continues on the new solution area. In order to facilitate the parameter adjustment during the evolutionary process, the algorithm utilizes a global variable called S_CR. This variable keeps track of the number of individuals that have successfully evolved over multiple generations.

5. Experimental results and analysis

In order to evaluate the performance of the proposed MEMINV algorithm, we experimented on the iMOPSE ^[4,5] dataset presented in Table 5.

Table 5. The iMOPSE datase.

	Code	Name	Tasks	Resources	Precedence Constraints	Skills
1	iM01	100_5_22_15	100	5	22	15
2	iM02	100_5_46_15	100	5	46	15
3	iM03	100_5_48_9	100	5	48	9
4	iM04	100_5_64_15	100	5	64	15
5	iM05	100_5_64_9	100	5	64	9
6	iM06	100_10_26_15	100	10	26	15
7	iM07	100_10_47_9	100	10	47	9
8	iM08	100_10_48_15	100	10	48	15
9	iM09	100_10_64_9	100	10	64	9
10	iM10	100_10_65_15	100	10	65	15
11	iM11	100_20_22_15	100	20	22	15
12	iM12	100_20_46_15	100	20	46	15
13	iM13	100_20_47_9	100	20	47	9
14	iM14	100_20_65_15	100	20	65	15
15	iM15	100_20_65_9	100	20	65	9
16	iM16	200_10_128_15	200	10	128	15
17	iM17	200_10_50_15	200	10	50	15
18	iM18	200_10_50_9	200	10	50	9
19	iM19	200_10_84_9	200	10	84	9
20	iM20	200_10_85_15	200	10	85	15
21	iM21	200_20_145_15	200	20	145	15
22	iM22	200_20_54_15	200	20	54	15
23	iM23	200_20_55_9	200	20	55	9
24	iM24	200_20_97_15	200	20	97	15
25	iM25	200_20_97_9	200	20	97	9
26	iM26	200_40_133_15	200	40	133	15
27	iM27	200_40_45_15	200	40	45	15
28	iM28	200_40_45_9	200	40	45	9
29	iM29	200_40_90_9	200	40	90	9
30	iM30	200_40_91_15	200	40	91	15

| Show Table

DownLoad: CSV

5.1. Experimental parameters

Experiments were conducted with the following parameters and data:

● Benchmark instances: iMOPSE dataset (iM01 to iM30), each instance is a project with full input parameters such as the number of tasks, the number of resources used to execute the project, the number of precedence constraints and the number of resource skills.

● The initial number of individuals (i.e., solution, individual, schedule): 100

● The number of generations: 50,000

● The number of times the experiment was carried out on each element of the dataset: 30

● Experiment tools: Visual Studion 2019, C#, Net Framework 4.5

● PC configuration: CPU Core i5 2.2 GHz, 6GB RAM, Windows 10

5.2. Performance Analysis

Experimental results with the iMOPSE dataset are presented in Table 5. The results are aggregated, compared and evaluated based on three factors:

● BEST - best makespan values - this is the shortest time to complete the project

● AVG - average execution time of 50 experiments with each instance dataset

● STD values - the standard deviation value between experiments on the same data instance

The schedule found by the proposed MEMINV algorithm is compared with the GA algorithm developed by Myszkowski ^[36], as shown in Table 6.

Table 6. The results from the iMOPSE dataset.

Code	Name	GA			MEMINV
Code	Name	BEST	AVG	STD	BEST	AVG	STD
	The projects have 100 tasks
iM01	100_5_22_15	517	524	5.3	475	478	2.8
iM02	100_5_46_15	584	587	4.7	584	596	4.5
iM03	100_5_48_9	528	535	9.7	523	526	10.7
iM04	100_5_64_15	527	530	2.5	505	506	1.8
iM05	100_5_64_9	508	521	9.9	487	498	4.9
iM06	100_10_26_15	292	292	1.7	295	301	0.3
iM07	100_10_47_9	296	296	2.3	283	285	2.0
iM08	100_10_48_15	279	282	2.9	272	281	3.7
iM09	100_10_64_9	296	305	6.6	256	260	0.9
iM10	100_10_65_15	286	290	5.0	285	296	3.6
iM11	100_20_22_15	163	169	5.8	140	141	2.1
iM12	100_20_46_15	197	207	6.9	166	172	8.3
iM13	100_20_47_9	185	186	0.5	181	183	0.6
iM14	100_20_65_15	240	240	0.5	207	212	5.5
iM15	100_20_65_9	181	187	4.5	181	182	1.3
	The projects have 200 tasks
iM16	200_10_128_15	577	583	4.9	576	585	2.3
iM17	200_10_50_15	553	577	17.5	546	572	17.5
iM18	200_10_50_9	585	589	5.0	549	554	4.8
iM19	200_10_84_9	567	583	11.4	535	542	6.8
iM20	200_10_85_15	549	555	4.9	540	543	3.7
iM21	200_20_145_15	326	329	1.9	282	285	1.7
iM22	200_20_54_15	363	385	20.8	328	345	14.5
iM23	200_20_55_9	312	318	4.2	267	273	5.0
iM24	200_20_97_15	424	438	9.7	409	422	11.2
iM25	200_20_97_9	321	326	6.2	283	285	1.1
iM26	200_40_133_15	215	222	6.2	169	171	5.3
iM27	200_40_45_15	201	210	6.3	178	179	0.1
iM28	200_40_45_9	209	213	2.9	181	183	1.9
iM29	200_40_90_9	211	215	3.1	196	200	1.8
iM30	200_40_91_15	200	205	3.4	174	181	3.2
	Sum			177.2			133.9

| Show Table

DownLoad: CSV

The experimental results show that the proposed algorithm MEMINV is more efficient than the GA algorithm on the following parameters:

● In term of BEST values, the MEMINV algorithm outperforms GA in 26 out of 30 projects, achieving improvements ranging from 0 to 22.33%. However, in 4 projects, MEMINV performs worse than GA, including the projects with 100 tasks and one project with 200 tasks. Figure 7.a and 7.b illustrate the BEST values comparisons for 15 projects with 100 tasks and 15 remains with 200 tasks, respectively.

Figure 7. Comparison of the BEST parameter between MEMINV and GA.

DownLoad: Full-Size Img PowerPoint

● Regarding AVG values, MEMINV yields better results than GA in 25 out of 30 projects, achieving improvements ranging from 0 to 23.31%. However, in 4 projects, MEMINV performs worse than GA, including four projects with 100 tasks and one project with 200 tasks. Figure 8.a and 8.b detail the AVG values comparisons for 15 projects with 100 tasks and 15 others with 200 tasks, respectively.

Figure 8. Comparison of the AVG parameter between MEMINV and GA.

DownLoad: Full-Size Img PowerPoint

● Moreover, MEMINV exhibits greater stability than GA with a total standard deviation of 133.9, compared to GA's 177.2 on 30 datasets of iMOPSE. Figure 9.a and 9.b present the STD values comparisons for 15 projects with 100 tasks and 15 projects with 200 tasks, respectively. Overall, these results suggest that MEMINV is a more stable and efficient algorithm for scheduling projects with a large number of tasks, making it well-suited for real-world industrial applications.

Figure 9. Comparison of the STD parameter between MEMINV and GA.

DownLoad: Full-Size Img PowerPoint

Experimental results demonstrate that the MEMINV algorithm is less effective for projects with fewer tasks, but it achieves higher efficiency for larger projects. This suggests that MEMINV is well-suited for scheduling real-world projects consisting of a series of jobs with a significant number of tasks. For instance, MEMINV can be applied in various fields, such as equipment manufacturing and industrial sewing lines.

6. Conclusion

In this paper, we have presented a mathematical formulation of the MS-RCPSP problem and proposed a new algorithm, MEMINV, that combines the strengths of the Memetic algorithm and the Inversion method. Our experiments on the IMOPSE dataset demonstrate that MEMINV outperforms previous algorithms regarding BEST and AVG values, achieving up to a 22.33% improvement on BEST values and a 23.31% improvement on AVG values. The total STD value suggests that the proposed algorithm exhibits more excellent stability, meaning that it produces less difference between experiment times.

The results suggest that MEMINV is a promising approach for solving complex scheduling problems with a large number of tasks, which is critical for various real-world industrial production scenarios, such as industrial machine lines or some other manufacturing sectors. Specifically, MEMINV can enable enterprises to create more efficient production schedules, leading to more automated and intelligent production systems that can replace manual labor.

In future work, we plan to investigate other approximation methods, such as random moves based on Gauss, Cauchy, etc., to enhance further the quality of the schedules produced by MEMINV. Overall, our research provides valuable insights into the MS-RCPSP problem and offers a practical solution that can improve the efficiency of production scheduling in various industries.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

References

[1]	S. Abbasbandy, E. Shivanian, A new analytical technique to solve Fredholm's integral equations, Numer. Algorithms, 56 (2011), 27–43. doi: 10.1007/s11075-010-9372-2
[2]	M. A. Abdou, M. M. El-Kojok, Numerical method for the two-dimensional mixed nonlinear integral equation in time and position, Univers. J. Integr. Equations, 4 (2016), 42–53.
[3]	M. A. Abdou, S. A. Raad, New numerical approach for the nonlinear quadratic integral equations, J. Comput. Theor. Nanosci., 13 (2016), 6435–6439. doi: 10.1166/jctn.2016.5582
[4]	A. Akbarzadeh, J. Fu, Z. Chen, Three-phase-lag heat conduction in a functionally graded hollow cylinder, Trans. Can. Soc. Mech. Eng., 38 (2014), 155–171. doi: 10.1139/tcsme-2014-0010
[5]	H. Almasieh, J. Meleh, Hybrid functions method based on radial basis functions for solving nonlinear Fredholm integral equations, J. Math. Ext., 7 (2014), 29–38.
[6]	P. Assari, H. Adibi, M. Dehghan, A meshless method based on the moving least squares (mls) approximation for the numerical solution of two-dimensional nonlinear integral equations of the second kind on non-rectangular domains, Numer. Algorithms, 67 (2014), 423–455. doi: 10.1007/s11075-013-9800-1
[7]	K. E. Atkinson, The Numerical Solution of Integral Equations of the Second Kind, Cambridge: Cambridge University Press, 1997.
[8]	I. Aziz, New algorithms for the numerical solution of nonlinear Fredholm and Volterra integral equations using Haar wavelets, J. Comput. Appl. Math., 239 (2013), 333–345. doi: 10.1016/j.cam.2012.08.031
[9]	C. Brezinski, M. Redivo-Zaglia, Extrapolation methods for the numerical solution of nonlinear Fredholm integral equations, J. Integr. Equations Appl., 31 (2019), 29–57.
[10]	H. Brunner, On the numerical solution of nonlinear Volterra-Fredholm integral equations by collocation methods, SIAM J. Numer. Anal., 27 (1990), 987–1000. doi: 10.1137/0727057
[11]	P. Cheng, J. Huang, Extrapolation algorithms for solving nonlinear boundary integral equations by mechanical quadrature methods, Numer. Algorithms, 58 (2011), 545–554. doi: 10.1007/s11075-011-9469-2
[12]	S. Chiriţă, On the time differential dual-phase-lag thermoelastic model, Meccanica, 52 (2017), 349–361. doi: 10.1007/s11012-016-0414-2
[13]	C. Constanda, M. E. Pérez, Integral Methods in Science and Engineering, Springer, 2010.
[14]	M. M. El-Borai, M. A. Abdou, M. M. El-Kojok, On a discussion of nonlinear integral equation of type Volterra-Fredholm, J. Korean Soc. Ind. Appl. Math., 10 (2006), 59–83.
[15]	J. A. Ezquerro, M. A. Hernández-Verón, Nonlinear Fredholm integral equations and majorant functions, Numer. Algorithms, 82 (2019), 1303–1323. doi: 10.1007/s11075-019-00656-3
[16]	J. Gao, M. Condon, A. Iserles, Spectral computation of highly oscillatory integral equations in laser theory, J. Comput. Phys., 395 (2019), 351–381. doi: 10.1016/j.jcp.2019.06.045
[17]	F. Ghoreishi, M. Hadizadeh, Numerical computation of the Tau approximation for the Volterra-Hammerstein integral equations, Numer. Algorithms, 52 (2009), 541. doi: 10.1007/s11075-009-9297-9
[18]	A. Hadjadj, J. Dussauge, Shock wave boundary layer interaction, Shock Waves, 19 (2009), 449–452. doi: 10.1007/s00193-009-0238-2
[19]	A. Jerri, Introduction to Integral Equations with Applications, John Wiley & Sons, 1999.
[20]	R. Katani, Numerical solution of the Fredholm integral equations with a quadrature method, SeMA J., 76 (2019), 271–276. doi: 10.1007/s40324-018-0175-z
[21]	F. R. Lin, Preconditioned iterative methods for the numerical solution of Fredholm equations of the second kind, Calcolo, 40 (2003), 231–248. doi: 10.1007/s10092-003-0078-x
[22]	K. Maleknejad, M. Hadizadeh, A new computational method for Volterra-Fredholm integral equations, Comput. Math. Appl., 37 (1999), 1–8.
[23]	S. Noeiaghdam, M. A. F. Araghi, S. Abbasbandy, Optimal convergence control parameter in the homotopy analysis method to solve integral equations based on the stochastic arithmetic, Numer. Algorithms, 81 (2019), 237–267. doi: 10.1007/s11075-018-0546-7
[24]	S. Pishbin, Numerical solution and structural analysis of two-dimensional integral-algebraic equations, Numer. Algorithms, 73 (2016), 305–322. doi: 10.1007/s11075-016-0096-9
[25]	A. B. Sawaoka, Shock Waves in Materials Science, Springer Science & Business Media, 2012.
[26]	H. Song, Z. Yang, H. Brunner, Analysis of collocation methods for nonlinear Volterra integral equations of the third kind, Calcolo, 56 (2019), 7. doi: 10.1007/s10092-019-0304-9
[27]	K. Takayama, Shock Waves: Proceedings of the 18th International Symposium on Shock Waves, Held at Sendai, Japan 21–26 July 1991, Springer Science & Business Media, 2012.
[28]	A. Wazwaz, A reliable treatment for mixed Volterra-Fredholm integral equations, Appl. Math. Comput., 127 (2002), 405–414.
[29]	A. Wazwaz, Linear and Nonlinear Integral Equations, Vol. 639, Berlin: Springer, 2011.
[30]	A. Wazwaz, S. M. El-Sayed, A new modification of the Adomian decomposition method for linear and nonlinear operators, Appl. Math. Comput., 122 (2001), 393–405.
[31]	J. Xie, X. Gong, W. Shi, R. Li, W. Zhao, T. Wang, Applying the three-dimensional block-pulse functions to solve system of Volterra-Hammerstein integral equations, Numer. Methods Partial Differ. Equations, 36 (2020), 1648–1661. doi: 10.1002/num.22496
[32]	J. Xie, Q. Huang, F. Zhao, Numerical solution of nonlinear Volterra-Fredholm-Hammerstein integral equations in two-dimensional spaces based on block pulse functions, J. Comput. Appl. Math., 317 (2017), 565–572. doi: 10.1016/j.cam.2016.12.028
[33]	J. Xie, Z. Ren, Y. Li, X. Wang, T. Wang, Numerical scheme for solving system of fractional partial differential equations with Volterra-type integral term through two-dimensional block-pulse functions, Numer. Methods Partial Differ. Equations, 35 (2019), 1890–1903. doi: 10.1002/num.22383
[34]	J. Xie, M. Yi, Numerical research of nonlinear system of fractional Volterra-Fredholm integral-differential equations via block-pulse functions and error analysis, J. Comput. Appl. Math., 34 (2019), 159–167.
[35]	S. M. Zemyan, The Classical Theory of Integral Equations: A Concise Treatment, Springer Science & Business Media, 2012.
[36]	F. Zhang, Shock Waves Science and Technology Library, Detonation Dynamics, Springer Science & Business Media, 2012.

This article has been cited by:

1.	Julián R. Wiest-Goyeneche, Elyn L. Solano-Charris, Carlos A. Vega-Mejía, Multi-skill resource-constrained project scheduling problem: a case study in an open-pit mining process, 2024, 0305-215X, 1, 10.1080/0305215X.2024.2376852
2.	Jingjing Wu, Xinyu Liu, Mengjun Zhang, Bin Li, Chenglin Zhao, 2024, An Efficient Shipyard Moulding-bed Scheduling Method Based on Genetic Algorithm, 979-8-3503-5456-0, 873, 10.1109/ISCTIS63324.2024.10698817
3.	Zijiao Zhang, Chong Wu, Shiyou Qu, Jiaming Liu, A hierarchical chain-based Archimedes optimization algorithm, 2023, 20, 1551-0018, 20881, 10.3934/mbe.2023924

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)