Multi-load AGVs scheduling by application of modified memetic particle swarm optimization algorithm

Abstract

The automated guided vehicles (AGVs) are extensively applied for material handling operations in the flexible manufacturing system (FMS) facilities. The scheduling decisions for the multi-load AGVs serving in the FMS with minimum travel time, waiting time and time to serve jobs are highly significant from the sustainable profits point of view. The present study proposes a combination of particle swarm optimization (PSO) for global search and memetic algorithm (MA) for local search termed as the modified memetic particle swarm optimization algorithm (MMPSO) for scheduling of multi-load AGVs in FMS. The newly proposed algorithm is applied for the generation of initial feasible solutions for scheduling of multi-load AGVs with minimum travel and minimum waiting time in the FMS. From the computational experiments, it is observed that the proposed MMPSO algorithm performs an effective and efficient exploration and exploitation process and further yields promising results for the multi-load AGVs scheduling problem in the FMS facility.

1 Introduction

The flexible manufacturing systems (FMS) constitute computer-controlled highly advanced, precise, flexible and programmable production systems and accessories. The throughput yield of FMS is significantly depended upon the efficient operations of the FMS resources. The automatic guided vehicle systems (AGVs) find their extensive application for material handling operations in the FMS facility. The function of AGVs is to load/unload and transfer the jobs from one production center to another or to the other locations within the FMS facility. The jobs being transferred can be in raw material stage or in finished stage. Optimum scheduling for AGVs in the FMS is highly required for the high productivity in material handling operations. Further, the throughput of manufacturing systems can observe multifold increase from the simultaneous scheduling of flexible manufacturing systems and the AGVs. For maximum throughput of FMS, jobs with more than one production sequence call for optimum production sequences, operation start and completion time, while an AGV serving the FMS requires an optimum decision for the scheduling (arrival and departure time) along with an appropriate selection of the dispatching and the conflict-free routing [1]. The FMS production systems with dynamic production schedules call for the dynamic material handling operations carried out by the AGVs. Estimation of parts travel time and their conflict-free routing is highly complicated with dynamic production and material handling schedules. The optimized material transfer schedules depend upon the appropriate selection and application of dispatching rules and conflict-free routes [2, 3].

In general, the FMS facility is comprised of different types of the programmable work centers which are programmed to perform a different kind of manufacturing operations on various types of parts. The various programmable work centers can be CNC milling, deburring, washing assembly, painting, coating, packaging, AGVs, etc. The pickup/delivery (P/D) station of work centers in the FMS is in contact with each other through a network of guide paths. The function of AGVs is to carry and transfer parts from anyone pickup/delivery (P/D) station of work center to another pickup/delivery (P/D) station of a work center while moving on the guide path, within the FMS facility as portrayed in Fig. 1. The AGVs can be classified as unidirectional, bidirectional, unit load and multi-load. The unidirectional AGV can only move in forwarding direction [4], and a bidirectional AGV can cruise forward as well as backward on a guide path [5, 6]. The unit load AGV is capable to transfer unit load only; on the other hand, the multi-load AGV systems can carry and transport more than unit load, which further improve the productivity of material transfer operations significantly [7,8,9]. The application of multi-load AGVs for material handling operations in the FMS facility exhibits promising potential to increase overall flexibility and FMS throughput.

Fig. 1

Multi-load AGVs and work centers configuration

The scheduling, conflict-free routing and dispatching of AGVs for material transfer operations can be performed independently or can be carried out simultaneously with the production center scheduling of the FMS. The integrated or simultaneous scheduling between the production work centers and AGVs can yield high throughput for the FMS. The simultaneous scheduling between AGVs and work centers is very dynamic and typical, and at the same time, the solutions yield of simultaneous scheduling found to be more promising in comparison with the independent scheduling. Certainly, the application of multi-load AGVs in material handling operations can assure a multifold increase in throughput of the FMS, but at the same time, their scheduling becomes more typical and complex. In the present study, an attempt is carried out for minimum waiting and travel time scheduling between multi-load AGVs and parts under production at the work centers of FMS. Initially, an analytical model for the integrated scheduling of the multi-load AGVs and parts under production with minimum waiting time and travel time at the work centers of FMS is presented. For the solution of the formulated scheduling problem, a new modified memetic particle swarm optimization algorithm (MMPSO) is proposed for the yield of initial feasible solutions. The solution yield of MMPSO algorithm was compared with the particle swarm optimization (PSO) algorithm’s solutions yield. From the comparison of both solutions yield, it was found that the MMPSO algorithm’s performance is better than the PSO algorithm for the random and deterministic scheduling conditions.

The present study is divided into following sections. Section 2 presents the related literature review on the multi-load AGVs, in Sect. 3; the assumptions, objective function and the analytical formulation of the problem are mentioned. Section 4 presents the discussions on PSO, MA and MMPSO algorithms. The computational experiment result yield for the initial feasible solutions is discussed in Sect. 5. The paper is concluded with possible future directions of work in Sect. 6.

2 Literature review

The research work on the scheduling of manufacturing systems and their operations can be found in the literature. Initially, many researchers have considered scheduling of unit load AGVs and scheduling of the work center as two different issues. Later on, with the development in the research and in light of an opportunity to harness more productivity from the available resources in the FMS facility, the researchers put an effort to address the integrated scheduling problems between the unit load AGVs and the work centers operating in the FMS facility. However, only a few research works found to be available in the literature to address the simultaneous scheduling issues between the multi-load AGVs and the work centers functioning in the FMS facility.

The pickup and drop of jobs are carried out by the AGVs according to its schedule. The AGVs perform the assigned work under certain conditions or under some constraints generally referred to priorities or deadlines, etc. An optimum AGV schedule assures for optimum distance travel of AGVs and minimum processing times for system resources. An optimum AGVs schedule also minimizes the AGVs fleet size requirement with least effect on the FMS throughput [2, 10, 11].

If appropriate routing and scheduling for AGVs are not carried out, then following operating conditions may occur frequently as reported by Qiu et al. [12].

• 1. Deadlock: If more than one AGV mutually waits for job’s release on the same path, then there is a deadlock.

• 2. Collisions: If more than one AGV adopts same guide path, then there is the probability of collision between AGVs.

• 3. Congestion: If too many AGVs travels on same guide path, then the situation of congestion arises which generally leads to low throughput and deadlock.

• 4. Livelocks: If two AGVs while traveling on two different guide paths meet at an intersection, then there is a livelock. If the livelock is not resolved timely, it may convert into deadlock or collision.

In general, the AGVs are considered to be reliable and travel at a predefined average speed. Hence, there is very less probability of breakdowns, livelocks, collisions and deadlocks. The scheduling issues can be classified into two types, namely static and dynamic. The load transfer requests are predefined in the static scheduling. The AGV routes are analyzed and developed before AGV moves onto them; any variation in job’s arrival time, deviation in driving time or any kind of breakdown of AGV leads to an adverse effect on the planning and execution of the schedule. The load transfer requests are random in case of dynamic scheduling. The real-time manufacturing conditions in FMS are stochastic and dynamic in nature. To utilize all manufacturing resources at the optimum level, the FMS operations should be dynamically scheduled and analyzed. The job arrival/departure, job’s loading and unloading time and AGVs travel time fluctuate during the real-time manufacturing operations. In real time, the manufacturing conditions are stochastic and highly dynamic in nature; hence, the manufacturing conditions call for the dynamic scheduling and dynamic update of the schedule within the predefined time duration. The schedule update is carried out according to the received information for every new job pickup/drop and job assignment within the FMS facility.

To yield maximum profit from the manufacturing operations, the time required for completion of manufacturing operations and other allied activities should be reduced to a minimum level. Appropriate time utilization in manufacturing operations can only be assured with appropriate scheduling of the FMS resources. The time window constraint in online scheduling for the real-time manufacturing conditions was applied by Yang et al. [13]. Authors found feasible scheduling solutions for the AGVs and also observed that the generation of a new service request also generates new assignment schedule for the AGVs. Meersmans [14] found solutions for scheduling problem for longer planning horizons and frequent rescheduling processes; authors developed a dynamic schedule for the material handling facility served by the AGVs and also applied a beam search heuristic algorithm for the dynamic scheduling of AGVs. The dynamic schedule found to be dependent on the length of planning horizon, and after completion of the planning horizon, the rescheduling was performed. Fleischmann et al. [15] and Powell et al. [16] also continued with the similar research work on AGVs scheduling in the FMS facility. Jerald et al. [17] performed simultaneous scheduling between AGVs and work centers. Authors minimize the work center idle time and penalty cost by application of the adaptive genetic algorithm (AGA). Authors compared results yield of the AGA and conventional genetic algorithm and found that the AGA’s performance was better than the conventional genetic algorithm.

A discrete event simulation to develop regression-based meta-models in the FMS was carried out by Kumar and Sridharan [18]. Authors applied seven scheduling rules on the AGVs to schedule and simulate the FMS operations. In the simulation experiment, authors gauged various performance measures such as mean flow time, mean tardiness and percentage tardy for the job transfer by the AGVs. In the simulation experiment, the fewest number of operations (FNOP) and the earliest modified due date (EMDD) scheduling rules found to yield better performance out of the all other applied scheduling rules. Authors also found mean flow time as a critical parameter for the estimate of lead time in job transfer by the AGVs. Sadrabadi and Sadjadi [19] developed a new interactive algorithm for the solution of multi-objective problems. The developed algorithm maintains constant interaction with the decision maker and starts solution from the infeasible region and moves step by step toward the feasible region. The algorithm handled its nonlinear utility effectively and found to be simple. Niu et al. [20] compared the performance of the genetic algorithm and particle swarm optimization algorithm combined with the genetic operators for the job scheduling problem. Authors applied an approach of ranking fuzzy numbers to find out a job sequence with minimum makespan and also uncertainty in the makespan. Petalas et al. [21] developed a new memetic particle swarm optimization algorithm that incorporating local search benefits for a standard particle swarm optimization algorithm. Authors applied the proposed algorithm to different constrained, unconstrained, mini-max programming problems and compared results of standard global and local variant of PSO algorithm. Authors found developed new memetic particle swarm optimization algorithm superior to the other algorithms.

An integrated hybrid genetic algorithm for optimization of various performance parameters for FMS was applied by the Umar et al. [22]. The FMS parameters such as AGV travel time, makespan, penalty cost due to job tardiness and AGV delay due to conflict avoidance, etc. were optimized by the authors. The authors applied combined scheduling rules, dispatching rules and conflict-free routing of AGVs and jobs within the FMS facility. In algorithm run, the multi-objective fitness function was evaluated and weights were assigned on the basis of its performance improvement. Authors also applied fuzzy logic control to control the overall performance of the algorithm. It was found that the simultaneous scheduling of AGVs, jobs, dispatching and routing in FMS can yield optimum solutions. Fazlollahtabar et al. [23] considered the due date of AGVs requiring for material handling among shops in a job shop layout and solved a scheduling problem for multiple automated guided vehicles (AGVs) in a manufacturing system. Authors observed that AGVs earliness and tardiness are highly significant in satisfying the expected cycle time of AGV. The multi-load AGVs are capable to carry and transfer more than one load on a defined guide path from one station to another within the FMS facility. The application of multi-load AGVs can reduce time spent in overall material handling activities. Bilge and Tanchoco [7] performed simulation experiments for the comparison and evaluation of the performance of multi-load AGVs with the unit load AGVs. A considerable rise in material handling system’s throughput was observed by the authors with the application of multi-load AGVs. The system’s productivity is improved when more than one load is picked up by multi-load AGV from one particular location in the FMS facility [9]. The author also found that with the application of multi-load AGVs in material handling operations the scheduling of AGVs becomes highly complex and typical to handle. Levitin and Abezgaouz [24] developed multi-load AGV routes such that the AGV with multiple loads visit each work center once and satisfy the LIFO constraint. Authors also developed an algorithm to search the shortest route to deliver the loads. Liu et al. [25] investigated PSO and MA (PSOMA)-based algorithm for the solutions of permutation flow shop scheduling problem (PFSSP). The applied algorithm minimized the maximum completion time for the NP-hard combinatorial problem. The performance parameters of multi-load AGVs were analyzed by the Ho et al. [26]. Authors carried out simulation test to gauge throughput and tardiness of FMS when served by the multi-load AGVs under load selection rules. From the simulation test results, authors observed that the load selection rules and pickup-dispatching rules affect each other’s performance. It was also investigated that the pickup-dispatching rule dispatching a multi-load AGV to the work center with highest loads in the queue generates the best tardiness and throughput values similarly; the load selection rule with a common destination point for transfer of load by the multi-load AGV yields the best throughput and tardiness values. Rashidi [27], Rashidi and Tsang [28] applied network simplex algorithm for scheduling of vehicles in port automation at container terminals.

From the literature study, it is learned that a very less research work has been carried out on multi-load AGVs scheduling for minimum waiting time and travel time. Considering aforementioned research gap, the present study focuses on the yield of initial feasible solutions by application of a novel modified memetic particle swarm optimization algorithm (MMPSO) for the scheduling of multi-load AGVs for minimum waiting time and travel time in the FMS facility.

3 Problem definition

3.1 Assumptions

Following assumptions are considered in the present study.

• 1. The guide path between two work centers is not to be compulsorily unique and due to any congestion on the guide path, the route of the multi-load AGVs can be changed by the centralized controller.

• 2. The location and number of work centers are fixed until the completion of all jobs.

• 3. Initially, the multi-load AGVs are empty.

• 4. The work centers and multi-load AGVs are reliable.

• 5. The AGVs move at constant speed.

• 6. There is no job preemption.

• 7. The job production time also includes its loading and unloading time.

• 8. The setup time for jobs on work centers is zero.

• 9. In the network, different nodes can represent the same physical location as the work center.

3.2 Problem statement

In the present study, the multi-load AGVs are to be deployed in FMS so that all imposed constraints are fulfilled. Further, an optimum material transfer schedule for the multi-load AGVs with minimum waiting time and minimum travel time can be realized. Initially, the multi-load AGVs can be available at different locations within the FMS facility. The positioning of AGVs can be at any work center or at any location in the guide path.

Notations

Let,

n:

Number of jobs

N:

Node set

P:

Set of nodes for pickup and delivery points other than the FMS facility

a:

Index for jobs

v:

Index for AGVs

k, k′:

Index for the work center

T_a:

Appointment time for the ath job

T_vo:

Time at which the AGV, v leaves the work center

T_vi:

Time at which the AGV v starts service at node i

T_ij:

Travel time from the physical location of node i, L_i, to the physical location of node j, L_j (for each pair of i and j in the N)

Q_v:

Capacity of AGV v

s:

Jobs at the buffer area

p_ak:

Processing time of job a being processed at work center k

d_u:

Due date of job a being processed at work center k

c_ak:

Completion time for job a being processed at work center k

X_ijv:

Movement of AGV, v from node i to node j

Y_vi:

Load at AGV v when it leaves node i

$\alpha ,\beta ,\gamma$:

Weights applied to the objective function due to loss of time

Node i and node n + i:

the pickup and delivery location of ith job in the network, respectively

With addition of node 0 and node 2n + 1, as the AGV initial start point and end point, within the network, the node set will become as,

N = {0, 1, 2…, n, n + 1, n + 2 …, 2n, 2n + 1}.

The pickup and delivery points are, respectively, included into two sets as

P⁺ = {1, 2 …, n}

P⁻ = {n + 1, n + 2 …, 2n}

P = P⁺ $\cup$ P⁻

The following parameters are known:

a = 1, 2,…, m

v = 1, 2,…, n

k = 1, 2,…, o, k^′ = 2,3,…, o

V = {1, 2 …, |V |}

If, X_ijv = 1; AGV v moves from node i to node j, else X _ijv = 0. So, its domain is {0, 1}.

Initially, the Y_vo = 0 and T_vo = 0

3.3 Objective function and constraints

The objective function and constraints of the problem are formulated analytically in Eq. 1 to Eq. 12. The multi-load AGVs loading conditions are presented in Eqs. (3, 4 and 5). The load on a multi-load AGV will be increased or decreased by 1 after visiting any pickup or drop-off point. The formulated scheduling problem for multi-load AGVs is an NP-hard problem and subjects to constraints satisfaction and optimization for minimum waiting time and travel time model. The multi-load AGVs and the work centers configuration is portrayed in Fig. 1.

$$ {\text{If }}(X_{ojv} = 1) \Rightarrow Y_{vj} = 1;v \in V,j \in P^{ + } \, $$

(1)

$$ {\text{If }}(X_{ijv} = 1) \Rightarrow \left\{ \begin{aligned} Y_{vj \, } = Y_{vi} + 1;v \in V,j \in P^{ + } ,i \in P,i \ne \, j \hfill \\ Y_{vj} = Y_{vi} - 1;v \in V,j \in P^{ - } ,i \in P,i \ne \, j \hfill \\ \end{aligned} \right\} $$

(2)

$$ {\text{If }}(X_{ojv} = 1) \Rightarrow T_{vj} = T_{vo} + T_{Lo,Lj} ;j \in P^{ + } ,v \in V $$

(3)

$$ {\text{If }}(X_{ijv} = 1) \, \Rightarrow T_{vj} = T_{vi} + T_{Li,Lj} ;i,j \in P,v \in V $$

(4)

$$ {\text{If }}(X_{i(2n + 1)v} = 1) \Rightarrow T_{v(2n + 1)} = T_{vi} + T_{Li,L(2n + 1)} ;i \in P^{ - } ,v \in V $$

(5)

$$ \sum\limits_{v \in V} {\sum\limits_{j \in N} {X_{ijv} = 1,i \in } } P^{ + } \, $$

(6)

$$ \sum\limits_{j \in N} {X_{ijv} } - \sum\limits_{j \in N} {X_{jiv} } = 1,i \in P,v \in V $$

(7)

$$ \sum\limits_{j \in N} {X_{ijv} } - \sum\limits_{j \in N} {Xj(n + i)v} = 1,i \in P^{ + } ,v \in V $$

(8)

$$ \sum\limits_{{j \in P^{ + } }} {X_{{{\text{o }}jv}} } = 1,v \in V $$

(9)

$$ \sum\limits_{{j \in P^{ - } }} {X_{i(2n + 1)} } = 1,v \in V \, $$

(10)

$$ Y_{vi} \le \, Q_{v} ,v \in V,i \in P \, $$

(11)

Objective function

$$ {\text{Minimum}}\,{\text{time}} = \sum\limits_{v \in V} {\left\{ {\alpha \sum\limits_{i \in P} {\sum\limits_{j \in P,j \ne 1} {X_{ijv} .T_{ij} + \sum\limits_{{{\text{jobs}}\,{\text{at}}\,{\text{the}}\,{\text{buffer}}\,{\text{area}}}} {\left( {\beta \sum\limits_{i \in P} {\left| {T_{i} - T_{vi} } \right|^{ + } + \delta \sum\limits_{i \in P} {\left| {T_{vi} - T_{i} } \right|^{ + } } } } \right)} } } } \right\}} $$

(12)

$$ \alpha = \sum\limits_{k = 1} {\sum\limits_{a = 1} {\left| {pak - duak} \right|^{2} } } $$

(13)

$$ \beta = \sum\limits_{k = 1} {\sum\limits_{a = 1} {\left| {pak - cak} \right|^{2} } } $$

(14)

$$ \delta = \sum\limits_{k = 1} {\sum\limits_{a = 1} {\left| { \, pak - qak} \right|^{2} } } $$

(15)

Initially, the multi-load AGVs starts traveling from the work center and it follows a pickup point while moving on a guide path. The AGV is allowed to move to any drop-off point or pickup point after picking upload from its first pickup point. Before delivering the job to the last work center, the multi-load AGV will deliver the job to the second last work centers. The starting service time of each node can be estimated by considering service time at current node and the traveling time between the current node and the present node. The constraints set are applied to the delivery and the pickup points. The applied constraint set ensures that a multi-load AGV will visit every pickup point once, and if an AGV gets an entry into a node, then the AGV will exit that node, and if a multi-load AGV visits any pickup node, then it will go to the associated delivery node also. Each multi-load AGV will make the first visit to the pickup node and last visit to the delivery node. The load carried by the AGV will not exceed its capacity. The total travel time of multi-load AGVs also includes waiting time of AGV and lateness time to serve the jobs. If the lateness time value and waiting time value are positive, then there will be the impact on the objective function.

4 Algorithms overview

4.1 Particle swarm optimization algorithm

The PSO algorithm works on the social interaction between particles in a multi-dimensional complex search space. The PSO algorithm interacts with individual particle within a population of particles to find an optimum area in the multi-dimensional complex search space. The particles are considered as moving points in the multi-dimensional complex search space. Initially, each particle has some initial velocity and position. The advance of each particle depends on the particle’s velocity, also referred as the global best position of the particle in the problem space [18].

The initialization of particle’s population is carried out with random velocities v_i(t) and positions p(t) of the particle, after initialization the fitness function is evaluated. The velocity and position of each particle are updated with every iteration in the algorithm. During an iteration of the algorithm, the fitness function is compared with the new velocity and the position. The iteration of the algorithm is carried out using Eq. (16). The algorithm evaluates particle’s new position p_i(t), in comparison with the old solutions to find the best position of the particle. After comparison and evaluation, the algorithm stores the particle best position as p^best_i. Similarly, the particle’s best position in the whole population is also stored as the global best position (p_gbest). The particles under consideration during an iteration of algorithm change and update their velocities on the basis of their cognitive and social learning. The process of particle’s velocity update at time interval t is shown in Eq. (16). The particle’s new position update is carried out from Eq. (17).

$$ vi(t + 1) = vi(t) + (c1 \times rand( \, ) \times (pi^{best} - pi(t))) + (c2 \times rand( \, ) \times (pgbest - pi(t))) $$

(16)

$$ pi(t + 1) = pi(t) + vi(t) $$

(17)

where v_i (t + 1) = new velocity for the ith particle. c₁ and c₂ = weighting coefficients for the personal best and global best positions, respectively. pi(t) = ith particle’s position at time t.

p_i ^best = ith particle’s best-known position. p_gbest = best position known to the swarm. rand () = function generating a uniform random variable ∈ [0, 1].

The velocity component from the previous iteration is shown by the first part of Eq. (16). The cognitive part of learning which interacts with the particle’s current and its best position is represented by the second part of Eq. (16). The interaction process of particles is also referred to as social learning. The pseudocode for particle swarm optimization algorithm is portrayed in Fig. 2.

Fig. 2

Pseudocode for particle swarm optimization algorithm

4.2 Memetic algorithm

The memetic algorithms are formed from the interplay of genetic evolution and evolution. In the algorithm, the generalization of genes into the discrete system is carried out which are further exposed to some evolutionary forces for variation and selection. The meme represents a unit of discrete system’s cultural information and indicates interplay of cultural and evolution.

In the memetic algorithm, exploitation of the population is carried out by the global search technique to find out good population area in the search space. Then, the method is applied with a combination of the local search heuristic to find individual solutions and to search out the local optimum solutions. The local search in the memetic algorithm performs the probabilistic bit flipping (point mutations) and selects solution with same or improved fitness. The algorithm presents dual performance capabilities of cultural evolution and genetic evolution in which selection, inheritance, transmission, and variation of memes and genes are carried out. The pseudocode of memetic algorithm is presented in Fig. 3.

Fig. 3

Pseudocode for memetic algorithm

Three subsequences of jobs for each multi-load AGV may be applied as follows:

• (a) The job relocation for each multi-load AGV—change and update of job served by multi-load AGV from a guide path into another guide path.

• (b) The job exchange for each multi-load AGV—address multi-load AGVs path issue by exchange of jobs between the two guide paths.

• (c) The job mix subsequence for each multi-load AGV—combination of job relocation and job exchange is applied and parallel search of the alternatives for a yield of minimum waiting and travel time.

The present study considers the job mix subsequence with a combination of job relocation and job exchange for each multi-load AGV, which found to yield better solutions.

4.3 Modified memetic particle swarm optimization algorithm (MMPSO) for multi-load AGVs

An algorithm’s performance significantly depends upon its capability of exploration of solutions (global search) and exploitation of solutions (local search). The appropriate balance between exploration and exploitation is highly imperative to achieve best out of from the algorithm’s performance. The PSO algorithm has two variants, namely global and local. The global variant gives more consideration toward the exploitation process in comparison with exploration process. In the local variant of PSO algorithm, the best position of the particle in the neighborhood is informed to the swarm particles by their neighbors only. This further makes the process of attraction to the specific best positions weaker and difficult to find the local optimum solutions. Hence, the local variant of PSO algorithm gives less consideration to exploitation process in comparison with the exploration process. However, the proposed new algorithm is formed from PSO algorithm and local search procedure of MA. The newly proposed algorithm is termed as modified memetic particle swarm optimization (MMPSO). The application of the MMPSO significantly improves the local and global search capability of the algorithm by combining the solutions (particle’s position). The randomly p % of the population from the solution is selected for the recombination. After recombination process of solutions, the fitness value of solutions is evaluated in comparison with the original or previous solution and the better solutions are kept and updated. The sufficient global and local search from MMPSO algorithm assures an appropriate balance between exploitation and exploration of algorithm process and yields good initial feasible solutions for minimum travel and waiting time also portrayed in Figs. 4 and 5 of flowchart 2 and flowchart 3, respectively. The combination of particle swarm optimization (PSO) and memetic algorithm (MA) as modified memetic particle swarm optimization algorithm is presented in Fig. 6, and the pseudocode of MMPSO is shown in Fig. 7.

Fig. 4

Flowchart for the process

Fig. 5

Flowchart of MMPSO algorithm

Fig. 6

Combined PSO and MA as MMPSO

Fig. 7

Pseudocode of MMPSO algorithm

For a yield of initial feasible solutions from MMPSO and PSO, following three methods may be applied:

• (a) Initial feasible solution (deterministic) by PSO: The number of jobs divided by the total number of AGVs is equal to the travel distance of each AGV.

• (b) Initial feasible solution (random) by PSO: The feasibility constraints are satisfied by selection of random jobs some random jobs and the process starts with the different neighborhoods.

• (c) Optimum solutions by the MMPSO: The initial optimum solutions are generated from the application of PSO algorithm under single load condition of multi-load AGVs after a yield of initial feasible solution the MMPSO algorithm is applied again to yield a better solution for the single or dual load condition of multi-load AGVs.

The combined PSO and MA also referred to MMPSO algorithm are applied as portrayed in flowcharts of Figs. 4 and 5.

5 Experimental results

The proposed analytical model and algorithm were tested by computational experiment on a hypothetically flexible manufacturing design facility, employed with multi-load AGVs for its material handling operations. The program developed and run in C++ to perform the computational experiment. The simulation experiments were executed on a computer with an Intel(R) Core(TM) i5 processor. The following parameters were set during the simulation run of program, c₁ = c₂ = 2.07, the initial temperature, F_o = 3.00, the cooling rate, λ = 0.90. The resulting yield for a manufacturing facility of 35 work centers and 20 multi-load AGVs is mentioned herein. The combination of MA and PSO algorithms also referred as MMPSO algorithm applied for the yield of initial feasible solutions for the aforesaid problem. The algorithm was run for 330 jobs, and 5597 iterations were carried out, also mentioned in Table 1. The resulting yield of the objective function by PSO algorithm and their comparison from MMPSO algorithm (column A) as initial feasible solution representing the travel time, waiting times of multi-load AGVs and the lateness time to serve the jobs in the manufacturing facility are also mentioned in Table 1 and presented in Fig. 8. Table 1 also presents the percentage increase of initial feasible solution from PSO and MMPSO and their comparison.

Table 1 Comparison of initial feasible solutions by PSO and MMPSO

Fig. 8

Comparisons of initial feasible solutions by MMPSO and PSO

The results yield of the initial feasible solution by PSO and MMPSO algorithms is statistically analyzed by application of student’s t test considering 5% of rejection of the true hypothesis with two equal means. The statistical analysis results are presented in Tables 2 and 3, respectively. The values of Pearson correlation, t-critical two-tail (distribution) and t test (paired two samples for means) for 34 dof are mentioned in Table 3. From the student’s t test, it is observed that the means are significantly different at a 95% degree of confidence level.

Table 2 Mean and variance of initial feasible solution alternatives PSO and MMPSO (deterministic, random)

Table 3 Student’s t test result (paired two sample for means) between initial feasible solution alternatives PSO and MMPSO (deterministic, random)

From the results yield, it is evident that there is an approximate 48–7% deterioration in objective function yield from the PSO algorithm (deterministic initial feasible solution and random initial feasible solution), respectively, in comparison with solution yield from the MMPSO algorithm (initial feasible solution) also presented in columns 6 and 8 of Table 1 in the form of percentage increase and comparison with column (A).

The results also reveal that the PSO algorithm directly reaches the global optimum solution for the problem, and then, the application of the MMPSO algorithm continues to find and yield a more local optimum solution for the problem under consideration. Hence, the application of MMPSO algorithm yields significantly good initial feasible solutions for the problem.

6 Conclusion and scope for future research work

The present study proposes a combination of two evolutionary algorithms, namely memetic algorithm (MA) and particle swarm optimization algorithm (PSO) as modified memetic particle swarm optimization algorithm (MMPSO) for searching optimum initial solutions (waiting times, traveling times of multi-load AGVs and lateness time) to serve the jobs by the multi-load AGVs in the flexible manufacturing facility. The resulting yield of MMPSO algorithm found to be promising in comparison with resulting yield of PSO algorithm. The application of MMPSO algorithm yields promising initial feasible solutions for the multi-load AGVs with minimum travel and waiting time for the real-time material handling operations in the FMS, the yield of results also assures a new horizon for future research toward scheduling approach of multi-load AGVs for minimum travel time, waiting time and minimum cost by application of the integrated evolutionary algorithms.

The proposed system is explained in detail and validated with a test problem of FMS facility constituting 35 work centers and 20 multi-load AGVs. It is observed that a multifold increase in FMS throughput can be achieved by using the MMPSO algorithm for scheduling of multi-load AGVs when applied into service for the real-time material handling activities in the FMS.

The future research work can be extended to carry out multi-objective scheduling for multi-load AGVs in the FMS facility by using clonal selection algorithm, NSGA II, SAM or other hybrid algorithms considering other critical operating factors of FMS and AGVs such as dispatching or scheduling rules, etc.