Automated Guided Vehicles battery management for industry 4.0

Abstract

The new wave of industry 4.0 has made battery-based automated guided vehicles (AGVs) an essential tool for material handling in manufacturing systems. However, many challenges related to battery management and machines and AGVs energy consumption. To handle these challenges an efficient battery management strategy is designed. The proposed approach supports multispeed operating modes for machines and AGVs, which offers a high flexibility to the manufacturing system. The aim of the proposed approach is to keep the minimal residual electric charge above the critical level, while enhancing the global performance of the manufacturing system. As a consequence, it increases the AGVs production hours and guarantees batteries safety.

The developed approach can bring economic benefits for industry 4.0, by increasing the productivity and avoiding AGVs batteries damage. Extended literature benchmark instances related to the manufacturing 4.0 are used to evaluate the efficiency of the suggested approach.

Keywords

Automated guided vehicle battery management industry 4.0 sustainability multi-speed operating mode

1 Introduction

The intense competition between manufacturers has forced firms to adopt the industry 4.0 as a new revolutionary industrial paradigm [1]. In this context, a great deal of attention has been granted to sustainability while increasing economic and ecological efficiency. One of the key factors of energy sustainability is the optimization of energy use, allowed by highly flexible manufacturing systems [2, 3]. Automated guided vehicles (AGVs) that ensure material handling systems are a key tool for modern flexible manufacturing systems [4].

Through a guided path made by wire, AGVs can travel automatically ensuring transport tasks [5]. Due to their agility and efficiency, AGVs are widely used [6]. They can be interfaced with other material and simply controlled from an intelligent computer system [7].

AGVs are generally used in warehouses, manufacturing facilities and distribution centers [8]. This paper scrutinizes the exploitation of AGVs in manufacturing facilities.

Although the usefulness of AGVs, many challenges arise. AGV consumes energy from an onboard battery. However, poor battery management can lead to total battery depletion; thus, making the vehicle unavailable for the system; which can reduce the overall performance of the manufacturing system. As far as replenishment is concerned, overcharging or undercharging AGV battery can damage it and reduces its lifetime. Consequently, the cost of AGVs fleet will be increased, which makes the manufacturing process more expensive. Moreover, the replenishment of depleted batteries at peak periods can lead to significant production delay. In fact, a firm can add 30 minutes of production work per lift truck each day by changing batteries at a proper time rather than at peak periods [9]. With regard to performance, the production hours of an AGVs fleet can be improved by adding new AGVs. Yet, this solution is too expensive and creates a congestion problem. Coming to flexibility, the mono-speed operating mode for robots and vehicles makes the manufacturing system less flexible to face volatility related to customer demands or energy prices.

AGVs battery management contributes to avoid battery deterioration and reduces the cost of AGVs fleet while increasing their efficiency [10]. Due to the fact that the transport task is a part of the manufacturing process, battery management impacts the overall manufacturing system [11]. However, studies on battery management are limited and there is no research paper that investigates the impact of battery management on the overall performance of manufacturing [12]. It is important to address the multi-speed operating mode of both AGVs and machines in the context of battery management. Considering a multi-speed operating mode for vehicles and machines allows to increase the flexibility of the manufacturing system. The latter would cope with the volatility of customer demands and energy cost, which could be expensive in specific periods.

This work focuses on studying how battery management can impact the overall performance of a manufacturing system, and how the flexibility of a manufacturing system can be improved through multi-speed operating as to ensure an efficient AGVs battery management approach. in addition, it aims at developing a battery management replenishment strategy which would avoid battery damage and increases the production hours of an AGVs fleet. Simulation experiments show that effective battery management can avoid battery depletion and enhance the efficiency of AGVs; therefore, improving the overall performance of the manufacturing system.

This study highlights four main tasks: processing by machines, transport by automated vehicles, battery management, and speed controlling of both machines and vehicles. The Author attempts to answer the following question: How can the use of energy be optimized and the production hours of AGVs be increased without impacting both battery lifetime and manufacturing time (makespan) as economic cost? The Author proposes to divide the main problem into four sub-problems: production task by machines, transport task by AGVs, battery management task for battery replenishment and handling trips, and speed controlling task of machines and AGVs. To achieve this goal, the battery management strategy must be designed in an effective way while handling the precedent considered tasks.

This paper is organized as follows: in Section 2, the considered problem is described. Section 3 is a state of art of relevant topics from the current research. Section 4 is divided into two sub-sections: the problem modeling and description of the proposed approach for battery management and energy optimization. Experiments and analyses are presented in Section 5. Section 6 recapitulates the conclusions and specifies the limitations of the current study, which can be considered in future studies.

2 Problem definition

The considered manufacturing system is an extension of the classical job shop scheduling problem (JSP), which is composed of a set of jobs J ={ J₁, …, J_n } to be executed by a set of machines M ={ M₁, …, M_m }. Each job (J_j) represents an occurrence of a product type manufacturing process, which consists of predetermined sequence of n_i operations, O_i ={ O_j,1, …, O_{j,n_j} }. Each operation O_j,i,m (the i^th operation of job J_i) is executed in a predetermined multi-speed machine m, with a given machine speed (normal speed, high speed). Each Job J_j enters the system by loading / unloading station (L/U), loaded on a given automated guided vehicle (v), selected among a set of AGVs A ={ A₁, …, A_s }. Then, the job is transported from L/U station to its target machine, according to a specific speed of AGV v (normal speed, high speed). Once, the operation O_j,1 is performed by the target machine, another AGV will be selected for the second operation O_j,2 of the same job J_j with a given AGV speed. The last performed operation O_{j,n_j} of J_j will be transported by an AGV v to the L/U station to be unloaded.

A limited number of battery-based uni-charge AGVs makes up the transport fleet. The transport task Tr_j,i,sr,ta which consists of moving the operation O_j,i from a source sr to a target ta, is composed of two successive sub transport tasks and is achieved in uni-directional ways to avoid collisions. The first sub transport task occurs when an AGV v receives a call. v will move from its current position to the call node. The current position of v might be either the last delivery station or the L/U station. Once O_j,i is loaded on the vehicle v, the second sub transport task will be performed by moving AGV from the source sr to the target ta station. The target station might be either a machine, or the L/U station if the operation is the last one (O_{j,n_j}). To avoid damaging AGVs’ batteries, the minimal detected battery level (MBL), should be above a certain valueλ (maximum discharge capacity or threshold level charge [11, 13]). This requires an efficient battery replenishment strategy. Assumptions of the considered problem are presented as follows:

Once a machine starts an operation, it can’t be interrupted.

All machines and AGVs are available at time 0, and each machine can execute only one operation at a given time.

Machines and AGVs never breakdown.

The processing time and the machine of an operation O_j,i are predetermined.

The batteries of AGVs are fully charged at time 0.

Both machines and AGVs can work at either normal or accelerated speed.

The electric energy consumption (watts) of machines and AGVs according to their speed is considered.

The AGVs battery replenishment during idle times is considered.

Two types of AGVs’ battery are studied: Lead Acid and Lithium-ion batteries.

Machines consume electricity during their idle times.

A Layout of the considered problem, inspired from the study of Bilge and Ulusoy’s benchmark [14] with additional constraints, is presented in Fig. 1. In the next section, our contribution is made after having knowledge of the precedent studies on JSP with transport constraints and AGVs battery management approaches.

Fig. 1

The considered manufacturing problem.

2.1 Related literature

Bilge and Ulusoy proposed, for the first time, an iterative heuristic to schedule machines while considering Automated Guided Vehicles (AGV) [14]. To optimize the completion time (makespan), the problem was divided into two sub problems: machines scheduling and vehicle scheduling. A new machine scheduling is generated at each iteration, then time windows will be constructed for vehicle trips, if it is possible. Mantel and Landeweerd dealt with design and operational control of AGV systems for job shop and flow shop [15]. Three main issues were discussed: track layout, the required number of AGVs and operational transport control. The proposed hierarchical queueing network was used to determine the adequate number of AGVs.

Later, Ulusoy et al. Tackled the problem of scheduling machines and AGVs in flexible manufacturing systems (FMSs) [16]. To optimize the makespan, a Genetic algorithm (GA) was put forward. In 60 % of the problems, GA reached the lower bound, indicating optimality. The obtained results showed that GA outperforms the precedent approach of the time window. In the same context, Abdelmaguid et al. worked on machines and AGVs scheduling in flexible manufacturing systems [17]. A mono-objective hybrid genetic algorithm was developed to optimize the makespan. They put forward a hybrid genetic/heuristic algorithm. According to the obtained results, the proposed GA outperformed other approaches.

In another study, Reddy and Rao considered the same machines and AGVs scheduling problem [18]. However, they suggested a multi-objective evolutionary algorithm for flexible manufacturing systems. Both sub problems: machines scheduling and AGVs scheduling were considered simultaneously. The objective was to minimize makespan, mean flow time and mean tardiness. Kesen and Baykoç worked on the adaptation of AGV system to Just In Time (JIT) philosophy [19]. They developed a JIT system based on the job shop environment. The transportation efficiency was improved by a dispatching algorithm for moving vehicles.

A few years later, Lacomme et al. introduced a framework based on disjunctive graph to represent the scheduling [7]. A memetic algorithm was presented for machines and AGVs scheduling for the job shop problem. The only considered objective was makespan. Zheng et al. developed a mixed integer linear programming (MILP) model with the objective of makespan minimization for machines and AGVs scheduling problem. They suggested a heuristic algorithm based on tabu search (TS) for large size problems [20].

Demesure et al. introduced a navigation approach in AGV system for flexible manufacturing system. They combined scheduled motion with priority-based negotiation [21]. The schedule motion ensures product transportation, while the priority policy avoids conflicts between AGVs. Mousavi suggested a multi-objective hybrid approach to reduce makespan and the required number of AGVs [22]. Machines and AGVs scheduling were first optimized by genetic algorithm (GA), then by particle swarm optimization (PSO). The hybrid GA-PSO algorithm outperformed both GA and PSO algorithms.

Recently, Kabir and Suzuki investigated the possibility of increasing productive hours through battery management of AGVs [23]. According to this study, the lead acid battery, which is considered as the most widely used battery, receives most of its charge during the initial phase (time) of charging as opposed to the later phase. The obtained results show that the productivity of a manufacturing system can be improved. Kabir and Suzuki presented in another research, a comparative analysis of different routing heuristics for battery management [11]. The latter concluded that all strategies should keep the minimal residual charge of batteries above a certain level. Abderrahim et al. addressed the scheduling problem in an AGV-based job shop manufacturing system [24]. Three sub-problems were taken into consideration: jobs affecting machines, product transport task’s allocation and AGVs fleet battery management. They try minimizing completion time while keeping the minimal battery level of each AGV above a secure threshold. However, the energy consumption was not considered in this work. Zou et al. investigated AGV scheduling problem with pickup and delivery from the goods handling process in a manufacturing workshop [25]. this study aims to maximize customer satisfaction while minimizing distribution cost. A multi-objective mixed-integer linear programming model is formulated. Then, a multi-objective evolutionary algorithm is developed. However, the authors ignored energy consumption of machines and AGVs.

The batteries installed on AGVs displayed a real weakness for an AGVs system, especially when battery depletion rates reach critical limits. Consequently, battery management is one of the real-world crucial constraints that should be taken into account. According to McHaney, there are two battery replenishment approaches: (I) battery charging in which AGVs are connected to chargers in order to reach a safe level, and (II) replacement in which a depleted battery is automatically replaced by a fully charged one via a battery swap station [13]. The battery charging approach is divided into four techniques: (1) automatic charging that involves transporting AGVs to a charging station for battery replenishment, (2) opportunity charging during idle times, (3) combining the last two techniques, and (4) rail-based charging which involves AGVs remaining coupled to a charging rail while traveling through a specific area of the AGV system.

According to Tsubota, the battery’s life cycle can be dramatically affected when the deep of discharge of a battery is under critical level [26]. This is why all battery management strategies should keep the residual charge of battery above a recommended levelλ. The recommended minimal level of battery is 28 % [11].

Most of precedent works focused on scheduling operations, disregarding the constraint related to AGVs battery replenishment and transport tasks, which are essential in the real world. These constraints allow avoiding AGVs’ battery damage and offering to managers more efficient decision tools made at the operational level. In previous works, energy consumption of machines and AGVs was neglected when considering battery management. In this study, machines and AGVs perform tasks at different speeds. This would result in another real-world constraint. According to Garey and Johnson, the considered problem is an NP-hard problem because while considering transport constraint, task allocation depends on the availability of machines and AGVs [27].

The aim of this paper is to optimize scheduling of assembling operations and transport tasks, (performed by machines and AGVs), minimize the overall electric energy consumption and maximize the minimal residual battery level (keep the minimum discharge level of each AGV’s battery higher thanλ level). To achieve all these goals, a battery management strategy is required. The following section presents the problem modeling and describes the recommended approach.

3 Problem modeling and the proposed approach

3.1 Problem modeling

The classical objective of the job shop problem is the makespan, which represents the completion time of all jobs. The makespan is calculated using Equation (1).

3.1.1 The model of energy efficiency

The proposed model is based on the optimization of three objective functions: makespan (Cmax), overall energy consumption (E) and minimal detected battery level (MBL).

Makespan: $C_{\max} = max_{1 \leq j \leq N} {fTn}_{j}$ (1)

Where tfn_j is the finishing time of the last operation in the job j among N jobs.

3.1.2 Overall energy consumption

Machines and AGVs consume electric power during their working and idle times. The rates of energy consumption are measured in terms of Amperes-hour. This consumption is based on input data, such as AGVs and machines Ampere draw in different states: working/idle time and normal/full speed for machines and AGVs, empty/loaded AGV. For example, a loaded AGV travelling with a full speed consumes more energy than an empty AGV moving with normal speed. The Ampere consumption rate of a machine performing a task at a full speed is higher than the Ampere consumption of a machine working at normal speed. In the same context, the energy consumption of machines and AGVs during idle times is less important than working times [13].

Tables 4 and 5 present the considered machines and AGV Ampere draw. Energy consumptions of machines and AGVs during working and idle periods are calculated using Equations (2) and (3). Thus, the overall energy consumption is calculated using Equation (4). $\begin{matrix} {Em}^{j, i, k} = {Pm}_{nor / acc} * P_{j, i, k} \\ {Em}^{a, b, k} = {Pm}_{nor / acc} * {IdleT}_{m, a, b} \end{matrix}$ (2) $\begin{matrix} {Ev}^{j, i, s, t} = {Pv}_{nor / acc} * {Trp}_{s, t, weight, speed} \\ {Ev}^{a, b} = {Pv}_{nor / acc} * {IdleT}_{v, a, b} \end{matrix}$ (3) $\begin{matrix} E = \sum_{j = 1}^{N} \sum_{i = 1}^{n_{j}} {Em}^{j, i, k} + \sum_{j = 1}^{N} \sum_{i = 1}^{n_{j}} {Em}^{a, b, k} \\ + \sum_{j = 1}^{N} \sum_{i = 1}^{n_{j}} {Ev}^{j, i, s, t} \sum_{l = 1}^{v} \sum_{x = 1}^{n_{l}} {Ev}_{l}^{a_{x}, b_{x}} \end{matrix}$ (4)

We note:

fTa_j: the finishing time of the last operation in the job j.

P_j,i,k: the processing time of the operation i of the job j by the machine k.

IdleT_m/v,a,b: the idle time [a, b] of a machine m or an AGV v.

Trp_{s,t,weight,speed}: the transport time of an AGV from source s to target t station according to a certain weight(empty/full) and moving with a speed (normal, accelerated).

Pm_nor/acc: the machine electrical energy (watts) transferred peer one minute, in normal or accelerated operating mode.

Pv_nor/acc: the AGV electrical energy (watts) transferred peer one minute, in normal or accelerated operation mode.

Ampere is the unit of current and Ampere-hour is the unit of charge.

3.1.3 Battery replenishment system

The manufacturing of a product type (job) requires a sequence of assembling operations, processed successively by different machines. Each job (a part using in assembling process) is picked up from a source (loading station/machine) and routed to a destination (unloading station/machine) by an AGV. Once a job is completely manufactured, it will be routed to the loading/unloading station in order to be unloaded. However, AGVs movements require electrical energy consumed from their on-board batteries. In order to avoid battery depletion, the system should manage the battery replenishment of AGVs. The proposed battery replenishment scheme is based on two strategies: (1) automatic battery swap and (2) opportunity charging.

3.1.4 Automatic battery swap

To manage AGVs battery, an automatic battery swap is proposed, in order to replace the old battery with a new full charged battery. When an AGV receives a call from a job, four different AGV behaviors are put forward:

Behavior 0: AGV travels from its current position to the final target without making any battery swapping;

Behavior 1: AGV travels from its current position to the battery station, swaps its battery with a full charged one, travels to the calling node to pick up the caller job and moves to the drop off node.

Behavior 2: AGV travels to the caller node, picks up the job, then returns to the battery station to swap its battery and travels to the drop off node.

Behavior 3: AGV travels to the caller node, picks up the job and routes it to the drop off node, then it returns to the battery station to swap its battery.

The selection of AGV’s behavior is guided by the battery DoD (Deep of Discharge) percentage. The chance of making a battery swap increases with high battery discharge. To guide the AGV behaviour, a probability of making battery swap is suggested in Equation (5). ${Pb}_{B . S} = (DOD) / 100) - charging_par$ (5)

Charging_par: is the adjusting parameter which belong to the interval [0, 0.5].

x randomly generated number that belongs to [0,1].

If x < Pb_B.S The battery switch (B.S) will be performed.

3.1.5 Opportunity charging

When an AGV performs a transport task of a job, the AGV will move to the next calling node to transport another job, or stop waiting for the same job to be accomplished by machine. Interfaces to battery chargers are installed at each stop position while batteries are automatically connected to chargers when AGV stops.

The battery replenishment process is based on two concepts: the deep of discharge (DoD) and the state of charge (SoC) of battery. DoD is the amount of Ampere-hour removed from a battery’s capacity [13]. The SoC is the capacity that is currently available and it is calculated using Equation (7) [28]. For example, when 15 Amperes-h is removed from a battery of capacity equal to 100 Ampere-h, then DoD = 15% and SoC = 85%. $SOC = 100 % - DoD$ (6)

According to Kabir et al. [23], the received electric charge level to a battery depends not only on charging time, but also on the residential electric charge (SoC). They stated that the most valuable received charge is during the initial phase of charging. They recommended three formulas to calculate the charging time (in minute) from DoD (x) for Load Acid batteries. These formulas targeted three states of charge (SoC): 90%, 95% and 100%. Equation (8) calculates the charging time (minutes) according to Deep of discharge when targeting 90%, 95% and 100% state of charge for Acid lead battery. $\begin{matrix} t = 51.115 * e^{2.5773 * x} \\ t = 37.442 * e^{3.7248 * x} \\ t = 205.29 * e^{2.6785 * x} \end{matrix}$ (7)

In the same perspective, Zhan put forward three other formulas for Lithium-ion batteries, which allow calculating charging time when targeting three states of charge 90%, 95% and 100% [29]. Equation (9) calculates the charging time according to the Deep of discharge when targeting 90%, 95% and 100% state of charge for Lithium-ion battery. $\begin{matrix} t = 11.809 * e^{0.3746 * x} \\ t = 19.055 * e^{0.3706 * x} \\ t = 31.365 * e^{0.3746 * x} \end{matrix}$ (8)

The charged energy percentage depends on several parameters: idle time, SOC target, battery type and the required charging time t to reach a targeted SoC. The battery received charge (RC) percentage is calculated using Equation (10). ${RC}_{%} = \frac{idle time * selected SOC %}{time of charge}$ (9)

Idle time: when an AGV is in stop state.

Selected SOC percentage: the target SOC percentage is 90%, 95% or 100%;

Time of charge: the required time (minutes) to reach 90%, 95% or 100% SOC with a given DOD of battery.

3.2 The proposed approach

Three objective functions are optimized in this study: makespan, overall energy consumption, and minimal detected battery level (MBL). Thus, the considered problem is a multi-objective optimization problem. Many approaches for multi-objective optimization have been recommended in the literature. Usually, the used methods are: single objective transformation, random weighting, and the Pareto method [30]. The latter is preferred by researchers because it allows obtaining a set of Pareto optimal solutions in an optimization process that is coherent with an actual scheduling problem [31]. Many representative algorithms exist, such as MOGA [32], NSGA and NSGA-2 [33], PESA and PESA-2 [34]. However, because of its better distribution and fast convergence speed, NSGA-2 is widely used.

3.2.1 The proposed NSGA-2

Chromosome coding

The chromosome is composed of five rows (Table 1):

Table 1
Chromosome coding

Job 2 1 2 2 3 1 3

AGV 1 2 1 1 2 1 2

AGV speed 0 0 1 0 0 0 1

Battery swap 1 0 3 2 0 3 0

Machine speed 0 1 0 0 1 1 1

Algorithm 1

Crowding distance

Algorithm: Crowding-Distance (I)
Begin
L = \|I\| // the number of solutions in the set I
For each i, set I [i] _distance = 0 // initialize the distance of each solution
For each objective m
I = sort (I, m) // sort solutions according to the value of each objective function
I [1] _distance = I [L] _distance =∞ // the boundaries solutions are always taken
For i = 2 to (L-1) // for all the other solutions
$I {[i]}_{distance} = I {[i]}_{distance} + ((I {[i + 1]}^{} m) - (I {[i - 1]}^{} m)) / (f_{m}^{\max} - f_{m}^{\min})$
End-for
End-for
End-for
End

Job: represents the schedule of production tasks affected to their machines. (e.g. {1^st job2, 1^st job 1, 2^ed job 2, etc.});

AGV: defines the selected transport vehicle for each job. (e.g., 2ed job 2 (3rd column) is affected to the AGV 1);

AGV speed: defines if the AGV (same column) moves at normal speed (0), or full speed (1);

Battery swap: specifies how the AGV behaves to manage its battery replenishment during the transport task. e.g. (0 for no battery swap, other values (1– 3) reflect different strategies of battery replenishment);

Machine speed: defines the speed of processing of each machine. (e.g., 0: normal processing and 1: fast processing)

3.2.2 The selection operator (Elitism Non-Dominated Sorting Algorithm)

The selection nature of the multi-objective genetic algorithm is more complex than the mono-objective one. This operator divides individuals into ranks and applies a strategy to evaluate and sort the individuals of the same rank: There are two types of Pareto sorting methods which are widely used: the recursion sorting [35] method and the adopted quick sorting method. According to recent works, the second method has better computational performance.

3.2.3 Selection strategy of non-dominated solution with the same rank

The application of non-dominated sorting generates individuals with different ranks, and those with low rank will be chosen to participate in the genetic evolution process. For the individuals of the same rank, some strategies ensure diversity of the colony during evolution. According to literature, the most important approaches are: information entropy, density-based clustering, niche technology and classification [36]. The adopted strategy in this paper is the density based on clustering. This strategy can capture both of diversity and distribution of population macroscopically. It can also make the relationship among individuals with the capability of controlling the colony during the evolution process [37]. The algorithm of Crowding-distance (I) is used to sort solutions of the same rank [33].

I [i] * m is the value of the m^th objective function of the solution i in the set of solution I.

$f_{m}^{\max}, f_{m}^{\min}$ : the maximum and the minimum values of the m^th objective function.

The solution i is better than the solution j if:

i_rank < j_rank or

i_rank = = j_rank & i_distance > j_distance

If two solutions belong to the same rank, the solution belonging to the less crowded zone is the best one. For the diversity of the population, individuals with a larger crowding distance have a big probability to participate to reproduction and evolution.

Designed genetic operators:

Crossover: two crossovers are advanced for exchanging information between parents. Both of them are inspired from the technique of POX, which allows generating valid chromosomes and avoiding an additional process of chromosome correction [38].

POX Assignment: the purpose of the suggested crossover is to exchange information while keeping the production task sequence. First, two sub sets of jobs are selected randomly (e.g., S1 = {J1, J3}, S2={2}). Each parent is cloned to a new child. This technique keeps for each child the column information of the selected job on its parent. The designed mask of modification guides the process of information exchange between parents (the job sequence in not exchanged). If the value in the mask equals 1, the exchange is permitted, otherwise, it is forbidden.

POX Sequencing: to exchange information between parents, the same approach as POX assignment. Yet, the mask of modification is applied only on the first line of job, and the other lines representing information about AGVs and machine features will be maintained in child chromosomes, as they are in each child’s parents.

Mutation: it is applied to a small portion of population with a probability less than 30%, in order to make a small change on chromosomes, avoiding a premature convergence of the genetic algorithm.

Two types of mutation are implemented in this paper: the first concerns classical mutation by swapping two columns, selected randomly. The second developed mutation is based on two mask arrays. Mask 1 for selecting the columns to be changed and mask 2 for selecting chromosome features to be modified.

3.2.4 Workflow of the suggested HNSGA-2(Hybrid NSGA-2)

The NSGA-2 algorithm is improved by efficient Tabu Search (TS) to optimize jobs and AGVs. The main purpose is to minimize Cmax and the overall energy consumption while maximizing the minimal battery level of AGVs. In this paper, the TS is integrated into NSGA-2 for local searching. Workflow of the proposed hybrid NSGA-2TS is shown in Fig. 2.

Fig. 2

The proposed hybrid NSGA-2.

3.2.5 Local search by Tabu search

One of the most successful meta-heuristic for combinatory optimization problems, especially for many scheduling problems, is Tabu Search (TS) [39]. By using movements, TS explores the solutions space to optimize an objective function. The main parameters of TS are: neighborhood structure, tabu list, aspiration criteria and stopping condition.

The recommended TS represented in Fig. 3, is based on three neighborhood functions:

Fig. 3

The proposed Tabu search (TS) integrated in NSGA-2.

NF1: Swap (job i, job j): select randomly two positions in the chromosome’s job sequence and swap them,

NF2: Change (AGV_ID): select randomly a position from the chromosome’s AGV ID sequence and replace the old AGV by another AGV ID,

NF3: Change (AGV Behavior): select randomly a position from the chromosome’s AGV behavior sequence and replace the old AGV behavior by another behavior, selected randomly.

The recommended TS improves the solutions generated from the genetic operators (crossover & mutation). This improvement can be in terms of minimal battery level of AGVs, or/and the overall energy consumption, or/and Cmax. The TS algorithm is stopped after a predetermined number of iterations.

3.2.6 Complexity analysis

The considered problem is NP-hard in the strong sense [24]. Contrary to the mathematical approach, the suggested metaheuristic approach provides solutions of high quality in reasonable time. The required execution time of HNSGA2 is less than 60 seconds for all instances. Suppose that B is the total number of the manufacturing operations of each problem instance. N_p and M are the population size and the number of objective functions to be optimized. In each iteration, HNSGA-2 needs a selection of solutions, generating offspring, applying the local search. Then, sorting solutions using fast non-dominated sorting and crowding distance assignment. The worst-case complexity of the main loop of HNSGA2 are as follows:

Selecting and generating offspring by genetic operators O (2N_pB)

Local search of one iteration is O(B)

Non-dominated sorting is $O (M (2 N_{p}^{2}) B)$

The Crowding-distance assignment is O (M (2N_p) log (2N_p) B)

Sorting solutions by dominance rule is O (2N_plog (2N_p) B)

Hence, the complexity of the algorithm HNSGA2 is

O ({BMN}_{p}^{2}) + O (B)

4 Experiments and analysis

To achieve an accurate simulation of battery constraint in AGVs system, well-known benchmarks [14] are used and extended in this paper (see Tables 4 and 5). These benchmarks are used to simulate the AGVs battery management with multi-speed operating mode for machines and AGVs. For each transport task, performed by an AGV, the pertinent Ampere draw is retrieved from battery data and the battery level is reduced by the consumed number of Amperes peer unit time (minute).

Table 2
The proposed crossover operator

Job 0 2 1 3 2 3 1 3 2 3 2

AGV 1 1 2 2 2 1 1 1 2 2 1

AGV speed 2 0 0 1 0 1 0 0 0 0 1

Battery swap 3 1 0 0 0 0 1 0 2 0 1

Machine speed 4 0 1 1 0 0 0 1 1 1 0

Parent 1 Parent 2

Mask 1 Mask 2

1 1 1 0 1 1

Mask of modification 2 1 0 1 0 0

3 0 1 1 0 0

4 0 1 1 0 1

Job 0 2 1 3 2 3 1 3 2 3 2

AGV 1 2 2 2 1 1 1 2 2 1 1

AGV speed 2 0 0 1 0 1 0 0 0 0 1

Battery swap 3 1 0 0 1 0 0 0 2 0 1

Machine speed 4 0 1 1 0 0 1 1 1 0 0

Child 1 Child 2

Table 3

The proposed mutation operator

Job	0	2	1	3	2	3	3	1	3	2	2
AGV	1	1	2	1	2	1	1	2	1	2	1
AGV speed	2	0	0	1	0	1	1	0	1	0	0
Battery swap	3	1	0	0	0	0	0	0	0	0	1
Machine speed	4	0	1	1	0	0	0	1	1	0	0
			before		After mutation 1
			Mask 2
	1	1	0	1
Mask of modification	2	1	1	0
	3	0	0	0
	4	0	1	0
Mask 1	1	0	1	0	1
Job	0	2	1	3	2	3	2	1	3	2	3
AGV	1	2	2	0	1	1	1	2	0	1	1
AGV speed	2	0	0	1	0	1	1	0	0	0	1
Battery swap	3	1	0	0	1	0	1	0	0	1	0
Machine speed	4	0	1	1	0	0	0	1	0	0	0
			before		After mutation 2

Table 4

Battery’s data (Ampere draw peer activity)

Travel empty normal speed	0	40 Amps
Travel empty full speed	1	50 Amps
Travel loaded normal speed	2	65 Amps
Travel loaded full speed	3	77 Amps
Battery size	4	100 Amps-h
Battery swap time	5	4 minutes
Stand by comp	6	20 Amps

Table 5

Machine’s data (Ampere draw peer minute)

Normal mode	0	10 Amps
Accelerated mode	1	16 Amps
Standby mode	2	4 Amps

After many experiments, the parameters that fit the recommended genetic algorithm are fixed as follows: population size: 100, crossover probability: 0.7, mutation probability: 0.2, criteria weights: 0.3 for makespan, 0.3 for energy consumption and 0.4 for MBL. The tabu search is stopped after 20 iterations.

The transport tasks of each AGV are presented on Tables 6 and 7. Each line corresponds to the transport task of a job ensured by an AGV. However, several lines are required to achieve completely the transport task from the original machine to the target one. The first three columns show the job to be transported, its current position and its target. Columns 4, 5 and 6 describe the job routing by identifying the AGV, the start and the finish position. Columns 7, 8 and 9 show the traveling time (in minutes), AGV load (empty/loaded with job) and the expected AGV battery level after finishing the current transport task. the last column indicates that the current job has achieved all its manufacturing operations (finished).

Table 6

AGV 1 monitoring without battery charging of instance EX33 generated by HNSGA-2 (Lithium-ion battery)

Job	Job source	Job target	AGV current position	AGV target position	AGV	Travel period (minutes)	AGV load	Battery Level %	Product type status
5	L/U	M3	1	L/U	M3	8	loaded	91.44	on progress
5	M3	M1	1	M3	M1	6	loaded	93.58	on progress
5	M1	L/U	1	M1	L/U	12	loaded	89.16	finished
2	L/U	M1	1	L/U	M1	4	loaded	84.88	on progress
4	M1	M2	1	M1	M2	6	empty	81.55	on progress
4	M2	L/U	1	2	L/U	10	loaded	77.82	finished
1	L/U	M1	1	L/U	M1	4	loaded	73.54	on progress
3	M1	L/U	1	M1	L/U	12	loaded	71.11	finished
2	L/U	M2	1	L/U	M2	8	empty	66.66	on progress
2	M2	L/U	1	M2	L/U	10	loaded	57.63	finished
1	L/U	M4	1	L/U	M4	12	empty	50.97	on progress
1	M4	L/U	1	M4	L/U	6	loaded	47.70	finished

Table 7

AGV 2 monitoring without battery charging of instance EX33 generated by HNSGA-2 (Lithium-ion battery)

Job	Job source	Job target	AGV	AGV current position	AGV target position	Travel period (minutes)	AGV load	Battery Level %	Product type status
3	L/U	M3	2	L/U	M3	8	loaded	91.44	on progress
4	L/U	M4	2	M3	L/U	8	empty	87.0	on progress
4	L/U	M4	2	L/U	M4	12	loaded	76.16	on progress
4	M4	M2	2	M4	M2	8	loaded	79.99	on progress
3	M3	M4	2	M2	M3	4	empty	77.21	on progress
3	M3	M4	2	M3	M4	4	loaded	72.94	on progress
3	M4	M1	2	M4	M1	8	loaded	68.62	on progress
2	M1	M3	2	M1	M3	8	loaded	61.39	on progress
2	M3	M2	2	M3	M2	4	loaded	60.26	on progress
1	M1	M2	2	M2	M1	4	empty	57.48	on progress
1	M1	M2	2	M1	M2	4	loaded	53.20	on progress
1	M2	M4	2	M2	M4	10	loaded	50.94	on progress

In Table 8, the proposed hybrid HNSGA-2 algorithm is compared with the classical NSGA-2 algorithm using 40 instances. Both algorithms optimize Cmax, MBL (Minimal Battery Level) and overall energy consumption. The state of charge (SoC) of AGV battery is fixed at 90% and the battery type is Lead Acid. The obtained results (Fig. 4) indicate that the algorithm HNSGA-2 largely outperforms the classical NSGA-2 algorithm in the considered problem. 92.50 % of solutions obtained by HNSGA-2 dominate the solutions provided by NSGA-2. However, only 7.50 % of solutions provided by both algorithms (HNSGA-2 & NSGA-2) are non-dominated solutions. The performance of the algorithm (NSGA-2) is explained by the suggested Tabu Search (TS) algorithm, which improves the generated solutions by the genetic operators (crossover and mutation).

Table 8

Comparison between classical NSGA-2 and the proposed hybrid HNSGA-2 for Acid Battery with opportunity charging (SoC = 90%)

Instance	NSGA-2			HNSGA-2
	Cmax	MBL	Energy	Cmax	MBL	Energy
	(minute)	(%)	consumption	(minute)	(%)	consumption
			(Ampere-h)			(Ampere-h)
EX11	123	69.31	169.06	123	70.87	162.07
EX21	162	31.73	251.59	112	67.08	159.46
EX31	183	60.80	256.03	121	76.86	171.46
EX41	173	57.23	278.13	134	56.85	213.06
EX51	160	61.66	215.56	102	64.14	152.33
EX61	207	69.95	263.53	141	64.10	191.19
EX71	186	40.05	313.10	144	51.89	205.39
EX81	215	58.42	292.80	175	70.61	200.19
EX91	206	72.61	264.93	191	72.08	203.33
E101	229	63.33	290.53	177	66.94	235.33
EX12	104	59.48	170.33	84	77.99	115.73
EX22	122	79.21	131.33	76	84.73	95.06
EX32	131	73.33	167.53	78	81.40	101.39
EX42	119	52.51	188.49	93	72.93	138.06
EX52	106	62.01	160.90	65	66.52	106.66
EX62	129	81.85	141.66	102	82.53	127.83
EX72	115	36.69	179.36	81	70.87	116.56
EX82	147	73.14	192.63	146	85.53	143.36
EX92	127	61.30	188.96	118	75.36	152.63
EX102	169	53.62	227.06	150	60.51	178.66
EX13	110	46.00	189.90	80	77.80	117.03
EX23	126	76.66	156.59	79	81.78	97.73
EX33	118	57.76	166.66	80	85.76	99.33
EX43	142	56.37	199.73	81	58.52	148.83
EX53	108	45.19	169.09	71	74.10	109.19
EX63	125	73.05	148.36	107	86.97	115.03
EX73	138	57.01	195.73	90	80.59	122.83
EX83	150	81.33	168.23	147	90.00	123.26
EX93	140	65.42	182.23	110	66.35	155.56
E103	173	57.43	232.23	145	67.63	207.13
EX14	182	34.63	293.69	123	58.08	176.86
EX24	177	37.90	291.56	147	78.02	170.46
EX34	211	59.54	320.46	131	63.32	187.26
EX44	226	40.15	313.99	161	47.75	243.36
EX54	172	37.66	305.86	115	58.14	167.33
EX64	224	54.87	319.80	157	72.49	190.13
EX74	272	40.98	388.83	151	54.56	223.16
EX84	257	33.45	376.45	167	66.03	240.16
EX94	210	57.05	288.30	181	73.05	202.59
EX104	268	37.39	394.99	193	61.53	287.40

Fig. 4

Domination percentage between NSGA-2 and HNSGA-2.

To evaluate the importance of the battery management part, embedded in chromosome coding, two versions of the HNSGA-2 algorithm were compared. Both Lead Acid and Lithium-ion battery types were tested. The minimal Battery Level (MBL) is reported on Table 9. The obtained results from these experiments (Table 9) show that the average Minimal Battery Level (MBL) was improved by 140.86 % for Lead Acid battery and 241.96 % for Lead Acid battery, using battery management in the chromosome coding. The minimal value of MBL, among all MBL values of 40 instances, calculated from HNSGA-2 without charging and HNSGA-2 with charging battery is reported on Table 10. The minimal MBL was improved by 178.21 % in the Lead Acid battery and 388.98 % in the Lithium-ion battery.

Table 9

NSGA-2 without battery swap neither opportunity charging versus HNSGA-2 with only opportunity charging

Instance	MBL (%) without charging	MBL % with opportunity charge by battery type and target SoC level
			Lead acid battery (%)			Lithium-ion battery (%)
	Acid battery	Lithium-ion battery	90 %	95 %	100 %	90 %	95 %	100 %
EX11	30.73	32.60	72.24	70.08	55.00	76.00	76.88	75.36
EX21	30.50	25.33	75.65	72.96	40.06	78.73	79.73	80.00
EX31	24.44	22.83	70.64	67.74	44.09	75.21	76.00	77.16
EX41	4.66	4.36	55.55	57.75	44.68	74.00	76.00	73.33
EX51	34.50	34.66	60.97	64.18	41.11	76.00	77.30	69.70
EX61	9.90	13.46	75.21	60.96	46.02	78.70	81.33	80.50
EX71	6.06	8.66	57.04	57.22	36.77	76.00	75.26	79.30
EX81	3.33	5.36	68.92	67.88	49.83	79.73	77.33	79.33
EX91	12.03	11.16	64.31	69.82	50.32	75.36	77.33	78.73
E101	– 9.33	– 6.43	76.47	77.20	63.43	75.33	78.66	74.66
EX12	52.20	51.73	73.72	72.38	63.13	85.50	84.20	84.73
EX22	62.20	59.40	84.37	77.31	72.92	89.53	83.43	87.30
EX32	57.63	57.66	85.06	81.18	40.47	87.43	89.63	84.73
EX42	28.96	34.83	67.12	65.40	26.44	79.53	80.81	78.66
EX52	51.38	5.09	78.87	73.00	56.25	80.96	86.40	79.53
EX62	46.43	44.86	83.86	83.54	77.63	88.20	90.00	87.30
EX72	46.33	46.40	78.10	80.12	60.98	87.20	86.00	82.00
EX82	32.20	33.63	86.00	86.43	82.79	86.86	89.20	89.86
EX92	36.16	30.43	75.36	74.29	57.37	83.83	80.00	74.40
EX102	15.13	– 22.33	72.43	68.17	56.75	85.33	86.00	83.77
EX13	49.39	46.06	72.87	71.06	64.34	82.71	77.80	81.33
EX23	56.16	50.16	88.35	81.40	72.96	88.96	81.33	81.40
EX33	55.16	47.73	81.85	77.09	69.40	86.76	83.33	82.43
EX43	33.20	27.60	67.96	72.21	51.78	81.43	81.26	80.16
EX53	49.03	47.70	78.56	72.46	56.10	76.66	81.40	80.36
EX63	44.66	38.63	87.23	80.64	65.14	88.20	83.10	85.72
EX73	41.46	36.73	81.44	63.10	59.04	80.66	82.76	82.76
EX83	34.60	29.16	87.43	86.66	75.56	88.00	89.66	89.76
EX93	29.59	27.33	80.66	75.48	61.27	78.06	80.95	77.76
E103	9.96	13.23	84.73	62.62	47.01	79.33	80.20	85.33
EX14	28.16	28.30	63.75	57.39	35.54	76.66	64.53	73.43
EX24	22.53	20.33	68.79	63.00	51.86	77.16	76.76	74.66
EX34	14.40	19.33	76.97	58.92	36.81	74.30	72.00	73.73
EX44	– 2.56	– 7.40	52.47	47.47	16.76	72.66	71.26	67.52
EX54	26.20	28.36	53.29	57.53	35.25	70.10	73.43	70.66
EX64	12.16	11.73	65.18	60.57	41.60	74.96	76.00	75.23
EX74	– 3.56	– 4.30	56.95	42.94	19.40	76.00	76.66	73.96
EX84	– 8.20	– 8.76	67.65	46.03	32.59	75.53	76.00	74.66
EX94	8.49	4.86	68.66	63.09	39.24	72.00	66.00	74.60
EX104	– 21.43	– 21.69	45.43	36.38	16.33	70.66	68.66	74.00

Table 10

Recapitulation of the minimal battery AGVs Battery Level according to battery type

	Without charging	With charging opportunity &without battery swap
	Lead Acid battery	Lithium-ion battery	Lead Acid battery	Lithium-ion battery
Average MBL %	26.31 %	23.21 %	63.37%	79.37 %
Minimal MBL %	– 21.43 %	– 22.33 %	16.76%	64.53 %

The graphical representation of the obtained solution is represented by the Gantt diagram. To illustrate the details of this representation, Fig. 5 shows the best solution obtained by HNSGA-2 using both battery opportunity charging and battery swap for the instance EX410. The Gantt diagram contains two parts: the machines assembling operations and the AGVs transporting tasks.

Fig. 5

Gantt diagram generated by HNSGA-2 with Opportunity Charging & a Battery Swap of the instance EX410.

In the machines part, each element represents a job manufacturing operation performed on the indicated machine. The format Jx (y) represents the job x transported by the AGV y. For example, J6(2) indicates that the job 6 was transported by the AGV 2.

In the AGV part, each AGV travels from its current position to its target to accomplish a job transport task. All AGVs start from Loading/unloading station, presented by the digit 0. The format “>T” means that the current AGV travels from its last position to its target T. The target can be either a machine or loading/unloading station (0).

AGVs are charged during their idle times (opportunity charging). Two battery swap operations were performed in both AGVs to keep their minimal battery level above the safe mode, in order to guarantee the continuity of the manufacturing process and avoid battery damage.

Fig. 6 shows energy details of the best solution represented in Fig. 5 for the instance problem EX410. Both battery level and overall energy consumption (machines and AGVs) are monitoring. The minimal battery level was tracked in AGV 2 in 106 minutes, with a value of 61.53 %. The last transport task of AGV 1 was achieved in 186 minutes and 154 minutes for AGV2.

Fig. 6

Evolution of overall energy consumption & AGVs battery level during manufacturing process of the instance EX410.

5 Conclusion and limitations

Unlike previous works, the developed approach optimizes the scheduling of both jobs and AGVs, while managing AGV battery and optimizing the overall energy consumption. Moreover, multi-speed machines and AGV operating is considered as a real-world constraint. The optimized criteria contribute to improving the production efficiency, by enhancing the use of AGVs and managing their batteries for longer battery lifetime and avoiding battery depletion. The battery SoC (State of charge) provides more production flexibility to manufacturers and allows them to get more AGVs productive hours.

The obtained results reveal the importance of battery management to keep the minimal battery level above a safe level, therefore preventing battery depletion and extending the battery life time. The proposed Tabu search embedded in NSGA-2 algorithm makes the proposed hybrid algorithm HNSGA-2 more efficient than the classical NSGA-2 algorithm. By optimizing the minimal residual charge battery level, makespan, and energy consumption, we can reduce the cost of purchasing new batteries while also reducing the amount of energy required by machines and AGVs to complete the manufacturing process. Consequently, the total travelled distance of AGVs will be reduced.

The HNSGA-2 provides a set of the best solutions called Pareto front. The latter offers more flexibility to managers in order to select, by adjusting criteria weights, the most suitable solution depending on the internal and the external manufacturing conditions.

Yet, and despite its precious advantages, the proposed approach has also its limitations. These can be considered in future studies. First, AGV battery capacity may be reduced over time. AGV and machine breakdown is a real recurrent problem which can affect productivity. Additional battery parameters may be monitored, such as temperature, charging / discharging current, the authorized number of battery swaps or the critical battery temperature level. All these issues keep open perspectives to consider the manufacturing system in a reactive way. In this context, the proposed approach in this paper may be used as a predictive model for unexpected events.

Author contributors

This work was conceived and developed by Mohammed El-Amine Meziane, an assistant professor at Higher school of Economics. The text was written by Mohammed El-Amine Meziane, proofread by Amir Samir, assistant professors of English and American Civilization at Higher School of Economics.

Funding

This work has been funded by the Algerian Ministry of Higher Education and Scientific Research.

Footnotes

Acknowledgments

The author would like to thank The Directorate General for Scientific Research and Technological Development (DGRSDT), an institution of the Algerian Ministry of Higher Education and Scientific Research, for their material support.

References

Parente

, Figueira

, Amorim

and Marques

, Production scheduling in the context of Industry 4.0: review and trends, Int. J. Prod. Res. 58(17) (2020), 17. doi: 10.1080/00207543.2020.1718794

Giret

, Trentesaux

and Prabhu

, Sustainability in manufacturing operations scheduling: A state of the art review, J. Manuf. Syst. 37 (2015), 126–140, doi: https://doi.org/10.1016/j.jmsy.2015.08.002

Jayal

A.D.

, Badurdeen

, Dillon

O.W.

and Jawahir

I.S.

, Sustainable manufacturing: Modeling and optimization challenges at the product, process and system levels, CIRP J. Manuf. Sci. Technol. 2(3) (2010), 144–152, doi: https://doi.org/10.1016/j.cirpj.2010.03.006

, Xu

, Zhong

R.Y.

and Wang

, A RFID-enabled positioning system in automated guided vehicle for smart factories, J. Manuf. Syst. 44 (2017), 179–190, doi: https://doi.org/10.1016/j.jmsy.2017.03.009

Hwi Kim

and Hwang

, An adaptive dispatching algorithm for automated guided vehicles based on an evolutionary process, Int. J. Prod. Econ. 60(1) (1999), 465–472.

Oboth

, Batta

and Karwan

, Dynamic conflict-free routing of automated guided vehicles, Int. J. Prod. Res. 37(9) (1999), 2003–2030. doi: 10.1080/002075499190888

Lacomme

, Larabi

and Tchernev

, Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles, Int. J. Prod. Econ. 143(1) (2013), 24–34. doi: https://doi.org/10.1016/j.ijpe.2010.07.012

Aized

, Modelling and performance maximization of an integrated automated guided vehicle system using coloured Petri net and response surface methods, Comput Ind Eng 57 (2009), 822–831.

Kabir

Q.S.

, Three essays on the battery management of automated guided vehicles, (2016).

10.

Kawakami

and Takata

, Battery Life Cycle Management for Automatic Guided Vehicle Systems, in Design for Innovative Value Towards a Sustainable Society, Dordrecht, (2012), 403–408.

11.

Kabir

Q.S.

and Suzuki

, Comparative analysis of different routing heuristics for the battery management of automated guided vehicles, Int. J. Prod. Res. 57(2) (2019), doi: 10.1080/00207543.2018.1475761

12.

Ryck

M.D.

, Versteyhe

and Debrouwere

, Automated guided vehicle systems, state-of-the-art control algorithms and techniques, J. Manuf. Syst. 54 (2020), 152–173. doi: https://doi.org/10.1016/j.jmsy.2019.12.002

13.

McHANEY

, Modelling battery constraints in discrete event automated guided vehicle simulations, Int. J. Prod. Res. 33(11), Art. no. 11, (1995), doi: 10.1080/00207549508904859

14.

Bilge

Ü.

and Ulusoy

, A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS, Oper. Res. 43(6) Art. no. 6, (1995), 10.1287/opre.43.6.1058

15.

Mantel

R.J.

and Landeweerd

H.R.A.

, Design and operational control of an AGV system, Int. J. Prod. Econ. 41(1) (1995), 257–266. doi: https://doi.org/10.1016/0925-5273(95)00018-6

16.

Ulusoy

, Sivrikaya-Şerifoǧlu

and Bilge

Ü.

, A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles, Comput. Oper. Res. 24(4) (1997), 335–351. doi: https://doi.org/10.1016/S0305-0548(96)00061-5

17.

Abdelmaguid

T.F.

, Nassef

A.O.

, Kamal

B.A.

and Hassan

M.F.

, A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles, Int. J. Prod. Res. 42(2) (2004), 267–281. doi: 10.1080/0020754032000123579

18.

Reddy

B.S.P.

and Rao

C.S.P.

, A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS, Int. J. Adv. Manuf. Technol. 31(5) (2006), 602–613, doi: 10.1007/s00170-005-0223-6

19.

Kesen

S.E.

and Baykoç

Ö.F.

, Simulation of automated guided vehicle (AGV) systems based on just-in-time (JIT) philosophy in a job-shop environment, Simul. Model. Pract. Theory 15(3) (2007),272–284, doi: https://doi.org/10.1016/j.simpat.2006.11.002

20.

Zheng

, Xiao

and Seo

, A tabu search algorithm for simultaneous machine/AGV scheduling problem, Int. J. Prod. Res. 52(19) (2014),5748–5763. doi: 10.1080/00207543.2014.910628

21.

Demesure

, Defoort

, Bekrar

, Trentesaux

and Djemaï

, Navigation Scheme with Priority-Based Scheduling of Mobile Agents: Application to AGV-Based Flexible Manufacturing System, J. Intell. Robot. Syst. 82(3) (2016), 495–512. doi: 10.1007/s10846-015-0273-4

22.

Mousavi

, Yap

H.J.

, Musa

S.N.

, Tahriri

and Md Dawal

S.Z.

, Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization, PLOS ONE 12(3) (2017), 1–24. doi: 10.1371/journal.pone.0169817

23.

Kabir

Q.S.

and Suzuki

, Increasing manufacturing flexibility through battery management of automated guided vehicles, Comput. Ind. Eng. 117 (2018), 225–236. doi: https://doi.org/10.1016/j.cie.2018.01.026

24.

Abderrahim

, Bekrar

, Trentesaux

, Aissani

and Bouamrane

, Manufacturing 4.0 Operations Scheduling with AGV Battery Management Constraints, Energies 13(18) Art. no. 18, (2020), doi: https://doi.org/10.3390/en13184948

25.

Zou

W.-Q.

, Pan

Q.-K.

and Wang

, An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery, Knowl.-Based Syst. 218 (2021), 106881, doi: https://doi.org/10.1016/j.knosys.2021.106881

26.

Tsubota

, Osumi

and Kosai

, Characteristics of valve-regulated lead/acid batteries for automotive applications under deep-discharge duty, J. Power Sources 33(1) (1991), Art. no. 1, doi: https://doi.org/10.1016/0378-7753(91)85053-Y

27.

Garey

and Johnson

, Computers and Intractability: A Guide to the Theory of NP-Completeness, (1978).

28.

Naidu

B.R.

, Panda

and Babu

B.C.

, 3 - Dynamic energy management and control of a grid-interactive DC microgrid system, in Smart Power Distribution Systems, Q. Yang, T. Yang, andW. Li, Eds. Academic Press, (2019), 41–67. doi: 10.1016/B978-0-12-812154-2.00003-1

29.

Zhan

, Xu

, Zhang

and Li

, Study on AGVs battery charging strategy for improving utilization, Procedia CIRP 81 (2019), 558–563. doi: https://doi.org/10.1016/j.procir.2019.03.155

30.

Xing

L.-N.

, Chen

Y.-W.

and Yang

K.-W.

, Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling, Appl. Soft Comput. 9(1) (2009), 362–376. doi: https://doi.org/10.1016/j.asoc.2008.04.013

31.

Moslehi

and Mahnam

, A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, Int. J. Prod. Econ. 129(1) (2011), 14–22. doi: https://doi.org/10.1016/j.ijpe.2010.08.004

32.

Fonseca

C.M.

and Fleming

P.J.

, Genetic Algorithms for Multiobjective Optimization: Formulation Discussion and Generalization, in Proceedings of the 5th International Conference on Genetic Algorithms, San Francisco, CA, USA, (1993), 416–423.

33.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput. 6(2) (2002), 182–197. doi: 10.1109/4235.996017

34.

Corne

, Knowles

J.D.

and Oates

M.J.

, The Pareto Envelope-Based Selection Algorithm for Multi-Objective Optimisation, in Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Berlin, Heidelberg, (2000), 839–848.

35.

Jensen

M.T.

, Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms, IEEE Trans. Evol. Comput. 7(5) (2003), 503–515. doi: 10.1109/TEVC.2003.817234

36.

Liu

, Pan

Q.-K.

, Gao

and Li

, Multi-Objective Flexible Job Shop Scheduling Problem Considering Machine Switching Off-On Operation, Procedia Manuf. 39 (2019), 1167–1176, doi: https://doi.org/10.1016/j.promfg.2020.01.353

37.

Bhesdadiya

R.H.

, Trivedi

I.N.

, Jangir

and Kumar

, An NSGA-III algorithm for solving multi-objective economic/environmental dispatch problem, Cogent Eng. 3(1) (2016), 1269383, doi: 10.1080/23311916.2016.1269383

38.

Lee

K.-

, Yamakawa

and Lee

K.-M.

, A genetic algorithm for general machine scheduling problems, in 1998 Second International Conference. Knowledge-Based Intelligent Electronic Systems. Proceedings KES’98 (Cat. No.98EX111), 2 (1998), 60–66, doi: 10.1109/KES.1998.725893

39.

Tuson

, Tabu Search, J. Oper. Res. Soc. 50(1) (1999), 106–107. doi: 10.1057/palgrave.jors.2600048

Automated Guided Vehicles battery management for industry 4.0

Abstract

Keywords

1 Introduction

2 Problem definition

3 Problem modeling and the proposed approach

3.1 Problem modeling

3.1.1 The model of energy efficiency

3.1.4 Automatic battery swap

3.2.1 The proposed NSGA-2

Table 1 Chromosome coding Job 2 1 2 2 3 1 3 AGV 1 2 1 1 2 1 2 AGV speed 0 0 1 0 0 0 1 Battery swap 1 0 3 2 0 3 0 Machine speed 0 1 0 0 1 1 1

3.2.3 Selection strategy of non-dominated solution with the same rank

3.2.4 Workflow of the suggested HNSGA-2(Hybrid NSGA-2)

4 Experiments and analysis

Author contributors

Funding

Footnotes

Acknowledgments

References

Table 1
Chromosome coding

Job 2 1 2 2 3 1 3

AGV 1 2 1 1 2 1 2

AGV speed 0 0 1 0 0 0 1

Battery swap 1 0 3 2 0 3 0

Machine speed 0 1 0 0 1 1 1