IEEE Robotics & Automation Magazine - June 2023 - 39

PERTURBATION MECHANISM BASED ON RL
The perturbation moves used in this work include two types:
1) randomized shift and 2) randomized swap of orders. The
randomized shift is to randomly select a batch and shift a
random number of orders in the batch to another one. Randomized
swap is to randomly select two batches and swap a
random number of orders among them.
Effective perturbation prevents an algorithm from experiencing
a premature convergence to a local optimum. For
obtaining the appropriate perturbation, we integrate RL into
the ILS to select a perturbation type and determine the perturbation
strength adaptively. Applying RL to create a perturbation
mechanism requires defining a state vector, action set,
and reward function.
The state vector should be able to describe the situation of
the system. In this work, it is described as follows:
()
s = exp) eo,
)
gg z
)
-
g
w Zz z
,
z()
-
w
max max
max
Z
Zmax
3
ALGORITHM 2: Pseudocode of Batching Algorithm.
Require: Set of orders N ,q Set of batches N .e
s #C /2 then
Ensure: Set of batches Ne
1: if
2: Waiting for orders to arrive within the next time window.
3: else if /CC21 #s then
4: The orders are combined into a batch.
5: else
6: while Nq
! Q do
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
if q 1== then
B Nq
=
.
break
else
Select a seed order m based on earliest arrival time.
" ,
Bm ,.lm
while C21 do
==2
for ;;
end if
end for
The similarity values of orders are sorted in a
nonincreasing order.
for ;;
nn qn1 #=++ do
if nm! and lCn
22 ln
2 #+
=+
BB ,.n= "
,
Deleted order n from N .q
break
else
continue
end if
end for
end while
end if
33: end while
34:
= "
35: end if
36: Return Ne
NN , Bee ,
BATCH OPERATIONS
Shift Removing a batch at a position to another one.
Swap Selecting two different batches and exchanging
their positions.
JUNE 2023 IEEE ROBOTICS & AUTOMATION MAGAZINE
39
TABLE 4. The operations performed at the batch level.
then
TABLE 3. The operations performed at the order level.
ORDER OPERATIONS
Shift Removing an order from one batch and shifting it to
other batches.
Swap Swapping two orders belonging to two different
batches.
nn qn1 #=++ do
if nm! then
Calculate the similarity hmn .
(14)
where () RR g) is the currentgz=+jx
().
kkun nNNq
!!~
r
cz
()
z
ly best solution of g(z), and j is a constant coefficient of tardiness.
improved
solutions at the zth iteration. maxw
w z is the number of consecutive iterations without
is the maximum
number allowed for consecutive iterations without improved
solutions. Zmax is the maximum iteration count.
Each action is constructed by using three constant parameters,
v1 , v2 , and v3 . v 1 and 2v are trained to determine
the perturbation iteration and perturbation attempt of the
perturbation strength, respectively.
a perturbation type. The action is updated by using the
f -greedy strategy.
The reward defines an expected benefit of executing action
a in state s at the zth iteration. If the RL's agent can obtain a
better schedule, the reduced fitness value percentage is used as
a reward function. Otherwise, the reward decreases exponentially
according to the number of delayed orders. In addition,
Q is updated as follows:
Qa Qa ra[( (, )( (, l))]Qal
(, )(1 )( ,)ss maxss
a J
! )) )bb c-+ +
l !
(15)
where J is the set of actions. b ! (, ]01 represents learning
rate. c ! [, ]01 represents discount factor.
ACCEPTANCE CRITERION
The acceptance criterion balances the intensification and
diversification of a search process. It defines a solution to be
perturbed at the next iteration. There are three basic criteria:
1) The currently best solution is always accepted, which is
conducive to intensification. 2) The current solution is always
accepted. This could explore new regions of the solution
space, thus increasing diversification. 3) The best or current
solution is selected probabilistically. For example, if
FF (),1
1dd$)
the current solution is accepted; otherwise,
it is not. Such a criterion could make a tradeoff between
intensification and diversification. However, finding the
appropriate value of d is challenging.
v 3 is used to determine
IEEE Robotics & Automation Magazine - June 2023

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2023
