30
I. Chatzikonstantinou et al.
Evaluation of Topological and Task Assignment Solution. To determine
whether a solution is feasible and well-performing, a model-based evaluation
procedure is followed. The procedure consists of the following steps:
1. For each point of interest at each workstation, find and store shortest path
to all targets using A* algorithm.
2. For each agent (worker, robot), find the total workstation assignment count.
Total workstation assignment is influential in calculating the performance of
each agent.
3. For each task/workstation pair, find the processing time given humans
and robots assigned to workstation. Each task is assigned to the assigned
agent with the highest relevant skill. Transport task processing times are
workstation-dependent.
4. For each process/workstation pair, find the allocation factor B pw i.e. what
percentage of the workstation’s time is used for this process?
5. For each process, find per workstation processing rate:
τ pw =
a∈p min a (S t,aw )B pw
6. For each process, find cumulative processing rate:
τ p =
w∈W τ pw
7. For each process and given desired processing rates, find the delay per process:
l p = τ p − Q p if Q P < τ p , 0 otherwise
8. Find cumulative process delay:
l tot =
p l p
The primary constraint here is to ensure that the total lag in processing times
as resulting from the solution evaluation vs. the desired ones expressed in Q tot
is zero, therefore l tot = 0.
To optimize the above problem definition, we use Variable Neighborhood
Search (VNS) [14]. VNS is a greedy hill descent algorithm that alternates
between steps of local search and perturbation (shaking) of solutions to escape
local optima. Search strategies (neighborhoods) are exchanged depending on
their hill descent performance, which is termed change of neighborhood. As part
of this study, we develop a set of search operators that are specific to the problem at hand. The operators are inspired by work on optimizing scheduling problems with VNS [15], and function on problem-specific entities. Specifically, we
define neighborhoods with respect to agent-to-workstation assignments, processto-workstation assignments, and perturbation mechanism based on shuffling of
entire workstation assemblies.
3.2 Detailed Task Scheduling
Following derivation of solution to the topological and task assignment problem
above, the assignments of agents to workstations, as well as task assignments
for each agent are available. These are introduced as constraints to a detailed
scheduling problem that takes precise task sequencing into account.
The detailed scheduling problem is formulated as a Mixed-Integer Linear
Problem (MILP), which is solved using an available third party solver. The
I. Chatzikonstantinou et al.
Evaluation of Topological and Task Assignment Solution. To determine
whether a solution is feasible and well-performing, a model-based evaluation
procedure is followed. The procedure consists of the following steps:
1. For each point of interest at each workstation, find and store shortest path
to all targets using A* algorithm.
2. For each agent (worker, robot), find the total workstation assignment count.
Total workstation assignment is influential in calculating the performance of
each agent.
3. For each task/workstation pair, find the processing time given humans
and robots assigned to workstation. Each task is assigned to the assigned
agent with the highest relevant skill. Transport task processing times are
workstation-dependent.
4. For each process/workstation pair, find the allocation factor B pw i.e. what
percentage of the workstation’s time is used for this process?
5. For each process, find per workstation processing rate:
τ pw =
a∈p min a (S t,aw )B pw
6. For each process, find cumulative processing rate:
τ p =
w∈W τ pw
7. For each process and given desired processing rates, find the delay per process:
l p = τ p − Q p if Q P < τ p , 0 otherwise
8. Find cumulative process delay:
l tot =
p l p
The primary constraint here is to ensure that the total lag in processing times
as resulting from the solution evaluation vs. the desired ones expressed in Q tot
is zero, therefore l tot = 0.
To optimize the above problem definition, we use Variable Neighborhood
Search (VNS) [14]. VNS is a greedy hill descent algorithm that alternates
between steps of local search and perturbation (shaking) of solutions to escape
local optima. Search strategies (neighborhoods) are exchanged depending on
their hill descent performance, which is termed change of neighborhood. As part
of this study, we develop a set of search operators that are specific to the problem at hand. The operators are inspired by work on optimizing scheduling problems with VNS [15], and function on problem-specific entities. Specifically, we
define neighborhoods with respect to agent-to-workstation assignments, processto-workstation assignments, and perturbation mechanism based on shuffling of
entire workstation assemblies.
3.2 Detailed Task Scheduling
Following derivation of solution to the topological and task assignment problem
above, the assignments of agents to workstations, as well as task assignments
for each agent are available. These are introduced as constraints to a detailed
scheduling problem that takes precise task sequencing into account.
The detailed scheduling problem is formulated as a Mixed-Integer Linear
Problem (MILP), which is solved using an available third party solver. The