# Selective Strategy Differential Evolution for Stochastic Internal Task Scheduling Problem in Cross-Docking Terminals

Authors: Dollaya Buakum; Warisa Wisittipanich
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

This study proposed an algorithm called selective strategy differential evolution (SSDE) to handle the complexity of the stochastic internal task scheduling problem in cross-docking terminals. The aims of this study are to assign workers and transfer equipment to internal operations and sequence those operations under randomness and uncertainty with the purpose to minimise total tardiness. The main feature of SSDE is its ability to adapt itself in order to execute the best search strategy. The proposed algorithm was tested on 16 instances using generated data based on real-case scenarios of a pharmaceutical distribution centre. The results showed the significant performance of SSDE to other existing algorithms in terms of solution quality and computational time. The key success factors of SSDE are the use of various search strategies in a single run and the application of suitable termination conditions.


---

## Body

## 1. Introduction

Warehouse management problem has driven researchers to seek the least-cost operation which optimize ordering and holding costs and maximize space utilization by leveraging existing technologies. A cross-docking strategy is one of the logistics practice of unloading goods from incoming trucks and loading them directly into outbound trucks with little to or storage in between. Since cross-docking does not involve storing goods in the warehouse, costs associated with handling and storage are reduced and deliveries are faster. In addition, cross-docking enables greater throughput without the need for opening up a new warehouse. Undeniably, insufficient operational management in cross-docking may obstruct its successful implementation. Recently, studies concerning operation problems in cross-docking have been addressing the real-world problem or specific conditions. Rijal et al. [1] studied truck scheduling and dock door assignment at unit-load cross-dock terminals where dock doors can operate in a mixed service mode. Zheng et al. [2] addressed the cold-chain cross-docking truck scheduling problem. Shahmardan and Sajadieh [3] investigated a truck scheduling problem at a cross-docking centre where inbound trucks were also used as outbound and they can be partially unloaded. Correa Issi, Linfati, and Escobar [4] proposed a mathematical model for truck scheduling in cross-docking in a mixed service mode dock area of a multinational food company in Chile. Chargui et al. [5] proposed a mathematical model to optimize the scheduling, storage, assignment, and sequencing of trucks at receiving and shipping docks for a problem inspired from a multiple door cross-dock facility of an industrial partner with multiple temporary storage zones. However, there exist some limitations to the aforementioned references. One of the common suggestions from those articles is to incorporate stochastic considerations into the problem to provide more practical and novel directions for future studies. In addition, adding a resource-constrained in the model was suggested by Shahmardan and Sajadieh (2020) as a direction for future research.Task environments in a real-world practice are subject to several uncertainties and randomness. Therefore, a practical model for scheduling problems should be established to address uncertainty issues. Picking orders is typically discussed under the assumptions that processing times and due dates are known in advance and machines are continuously available. However, in practice, some of these assumptions in man-to-goods picking systems are unrealistic. In fact, workers may have different speeds owing to fatigue or other reasons. In addition, workers moving between picking locations can disrupt and lock each other. The phenomenon of pickers locking results in the time loss arising from waiting for the ability to continue the picking process [6].The stochastic internal task scheduling problem is a more practical model to deal with uncertainties and randomness in a real-world environment. This consideration could fill the current research gap in the cross-docking platform. To date, there are few studies on the stochastic internal task scheduling problem in a cross-dock terminal. Buakum and Wisittipanich [7] proposed a mathematical model for stochastic internal task scheduling to minimise the total tardiness of customer orders. The goal of their study was to simultaneously assign internal cross-docking workers and transportation equipment to obtain the optimal internal task schedule in a single unloading activity. Figure 1 represents a single unloading activity in a cross-docking terminal. In the cross-docking terminal, the cross-docking operations can be divided into two phases: incoming and outgoing phases. In the incoming phase, the containers reach the cross-dock with different products. Each incoming container is processed by a breakdown operation such as scanning or sorting processes. In the outgoing phase, customers’ orders are built up. Each customer order is processed by a build-up order operation, and some orders may require value-adding services, such as repacking or labelling.Figure 1
Tasks for a single unloading activity in a cross-docking terminal.In 2020, Buakum and Wisittipanich formulated a mathematical model of stochastic internal task scheduling problems in a cross-docking terminal using chance-constrained programming. In their study, an exact method using an optimisation solver was employed to obtain the optimal solution. The preliminary results showed that the problem was NP-hardness (nondeterministic polynomial-time hardness). The model consumed very high amount of computational time when the problem size slightly increased, and it failed to solve a large-scale case of the real-world problem. As a result, the exact method was not robust for dealing with uncertainty of processing time and due date.Thus, this study focuses on metaheuristic applications to obtain a near-optimal solution within an acceptable computing time. This application aims to apply the stochastic model proposed by Buakum and Wisittipanich [7] in order to schedule large-scale internal tasks for timely medicine delivery to prevent negative effects on patients. Taking inspiration from the aforementioned problem statements, differential evolution (DE), a type of stochastic search and optimisation method, is used in this study. Starting from a population of randomly initialised solutions, the original DE algorithm employs simple mutation and crossover operators to generate new candidate solutions. Therefore, the performance of the DE algorithm is sensitive to the mutation and crossover schemes. Recently, various DE strategies with new mutation and crossover schemes have been introduced to enhance DE searching ability. However, a large amount of time is required to determine the appropriate DE evaluation strategies for specific problems under consideration.To overcome this dilemma, this study proposes a novel self-adaptive and strategy selection-based DE technique called selective strategy differential evolution (SSDE). The main contributions of this study are listed as follows:(i)
The robust methods of the SSDE algorithm is proposed for dealing with uncertainty of processing time and due date; thus, the SSDE can properly handle large-scale internal task scheduling problems in a cross-docking terminal.(ii)
An intelligible modification procedure that transforms classical DE to the SSDE is presented in this work. In addition, the application of suitable termination conditions is implemented in SSDE.(iii)
The development of encoding and decoding procedures is proposed for finding the optimal order-picking operation in a single unloading manner under stochastic environments.The remainder of this paper is organised as follows: Section2 reviews related studies on the internal task scheduling problem in a cross-docking terminal. This section also reviews the modification of the classical DE algorithm and DE applications in cross-docking. Section 3 presents the mathematical model of the problem. Section 4 describes three classical metaheuristics used for experimental comparison in this study. Section 5 introduces the SSDE algorithm, and the solution representation of the encoding and decoding schemes is described in Section 6. A computational experiment using scenarios from a real-case study is reported in Section 7. Finally, the conclusion is provided in Section 8.


## 2. Related Studies

The internal task scheduling problem in cross-dock terminals was first studied by Li et al. [8]. The problem was considered to be a parallel machine scheduling problem. The mathematical model was formulated with the objective of just-in-time shipments, and the resource constraint in the model was limited to the number of workers. Then, two heuristic algorithms such as squeaky wheel optimisation embedded in a genetic algorithm (SWOGA) and linear programming within a genetic algorithm (LPGA) were implemented to solve the problem and compared with solutions obtained from a CPLEX solver. The comparison results showed that the CPLEX solver has limited memory for solving the problem, whereas metaheuristic methods can provide near-optimal solutions for all test problems. Later, Alvarez-Perez et al. [11] proposed another metaheuristic, the reactive greedy randomised adaptive search procedure and tabu search (RGTS), to solve the same problem as that of Li et al. (2004). The results showed that the RGTS obtains better objective values and less computational time than the SWOGA and LPGA in some instances.Workers and transferring tools are both important resources for internal tasks in cross-docking terminals in real-world problems. Recently, the developed mathematical model of internal task scheduling in cross-dock terminals was proposed to simultaneously assign workers and transfer equipment for operations to minimise the makespan [12]. The model was formulated in a deterministic environment; however, tasks in the real-world were operated under a stochastic environment. Therefore, Buakum and Wisittipanich [7] transformed the deterministic model into a stochastic model by using chance-constrained programming to minimise the total tardiness, in which the processing times and due dates of operations were considered as stochastic parameters. An exact method using the LINGO optimisation solver was used to find the optimal solution for the generated data. The results showed that LINGO required high computational time and was terminated with memory insufficiency in a large-scale case of the real-world problem. Several research studies have considered the internal task scheduling problem as a parallel machine scheduling (Li et al. [8] [7, 11, 12]). Afshar-Bakeshloo et al. [9] considered the internal task scheduling problem as single machine scheduling while Hamdi and Tekaya [10] considered the internal task scheduling as flow shop scheduling in deterministic environment.A classical DE was first suggested by Storn and Price [13], which proved its high performance in solving scheduling problems [14–17]. In addition, better DE performance was observed when compared to other evolutionary algorithms (EAs), such as PSO on a suite of 34 widely used benchmark problems [18]. Nevertheless, low convergence speed is a problem of a classical DE, which requires high computational efforts. To overcome this restriction, several variations of the DE algorithm have been suggested to improve the performance of DE by modifying the evolution process during the search or integrating some additional processes into the DE to increase the convergence rate, such as local search [19], external archive [20], or antiaging mechanisms [21]. Pant et al. [22] presented an extensive survey of existence of DE. A number of research articles have been shown through variants of differential evolution like initialization techniques, modifications in mutation schemes, modified crossover schemes, modifications done in selection schemes, changes in parameters, and hybrid variants of different evolution.Consequently, in terms of adaptive DE variants, different adaptation mechanisms have been introduced to dynamically update the DE algorithm to reproduce new generation of vectors without any prior knowledge of the relationship between the algorithm and the characteristics of optimisation problems. The adaptation mechanisms in the DE algorithm can be categorized into three classes as follows.


### 2.1. Parameter Adaptation

The performance of DE highly depends on the control parameters in the mutation operator, scaling factorF, the crossover operator, and crossover rate CR. Therefore, some studies have focused on the modification of control parameters in mutation and crossover operations [20, 23–28]. For example, Huynh et al. [28] proposed Q-learning model; the parameter controller adaptively adjusts the algorithm parameters at runtime using information from previous iterations.


### 2.2. Strategy Adaptation

In 2005, Price et al. [29] proposed other variants of DE derived from the different strategies of mutation and crossover schemes. However, a significant amount of time was required to find the best strategies for each specific problem. In order to automatically select the most suitable strategy while solving a problem without any prior knowledge, some approaches were introduced to apply multistrategies in a single run [30–33]. In the strategy adaptation class, parameter adaptive ability and/or other additional abilities could be implemented along with strategies adaptive ability [34–47]. For example, Do et al. [46] proposed a modified DE by adjusting scale factor F and crossover rate c as well as the mutation and selection phases of the original DE are also replaced by the best individual-based mutation and elitist selection techniques. In addition to adaptive mutation or crossover phases, the adaptive initialization phase was considered in this class. For example, Tang and Lee [47] proposed a straightforward and effective scheme for adaptive initialization and coupled with a linear reduction to the DE population size [26], called L-SHADE, for solving constrained optimisation problems.


### 2.3. Algorithm Adaptation

Since several DE variants have been proposed in recent years, some studies proposed approaches to employ multiple state-of-the-art DE variants for solving particular problems [48, 49].According to the aforementioned references, Buakum and Wisittipanich [33] proposed the modified DE algorithm in the strategy adaptation class which contained both different mutation and crossover schemes in the strategy pool called self-learning differential evolution (SLDE) algorithm. The adaptive ability of SLDE was made by the ranking and updating probability of each constituent strategy in each generation. Thus, both the mutation and crossover operators were adaptable, and the strategy assignment of the proposed algorithm was based on one active strategy. However, SLDE was designed in deterministic aspect only.To present a more practical problem and provide novel directions for addressing this problem, this study consider the stochastic internal task scheduling problem and proposed the modified DE algorithm which extends the SLDE in the stochastic aspect. Then, five metaheuristic algorithms, GA, PSO, DE, RAM-EPSDE, and SSDE are applied in the comparison experiments.


## 2.1. Parameter Adaptation

The performance of DE highly depends on the control parameters in the mutation operator, scaling factorF, the crossover operator, and crossover rate CR. Therefore, some studies have focused on the modification of control parameters in mutation and crossover operations [20, 23–28]. For example, Huynh et al. [28] proposed Q-learning model; the parameter controller adaptively adjusts the algorithm parameters at runtime using information from previous iterations.


## 2.2. Strategy Adaptation

In 2005, Price et al. [29] proposed other variants of DE derived from the different strategies of mutation and crossover schemes. However, a significant amount of time was required to find the best strategies for each specific problem. In order to automatically select the most suitable strategy while solving a problem without any prior knowledge, some approaches were introduced to apply multistrategies in a single run [30–33]. In the strategy adaptation class, parameter adaptive ability and/or other additional abilities could be implemented along with strategies adaptive ability [34–47]. For example, Do et al. [46] proposed a modified DE by adjusting scale factor F and crossover rate c as well as the mutation and selection phases of the original DE are also replaced by the best individual-based mutation and elitist selection techniques. In addition to adaptive mutation or crossover phases, the adaptive initialization phase was considered in this class. For example, Tang and Lee [47] proposed a straightforward and effective scheme for adaptive initialization and coupled with a linear reduction to the DE population size [26], called L-SHADE, for solving constrained optimisation problems.


## 2.3. Algorithm Adaptation

Since several DE variants have been proposed in recent years, some studies proposed approaches to employ multiple state-of-the-art DE variants for solving particular problems [48, 49].According to the aforementioned references, Buakum and Wisittipanich [33] proposed the modified DE algorithm in the strategy adaptation class which contained both different mutation and crossover schemes in the strategy pool called self-learning differential evolution (SLDE) algorithm. The adaptive ability of SLDE was made by the ranking and updating probability of each constituent strategy in each generation. Thus, both the mutation and crossover operators were adaptable, and the strategy assignment of the proposed algorithm was based on one active strategy. However, SLDE was designed in deterministic aspect only.To present a more practical problem and provide novel directions for addressing this problem, this study consider the stochastic internal task scheduling problem and proposed the modified DE algorithm which extends the SLDE in the stochastic aspect. Then, five metaheuristic algorithms, GA, PSO, DE, RAM-EPSDE, and SSDE are applied in the comparison experiments.


## 3. Mathematical Model of the Problem

The problem statement and a mathematical model were taken from Buakum and Wisittipanich [13]. The problem was formulated to minimise the total tardiness of the order-picking operation according to prescriptions in a single unloading activity. In a stochastic environment, processing times and due dates were set as random parameters, and their distributions were assumed to be known in advance. Based on the limited number of workers and transfer equipment, the goal of the formulation was to obtain an optimal schedule to simultaneously assign workers and transfer equipment for handling medicine pallets and prescriptions. The due date of each prescription was set based on the delivery date and patient location. The basic assumptions of the mathematical model were shown as follows:(i)
All workers are identical and 100% reliable.(ii)
No preemptions occur in scheduling.(iii)
The optimal schedule is based on a single unloading activity. Thus, the picking order of each prescription proceeds once the medicine pallets are completely unloaded.In the stochastic model formulation, the processing time for breaking down the medicine pallets and picking order of the prescription was assumed to be random variables subjected to a normal distribution, while the due date of the picking order was assumed to be a random variable subject to a uniform distribution.


### 3.1. Indices

i,i’: incoming medicine pallet (i,i’ = 1,…,n)j,j’: outgoing medicine container (j, j’ = 1,…,o)k: worker (k = 1,…,m)l: transfer equipment; TF (l = 1,…,q)


### 3.2. Decision Variables

xik is 1ifworkerkisassignedforincomingpalleti;otherwise,0yjk is 1ifworkerkisassignedforoutgoingcontainerj;otherwise,0Iii′k is 1ifincomingpalletiprecedesi′bythesameworkerk;otherwise,0Jjj′k is 1ifoutgoingcontainerjprecedesj′bythesameworkerk;otherwise,0aii′l is 1ifincomingpalletiprecedesi′bythesameTFl;otherwise,0bjj′l is 1ifoutgoingcontainerjprecedesj′bythesameTFl;otherwise,0Uikl is 1ifworkerkandtoollareassignedforincomingpalleti;otherwise,0Vjkl is 1ifoutgoingcontainerjisprocessedbyworkerkandTFl;otherwise,0αikl is the start time of medicine incoming pallet i break down by worker k TF lβjkl is the start time of outgoing medicine container j preparation by worker k TF lcikl is the completion time of incoming pallet i break down by team k TF lzjkl is the completion time of outgoing medicine container j by worker k TF ltj is the tardiness of outgoing medicine container j


### 3.3. Parameters

n is the number of incoming medicine palletso is the number of outgoing medicine containersm is the number of workersq is the number of transfer equipmentri is the ready time of incoming medicine pallet i break downpMUi is the mean processing time required to break down incoming medicine pallet ipSTDi is the standard deviation of processing time required to break down incoming medicine pallet ipoMUj is the mean processing time for preparing outgoing medicine container jpoSTDj is the standard deviation of processing time for preparing outgoing medicine container jdUj is the upper point of due date of outgoing medicine container jdLj is the lower point of due date of outgoing medicine container jSij is 1 if outgoing medicine container j is pulled from medicine pallet i; otherwise, 0hil is 1 if incoming medicine pallet i can be transferred by TF l; otherwise, 0fjl is 1 if outgoing medicine container j can be transferred by TF l; otherwise, 0G is a large numberρ is the confidence level for satisfaction with the constraint set, 1 ≥ ρ ≥ 0


### 3.4. Objective Function

(1)Minimise∑j=1ntj,∀j.Equation (1) is the objective function for minimising the total tardiness.


### 3.5. Constraints

Equations (2) and (3) ensure that each incoming medicine pallet and outgoing medicine container must be processed by one worker, respectively.(2)∑k=1mxik=1,∀i,(3)∑k=1myjk=1,∀j.Equations (4)–(7) guarantee the precedence relationship when incoming medicine pallets or outgoing medicine containers are processed with the same worker [11]:(4)xik+xi′k−Iii′k+Ii′ik≤1,∀ii′k,i≠i′,(5)2Iii′k+Ii′ik−xik−xi′k≤0,∀ii′k,i≠i′,(6)yjk+yj′k−Jjj′k+jj′jk≤1,∀jj′k,j≠j′,(7)2Jjj′k+Jj′jk−yjk−yj′k≤0,∀jj′k,j≠j′.Equations (8) and (9) guarantee the relationships when incoming medicine pallets or outgoing medicine containers are transferred by the same transfer equipment, respectively.(8)Uikl+Ui′kl−aii′l+ai′il≤1,∀ii′l,i≠i′,(9)Vjkl+Vj′kl−bjj′l+bj′jl≤1,∀jj′l,j≠j′.Equations (10)–(13) ensure that each incoming medicine pallet or outgoing medicine container must be transferred by only one transfer equipment that is eligible for use.(10)∑k=1m∑l=1qUikl=1,∀i,(11)∑k=1m∑l=1qVjkl=1,∀j,(12)∑k=1m∑l=1qUikl×hil×xik=1,∀i,(13)∑k=1m∑l=1qVjkl×fjl×yik=1,∀j.Equations (14)–(17) state that the probability of the constraint sets must be satisfied by at least ρ to ensure sufficient time between breaking down an incoming medicine pallet and to prepare an outgoing medicine container for each worker or piece of transferring equipment.(14)Probcikl≤ci′kl−pi′+G1−Iii′k≥ρ,∀l,∀ii′k,i≠i′,(15)Probcikl≤ci′kl−pi′+G1−aii′l≥ρ,∀k,∀ii′l,i≠i′,(16)Probzjkl≤zj′kl−poj′+G1−Jjj′k≥ρ,∀ljj′k,j≠j′,(17)Probzjkl≤zj′kl−poj′+G1−bjj′l≥ρ,∀kjj′l,j≠j′.Equations (18) and (19) enforce the start time of breaking down an incoming medicine pallet and start time of preparing an outgoing medicine container, respectively.(18)αikl≥ri,∀ikl,(19)βjkl≥cikl,∀ijkl.Equations (20) and (21) state that the probability of the constraint sets must be satisfied by at least ρ to ensure the ready times of braking down an incoming medicine pallet and preparing an outgoing medicine container, respectively.(20)Probcikl−ri≥pi≥ρ,∀ikl,(21)Probzjkl−cikl≥poj≥ρ,∀jk;i=1st,..,lastpredecessorofj.Equations (22) and (23) state that the probability of the constraint sets must be satisfied by at least ρ to determine the completion time of each incoming medicine pallet and outgoing medicine container, respectively.(22)Probαikl+pi≥ci≥ρ,∀ikl,(23)Probβjkl+poj≥zj≥ρ,∀ikl.Equation (24) ensures that the probability of tardiness for outgoing medicine container j must be satisfied by at least ρ.(24)Probtj≥max0,cjkv−dj≥ρ,∀j,k,v.Equation (25) specifies that all decision variables are binary.(25)yik,Yjk,Iii′k,Jjj′k,aii′l,Ajj′l,Uikl,Vjkl∈0,1.


## 3.1. Indices

i,i’: incoming medicine pallet (i,i’ = 1,…,n)j,j’: outgoing medicine container (j, j’ = 1,…,o)k: worker (k = 1,…,m)l: transfer equipment; TF (l = 1,…,q)


## 3.2. Decision Variables

xik is 1ifworkerkisassignedforincomingpalleti;otherwise,0yjk is 1ifworkerkisassignedforoutgoingcontainerj;otherwise,0Iii′k is 1ifincomingpalletiprecedesi′bythesameworkerk;otherwise,0Jjj′k is 1ifoutgoingcontainerjprecedesj′bythesameworkerk;otherwise,0aii′l is 1ifincomingpalletiprecedesi′bythesameTFl;otherwise,0bjj′l is 1ifoutgoingcontainerjprecedesj′bythesameTFl;otherwise,0Uikl is 1ifworkerkandtoollareassignedforincomingpalleti;otherwise,0Vjkl is 1ifoutgoingcontainerjisprocessedbyworkerkandTFl;otherwise,0αikl is the start time of medicine incoming pallet i break down by worker k TF lβjkl is the start time of outgoing medicine container j preparation by worker k TF lcikl is the completion time of incoming pallet i break down by team k TF lzjkl is the completion time of outgoing medicine container j by worker k TF ltj is the tardiness of outgoing medicine container j


## 3.3. Parameters

n is the number of incoming medicine palletso is the number of outgoing medicine containersm is the number of workersq is the number of transfer equipmentri is the ready time of incoming medicine pallet i break downpMUi is the mean processing time required to break down incoming medicine pallet ipSTDi is the standard deviation of processing time required to break down incoming medicine pallet ipoMUj is the mean processing time for preparing outgoing medicine container jpoSTDj is the standard deviation of processing time for preparing outgoing medicine container jdUj is the upper point of due date of outgoing medicine container jdLj is the lower point of due date of outgoing medicine container jSij is 1 if outgoing medicine container j is pulled from medicine pallet i; otherwise, 0hil is 1 if incoming medicine pallet i can be transferred by TF l; otherwise, 0fjl is 1 if outgoing medicine container j can be transferred by TF l; otherwise, 0G is a large numberρ is the confidence level for satisfaction with the constraint set, 1 ≥ ρ ≥ 0


## 3.4. Objective Function

(1)Minimise∑j=1ntj,∀j.Equation (1) is the objective function for minimising the total tardiness.


## 3.5. Constraints

Equations (2) and (3) ensure that each incoming medicine pallet and outgoing medicine container must be processed by one worker, respectively.(2)∑k=1mxik=1,∀i,(3)∑k=1myjk=1,∀j.Equations (4)–(7) guarantee the precedence relationship when incoming medicine pallets or outgoing medicine containers are processed with the same worker [11]:(4)xik+xi′k−Iii′k+Ii′ik≤1,∀ii′k,i≠i′,(5)2Iii′k+Ii′ik−xik−xi′k≤0,∀ii′k,i≠i′,(6)yjk+yj′k−Jjj′k+jj′jk≤1,∀jj′k,j≠j′,(7)2Jjj′k+Jj′jk−yjk−yj′k≤0,∀jj′k,j≠j′.Equations (8) and (9) guarantee the relationships when incoming medicine pallets or outgoing medicine containers are transferred by the same transfer equipment, respectively.(8)Uikl+Ui′kl−aii′l+ai′il≤1,∀ii′l,i≠i′,(9)Vjkl+Vj′kl−bjj′l+bj′jl≤1,∀jj′l,j≠j′.Equations (10)–(13) ensure that each incoming medicine pallet or outgoing medicine container must be transferred by only one transfer equipment that is eligible for use.(10)∑k=1m∑l=1qUikl=1,∀i,(11)∑k=1m∑l=1qVjkl=1,∀j,(12)∑k=1m∑l=1qUikl×hil×xik=1,∀i,(13)∑k=1m∑l=1qVjkl×fjl×yik=1,∀j.Equations (14)–(17) state that the probability of the constraint sets must be satisfied by at least ρ to ensure sufficient time between breaking down an incoming medicine pallet and to prepare an outgoing medicine container for each worker or piece of transferring equipment.(14)Probcikl≤ci′kl−pi′+G1−Iii′k≥ρ,∀l,∀ii′k,i≠i′,(15)Probcikl≤ci′kl−pi′+G1−aii′l≥ρ,∀k,∀ii′l,i≠i′,(16)Probzjkl≤zj′kl−poj′+G1−Jjj′k≥ρ,∀ljj′k,j≠j′,(17)Probzjkl≤zj′kl−poj′+G1−bjj′l≥ρ,∀kjj′l,j≠j′.Equations (18) and (19) enforce the start time of breaking down an incoming medicine pallet and start time of preparing an outgoing medicine container, respectively.(18)αikl≥ri,∀ikl,(19)βjkl≥cikl,∀ijkl.Equations (20) and (21) state that the probability of the constraint sets must be satisfied by at least ρ to ensure the ready times of braking down an incoming medicine pallet and preparing an outgoing medicine container, respectively.(20)Probcikl−ri≥pi≥ρ,∀ikl,(21)Probzjkl−cikl≥poj≥ρ,∀jk;i=1st,..,lastpredecessorofj.Equations (22) and (23) state that the probability of the constraint sets must be satisfied by at least ρ to determine the completion time of each incoming medicine pallet and outgoing medicine container, respectively.(22)Probαikl+pi≥ci≥ρ,∀ikl,(23)Probβjkl+poj≥zj≥ρ,∀ikl.Equation (24) ensures that the probability of tardiness for outgoing medicine container j must be satisfied by at least ρ.(24)Probtj≥max0,cjkv−dj≥ρ,∀j,k,v.Equation (25) specifies that all decision variables are binary.(25)yik,Yjk,Iii′k,Jjj′k,aii′l,Ajj′l,Uikl,Vjkl∈0,1.


## 4. Classical Metaheuristic Approach

### 4.1. GA

The genetic algorithm (GA) is an adaptive search technique used to solve optimisation problems. Although the GA was developed much earlier than 1975, the basic principles of GA were first emphasized by Holland in 1975 [50]. The GA evolution procedure is based on the laws of natural selection and genetics. In the GA, the solutions are represented as chromosomes. The chromosomes are evaluated for fitness values and ranked from best to worst based on their fitness values.During a genetic operation, chromosomes are selected from the population and recombined to produce offspring that comprise the population of the next generation. This process is accomplished through repeated applications of three genetic operators: selection, crossover, and mutation.


### 4.2. PSO

Particle swarm optimisation (PSO) is a population-based random search method that imitates the physical movements of individuals in a swarm as a searching mechanism. The PSO algorithm was originally proposed by Eberhart and Kennedy in 1995 [51]. Similar to the GA, the population in PSO is initialised with random solutions. In PSO, a solution is represented as a particle, and the population of solutions is called a swarm of particles. Each particle has two main attributes: position and velocity. The difference between PSO and GA lies in evolutionary procedures. The key concept of PSO is that each particle learns from the cognitive knowledge of its experiences (personal best, pbest) and the social knowledge of the swarm (global best, gbest) to guide itself to a better position. A particle moves to a new position using an updated velocity. Once a new position is reached, the best position of each particle and the best position of the swarm are updated as needed. The velocity of each particle is then adjusted based on the particle experiences. This process is repeated until a stopping criterion is satisfied.


### 4.3. DE

Differential evolution (DE), introduced by Storn and Price in 1995 [13], is an evolutionary algorithm designed to deal with continuous optimisation problems. Similar to GA and PSO, DE is a population-based random search algorithm. In DE, the initial D-dimensional vector population of size N is randomly generated and should cover the entire search space. Typically, the DE population evolves through repeated cycles of three main DE operators: mutation, crossover, and selection. However, DE has a different mechanism for generating new solutions explained as follows.


#### 4.3.1. Mutation

A mutant vector is generated by combining three vectors randomly selected from the population, excluding the target vector,XG. Equation (26) shows the combination process of three randomly selected vectors to form the mutant vector VG as follows:(26)VG=X1,G+FX2,G–X3,G,where X1,G, X2,G, and X3,G are three randomly selected vectors from the population in generation G and F is a scale factor which is the main parameter of the DE algorithm.


#### 4.3.2. Crossover

To increase the diversity of the perturbed parameter vectors after mutation, a trial vector,UG, is generated by a crossover operation. The crossover probability (0 ≤ Cr ≤ 1) must be specified for the crossover operator to control the probability of selecting the value in each dimension from a mutant vector. In classic DE, the uniform crossover is employed, and the trial vector is generated using the following equation:(27)Uj,G=Vj,G,ifrandbj≤Cr,Xj,G,Otherwise,where randb(j) is the jth evaluation of a uniform random number generator with the outcome ∈ [0, 1].


#### 4.3.3. Selection

To determine a survival vector for the next generation, a comparison of fitness values between a trial vector,UG, and a target vector, XG, is performed in the selection operator. The simple criterion is to maintain the vector with a better fitness value. If UG yields a better fitness value than XG, XG + 1 is set to UG; otherwise, the old value XG is retained.


### 4.4. RAM-EPSDE

Ranked-Based Mutation Adaptation (RAM), proposed by Leon and Xiong in 2018, is a selection method of different mutation strategies of DE. In RAM, the mutation strategy was selected according to probabilities of each population subgroups. RAM was used to enhance the classical DE algorithm by integrating with other adaptive DE algorithms.Ensemble of Parameters and Mutation Strategies DE (EPSDE) algorithm, proposed by [31], was another adaptive parameter and searching strategies DE. EPSDE randomly selected different mutation and crossover strategies and parameter values in its pool listed as follows:(1)
Mutation strategies are DE/best/2/bin, DE/rand/1, and DE/current-to-rand/1/bin(2)
Crossover strategies are binomial crossover and exponential crossover(3)
Parameter values are the population size (NP = 50), F ∈ [0.5, 0.9], and CR ∈ [0.1, 0.5, 0.9]Later, Leon et al. [19] introduced an integration of RAM into EPSDE and named the algorithm as RAM-EPSDE with an aim to improve the search efficiency.


## 4.1. GA

The genetic algorithm (GA) is an adaptive search technique used to solve optimisation problems. Although the GA was developed much earlier than 1975, the basic principles of GA were first emphasized by Holland in 1975 [50]. The GA evolution procedure is based on the laws of natural selection and genetics. In the GA, the solutions are represented as chromosomes. The chromosomes are evaluated for fitness values and ranked from best to worst based on their fitness values.During a genetic operation, chromosomes are selected from the population and recombined to produce offspring that comprise the population of the next generation. This process is accomplished through repeated applications of three genetic operators: selection, crossover, and mutation.


## 4.2. PSO

Particle swarm optimisation (PSO) is a population-based random search method that imitates the physical movements of individuals in a swarm as a searching mechanism. The PSO algorithm was originally proposed by Eberhart and Kennedy in 1995 [51]. Similar to the GA, the population in PSO is initialised with random solutions. In PSO, a solution is represented as a particle, and the population of solutions is called a swarm of particles. Each particle has two main attributes: position and velocity. The difference between PSO and GA lies in evolutionary procedures. The key concept of PSO is that each particle learns from the cognitive knowledge of its experiences (personal best, pbest) and the social knowledge of the swarm (global best, gbest) to guide itself to a better position. A particle moves to a new position using an updated velocity. Once a new position is reached, the best position of each particle and the best position of the swarm are updated as needed. The velocity of each particle is then adjusted based on the particle experiences. This process is repeated until a stopping criterion is satisfied.


## 4.3. DE

Differential evolution (DE), introduced by Storn and Price in 1995 [13], is an evolutionary algorithm designed to deal with continuous optimisation problems. Similar to GA and PSO, DE is a population-based random search algorithm. In DE, the initial D-dimensional vector population of size N is randomly generated and should cover the entire search space. Typically, the DE population evolves through repeated cycles of three main DE operators: mutation, crossover, and selection. However, DE has a different mechanism for generating new solutions explained as follows.


### 4.3.1. Mutation

A mutant vector is generated by combining three vectors randomly selected from the population, excluding the target vector,XG. Equation (26) shows the combination process of three randomly selected vectors to form the mutant vector VG as follows:(26)VG=X1,G+FX2,G–X3,G,where X1,G, X2,G, and X3,G are three randomly selected vectors from the population in generation G and F is a scale factor which is the main parameter of the DE algorithm.


### 4.3.2. Crossover

To increase the diversity of the perturbed parameter vectors after mutation, a trial vector,UG, is generated by a crossover operation. The crossover probability (0 ≤ Cr ≤ 1) must be specified for the crossover operator to control the probability of selecting the value in each dimension from a mutant vector. In classic DE, the uniform crossover is employed, and the trial vector is generated using the following equation:(27)Uj,G=Vj,G,ifrandbj≤Cr,Xj,G,Otherwise,where randb(j) is the jth evaluation of a uniform random number generator with the outcome ∈ [0, 1].


### 4.3.3. Selection

To determine a survival vector for the next generation, a comparison of fitness values between a trial vector,UG, and a target vector, XG, is performed in the selection operator. The simple criterion is to maintain the vector with a better fitness value. If UG yields a better fitness value than XG, XG + 1 is set to UG; otherwise, the old value XG is retained.


## 4.3.1. Mutation

A mutant vector is generated by combining three vectors randomly selected from the population, excluding the target vector,XG. Equation (26) shows the combination process of three randomly selected vectors to form the mutant vector VG as follows:(26)VG=X1,G+FX2,G–X3,G,where X1,G, X2,G, and X3,G are three randomly selected vectors from the population in generation G and F is a scale factor which is the main parameter of the DE algorithm.


## 4.3.2. Crossover

To increase the diversity of the perturbed parameter vectors after mutation, a trial vector,UG, is generated by a crossover operation. The crossover probability (0 ≤ Cr ≤ 1) must be specified for the crossover operator to control the probability of selecting the value in each dimension from a mutant vector. In classic DE, the uniform crossover is employed, and the trial vector is generated using the following equation:(27)Uj,G=Vj,G,ifrandbj≤Cr,Xj,G,Otherwise,where randb(j) is the jth evaluation of a uniform random number generator with the outcome ∈ [0, 1].


## 4.3.3. Selection

To determine a survival vector for the next generation, a comparison of fitness values between a trial vector,UG, and a target vector, XG, is performed in the selection operator. The simple criterion is to maintain the vector with a better fitness value. If UG yields a better fitness value than XG, XG + 1 is set to UG; otherwise, the old value XG is retained.


## 4.4. RAM-EPSDE

Ranked-Based Mutation Adaptation (RAM), proposed by Leon and Xiong in 2018, is a selection method of different mutation strategies of DE. In RAM, the mutation strategy was selected according to probabilities of each population subgroups. RAM was used to enhance the classical DE algorithm by integrating with other adaptive DE algorithms.Ensemble of Parameters and Mutation Strategies DE (EPSDE) algorithm, proposed by [31], was another adaptive parameter and searching strategies DE. EPSDE randomly selected different mutation and crossover strategies and parameter values in its pool listed as follows:(1)
Mutation strategies are DE/best/2/bin, DE/rand/1, and DE/current-to-rand/1/bin(2)
Crossover strategies are binomial crossover and exponential crossover(3)
Parameter values are the population size (NP = 50), F ∈ [0.5, 0.9], and CR ∈ [0.1, 0.5, 0.9]Later, Leon et al. [19] introduced an integration of RAM into EPSDE and named the algorithm as RAM-EPSDE with an aim to improve the search efficiency.


## 5. SSDE

### 5.1. SSDE Framework

Selective strategy DE (SSDE) is proposed in this study to enhance the DE performance. The modifications to the classical DE algorithm are listed in Table1. In contrast to the classical DE, SSDE uses six different strategies obtaining from the combination of mutation and crossover schemes proposed by Price et al. [29] in order to maintain both the exploitation and exploration abilities of DE [29]. In the classic DE, a new population is generated using one strategy, while a new population of SSDE can be generated using various strategies. The ability to adjust itself to use different potential strategies towards a better solution is the key to enhancing the search speed of the SSDE.Table 1
Modifications in DE algorithm.
No.ModificationClassical DESSDE1Mutation operator1 schemeVG = X1,G + F(X1,G − X2,G)3 schemesVG = X1,G + F(X1,G − X2,G)VG = Xb,G + F(X2,G − X2,G)VG = Xb,G + F(X1,G– X2,G) + F(X3,G − X4,G)2Crossover operator1 schemeBinomial crossover2 schemesBinomial crossoverExponential crossover3Generating new populationUsing a DE strategy in a single runUsing various DE strategies in a single runThere are 6 strategies from the combination of mutation and crossover schemes4Termination condition1 conditionMax iterations3 conditionMax iterationsNo more improvementObjective reach to the targetIn addition, to improve the computational time cost, other termination conditions are added to SSDE as follows:(i)
Maximum iterations: similar to classical DE and other evolutionary algorithms, SSDE algorithm is terminated when the maximum number of iterations is reached(ii)
No further improvement: different from the termination condition of classical DE, the algorithm is terminated when an improvement probability does not increase for a specific number ofn iterations(iii)
The optimal solution is obtained: when the objective reaches the target value, for example, zero tardiness, the algorithm is terminated


### 5.2. SSDE Procedure

The SSDE procedure is divided into two main stages: learning and running. In the learning stage, each strategy is used to perform the evaluation process forn iterations. Then, the ability to achieve a better fitness value for each strategy is recorded according to the improvement probability. Next, the improvement probabilities of all strategies are sorted in ascending order to rank for qualities. In the running stage, the improvement probability is updated for every m iterations. First, the evolutionary process is performed by employing the first-rank strategy. Subsequently, if the improvement probability of the candidate strategy is lower than that of the others after the update, SSDE switches its strategy to the highest improvement probability strategy. This process is repeated until the algorithm terminates. The pseudocode of the SSDE algorithm with the proposed modification is shown in Figure 2.Figure 2
The pseudocode of the SSDE algorithm.


## 5.1. SSDE Framework

Selective strategy DE (SSDE) is proposed in this study to enhance the DE performance. The modifications to the classical DE algorithm are listed in Table1. In contrast to the classical DE, SSDE uses six different strategies obtaining from the combination of mutation and crossover schemes proposed by Price et al. [29] in order to maintain both the exploitation and exploration abilities of DE [29]. In the classic DE, a new population is generated using one strategy, while a new population of SSDE can be generated using various strategies. The ability to adjust itself to use different potential strategies towards a better solution is the key to enhancing the search speed of the SSDE.Table 1
Modifications in DE algorithm.
No.ModificationClassical DESSDE1Mutation operator1 schemeVG = X1,G + F(X1,G − X2,G)3 schemesVG = X1,G + F(X1,G − X2,G)VG = Xb,G + F(X2,G − X2,G)VG = Xb,G + F(X1,G– X2,G) + F(X3,G − X4,G)2Crossover operator1 schemeBinomial crossover2 schemesBinomial crossoverExponential crossover3Generating new populationUsing a DE strategy in a single runUsing various DE strategies in a single runThere are 6 strategies from the combination of mutation and crossover schemes4Termination condition1 conditionMax iterations3 conditionMax iterationsNo more improvementObjective reach to the targetIn addition, to improve the computational time cost, other termination conditions are added to SSDE as follows:(i)
Maximum iterations: similar to classical DE and other evolutionary algorithms, SSDE algorithm is terminated when the maximum number of iterations is reached(ii)
No further improvement: different from the termination condition of classical DE, the algorithm is terminated when an improvement probability does not increase for a specific number ofn iterations(iii)
The optimal solution is obtained: when the objective reaches the target value, for example, zero tardiness, the algorithm is terminated


## 5.2. SSDE Procedure

The SSDE procedure is divided into two main stages: learning and running. In the learning stage, each strategy is used to perform the evaluation process forn iterations. Then, the ability to achieve a better fitness value for each strategy is recorded according to the improvement probability. Next, the improvement probabilities of all strategies are sorted in ascending order to rank for qualities. In the running stage, the improvement probability is updated for every m iterations. First, the evolutionary process is performed by employing the first-rank strategy. Subsequently, if the improvement probability of the candidate strategy is lower than that of the others after the update, SSDE switches its strategy to the highest improvement probability strategy. This process is repeated until the algorithm terminates. The pseudocode of the SSDE algorithm with the proposed modification is shown in Figure 2.Figure 2
The pseudocode of the SSDE algorithm.


## 6. Solution Representation

Since evolutionary algorithms were developed for continuous optimisation, each individual in the population must be transformed into a practical solution. In this study, a solution representation with encoding and decoding was developed to obtain the schedule of internal tasks in a cross-dock terminal with the minimum total tardiness.In the encoding procedure, the number of dimensions was set to be equal to the total number of operations in a single unloading activity. Then, a uniform random number was generated for each dimension in the interval [0, 1]. The pseudocode of the encoding procedure is shown in Figure3.Figure 3
The pseudocode of the encoding procedure.The decoding procedure transforms random numbers of each dimension into a practical solution. The decoding procedure consists of the following steps:Step 1: defining the condition for assigning workers to operations according to the range and the boundary value, which are calculated from the dimension value and number of workers.Step 2: allocating the transferring equipment to operations in a balanced manner. The assignment in this step is based on the dimension value and its eligibility for handling that operation.Step 3: applying a sorting list rule to generate a sequence of operations.Step 4: generating random values of processing times and due dates according to the stochastic environment of the problem. Then, the start time, end time, the tardiness of each operation, and the total tardiness were calculated according to the random processing times and due dates. The pseudocode of the decoding procedure is shown in Figure4.Figure 4
Pseudocode of the decoding procedure.


## 7. Computational Experiments

The computational experiments were divided into two parts. SSDE performance is first tested using benchmark functions. Then, SSDE is used for solving the larger-scale problem of internal tasks scheduling in a cross-docking terminal. The performance of SSDE was evaluated and compared with other metaheuristics, GA, PSO, DE, and RAM-EPSDE. The analysis of numerical results in terms of solution quality and convergence behaviour was also investigated. It is noted that the computational experiments were run on an Intel® Pentium IntelCoreTM i5 8th Gen CPU (1.60 GHz) with 8 GB RAM.


### 7.1. Benchmark Test Functions

In this section, the performance of the SSDE is verified using five benchmark functions. These functions are bound-constrained high-dimensional single-objective optimisation (Dim = 100/1000/2000) of CEC 2020 [52]. The unimodal functions F1 and F2 have only one global optimal value, so they can be used to test the local search ability of the algorithm, while the multimodal functions F3–F5 with more than two optimal values are used to evaluate the global exploration ability. The benchmark functions used in this study are listed in Table 2.Table 2
The benchmark functions.
IDFunctionRangefminF1fx=∑i=1nxi+∏i=1nxi[−10, 10]0F2fx=∑i=1nxi+0.52[−100, 100]0F3x=∑i=1nxi2−10cos2πxi+10[−5.12, 5.12]0F4fx=−20exp−201/n∑i=1nxi2−exp1/n∑i=1ncos2πxi[−32, 32]0F5fx=1/4000∑i=1nxi2−∏i=1ncosxi/i+1[−600, 600]0The numeric experiment results obtained from SSDE were compared with those from other algorithms, including MFO [53], SOGWO [54], PFA [55], EO [56], and MMPA [57]. The parameter setting of the comparison algorithms is shown in Table 3.Table 3
Parameter setting for testing the benchmark functions.
AlgorithmParametersMFOa = −1 (linearly decreased over iterations)SOGWOa = 2 (linearly decreased over iterations)PFA∼EOa1 = 2, a2 = 1, GP = 0.5, t = 1 (nonlinearly decreased over iterations)MMPAFADs = 0.2SSDEF = 0.2, Cr = 0.9These parameters were selected according to the suggestions presented by the developers of the algorithms in the aforementioned references. The population size of each algorithm was set to 30, and the number of iterations was set to 500. Table4 shows the comparison results of SSDE and other existing algorithms obtained from 30 independent runs.Table 4
Comparison results among different algorithms for unimodal and multimodal functions with 100 D/1000 D/2000 D.
IDDimensionsPSOMFOPFASOGWOMMPASSDEMeanStdMeanStdMeanStdMeanStdMeanStdMeanStdBestF11003.87E + 019.22E + 002.42E + 024.33E + 012.51E − 177.89E − 024.16E − 081.45E − 080.00E + 000.00E + 006.70E + 014.39E + 005.17E + 0110001.39E + 035.48E + 01InfeasibleInfeasible6.62E − 013.00E − 010.00E + 000.00E + 001.28E + 036.01E + 011.13E + 0320001.52E + 427.71E + 42InfeasibleInfeasible9.74E + 003.79E + 003.47E − 511.32E − 502.59E + 041.58E + 032.26E + 04F21002.02E + 015.55E + 005.83E + 041.31E + 044.36E + 001.63E + 001.01E + 011.10E + 004.41E + 004.17E − 019.81E + 016.40E + 006.76E + 0110004.10E + 041.86E + 031.30E + 044.94E + 042.29E + 052.74E + 042.03E + 022.03E + 021.94E + 023.20E + 003.63E + 043.08E + 033.10E + 0420001.88E + 056.32E + 035.94E + 066.94E + 041.02E + 069.48E + 048.23E + 048.00E + 044.26E + 022.52E + 007.56E + 057.87E + 045.86E + 05F31006.06E + 027.36E + 018.59E + 027.15E + 014.87E + 026.42E + 017.63E + 005.54E + 000.00E + 000.00E + 002.62E + 022.94E + 011.98E + 0110001.47E + 046.48E + 021.55E + 042.09E + 021.03E + 044.34E + 021.99E + 024.99E + 010.00E + 000.00E + 007.31E + 034.01E + 026.26E + 0320003.15E + 041.03E + 033.31E + 042.74E + 022.35E + 048.57E + 025.59E + 021.07E + 020.00E + 000.00E + 001.92E + 046.38E + 021.72E + 04F41003.73E + 002.96E − 011.99E + 019.58E − 026.18E + 006.46E + 001.44E − 075.68E − 088.88E − 160.00E + 005.41E + 007.62E − 013.76E + 0010001.59E + 012.90E − 012.04E + 012.03E − 011.99E + 015.90E − 011.92E − 022.83E − 038.88E − 160.00E + 008.23E + 005.05E − 016.86E + 0020001.76E + 011.13E − 012.04E + 012.67E − 012.04E + 012.99E − 011.18E − 011.50E − 028.88E − 160.00E + 009.86E + 004.37E − 018.75E + 00F51003.93E − 019.30E − 025.30E + 021.62E + 026.93E − 012.20E − 018.69E − 031.25E − 020.00E + 000.00E + 006.16E + 002.23E + 001.99E + 0010002.80E + 021.71E + 012.45E + 045.24E + 022.16E + 032.18E + 021.55E − 011.16E − 010.00E + 000.00E + 002.84E + 023.26E + 012.13E + 0220007.55E + 023.21E + 015.36E + 046.40E + 029.22E + 038.38E + 021.14E + 002.22E − 010.00E + 000.00E + 007.62E + 021.42E + 024.57E + 02According to the results in Table4, although the SSDE is not able to obtain better solutions than SOGWO and MMPA, it performs better than PSO, MFO, and PFA in both unimodal and multimodal functions. This can be due to the fact that SSDE was particularly developed for solving a combinatorial problem, not a continuous optimisation problem. In the next section, experiments are conducted to demonstrate the performance of SSDE in solving internal tasks scheduling problems in cross-docking terminals.


### 7.2. Parameter Setting and Instances of Internal Task Scheduling Problem

To determine the best set of key parameter values of each algorithm, the Taguchi method was used to reduce the computational load from a full factorial experiment. For each algorithm, a three-factor with four-level experiment was performed on three instances of the scenario of the real-world cross-docking problem. It is noted that, in this study, the parameters of the RAM-EPSDE were set according to the original EPSDE in [31]. In addition, the number of function evaluations (number of iterations × population size) was set to a fixed value of 50,000 for all algorithms. The best parameter values for each algorithm derived from the parameter settings are listed in Table 5.Table 5
Best parameter values for each algorithm.
AlgorithmParameters and their best levelFunction evaluationMutation rateCrossover rate,CrGA100 × 5000.100.3Function evaluationInertia weightAcceleration (Cp,Cg)PSO200 × 2500.6–1.00.7, 0.7Function evaluationScale factor,FCrossover rate,CrDE500 × 1001.00.6RAM-ESPDE1000 × 50[0.5, 0.9][0.1, 0.5, 0.9]SSDE100 × 5002.00.9The computational experiment was performed on 15 instances. Instances 1 to 7 were small-size problems with generated data. Instances 8 to 15 were large-size problems in which the data were derived from the real-scenario of a medicine distribution centre. The problem size is identified by four generated parameters which are number of workers (m), number of transfer equipment (q), number of incoming medicine pallets (n), and number of outgoing medicine containers (o). In addition, to make the problem more practical, in some instances, some customer orders are restricted for the use of particular transferring equipment.


### 7.3. Experimental Results on the Instances of Internal Task Scheduling Problem

In this section, the performance of the proposed SSDE was evaluated using the real-case scenarios of a pharmaceutical distribution centre. The experimental results obtained from the SSDE, in terms of solution quality and computational time, were compared to solutions obtained from the optimisation solver LINGO and other metaheuristics. It is noted that the comparison of all metaheuristics was executed under the same conditions of solution representation and total number of function evaluations. Table6 shows the comparison results of total tardiness among different metaheuristics. The best, average, and standard deviation of total tardiness obtained from those algorithms are also reported.Table 6
Comparison of total tardiness and computational time among different algorithms.
InsProblem sizeLingoGAPSODERAM-EPSDESSDE(m, q, n, o)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)BestAvgSDAvgBestAvgSDAvgBestAvgSDAvgBestAvgSDAvgBestAvgSDAvg12, 2, 3, 30.9735.21.01.40.40.11.01.40.30.21.11.60.50.11.01.30.30.21.01.50.40.222, 2, 4, 39.15137.46.98.50.80.26.38.21.00.26.28.51.30.29.210.01.00.36.88.91.00.332, 2, 4, 412.12513.512.614.00.70.212.913.90.60.212.514.00.50.213.214.00.40.312.714.00.50.343, 3, 4, 530.311169.29.510.50.60.29.010.70.70.39.210.40.60.29.410.30.60.39.310.40.60.353, 3, 4, 629.391452.18.49.50.50.38.59.50.50.38.89.50.40.39.19.70.50.38.59.60.50.363, 3, 4, 772.6315579.718.819.80.50.318.519.60.70.418.419.70.50.321.321.90.40.319.421.41.40.373, 3, 4, 884.41197696.928.429.90.90.328.430.00.90.428.630.00.70.328.429.50.80.428.630.71.20.485,5,40,239n/an/a2359.42675.5150.851.523.9343.5222.455.70.021.629.450.90.033.633.351.30.00.00.011.795,5,40,247n/an/a2779.63315.4189.155.26.6340.2271.456.10.032.731.653.91.9289.6144.854.60.01.23.824.1105,5,40,250n/an/a1724.22113.6219.958.04.7518.4410.557.30.04.66.855.10.08.310.855.90.00.00.09.7115,5,40,256n/an/a3327.23831.0210.659.9104.5757.9399.259.12.664.952.857.623.9307.3156.058.90.00.00.014.8125,5,40,264n/an/a2615.23010.5217.461.262.1464.9292.964.60.027.129.260.30.0129.3163.860.80.00.00.013.1138,8,60,328n/an/a1788.82183.7182.589.812.9426.6370.391.622.1606.8405.392.30.0178.1172.261.30.00.00.022.3148,8,60,370n/an/a5263.16144.6443.3108.91781.73441.9924.6104.91978.33072.9706.9110.21019.22641.6858.3109.40.01.56.442.21510,10,80,518n/an/a12247.514265.1919.1197.37828.511064.31635.4202.89015.910928.31004.5198.86465.99917.71356.9198.60.071.3167.2139.6Notes: (1) n/a was due to LINGO running out of working memory to generate the model. (2) All customer orders in instances 1, 4, 8, 9, 11, 12, and 14 could use any transferring equipment. (3) Some customer orders in instances 2, 3, 5, 6, 7, 10, 13, and 15 could not use some of transferring equipment.It can be seen from Table6 that, for small-size problems, the total tardiness obtained from the metaheuristic method was lower than the exact method. This may be because of a stochastic setting in the mathematical model of the problem. In addition, there was no difference in the recording results including the best, mean, and standard deviation among metaheuristic methods. However, for large-sized problems, LINGO could not find solution since it ran out of memory for generating the model. Among metaheuristics, SSDE generally provided superior solution quality than other algorithms since most of the best, average, and standard deviation values of total tardiness are lower. In addition, SSDE clearly outperformed GA, PSO, classic DE, and RAM-EPSDE by providing solutions with zero tardiness values and zero standard deviations for most instances. It is noteworthy that the quality of the solutions obtained by the metaheuristic methods deteriorated as the problem size increased. This may suggest that newly generated solutions could not escape from the local optimal when the problem became more complex. Therefore, a high diversification for generating new populations leads to a better solution. Consequently, GA provided the highest total tardiness, whereas PSO, classic DE, and RAM-EPSDE yielded lower total tardiness. In conclusion, the numerical results showed that SSDE yielded the best total tardiness and computational time.Moreover, a one-sidedt-test was performed to compare SSDE performance with those of the classical DE algorithm and RAM-EPSDE in terms of the average total tardiness for large-size instances. The t-value according to equation (28) was calculated to confirm the significant difference of compared algorithms.(28)t=x¯Comparedalgo−x¯SSDEsComparedalgo2/nComparedalgo+sSSDE2/nSSDE.In Equation (28), x¯ and s are the mean and standard deviations of total tardiness obtained from 30 replicated runs (n), respectively. It is noteworthy that α is an uncertainty level, set at 5% for this experiment, and n is the degree of freedom (n = 30 − 1 = 29). Hence, the critical value of t0.05, 29 is equal to 1.699. If t-value is higher than the critical value, the average total tardiness obtained from SSDE is significantly lower. Table 7 shows the results of a one-sided t-test of average total tardiness. It can be seen that the t-values of average total tardiness were higher than the critical value for all large-size instances. Thus, it was clear that the total tardiness obtained from the SSDE was significantly lower than that of the classical DE and RAM-EPSDE with 95% confidence level.Table 7
Thet-values of average total tardiness from the one-sided t-test.
InsProblem sizet-value of avg totalt-value of avg total(m, q, n, o)μDE − μSSDEμRAM-EPSDE − μSSDE85-5-40-2394.025.5395-5-40-2475.4210.91105-5-40-2503.714.21115-5-40-2566.7310.79125-5-40-2645.084.32138-8-60-3288.205.66148-8-60-37023.8016.851510-10-80-51858.4039.45In addition, the ability to escape from the local optimal and attain a better solution can be observed by behaviour of convergence. In this study, the comparison of convergence behaviour among different algorithms was investigated using the graph of average fitness values versus the number of function evaluations as shown in Figure5.Figure 5
Comparison of convergence behaviour among algorithms.According to Figure5, GA showed the lowest convergence speed, while PSO and DE yielded better speeds. This may be because the task scheduling problem requires diversification to generate new populations through an evolutionary process and handle a large number of prescriptions. The convergence speeds of RAM-EPSDE were better than the classical DE due to the use of multisearching strategies. Although integrating RAM with EPSDE leads to an improvement of the original DE, crossover strategies and parameter settings are not considered in the adaptation. In contrast, SLDE adapts both of its mutation and crossover strategies. In addition, the parameter values of SLDE were derived from the parameter testing using the real-case study. Consequently, SLDE showed its robustness compared to RAM-EPSDE in internal task scheduling problems. In addition, SSDE showed its outstanding competence in escaping from the local optimal and reaching a better solution. The superior performance of the SSDE is attributed to the application of various modified DE strategies and self-adaptive methods through the evolutionary processes of SSDE.


## 7.1. Benchmark Test Functions

In this section, the performance of the SSDE is verified using five benchmark functions. These functions are bound-constrained high-dimensional single-objective optimisation (Dim = 100/1000/2000) of CEC 2020 [52]. The unimodal functions F1 and F2 have only one global optimal value, so they can be used to test the local search ability of the algorithm, while the multimodal functions F3–F5 with more than two optimal values are used to evaluate the global exploration ability. The benchmark functions used in this study are listed in Table 2.Table 2
The benchmark functions.
IDFunctionRangefminF1fx=∑i=1nxi+∏i=1nxi[−10, 10]0F2fx=∑i=1nxi+0.52[−100, 100]0F3x=∑i=1nxi2−10cos2πxi+10[−5.12, 5.12]0F4fx=−20exp−201/n∑i=1nxi2−exp1/n∑i=1ncos2πxi[−32, 32]0F5fx=1/4000∑i=1nxi2−∏i=1ncosxi/i+1[−600, 600]0The numeric experiment results obtained from SSDE were compared with those from other algorithms, including MFO [53], SOGWO [54], PFA [55], EO [56], and MMPA [57]. The parameter setting of the comparison algorithms is shown in Table 3.Table 3
Parameter setting for testing the benchmark functions.
AlgorithmParametersMFOa = −1 (linearly decreased over iterations)SOGWOa = 2 (linearly decreased over iterations)PFA∼EOa1 = 2, a2 = 1, GP = 0.5, t = 1 (nonlinearly decreased over iterations)MMPAFADs = 0.2SSDEF = 0.2, Cr = 0.9These parameters were selected according to the suggestions presented by the developers of the algorithms in the aforementioned references. The population size of each algorithm was set to 30, and the number of iterations was set to 500. Table4 shows the comparison results of SSDE and other existing algorithms obtained from 30 independent runs.Table 4
Comparison results among different algorithms for unimodal and multimodal functions with 100 D/1000 D/2000 D.
IDDimensionsPSOMFOPFASOGWOMMPASSDEMeanStdMeanStdMeanStdMeanStdMeanStdMeanStdBestF11003.87E + 019.22E + 002.42E + 024.33E + 012.51E − 177.89E − 024.16E − 081.45E − 080.00E + 000.00E + 006.70E + 014.39E + 005.17E + 0110001.39E + 035.48E + 01InfeasibleInfeasible6.62E − 013.00E − 010.00E + 000.00E + 001.28E + 036.01E + 011.13E + 0320001.52E + 427.71E + 42InfeasibleInfeasible9.74E + 003.79E + 003.47E − 511.32E − 502.59E + 041.58E + 032.26E + 04F21002.02E + 015.55E + 005.83E + 041.31E + 044.36E + 001.63E + 001.01E + 011.10E + 004.41E + 004.17E − 019.81E + 016.40E + 006.76E + 0110004.10E + 041.86E + 031.30E + 044.94E + 042.29E + 052.74E + 042.03E + 022.03E + 021.94E + 023.20E + 003.63E + 043.08E + 033.10E + 0420001.88E + 056.32E + 035.94E + 066.94E + 041.02E + 069.48E + 048.23E + 048.00E + 044.26E + 022.52E + 007.56E + 057.87E + 045.86E + 05F31006.06E + 027.36E + 018.59E + 027.15E + 014.87E + 026.42E + 017.63E + 005.54E + 000.00E + 000.00E + 002.62E + 022.94E + 011.98E + 0110001.47E + 046.48E + 021.55E + 042.09E + 021.03E + 044.34E + 021.99E + 024.99E + 010.00E + 000.00E + 007.31E + 034.01E + 026.26E + 0320003.15E + 041.03E + 033.31E + 042.74E + 022.35E + 048.57E + 025.59E + 021.07E + 020.00E + 000.00E + 001.92E + 046.38E + 021.72E + 04F41003.73E + 002.96E − 011.99E + 019.58E − 026.18E + 006.46E + 001.44E − 075.68E − 088.88E − 160.00E + 005.41E + 007.62E − 013.76E + 0010001.59E + 012.90E − 012.04E + 012.03E − 011.99E + 015.90E − 011.92E − 022.83E − 038.88E − 160.00E + 008.23E + 005.05E − 016.86E + 0020001.76E + 011.13E − 012.04E + 012.67E − 012.04E + 012.99E − 011.18E − 011.50E − 028.88E − 160.00E + 009.86E + 004.37E − 018.75E + 00F51003.93E − 019.30E − 025.30E + 021.62E + 026.93E − 012.20E − 018.69E − 031.25E − 020.00E + 000.00E + 006.16E + 002.23E + 001.99E + 0010002.80E + 021.71E + 012.45E + 045.24E + 022.16E + 032.18E + 021.55E − 011.16E − 010.00E + 000.00E + 002.84E + 023.26E + 012.13E + 0220007.55E + 023.21E + 015.36E + 046.40E + 029.22E + 038.38E + 021.14E + 002.22E − 010.00E + 000.00E + 007.62E + 021.42E + 024.57E + 02According to the results in Table4, although the SSDE is not able to obtain better solutions than SOGWO and MMPA, it performs better than PSO, MFO, and PFA in both unimodal and multimodal functions. This can be due to the fact that SSDE was particularly developed for solving a combinatorial problem, not a continuous optimisation problem. In the next section, experiments are conducted to demonstrate the performance of SSDE in solving internal tasks scheduling problems in cross-docking terminals.


## 7.2. Parameter Setting and Instances of Internal Task Scheduling Problem

To determine the best set of key parameter values of each algorithm, the Taguchi method was used to reduce the computational load from a full factorial experiment. For each algorithm, a three-factor with four-level experiment was performed on three instances of the scenario of the real-world cross-docking problem. It is noted that, in this study, the parameters of the RAM-EPSDE were set according to the original EPSDE in [31]. In addition, the number of function evaluations (number of iterations × population size) was set to a fixed value of 50,000 for all algorithms. The best parameter values for each algorithm derived from the parameter settings are listed in Table 5.Table 5
Best parameter values for each algorithm.
AlgorithmParameters and their best levelFunction evaluationMutation rateCrossover rate,CrGA100 × 5000.100.3Function evaluationInertia weightAcceleration (Cp,Cg)PSO200 × 2500.6–1.00.7, 0.7Function evaluationScale factor,FCrossover rate,CrDE500 × 1001.00.6RAM-ESPDE1000 × 50[0.5, 0.9][0.1, 0.5, 0.9]SSDE100 × 5002.00.9The computational experiment was performed on 15 instances. Instances 1 to 7 were small-size problems with generated data. Instances 8 to 15 were large-size problems in which the data were derived from the real-scenario of a medicine distribution centre. The problem size is identified by four generated parameters which are number of workers (m), number of transfer equipment (q), number of incoming medicine pallets (n), and number of outgoing medicine containers (o). In addition, to make the problem more practical, in some instances, some customer orders are restricted for the use of particular transferring equipment.


## 7.3. Experimental Results on the Instances of Internal Task Scheduling Problem

In this section, the performance of the proposed SSDE was evaluated using the real-case scenarios of a pharmaceutical distribution centre. The experimental results obtained from the SSDE, in terms of solution quality and computational time, were compared to solutions obtained from the optimisation solver LINGO and other metaheuristics. It is noted that the comparison of all metaheuristics was executed under the same conditions of solution representation and total number of function evaluations. Table6 shows the comparison results of total tardiness among different metaheuristics. The best, average, and standard deviation of total tardiness obtained from those algorithms are also reported.Table 6
Comparison of total tardiness and computational time among different algorithms.
InsProblem sizeLingoGAPSODERAM-EPSDESSDE(m, q, n, o)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)TardinessRun time (s)BestAvgSDAvgBestAvgSDAvgBestAvgSDAvgBestAvgSDAvgBestAvgSDAvg12, 2, 3, 30.9735.21.01.40.40.11.01.40.30.21.11.60.50.11.01.30.30.21.01.50.40.222, 2, 4, 39.15137.46.98.50.80.26.38.21.00.26.28.51.30.29.210.01.00.36.88.91.00.332, 2, 4, 412.12513.512.614.00.70.212.913.90.60.212.514.00.50.213.214.00.40.312.714.00.50.343, 3, 4, 530.311169.29.510.50.60.29.010.70.70.39.210.40.60.29.410.30.60.39.310.40.60.353, 3, 4, 629.391452.18.49.50.50.38.59.50.50.38.89.50.40.39.19.70.50.38.59.60.50.363, 3, 4, 772.6315579.718.819.80.50.318.519.60.70.418.419.70.50.321.321.90.40.319.421.41.40.373, 3, 4, 884.41197696.928.429.90.90.328.430.00.90.428.630.00.70.328.429.50.80.428.630.71.20.485,5,40,239n/an/a2359.42675.5150.851.523.9343.5222.455.70.021.629.450.90.033.633.351.30.00.00.011.795,5,40,247n/an/a2779.63315.4189.155.26.6340.2271.456.10.032.731.653.91.9289.6144.854.60.01.23.824.1105,5,40,250n/an/a1724.22113.6219.958.04.7518.4410.557.30.04.66.855.10.08.310.855.90.00.00.09.7115,5,40,256n/an/a3327.23831.0210.659.9104.5757.9399.259.12.664.952.857.623.9307.3156.058.90.00.00.014.8125,5,40,264n/an/a2615.23010.5217.461.262.1464.9292.964.60.027.129.260.30.0129.3163.860.80.00.00.013.1138,8,60,328n/an/a1788.82183.7182.589.812.9426.6370.391.622.1606.8405.392.30.0178.1172.261.30.00.00.022.3148,8,60,370n/an/a5263.16144.6443.3108.91781.73441.9924.6104.91978.33072.9706.9110.21019.22641.6858.3109.40.01.56.442.21510,10,80,518n/an/a12247.514265.1919.1197.37828.511064.31635.4202.89015.910928.31004.5198.86465.99917.71356.9198.60.071.3167.2139.6Notes: (1) n/a was due to LINGO running out of working memory to generate the model. (2) All customer orders in instances 1, 4, 8, 9, 11, 12, and 14 could use any transferring equipment. (3) Some customer orders in instances 2, 3, 5, 6, 7, 10, 13, and 15 could not use some of transferring equipment.It can be seen from Table6 that, for small-size problems, the total tardiness obtained from the metaheuristic method was lower than the exact method. This may be because of a stochastic setting in the mathematical model of the problem. In addition, there was no difference in the recording results including the best, mean, and standard deviation among metaheuristic methods. However, for large-sized problems, LINGO could not find solution since it ran out of memory for generating the model. Among metaheuristics, SSDE generally provided superior solution quality than other algorithms since most of the best, average, and standard deviation values of total tardiness are lower. In addition, SSDE clearly outperformed GA, PSO, classic DE, and RAM-EPSDE by providing solutions with zero tardiness values and zero standard deviations for most instances. It is noteworthy that the quality of the solutions obtained by the metaheuristic methods deteriorated as the problem size increased. This may suggest that newly generated solutions could not escape from the local optimal when the problem became more complex. Therefore, a high diversification for generating new populations leads to a better solution. Consequently, GA provided the highest total tardiness, whereas PSO, classic DE, and RAM-EPSDE yielded lower total tardiness. In conclusion, the numerical results showed that SSDE yielded the best total tardiness and computational time.Moreover, a one-sidedt-test was performed to compare SSDE performance with those of the classical DE algorithm and RAM-EPSDE in terms of the average total tardiness for large-size instances. The t-value according to equation (28) was calculated to confirm the significant difference of compared algorithms.(28)t=x¯Comparedalgo−x¯SSDEsComparedalgo2/nComparedalgo+sSSDE2/nSSDE.In Equation (28), x¯ and s are the mean and standard deviations of total tardiness obtained from 30 replicated runs (n), respectively. It is noteworthy that α is an uncertainty level, set at 5% for this experiment, and n is the degree of freedom (n = 30 − 1 = 29). Hence, the critical value of t0.05, 29 is equal to 1.699. If t-value is higher than the critical value, the average total tardiness obtained from SSDE is significantly lower. Table 7 shows the results of a one-sided t-test of average total tardiness. It can be seen that the t-values of average total tardiness were higher than the critical value for all large-size instances. Thus, it was clear that the total tardiness obtained from the SSDE was significantly lower than that of the classical DE and RAM-EPSDE with 95% confidence level.Table 7
Thet-values of average total tardiness from the one-sided t-test.
InsProblem sizet-value of avg totalt-value of avg total(m, q, n, o)μDE − μSSDEμRAM-EPSDE − μSSDE85-5-40-2394.025.5395-5-40-2475.4210.91105-5-40-2503.714.21115-5-40-2566.7310.79125-5-40-2645.084.32138-8-60-3288.205.66148-8-60-37023.8016.851510-10-80-51858.4039.45In addition, the ability to escape from the local optimal and attain a better solution can be observed by behaviour of convergence. In this study, the comparison of convergence behaviour among different algorithms was investigated using the graph of average fitness values versus the number of function evaluations as shown in Figure5.Figure 5
Comparison of convergence behaviour among algorithms.According to Figure5, GA showed the lowest convergence speed, while PSO and DE yielded better speeds. This may be because the task scheduling problem requires diversification to generate new populations through an evolutionary process and handle a large number of prescriptions. The convergence speeds of RAM-EPSDE were better than the classical DE due to the use of multisearching strategies. Although integrating RAM with EPSDE leads to an improvement of the original DE, crossover strategies and parameter settings are not considered in the adaptation. In contrast, SLDE adapts both of its mutation and crossover strategies. In addition, the parameter values of SLDE were derived from the parameter testing using the real-case study. Consequently, SLDE showed its robustness compared to RAM-EPSDE in internal task scheduling problems. In addition, SSDE showed its outstanding competence in escaping from the local optimal and reaching a better solution. The superior performance of the SSDE is attributed to the application of various modified DE strategies and self-adaptive methods through the evolutionary processes of SSDE.


## 8. Conclusion

A novel SSDE algorithm was proposed to handle the complexity of stochastic internal task scheduling problems in cross-dock terminals. The aim of this study was to assign workers and transfer equipment to operations and to sequence those operations to minimise total tardiness. The ability to adapt itself to execute the best strategy was the key to the success of SSDE. In SSDE, fitness values were considered to prioritise the capability of each strategy in the learning stage. Subsequently, the improvement probability was used in the strategy selection during the running stage.In this study, a solution representation with encoding and decoding procedures was also developed to transform a random number into a scheduling solution. Then, an exact method using the LINGO optimisation solver and metaheuristics was applied to solve 15 instance problems using generated data based on a real-case scenario of a pharmaceutical distribution centre. The performance of the SSDE was compared with the results obtained from LINGO and other classical metaheuristics in terms of solution quality and computational time. Based on the experimental results, there was no difference in the solution quality when solving small problems. However, LINGO took a long time to solve small problems and suffered from insufficient working memory when attempting to solve large problems. In contrast, all metaheuristic algorithms required less computing time to provide solutions for all instances. Based on numerical results and convergence behaviour, SSDE significantly outperformed classical DE and other algorithms in terms of both solution quality and computational time. In addition, SSDE presented faster convergence than the other algorithms. Hence, SSDE is an alternative approach for solving stochastic internal task scheduling problems in cross-dock terminals.



---

*Source: 1398448-2022-11-04.xml*