JOC-2021-02-OA-049

Baxter, Keskinocak, and Singh

Heterogeneous Multi-Resource Allocation with Subset Demand Requests

Heterogeneous Multi-Resource Allocation with Subset Demand Requests

Arden Baxter1,2, Pinar Keskinocak1,2, Mohit Singh1 1H. Milton Stewart School
of Industrial and Systems Engineering and 2 Center for Health and Humanitarian
Systems, Georgia Institute of Technology, Atlanta, GA, 30332,
<EMAIL_ADDRESS>
We consider the problem of allocating multiple heterogeneous resources
geographically and over time to meet demands that require some subset of the
available resource types simultaneously at a specified time, location, and
duration. The objective is to maximize the total reward accrued from meeting
(a subset of) demands. We model this problem as an integer program, show that
it is NP-hard, and analyze the complexity of various special cases. We
introduce approximation algorithms and an extension to our problem that
considers travel costs. Finally, we test the performance of the integer
programming model in an extensive computational study.

deterministic integer programming, resource allocation, network flows,
complexity analysis

##  1 Introduction

In this paper, we introduce the heterogeneous multiple resource type
allocation problem where multiple (e.g., a subset) resource types are
requested by demands ($mRmD$) simultaneously at a specified time and location
for a certain duration and the goal is to maximize total reward from meeting
(as subset of) demands. $mRmD$ has vast applications in resource allocation
and scheduling. For example, hospital operations require the coordinated
scheduling of doctors, nurses, and operating rooms. Similarly, in the home
health care setting (i.e., providing supportive care in the home for illness,
injury, or disability), patients may require visits from various members of
the home health care team (e.g., home health aides, registered nurses,
therapists, physicians, etc.). In some cases, multiple members may be needed
simultaneously; for example, home health aides may need direct supervision by
a registered nurse to perform any task for which they have not received
satisfactory training (Wright (2018)).

Resource allocation and scheduling in networks have been studied across
various applications in the operations research literature, including vehicle
routing, machine scheduling, and robotics task allocation. However, most of
the previous work considered either a single resource type (e.g., vehicle,
ambulance, commodity, etc.) (De Angelis et al. (2007); Huang et al. (2012)) or
independently scheduling/routing multiple resource types (Viswanath and Peeta
(2003)). There remains a significant gap in the literature on the efficient
allocation of resources that may require some level of collaboration or
coordination when the requirements of a certain demand cannot be met by a
single resource type, i.e., resources of distinct types may be needed
simultaneously or sequentially to meet a demand. While some studies
(Rauchecker and Schryen (2019); Altay (2013); Su et al. (2016); Lee et al.
(2013)) explored the idea of collaboration between resources, the majority
focused on tasks that can be done sequentially or independently by different
resources.

We model $mRmD$ as an integer program, show that the problem and some special
cases are NP-hard while other special cases are solvable in polynomial time,
present approximation algorithms with provable bounds, and present results of
a computational study which builds on the theoretical foundation.

The remainder of this paper is structured as follows: Section 2 presents and
discusses relevant literature. Sections 3 and 4 introduce our problem and give
a description of the formulation. Theoretical results are presented in
Sections 5 and 6. In Section 7, we introduce an extension to our problem that
considers travel costs. Finally, a computational study is discussed in Section
8 before concluding in Section 9.

##  2 Literature Review

Problems similar to $mRmD$ have been studied in emergency response and
disaster management (Baxter et al. (2020)), machine and project scheduling,
robotic task allocation, and vehicle routing problems. Some of the theoretical
notions of our work also align with interval graphs (Gilmore and Hoffman
(1964); Olariu (1991); Yannakakis and Gavril (1987); Mertzios (2008); Carlisle
and Lloyd (1995)) where a demand can be represented as an interval with its
start time and service duration.

Multi-task scheduling aims to schedule jobs with different tasks among
multiple machines to minimize the maximum completion time (makespan) (Mao
(1995)) or maximize utility (Fang et al. (2017)). These problems typically do
not consider a spatial component (or sequence-dependent setup times) nor
multiple simultaneous resource requirements. An exception is Chen and Lee
(1999), studying the one-job-on-multiple-machines model where several machines
need to be assigned simultaneously to process each job to minimize the
completion time of all jobs.

Within the emergency/humanitarian response management and vehicle routing
streams, researchers addressed the problem of scheduling/routing single or
multiple heterogeneous resources, with some coordination or collaboration in
the latter case (Rauchecker and Schryen (2019); Altay (2013); Su et al.
(2016); Lee et al. (2013)). De Angelis et al. (2007); Viswanath and Peeta
(2003); Huang et al. (2012) studied vehicle routing and resource allocation
decisions during humanitarian relief, with a single resource type and no
dependencies among multiple resource types. Rauchecker and Schryen (2019)
defined collaboration as tight (all resource units needed by a demand must
arrive simultaneously) or loose (resources may work independently to meet
demand). While most of the previous work focused on loose collaboration,
$mRmD$ calls for tight collaboration. Hashemi Doulabi et al. (2020); Bredström
and Rönnqvist (2008); Di Mascolo et al. (2014) focused on the vehicle routing
problem with synchronized visits (an example of tight collaboration where
customers may require multiple vehicles simultaneously) and considered
objectives including minimizing waiting time/delay in service, travel time, or
costs.

The multi-robot task allocation problem is to allocate several homogeneous or
heterogeneous robots (resources) to a number of tasks (demands) under system
constraints to minimize the makespan (Xu et al. (2016); Gombolay et al.
(2018); Zheng and Koenig (2008); Liu and Kroll (2012)), maximize the utility
(Amador Nelke and Zivan (2017)), or minimize the total distance traveled
(Kartal et al. (2016)). Xu et al. (2016); Zheng and Koenig (2008); Liu and
Kroll (2012) characterize tasks by spatial constraints whereas Amador Nelke
and Zivan (2017); Gombolay et al. (2018); Kartal et al. (2016) consider both
spatial and temporal constraints. Xu et al. (2016); Amador Nelke and Zivan
(2017); Zheng and Koenig (2008) consider multi-robot tasks, which may require
multiple homogeneous (Amador Nelke and Zivan (2017); Xu et al. (2016); Zheng
and Koenig (2008)) or heterogeneous (Amador Nelke and Zivan (2017)) robots to
be completed. In contrast to our study, in (Amador Nelke and Zivan (2017)) a
robot can delay the start or interrupt the service of a task for a penalty,
and all tasks are eventually completed, with the goal of maximizing the total
utility.

##  3 Problem Description

A set of demands ($D$) has to be processed by a set of resource types ($R$).
Each resource type $r\in R$ has a set of starting locations, $S^{r}$, and
$l_{s}^{r}$ resources at each starting location $s\in S^{r}$, i.e., there are
$\sum\limits_{s\in S^{r}}l_{s}^{r}$ resources of type $r\in R$. A demand $d\in
D$ requires a single unit of resource types $M_{d}\subseteq R$ simultaneously
at time $\tau_{d}$ for a duration of $\Delta_{d}$ (service time), resulting in
a reward of $w_{d}$ only if met on time. Travel time between any two locations
$x$ and $y$ is denoted by $f_{xy}$ (e.g., $f_{ij}$ denotes the travel time
between the locations of demands $i$ and $j$ and $f_{sd}$ denotes the travel
time between a resource’s starting location $s$ and the location of demand
$d$). The goal is to assign resources to demands to maximize the total reward
of meeting (a subset of) demands. The notation is summarized in Table 1.

###### Definition 3.1

An instance $\mathcal{I}$ of $mRmD$ is defined as (i) sets $D,R,S^{r}$ for all
$r\in R$, and $M_{d}$ for all $d\in D$, (ii) integer-valued parameters
$l_{s}^{r}$ for all $s\in S^{r},r\in R$ and $\tau_{d},\Delta_{d},w_{d}$ for
all $d\in D$, and (iii) integer-valued travel times, $f_{xy}$, between any two
locations $x$ and $y$.

Pre-processing: Note that an instance $\mathcal{I}$ of $mRmD$ may be described
as a directed acyclic graph. Nodes represent the resource starting locations
$S^{r},r\in R$ and demands $d\in D$. Then, we may create arcs $(i,j)$ between
two demand nodes $i$ and $j$ if and only if demand $j$ can be served
immediately after demand $i$ by a resource, i.e.,
$\tau_{i}+\Delta_{i}+f_{ij}\leq\tau_{j}$. Further, we create arcs $(s,d)$
between a resource starting location node $s$ and a demand node $d$ if and
only if a resource from that starting location can serve demand $d$, i.e.,
$f_{sd}\leq\tau_{d}$. We introduce pre-processing adjacency matrices $A$ and
$B$ to determine the arcs $(i,j)$ and $(s,d)$ created in the directed graph,
respectively. That is, matrix $A$ has a row and column for each demand and
cell $A_{ij}=1$ if and only if demand $j$ can be served immediately after
demand $i$ and the resource type requirements of $i$ and $j$ intersect. Matrix
$B$ has a row for each resource’s starting location, a column for each demand,
and cell $B_{sd}=1$ if and only if a resource at starting at location $s$ can
serve demand $d$ (on time, if $d$ was the first demand to be served by this
resource). The pre-processing adjacency matrices are formally defined as
follows:

$\displaystyle A_{ij}$ $\displaystyle=\begin{cases}1,\text{ if}\hskip
10.00002pt\tau_{i}+\Delta_{i}+f_{ij}\leq\tau_{j},\hskip 10.00002ptM_{i}\cap
M_{j}\neq\emptyset\\\ 0,\text{ otherwise}\end{cases}$ $\displaystyle i,j\in D$
$\displaystyle B_{sd}$ $\displaystyle=\begin{cases}1,\text{ if}\hskip
10.00002ptf_{sd}\leq\tau_{d},s\in S^{r},r\in M_{d}\\\ 0,\text{
otherwise}\end{cases}$ $\displaystyle s\in S^{r},r\in R,d\in D$

Note that since arcs in our directed graph were only created if demands could
be initially served by a resource, or served back-to-back by a resource, then
any path in the graph is a feasible schedule for a resource that ensures all
demands are served on time and for their service duration.

###### Definition 3.2

A feasible solution for $mRmD$ is defined as a set of paths from which it is
easy to build in polynomial time the set of demands that is met.

##  4 Integer Programming Formulation

Table 1: Notation for problem description and IPM $D$ | Set of demands
---|---
$R$ | Set of resource types
$S^{r}$ |  Set of starting locations for $r\in R$
$l_{s}^{r}$ |  Number of resources of type $r\in R$ starting at location $s\in S^{r}$
$f_{ij}$ |  Travel time between $i\in\\{\cup_{r\in R}S^{r}\\}\cup D,j\in D$
$M_{d}$ |  Subset of resources required by $d\in D$
$\tau_{d}$ |  Service start time for $d\in D$
$\Delta_{d}$ |  Service duration for $d\in D$
$w_{d}$ |  Reward for meeting $d\in D$
$\boldsymbol{y_{d}}$= | $\begin{cases}1,\text{ if demand }d\text{ is satisfied}\\\ 0,\text{ otherwise}\hskip 108.00018ptd\in D\end{cases}$
$\boldsymbol{x_{ij}^{r}}$= | $\begin{cases}1,\text{ if resource type }r\text{ serves demand }\\\ \hskip 18.00003ptj\text{ after demand }i\\\ 0,\text{ otherwise}\hskip 108.00018pti,j,r:A_{ij}=1,r\in M_{i}\cap M_{j},i,j\in D\\\ \end{cases}$
$\boldsymbol{x_{sd}^{r}}$= | $\begin{cases}1,\text{ if resource type }r\\\ \hskip 18.00003pt\text{from starting location }s\\\ \hskip 18.00003pt\text{initially serves demand }d\\\ 0,\text{ otherwise}\hskip 108.00018pts,d,r:B_{sd}=1,s\in S^{r},r\in M_{d},d\in D\\\ \end{cases}$
$\boldsymbol{x_{dt}^{r}}$= | $\begin{cases}1,\text{ if resource type }r\\\ \hskip 18.00003pt\text{serves demand }d\text{ last}\\\ 0,\text{ otherwise}\hskip 108.00018ptr\in M_{d},d\in D\\\ \end{cases}$

In this section, we present an integer programming model (IPM) for $mRmD$. For
an overview of the notation and description of the decision variables, please
refer to Table 1. Given our description of a an instance of $mRmD$ and its
feasible solution in Section 3, $x$ variables describe the arcs traversed by
resources and $y$ denotes whether or not a demand node was visited by all of
its required resource types. Note that we use $t$ to denote a dummy sink.

$\displaystyle\max~{}\sum_{d\in D}y_{d}w_{d}$ (1)

s.t.

$\displaystyle\sum_{d\in D|B_{sd}=1}x_{sd}^{r}\leq l_{s}^{r}$ $\displaystyle
s\in S^{r},r\in R$ (2) $\displaystyle\sum_{s\in
S^{r}|B_{si}=1}x_{si}^{r}+\sum_{h\in D|A_{hi}=1}x_{hi}^{r}=\sum\limits_{j\in
D|A_{ij}=1}x_{ij}^{r}+x_{it}^{r}$ $\displaystyle r\in M_{i},i\in D$ (3)
$\displaystyle\sum_{s\in S^{r}|B_{si}=1}x_{si}^{r}+\sum_{h\in
D|A_{hi}=1}x_{hi}^{r}\geq y_{i}$ $\displaystyle r\in M_{i},i\in D$ (4)
$\displaystyle y_{d}\in\\{0,1\\}$ $\displaystyle d\in D$ (5) $\displaystyle
x_{sd}^{r}\in\\{0,1\\}$ $\displaystyle B_{sd}=1,s\in S^{r},r\in M_{d},d\in D$
(6) $\displaystyle x_{ij}^{r}\in\\{0,1\\}$ $\displaystyle A_{ij}=1,r\in
M_{i}\cap M_{j},i,j\in D$ (7) $\displaystyle x_{dt}^{r}\in\\{0,1\\}$
$\displaystyle r\in M_{d},d\in D$ (8)

The objective function (1) of IPM is to maximize the overall reward obtained
from satisfying demands. Constraints (2) ensure that the number of resources
that leave starting location $s$ is less than or equal to the number of
resources available at that location. Constraints (3) maintain flow
conservation, i.e., the flow of resources arriving to and leaving a demand
must be equal. Constraints (4) enforce that a demand is satisfied only if it
has been serviced by all of its required resource types. Domain constraints
for the variables are given in (5)-(8).

Another valid formulation is to consider time indices and define variables for
whether a specific resource of a certain type is at a given location at each
time index (see Appendix 10 for details). However, this formulation could
involve significantly more variables and constraints than IPM and is
computationally prohibitive, as shown in Table 8 of Appendix 10.

##  5 Complexity Results

First, we show complexity results for $mRmD$, including flow decomposition
techniques to determine the feasibility of serving all demands in an $mRmD$
instance. Then we show that $mRmD$ cannot be approximated within a certain
order. Finally, we show complexity results for special cases of $mRmD$, which
are then used in later sections. Tables 2 and 3 summarize $mRmD$ and some of
its special cases and corresponding complexity results shown in this section.

Table 2: Special Cases of the Problem Name | Description
---|---
$1R1D$ |  Single resource type; this is equivalent to $1RmD$.
$mR1D$ | Multiple resource types, each demand requires a single resource type.
$2RmD$ | Two resource types, each demand requires either one or both resource types.
$mR\\{\text{1 or all}\\}D$ | Multiple resource types, each demand requires either one or all resource types.
$mR\\{\text{1 or 2}\\}D$ | Multiple resource types, each demand requires either one or two resource types.
$mRmD$ |  | Multiple resource types, each demand requires a subset. This is the general case.
---
Table 3: Summary of Complexity Results Name |  | Travel
---
Time
| Service
---
Time
| Demand
---
Start Time
Theorem | Complexity
$1R1D$ | any | any | any | 5.16 | P
$mR1D$ | any | any | any | 5.16 | P
$2RmD$ | 0 | $\infty$ | 0 | 5.12 | P
$2RmD$ | 0 | 1 | any | 5.14 | P
$2RmD$ | any | any | any | 5.1 | NP-hard
$mR\\{\text{1 or all}\\}D$ | 0 | $\infty$ | 0 | 5.12 | P
$mR\\{\text{1 or all}\\}D$ | 0 | 1 | any | 5.14 | P
$mR\\{\text{1 or 2}\\}D$ | any | any | any | 5.10 | NP-hard
$mRmD$ | any | any | any |  5.1,5.8 | NP-hard

###### Theorem 5.1

$mRmD$ is NP-hard, for $|R|\geq 2$.

###### Proof 5.2

Proof. Refer to Appendix 11.1 for the details.

###  5.1 Flow Decomposition

In this subsection, we introduce flow decomposition techniques to determine
the feasibility of serving all demands in $mRmD$ instances. We first define
some additional notation that is used here, as well as in Section 6. Let $|R|$
be the number of resource types (labeled $1,2,\ldots,|R|)$ and $D^{r}\subseteq
D$ be the set of demands that require a resource unit of type $r\in R$, i.e.,
$D^{r}\coloneqq\\{i\in D|r\in M_{i}\\}$.

###### Theorem 5.3

The convex hull induced by the feasible points of IPM remains the same when
the $x$ variables are relaxed.

###### Proof 5.4

Proof. Consider the convex hull induced by the feasible points of IPM. We show
that when the $x$ variables are relaxed, the extreme points remain the same.
Let the binary $y$ variables be fixed (i.e., the demands met are known). In
the IPM, when $y$ variables are fixed, the objective function (1) becomes
fixed, constraints (5) are removed, and the formulation can be decomposed into
$|R|$ maximization problems as follows

$\displaystyle\max~{}$ $\displaystyle 0$ (1a)

s.t.

$\displaystyle\sum_{d\in D^{r}|B_{sd}=1}x_{sd}^{r}\leq l_{s}^{r}$
$\displaystyle s\in S^{r}$ (2a) $\displaystyle\sum_{s\in
S^{r}|B_{si}=1}x_{si}^{r}+\sum_{h\in
D^{r}|A_{hi}=1}x_{hi}^{r}=\sum\limits_{j\in
D^{r}|A_{ij}=1}x_{ij}^{r}+x_{it}^{r}$ $\displaystyle i\in D^{r}$ (3a)
$\displaystyle\sum_{s\in S^{r}|B_{si}=1}x_{si}^{r}+\sum_{h\in
D^{r}|A_{hi}=1}x_{hi}^{r}\geq y_{i}$ $\displaystyle i\in D^{r}$ (4a)
$\displaystyle x_{sd}^{r}\in\\{0,1\\}$ $\displaystyle B_{sd}=1,s\in S^{r},d\in
D^{r}$ (6a) $\displaystyle x_{ij}^{r}\in\\{0,1\\}$ $\displaystyle
A_{ij}=1,i,j\in D^{r}$ (7a) $\displaystyle x_{dt}^{r}\in\\{0,1\\}$
$\displaystyle d\in D^{r}$ (8a)

We denote this formulation as IPM-R; note that it is a feasibility problem.

###### Lemma 5.5

IPM-R can be modeled and solved as a MCF.

###### Proof 5.6

Proof See Appendix 11.2 for the details.

Since IPM-R can be modeled and solved as a MCF (Lemma 5.5), then the $x$
variables can be relaxed and maintain the same extreme points.

Note that when all demands can be satisfied in an instance of $mRmD$, this is
equivalent to setting all the $y$ variables to 1 and modeling the instance as
$|R|$ feasibility problems that can be solved in polynomial time.

###### Corollary 5.7

The feasibility of serving all demands of an $mRmD$ instance can be determined
in polynomial time.

Next we show that it is hard to even approximately solve $mRmD$ under natural
complexity theoretic assumptions.

###### Theorem 5.8

$mRmD$ cannot be approximated within
$O(\min\\{|R|^{\frac{1}{2}-\epsilon},|D|^{1-\epsilon}\\})$ unless $NP\subseteq
ZPP$ (for every $\epsilon>0$), where $|R|$ is the number of resource types and
$|D|$ is the number of demands.

###### Proof 5.9

Proof. See Appendix 11.3.

For the remainder of this section, we present complexity results for special
cases of $mRmD$ showing that not only the general problem but even very
special cases remain NP-hard. Moreover, we identify other special cases that
are solvable in polynomial time.

###### Theorem 5.10

$mR\\{\text{1 or 2}\\}D$ is NP-hard.

###### Proof 5.11

Proof. Refer to Appendix 11.4 for the details.

###### Theorem 5.12

The special case of $mR\\{\text{1 or all}\\}D$ where travel times are zero,
service times are infinite, and all demands have the same service start time
is solvable in polynomial time.

###### Proof 5.13

Proof. See Appendix 11.5.

###### Theorem 5.14

The special case of $mR\\{\text{1 or all}\\}D$ where travel times are zero and
service times are one is solvable in polynomial time.

###### Proof 5.15

Proof. Since all service times are one and service start times are integral,
then we can group demands by their start times and apply Algorithm
$\mathcal{E}$ (introduced in Appendix 11.5) to each independent group of
demands.

###### Theorem 5.16

$1R1D$ and $mR1D$ are solvable in polynomial time.

###### Proof 5.17

Proof.$1R1D$ can be modeled as a minimum cost flow (MCF) problem on a directed
acyclic graph. See Appendix 11.6. $mR1D$ can be decomposed into $m$
independent $1R1D$ problems, which are solvable in polynomial time.

MCF problems can be solved in polynomial time (Ahuja et al. (1993)). For
example, the minimum mean cycle-canceling algorithm is a strongly polynomial
algorithm which runs in $O(m^{2}n\log n)$ time, where $n,m$ are the number of
nodes and arcs, respectively, in the network (Gauthier et al. (2015)).

Observation 1. If the travel times are zero, then $1R1D$ can be formulated as
a maximum weighted coloring problem on an interval graph. See Appendix 11.7.

Observation 2. If the travel times are not zero, $1R1D$ cannot be formulated
as a maximum weighted coloring problem on an interval graph. This can been
shown simply through the use of counterexamples and the characterizations of
interval graphs (Gilmore and Hoffman (1964)).

##  6 Approximation Algorithms

In this section, we present approximation algorithms for special cases of
$mRmD$ and prove performance guarantees. Table 4 presents a summary of the
results.

Table 4: Summary of Approximation Algorithm Results Name | Theorem | Result |  | Resource
---
Starting Location
Algorithm $\mathcal{A}$ | 6.2 |  $|R|$-approx. | same
Algorithm $\mathcal{B}$ | 6.7 |  $\chi$-approx. | same
Algorithm $\mathcal{C}$ | 6.13 |  $\frac{a}{b}$-approx. | same
Bicriteria | 6.20 |  $\Big{(}(1-\frac{1}{k}),(\frac{1}{1-k\epsilon})\Big{)}$-bicriteria approx. | any

In the remainder of this section, we use the following notation. Let $m_{i}$
be the number of resources of type $i$ for $i=1,\ldots,|R|$. Without loss of
generality, we assume that $m_{1}\leq m_{2}\leq\ldots\leq m_{|R|}$. Let sub-
problem $1R1D^{r}$ refer to a $1R1D$ problem instance that arises from the
$mRmD$ instance at hand by considering only the $r^{th}$ resource type
($m_{r}$ resources) and the corresponding subset of relevant demands $D^{r}$,
as defined in Section 5.1. Let $OPT(\mathcal{I})$ represent the optimal
objective value for instance $\mathcal{I}$ of $mRmD$. Similarly, let
$\chi(\mathcal{I})$ represent the objective value of the solution produced by
applying Algorithm $\chi$ to instance $\mathcal{I}$ of $mRmD$.

###### Definition 6.1

An $\alpha$-approximation algorithm for $mRmD$, where $\alpha>1$, is an
algorithm that for every instance of $mRmD$, returns a feasible solution with
objective value at least $\frac{1}{\alpha}$ times the optimal objective.
Moreover the running time of the algorithm is polynomial in the size of the
instance.

Input : $\mathcal{I}$

1 $\mathcal{A}$$(\mathcal{I})\leftarrow 0$

2 for  _$1\leq r\leq|R|$_ do

3 Solve $1R1D^{r}$; Let $\mathcal{A}$${}_{r}(\mathcal{I})$ denote the
objective value.

4 if  _$\mathcal{A}$ ${}_{r}(\mathcal{I})\geq$ $\mathcal{A}$$(\mathcal{I})$_
then

5 $\mathcal{A}$$(\mathcal{I})\leftarrow$$\mathcal{A}$${}_{r}(\mathcal{I})$

6

7 end if

8 $D\leftarrow D\setminus D^{r}$

9 end for

Output: $\mathcal{A}$$(\mathcal{I})$

Algorithm 1 $\mathcal{A}$

Algorithm $\mathcal{A}$ Description: Algorithm $\mathcal{A}$ iterates through
the $|R|$ resource types and solves $1R1D^{r}$ to determine the value of each
resource type. The algorithm then picks the best resource type found and
serves the optimal set of demands that request that type.

###### Theorem 6.2

Algorithm $\mathcal{A}$ is an $|R|$-approximation algorithm for $mRmD$
instances with the same starting location for every resource.

###### Proof 6.3

Proof. First note that using Algorithm $\mathcal{A}$, we may construct a
feasible solution to instance $\mathcal{I}$ of $mRmD$ with an objective value
of $\mathcal{A}$($\mathcal{I})$. Because all resources have the same starting
location and demands $D^{r}$ only request resource type $r$ or larger (where
larger resource types have at least as many resources as type $r$), then all
other resource types larger than $r$ may follow the same schedule determined
by the solution to $1R1D^{r}$ to ensure all demands are met by their requested
resource types. Thus, the feasible solution will consist of the paths from the
$1R1D^{r}$ sub-problem that produced the maximum objective value for all
resource types greater than or equal to $r$.

Now, we may partition the optimal objective value $OPT(\mathcal{I})$ for
instance $\mathcal{I}$ of $mRmD$ into values
$OPT_{r}(\mathcal{I}),r=1,\ldots,|R|$, such that
$\sum_{i=1}^{|R|}OPT_{r}(\mathcal{I})=OPT(\mathcal{I})$ and each
$OPT_{r}(\mathcal{I})$ represents the objective value of all demands met whose
smallest resource type requests is $r$.

###### Lemma 6.4

$\mathcal{A}$${}_{r}(\mathcal{I})\geq OPT_{r}(\mathcal{I})$ for
$r=1,\ldots,|R|$.

###### Proof 6.5

Proof. Clearly, $OPT_{r}(\mathcal{I})$ is a feasible objective value for the
$r^{th}$ iteration of Algorithm $\mathcal{A}$, as at the end of each
iteration, we remove $D^{r}$ from $D$. That is, the sets of demands considered
in each iteration of Algorithm $\mathcal{A}$ are also partitioned according to
the indices of their requested resource types. However,
$\mathcal{A}$${}_{r}(\mathcal{I})$ is the optimal objective value of the
$r^{th}$ iteration of Algorithm $\mathcal{A}$ and so
$\mathcal{A}$${}_{r}(\mathcal{I})\geq OPT_{r}(\mathcal{I})$.

Further, $\mathcal{A}$$(\mathcal{I})\geq$$\mathcal{A}$${}_{r}(\mathcal{I})$
for $r=1,\ldots,|R|$ and so we have

$\sum_{r=1}^{|R|}\text{$\mathcal{A}$}(\mathcal{I})\geq\sum_{r=1}^{|R|}\text{$\mathcal{A}$}_{r}(\mathcal{I})\geq\sum_{r=1}^{|R|}OPT_{r}(\mathcal{I})=OPT(\mathcal{I}).$

This implies

$|R|\cdot\text{$\mathcal{A}$}(\mathcal{I})\geq OPT(\mathcal{I})$

and so, dividing both sides by $|R|$, we obtain

$\text{$\mathcal{A}$}(\mathcal{I})\geq\frac{OPT(\mathcal{I})}{|R|}.\Halmos$

###### Remark 6.6

Note that Algorithm $\mathcal{A}$ can be solved in polynomial time as it
relies on solving $|R|$ MCF problems.

For a problem instance $\mathcal{I}$ of $mRmD$, we create a conflict graph
$G=(V,E)$ as follows:
Nodes
Create a node $v=M_{j}$ for each unique $M_{j}$, $j\in D$
Arcs
$(u,v)\in E$ if $u\cap v\neq\emptyset$, $u,v\in V$
Let $\bar{D}^{v}\coloneqq\\{d\in D|M_{d}=v\\}$ for all $v\in V$ and the sub-
problem $1R1\bar{D}^{v}$ refer to a $1R1D$ problem instance that arises from
the $mRmD$ instance at hand by considering all resources of type $i$ where $i$
is the smallest index in set $v$ and the corresponding subset of relevant
demands $\bar{D}^{v}$.

1 Suppose there exists a $\chi$-coloring of $G$. Label the colors
$1,2,\ldots,\chi$. Let $S_{i}$ be the set of nodes that are colored $i$.

Input : $\mathcal{I},G,\chi$, $S_{i}$, $i\in\\{1,2,\ldots,\chi\\}$

2 $\mathcal{B}$$(\mathcal{I})\leftarrow 0$

3 for  _$1\leq i\leq\chi$_ do

4 for  _$v\in S_{i}$_ do

5 Solve $1R1\bar{D}^{v}$; Let $\mathcal{B}$${}_{v}(\mathcal{I})$ denote the
objective value.

6

7 end for

8 if  _$\sum_{v\in
S_{i}}\text{$\mathcal{B}$}_{v}(\mathcal{I})\geq\text{$\mathcal{B}$}(\mathcal{I}):$_
then

9 $\text{$\mathcal{B}$}(\mathcal{I})\leftarrow\sum_{v\in
S_{i}}\text{$\mathcal{B}$}_{v}(\mathcal{I})$

10 end if

11

12 end for

Output: $\text{$\mathcal{B}$}(\mathcal{I})$

Algorithm 2 $\mathcal{B}$

Algorithm $\mathcal{B}$ Description: Given a $\chi$-coloring of the conflict
graph $G$, Algorithm $\mathcal{B}$ iterates through the $\chi$ colors in the
coloring of $G$ and solves $1R1\bar{D}^{v}$ for all nodes $v$ of that color to
determine the value of each color. The algorithm then picks the best color
found and serves the optimal set of demands of that color.

###### Theorem 6.7

Given a $\chi$-coloring of the conflict graph $G$, Algorithm $\mathcal{B}$ is
a $\chi$-approximation algorithm for $mRmD$ instances with the same starting
location for every resource.

###### Proof 6.8

Proof. First note that using Algorithm $\mathcal{B}$, we may construct a
feasible solution to instance $\mathcal{I}$ of $mRmD$ with an objective value
of $\mathcal{B}$($\mathcal{I}$). Because all resources have the same starting
location and the resource type used to solve $1R1\bar{D}^{v}$ is the one with
the smallest number of resources in the subset $v$, then all other resource
types in $v$ may follow the same schedule determined by the solution to
$1R1\bar{D}^{v}$ to ensure all demands are met by their requested resource
types. Thus, the feasible solution will consist of the paths from the
$1R1\bar{D}^{v}$ sub-problem for all resources in $v$ and for all $v\in
S_{i}$, for the color $i$ that produced the maximum objective value.

Now, we may partition the optimal objective value $OPT(\mathcal{I})$ for
instance $\mathcal{I}$ of $mRmD$ into values $OPT_{v}(\mathcal{I}),v\in
S_{i},i\in\\{1,\ldots,\chi\\}$, where $\sum_{i=1}^{\chi}\sum_{v\in
S_{i}}OPT_{v}(\mathcal{I})=OPT(\mathcal{I})$ and each $OPT_{v}(\mathcal{I})$
represents the objective value of all demands $d$ met whose subset request
$M_{d}=v$.

###### Lemma 6.9

$\text{$\mathcal{B}$}_{v}(\mathcal{I})\geq OPT_{v}(\mathcal{I})$, $v\in
S_{i}$, $i=1,\ldots,\chi$.

###### Proof 6.10

Proof. Clearly, $OPT_{v}(\mathcal{I})$ is a feasible objective value to
$1R1\bar{D}^{v}$. However, $\text{$\mathcal{B}$}_{v}(\mathcal{I})$ is the
optimal objective value to $1R1\bar{D}^{v}$ and so,
$\text{$\mathcal{B}$}_{v}(\mathcal{I})\geq OPT_{v}(\mathcal{I})$.

Further, $\text{$\mathcal{B}$}(\mathcal{I})\geq\sum_{v\in
S_{i}}\text{$\mathcal{B}$}_{v}(\mathcal{I})$ for $i=1,\ldots,\chi$ and so we
have

$\sum_{i=1}^{\chi}\text{$\mathcal{B}$}(\mathcal{I})\geq\sum_{i=1}^{\chi}\sum_{v\in
S_{i}}\text{$\mathcal{B}$}_{v}(\mathcal{I})\geq\sum_{i=1}^{\chi}\sum_{v\in
S_{i}}OPT_{v}(\mathcal{I})=OPT(\mathcal{I}).$

This implies

$\chi\cdot\text{$\mathcal{B}$}(\mathcal{I})\geq OPT(\mathcal{I})$

and so, dividing both sides by $\chi$, we obtain

$\text{$\mathcal{B}$}(\mathcal{I})\geq\frac{OPT(\mathcal{I})}{\chi}.\Halmos$

###### Remark 6.11

Note that given a $\chi$-coloring of the conflict graph $G=(V,E)$, Algorithm
$\mathcal{B}$ can be solved in polynomial time as it relies on solving $|V|$
MCF problems.

Theorem 6.7 may be generalized to an $a:b$-coloring.

###### Definition 6.12

An $a:b$-coloring is a $b$-fold coloring out of $a$ available colors, where a
$b$-fold coloring is an assignment of sets of size $b$ to nodes of a graph
such that adjacent nodes receive disjoint sets.

1 Suppose there exists an a:b-coloring of $G$. Label the colors
$1,2,\ldots,a$. Let $S_{i}$ be the set of nodes that are fractionally colored
$i$.

Input : $\mathcal{I},G,a$, $S_{i}$, $i\in\\{1,2,\ldots,a\\}$

2 $\text{$\mathcal{C}$}(\mathcal{I})\leftarrow 0$

3 for  _$1\leq i\leq a$_ do

4 for  _$v\in S_{i}$_ do

5 Solve $1R1\bar{D}^{v}$; Let $\text{$\mathcal{C}$}_{v}(\mathcal{I})$ denote
the objective value.

6 end for

7 if  _$\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})\geq\text{$\mathcal{C}$}(\mathcal{I}):$_
then

8 $\text{$\mathcal{C}$}(\mathcal{I})\leftarrow\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})$

9 end if

10

11 end for

Output: $\text{$\mathcal{C}$}(\mathcal{I})$

Algorithm 3 $\mathcal{C}$

Algorithm $\mathcal{C}$ Description: Given an $a:b$-coloring of the conflict
graph $G$, Algorithm $\mathcal{C}$ iterates through the $a$ colors in the
$a:b$-coloring of $G$ and solves $1R1\bar{D}^{v}$ for all nodes $v$ of that
color to determine the value of each color. The algorithm then picks the best
color found and serves the optimal set of demands of that color.

###### Theorem 6.13

Given an $a:b$-coloring of the conflict graph $G$, Algorithm $\mathcal{C}$ is
an $\frac{a}{b}$-approximation algorithm for $mRmD$ instances with the same
starting location for every resource.

###### Proof 6.14

Proof. First note that using Algorithm $\mathcal{C}$, we may construct a
feasible solution to instance $\mathcal{I}$ of $mRmD$ with an objective value
of $\mathcal{C}$($\mathcal{I}$). Because all resources have the same starting
location and the resource type used to solve $1R1\bar{D}^{v}$ is the one with
the smallest number of resources in the subset $v$, then all other resource
types in $v$ may follow the same schedule determined by the solution to
$1R1\bar{D}^{v}$ to ensure all demands are met by their requested resource
types. Thus, the feasible solution will consist of the paths from the
$1R1\bar{D}^{v}$ sub-problem for all resources in $v$ and for all $v\in
S_{i}$, for the color $i$ that produced the maximum objective value.

Now, we may partition the optimal objective value $OPT(\mathcal{I})$ for
instance $\mathcal{I}$ of $mRmD$ into values
$OPT_{j}(\mathcal{I}),j=1,\ldots,a$, where $b\cdot
OPT(\mathcal{I})=\sum_{j=1}^{a}OPT_{j}(\mathcal{I})$ and each
$OPT_{j}(\mathcal{I})$ represents the objective value of all demands met that
are fractionally colored $j$.

###### Lemma 6.15

$\sum_{v\in S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})\geq
OPT_{i}(\mathcal{I})$ for all $i=1,\ldots,a$.

###### Proof 6.16

Proof. Clearly, $OPT_{i}(\mathcal{I})$ is a feasible objective value to the
$i^{th}$ iteration of Algorithm $\mathcal{C}$. However, $\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})$ is the optimal objective value to
the $i^{th}$ iteration and so, $\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})\geq OPT_{i}(\mathcal{I})$.

Further, $\text{$\mathcal{C}$}(\mathcal{I})\geq\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})$ for $i=1,\ldots,a$ and so we have

$\sum_{i=1}^{a}\text{$\mathcal{C}$}(\mathcal{I})\geq\sum_{i=1}^{a}\sum_{v\in
S_{i}}\text{$\mathcal{C}$}_{v}(\mathcal{I})\geq\sum_{i=1}^{a}OPT_{i}(\mathcal{I})=b\cdot
OPT(\mathcal{I}).$

This implies

$a\cdot\text{$\mathcal{C}$}(\mathcal{I})\geq b\cdot OPT(\mathcal{I})$

and so, dividing both sides by $a$, we obtain

$\text{$\mathcal{C}$}(\mathcal{I})\geq\frac{b}{a}\cdot
OPT(\mathcal{I}).\Halmos$

###### Remark 6.17

Note that given an $a:b$-coloring of the conflict graph $G=(V,E)$, Algorithm
$\mathcal{C}$ can be solved in polynomial time as it relies on solving
$b\cdot|V|$ MCF problems.

###### Definition 6.18

An $(\alpha,\beta)$-bicriteria approximation algorithm for $mRmD$,
$(\alpha>1,\beta>1)$, is an algorithm that given any instance of the problem,
returns a solution whose objective value is at least $\frac{1}{\alpha}$
fraction of the optimal objective and uses at most $\beta$ times more
resources for every resource type. Moreover, the running time of the algorithm
is polynomial in size of the input instance.

In the following theorem, we show that there exists a good bicriteria
algorithm for instances where the optimal solution is able to satisfy nearly
all the demand. The result can be interpreted as a smooth degradation of
Corollary 5.7 that shows the decision problem of deciding whether all demands
are satisfiable is polynomial time solvable.

###### Definition 6.19

Given a parameter $\epsilon>0$, an instance of $mRmD$ is
$(1-\epsilon)$-satisfiable if the optimal solution has objective at least
$(1-\epsilon)$ times the total reward possible, $\sum_{d\in D}w_{d}$.

###### Theorem 6.20

For any $0<\epsilon<1$ and $1\leq k\leq\frac{1}{\epsilon}$, there exists a
$\Big{(}\frac{k-1}{k},\frac{1}{1-k\epsilon}\Big{)}$-bicriteria approximation
algorithm for $(1-\epsilon)$-satisfiable instances of $mRmD$.

###### Remark 6.21

Note that when we multiply the number of resources of each resource type by
$(\frac{1}{1-k\epsilon})$, there is a possibility that the number of resources
of each type is no longer integral. Without loss of generality, we may round
up any non-integral values.

###### Remark 6.22

As an instantiation of Theorem 6.20, consider the parameter $\epsilon=0.01$
and $k=5$. Then, given an instance where the optimal solution satisfies at
least $99\%$ of the weighted sum of demands, Theorem 6.20 returns a solution
that uses 25% more resources of every resource type whose objective value is
at least 94% of the weighted sum of demands.

###### Proof 6.23

Proof of Theorem 6.20. Clearly, the objective of the linear relaxation,
$OPT_{LP}(\mathcal{I})$, of IPM (i.e., all variables are within the range
$[0,1]$) for $(1-\epsilon)$-satisfiable instances of $mRmD$ must also be at
least $(1-\epsilon)$ times the total reward possible, $\sum_{d\in D}w_{d}$.
The algorithm uses the solution to the linear relaxation of IPM and Algorithm
$\mathcal{D}$ to construct an integral solution to IPM whose objective is at
least $(\frac{k-1}{k})OPT_{LP}(\mathcal{I})$ and uses no more than
$(\frac{1}{1-k\epsilon})$ times more resources for every resource type. Let
$(\mathbf{y}^{LP},\mathbf{x}^{LP})$ represent the optimal solution to the
linear relaxation and define the following sets:

$B=\\{i:y_{i}^{LP}<1-k\epsilon\\}\text{ and }G=D\setminus B.$

Now, consider the solution $(\mathbf{y}^{\prime},\mathbf{x}^{\prime})$ where

$\displaystyle y_{i}^{\prime}$ $\displaystyle=\begin{cases}1\hskip
10.00002pt\forall i\in G\\\ 0\hskip 8.00003pt\text{ else, }\end{cases}$
$\displaystyle x_{ij}^{r^{\prime}}$
$\displaystyle=\frac{x_{ij}^{rLP}}{1-k\epsilon}$ $\displaystyle r\in M_{i}\cap
M_{j},i,j\in D,$ $\displaystyle x_{sd}^{r^{\prime}}$
$\displaystyle=\frac{x_{sd}^{rLP}}{1-k\epsilon}$ $\displaystyle s\in
S^{r},r\in M_{d},d\in D,$ $\displaystyle x_{dt}^{r^{\prime}}$
$\displaystyle=\frac{x_{dt}^{rLP}}{1-k\epsilon}$ $\displaystyle r\in
M_{d},d\in D.$

Note that since $x$ variables may be relaxed (see Theorem 5.3),
$(\mathbf{y}^{\prime},\mathbf{x}^{\prime})$ is a solution to IPM when
resources of each resource type are increased by a factor of
$(\frac{1}{1-k\epsilon})$ that satisfies all constraints except the upper
bound on the $x$ variables.

###### Lemma 6.24

A solution $(\mathbf{y},\mathbf{x})$ to IPM in which the $x$ variables are
unbounded above may be transformed into a feasible solution
$(\mathbf{y},\mathbf{\bar{x}})$ to IPM in which the $x$ variables are bounded
above by 1.

###### Proof 6.25

Proof. Note that from Section 3, we may describe the solution
$(\mathbf{y},\mathbf{x})$ as a directed acyclic graph $G=(V,A)$ where each
$x^{r}_{ij}\in\mathbf{x}$ corresponds to the flow along arc $(i,j)\in A$ for
resource type $r\in R$ and $i,j\in V$. Now, the unbounded solution
$(\mathbf{y},\mathbf{x})$ may be transformed into the bounded solution
$(\mathbf{y},\mathbf{\bar{x}})$ by the procedure described in Algorithm
$\mathcal{D}$. The number of operations in Algorithm $\mathcal{D}$ is finite
since at each stage, the total flow along all edges in $G$ is decreasing as we
send the same flow value on fewer number of arcs. It is also important to note
that all variables used in Algorithm $\mathcal{D}$ must exist by the triangle
inequality. Further, the $\mathbf{y}$ variable values remain valid because for
every node in which flow in and flow out is reduced, the flow is never reduced
to less than 1.

Input : $(\mathbf{y},\mathbf{x})$

1 $\mathbf{\bar{x}}\leftarrow\mathbf{x}$

2 while  _There are still $\bar{x}^{r}_{ij}>1$_ do

3 if  _$i$ is a source and $j$ is a sink_ then

4 Reduce flow value of $\bar{x}^{r}_{ij}$ to 1.

5 end if

6 if  _$i$ is a source and $j$ is not a sink_ then

7 Pick some $\bar{x}^{r}_{jk}>0$. Let
$\delta=\min\\{\bar{x}^{r}_{ij}-1,\bar{x}^{r}_{jk}\\}$. Reduce flow value
along $\bar{x}^{r}_{ij}-\bar{x}^{r}_{jk}$ path by $\delta$ and increase flow
value of $\bar{x}^{r}_{ik}$ by $\delta$.

8 end if

9 if  _$i$ is not a source and $j$ is a sink_ then

10 Pick some $\bar{x}^{r}_{hi}>0$. Let
$\delta=\min\\{\bar{x}^{r}_{ij}-1,\bar{x}^{r}_{hi}\\}$. Reduce flow value
along $\bar{x}^{r}_{hi}-\bar{x}^{r}_{ij}$ path by $\delta$ and increase flow
value of $\bar{x}^{r}_{hj}$ by $\delta$.

11 end if

12 else

13 Pick some $\bar{x}^{r}_{hi},\bar{x}^{r}_{jk}>0$. Let
$\delta=\min\\{\bar{x}^{r}_{ij}-1,\bar{x}^{r}_{hi},\bar{x}^{r}_{jk}\\}$.
Reduce flow value along $\bar{x}^{r}_{hi}-\bar{x}^{r}_{ij}-\bar{x}^{r}_{jk}$
path by $\delta$ and increase flow value of $\bar{x}^{r}_{hk}$ by $\delta$.

14 end if

15

16 end while

Output: $(\mathbf{y},\mathbf{\bar{x}})$

Algorithm 4 $\mathcal{D}$

By Lemma 6.24, we may transform $(\mathbf{y}^{\prime},\mathbf{x}^{\prime})$
into a feasible solution to IPM when resources are increased by
$(\frac{1}{1-k\epsilon})$ and the $x$ variables satisfy their bound
restrictions. Denote this solution by
$(\mathbf{y}^{\prime},\mathbf{x}^{\prime\prime})$.

Now from Theorem 5.3 we know that if the $\mathbf{y}^{\prime}$ variables are
fixed, then IPM decomposes into $|R|$ MCF problems which can be solved in
polynomial time and produce an integral optimal solution. Therefore, we can
fix the $\mathbf{y}^{\prime}$ variables and solve IPM optimally, letting
$OPT(\mathcal{I}),(\mathbf{y}^{\prime},\mathbf{x}^{*})$ represent the optimal
objective value and solution, respectively.

###### Lemma 6.26

$OPT(\mathcal{I})\geq(\frac{k-1}{k})OPT_{LP}(\mathcal{I}).$

###### Proof 6.27

Proof. First note that

$\sum_{i\in B}y_{i}^{LP}w_{i}+\sum_{i\in G}w_{i}\geq\sum_{i\in
B}y_{i}^{LP}w_{i}+\sum_{i\in
G}y_{i}^{LP}w_{i}=OPT_{LP}(\mathcal{I})\geq(1-\epsilon)\sum_{i\in
B}w_{i}+(1-\epsilon)\sum_{i\in G}w_{i}.$

This implies that

$\displaystyle\epsilon\sum_{i\in G}w_{i}$
$\displaystyle\geq(1-\epsilon)\sum_{i\in B}w_{i}-\sum_{i\in B}y_{i}^{LP}w_{i}$
(9) $\displaystyle>(1-\epsilon)\sum_{i\in B}w_{i}-(1-k\epsilon)\sum_{i\in
B}w_{i}$ (10) $\displaystyle=\epsilon(k-1)\sum_{i\in B}w_{i}$ (11)

where (10) comes from the fact that $\sum_{i\in
B}y_{i}^{LP}w_{i}<(1-k\epsilon)\sum_{i\in B}w_{i}$. Now, we have that
$\sum_{i\in G}w_{i}\geq(k-1)\sum_{i\in B}w_{i}$ and so

$OPT(\mathcal{I})=\sum_{i\in
G}w_{i}\geq\left(\frac{k-1}{k}\right)\left(\sum_{i\in G}w_{i}+\sum_{i\in
B}w_{i}\right)\geq\left(\frac{k-1}{k}\right)OPT_{LP}(\mathcal{I}).\Halmos$

Thus, we have shown that $(\mathbf{y}^{\prime},\mathbf{x}^{*})$ is an integral
solution to IPM using $(\frac{1}{1-k\epsilon})$ times more resources for every
resource type whose objective value, $OPT(\mathcal{I})$, is greater than or
equal to $(\frac{k-1}{k})OPT_{LP}(\mathcal{I})$.

##  7 Extension

We present an extension to $mRmD$ (denoted by $mRmDc$) that considers integer-
valued travel costs $(c)$ between different locations (e.g., $c_{ij}$ denotes
the travel cost between the locations of demands $i$ and $j$ and $c_{sd}$ is
the travel cost between a resource’s starting location $s$ and the location of
demand $d$. The integer programming model incorporating travel costs (IPM-C)
is as follows:

$\displaystyle\max~{}\sum_{d\in D}y_{d}w_{d}-\sum_{r\in R}\Big{(}\sum_{s\in
S^{r}}\sum_{d\in D}x_{sd}^{r}c_{sd}+\sum_{i\in D}\sum_{j\in
D}x_{ij}^{r}c_{ij}\Big{)}$ (12)

s.t.

$(2)-(8)$

###### Theorem 7.1

Assume that the travel cost between any two locations is less than or equal to
$\frac{1}{2|R|}$ times the minimum reward for a demand $(w^{min})$. Then
Algorithm $\mathcal{A}$ is a $2|R|$-approximation algorithm for $mRmDc$
instances with the same starting location for every resource.

###### Proof 7.2

Proof. Note that we may run Algorithm $\mathcal{A}$ on instance $\mathcal{I}$
of $mRmDc$ assuming travel costs are zero, where
$\text{$\mathcal{A}$}(\mathcal{I}),D_{\text{$\mathcal{A}$}}\subseteq D$ are
the objective value and set of demands met in the solution produced by
Algorithm $\mathcal{A}$, repsectively. Let $C,C^{*}$ be the total travel costs
incurred from the solutions of Algorithm $\mathcal{A}$ and the optimal
solution, respectively. Thus, the objective value produced by Algorithm
$\mathcal{A}$ is $\text{$\mathcal{A}$}(\mathcal{I})-C$ and the optimal
objective value is $OPT(\mathcal{I})-C^{*}$. Then we have

$\displaystyle\text{$\mathcal{A}$}(\mathcal{I})-C$
$\displaystyle\geq\text{$\mathcal{A}$}(\mathcal{I})-c|D_{\text{$\mathcal{A}$}}||R|$
(13)
$\displaystyle\geq\text{$\mathcal{A}$}(\mathcal{I})-\Big{(}\frac{1}{2|R|}w^{min}\Big{)}|D_{\text{$\mathcal{A}$}}||R|$
(14) $\displaystyle\geq\frac{1}{2}\text{$\mathcal{A}$}(\mathcal{I})$ (15)
$\displaystyle\geq\frac{1}{2|R|}OPT(\mathcal{I})$ (16)
$\displaystyle\geq\frac{1}{2|R|}(OPT(\mathcal{I})-C^{*}).$ (17)

Note that (14) follows from the assumption about travel costs and (16) is from
the results of Theorem 6.2.

##  8 Computational Study

To test IPM, we created different problem instances using 2-7 resource types,
100-800 demands, and varied number of resources. In all cases, demand start
times are randomly chosen in the interval of [0, 1440], used to represent
scheduling a day (in minutes), with demands and resources randomly placed on a
20x20 grid structure. Adjacent nodes on the grid are 1 minute apart. Service
times are determined from a triangular distribution with a minimum of 15
minutes, maximum of 120 minutes, and mode of 30 minutes. All resource types
have the same number of resources (e.g., if there are 3 resource types and a
total of 12 resources then there are 4 resources of each type for that
instance). Rewards for demands are proportional to their service time and the
number of resource types the demand requires. Resource requirement subsets are
determined randomly, with a 50% chance that a certain resource type will be
required by a demand incident. Results presented are averages of 10 instances.
All instances were ran using Gurobi version 8.0.1.

Tables 6 and 6 present the run times (in seconds) for all instances
considered, where $|R|$ is the number of resource types, $|D|$ is the number
of demands, and $L$ is the total number of resources. Note that Scaled Demands
refers to results for instances in which the reward for demand was multiplied
by a factor of 100. As expected, as the number of demands or number of
resource types increases, the run time increases. Computational experiments
show that for small and medium sized problems (less than 5 resource types),
IPM can be efficiently solved by Gurobi. However, larger sized problems are
harder to solve. For example, problem instances with 7 resource types and
between 700 and 800 demands took, on average, between 12 and 50 minutes to
solve. Results are similar between instances with and without scaling.
Appendix 10 describes an alternate formulation for $mRmD$ and shows that the
runtimes for IPM are faster. Appendix 12.1 presents a discussion on the trade-
off between resource capacity and the objective function value (i.e., demands
met), as highlighted by Theorem 6.20.

Table 5: Results for number of resource types equal to 2,3 and 4

$|R|$ | $|D|$ | L | Run time |  | Run time
---
(Scaled Demands)
2 | 100 | 10 | 0.08 | 0.10
2 | 200 | 14 | 0.25 | 0.33
2 | 300 | 18 | 0.65 | 0.90
2 | 400 | 22 | 1.24 | 1.85
2 | 500 | 26 | 3.10 | 2.74
2 | 600 | 30 | 4.88 | 5.88
2 | 700 | 34 | 8.58 | 7.20
2 | 800 | 38 | 12.06 | 13.96
3 | 100 | 12 | 0.12 | 0.10
3 | 200 | 18 | 0.32 | 0.59
3 | 300 | 24 | 1.44 | 1.48
3 | 400 | 30 | 2.66 | 3.70
3 | 500 | 36 | 4.80 | 7.35
3 | 600 | 42 | 9.04 | 15.42
3 | 700 | 48 | 22.21 | 21.33
3 | 800 | 54 | 26.60 | 40.69
4 | 100 | 16 | 0.15 | 0.25
4 | 200 | 24 | 0.77 | 1.13
4 | 300 | 32 | 2.75 | 3.04
4 | 400 | 40 | 5.71 | 7.89
4 | 500 | 48 | 18.72 | 16.69
4 | 600 | 56 | 21.07 | 30.45
4 | 700 | 64 | 98.42 | 52.30
4 | 800 | 72 | 147.81 | 72.01

Table 6: Results for number of resource types equal to 5,6 and 7

$|R|$ | $|D|$ | L | Run time |  | Run time
---
(Scaled Demands)
5 | 100 | 20 | 0.13 | 0.22
5 | 200 | 30 | 0.92 | 1.60
5 | 300 | 40 | 5.39 | 6.31
5 | 400 | 50 | 8.08 | 17.57
5 | 500 | 60 | 43.06 | 44.37
5 | 600 | 70 | 55.82 | 161.77
5 | 700 | 80 | 145.10 | 100.11
5 | 800 | 90 | 276.00 | 349.65
6 | 100 | 24 | 0.24 | 0.40
6 | 200 | 36 | 1.31 | 2.41
6 | 300 | 48 | 7.13 | 9.01
6 | 400 | 60 | 21.74 | 22.78
6 | 500 | 72 | 87.24 | 76.92
6 | 600 | 84 | 184.65 | 349.21
6 | 700 | 96 | 474.84 | 313.35
6 | 800 | 108 | 1133.85 | 778.51
7 | 100 | 28 | 0.34 | 0.58
7 | 200 | 42 | 2.89 | 3.51
7 | 300 | 56 | 13.07 | 20.42
7 | 400 | 70 | 111.12 | 65.29
7 | 500 | 84 | 169.17 | 195.20
7 | 600 | 98 | 564.02 | 463.19
7 | 700 | 112 | 754.89 | 985.09
7 | 800 | 126 | 2965.94 | 2360.52

###  8.1 Computational Study with Travel Costs

We ran the same instances as above using IPM-C, where travel costs were
equivalent to travel times (i.e., demands that are 3 minutes apart have a
travel cost of 3 in the objective). Results and analysis can be found in
Appendix 12.2.

##  9 Conclusions

In this study, we formulated the heterogeneous multi-resource allocation
problem ($mRmD$) where each demand requests a subset of resources
simultaneously at a specified time, location, and duration as an integer
program (IPM). Complexity results were given for $mRmD$, as well as various
special cases. A polyhedral result was introduced that allowed us to relax
variables in IPM. Further, we developed approximation algorithms for
variations of $mRmD$ and proved the correctness of their performance
guarantees. Finally, we tested the performance of the model computationally
using Gurobi.

One simple extension of $mRmD$ (labeled Extension 2) is to consider that
resource types may need to visit a destination location before moving on to
meet the next demand. For example, after meeting a demand incident, an
ambulance may need to drop the patient off at the hospital before proceeding
to the next demand location. The problem description and formulation for
Extension 2 are provided in Appendix 13. As the structure of the solution
space does not change significantly, the complexity results in Section 5 can
be applied to this extension, with computational results being very similar to
those discussed in Section 8.

In this work, we have assumed that all demand requests are known ahead of time
(e.g., deterministic). While this formulation can be used to influence
planning decisions, future research could consider stochastic and dynamic
versions of $mRmD$ (i.e., when all demand incidents may not be known ahead of
time). Further, our problem could be generalized to consider requiring
multiple units of each resource type.

This research has been supported in part by National Science Foundation (NSF)
Graduate Research Fellowship DGE-1650044, NSF grant CMMI-1538860, NSF-
AF:1910423 and NSF-AF:1717947 and the following Georgia Tech benefactors:
William W. George, Andrea Laliberte, Joseph C. Mello, Richard “Rick” E. &
Charlene Zalesky, and Claudia & Paul Raines. The authors would also like to
thank the editor and reviewers for their comments and suggestions; their
diligent and detailed reviews thoroughly improved our manuscript.

##  10 Alternate Formulation for $mRmD$

Table 7: Notation for IPM-Alt $D$ | Set of demands
---|---
$R$ | Set of resource types
$S^{r}$ |  Set of starting locations for $r\in R$
$l_{s}^{r}$ |  Number of resources of type $r\in R$ starting at location $s\in S^{r}$
$\mathcal{K}^{r}$ |  Number of resources of type $r\in R$
$f_{ij}$ |  Travel time between $i,j\in\\{\cup_{r\in R}S^{r}\\}\cup D$
$M_{d}$ |  Subset of resources required by $d\in D$
$\tau_{d}$ |  Service start time for $d\in D$
$\Delta_{d}$ |  Service duration for $d\in D$
$w_{d}$ |  Reward for meeting $d\in D$
$T$ | Last time period for demand to be served
$\boldsymbol{y_{d}}$= | $\begin{cases}1,\text{ if demand }d\text{ is satisfied}\\\ 0,\text{ otherwise}\hskip 108.00018ptd\in D\end{cases}$
$\boldsymbol{x_{it}^{k,r}}$= | $\begin{cases}1,\text{ if resource }k\text{ of type }r\text{ is at }\\\ \hskip 18.00003pt\text{ location }i\text{ at time }t\\\ 0,\text{ otherwise}\hskip 108.00018pti,t,k,r:i\in\\{\cup_{r\in R}S^{r}\\}\cup D,t\in\\{0,\ldots,T\\},\\\ \hskip 189.00032ptk\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in R\\\ \end{cases}$
$\boldsymbol{z_{d}^{k,r}}$= | $\begin{cases}1,\text{ if demand }d\text{ is met by resource }\\\ \hskip 18.00003ptk\text{ of type }r\\\ 0,\text{ otherwise}\hskip 108.00018ptd,k,r:k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in M_{d},d\in D\\\ \end{cases}$

We present an alternative integer programming model (IPM-Alt) for $mRmD$. For
an overview of the notation and description of the decision variables, please
refer to Table 7.

$\displaystyle\max~{}\sum_{d\in D}y_{d}w_{d}$ (18)

s.t.

$\displaystyle\sum_{k=1}^{\mathcal{K}^{r}}x_{s0}^{k,r}=l_{s}^{r}$
$\displaystyle s\in S^{r},r\in R$ (19) $\displaystyle\sum_{s\in
S^{r}}x_{s0}^{k,r}=1$ $\displaystyle k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in
R$ (20) $\displaystyle\sum_{i\in\\{\cup_{r\in R}S^{r}\\}\cup
D}x_{it}^{k,r}\leq 1$ $\displaystyle
t\in\\{0,\ldots,T\\},k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in R$ (21)
$\displaystyle x_{it}^{k,r}+x_{jt^{\prime}}^{k,r}\leq 1$ $\displaystyle
t^{\prime}>t|f_{ij}>t^{\prime}-t,i,j\in\\{\cup_{r\in R}S^{r}\\}\cup D,$ (22)
$\displaystyle t\in\\{0,\ldots,T-1\\},k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in
R$ $\displaystyle x_{dt}^{k,r}\geq z_{d}^{k,r}$ $\displaystyle
t\in\\{\tau_{d},\ldots,\tau_{d}+\Delta_{d}\\},k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in
M_{d},d\in D$ (23) $\displaystyle\sum_{k=1}^{\mathcal{K}^{r}}z_{d}^{k,r}\geq
y_{d}$ $\displaystyle r\in M_{d},d\in D$ (24) $\displaystyle
y_{d}\in\\{0,1\\}$ $\displaystyle d\in D$ (25) $\displaystyle
x_{it}^{k,r}\in\\{0,1\\}$ $\displaystyle i\in\\{\cup_{r\in R}S^{r}\\}\cup
D,t\in\\{0,\ldots,T\\},k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in R$ (26)
$\displaystyle z_{d}^{k,r}\in\\{0,1\\}$ $\displaystyle
k\in\\{1,\ldots,\mathcal{K}^{r}\\},r\in M_{d},d\in D$ (27)

The objective function (18) of IPM-Alt is to maximize the overall reward
obtained from satisfying demands. Constraints (19) ensure that the number of
resources at starting location $s$ at time 0 is equal to the number of
resources available at that location. Constraints (20) assign each resource to
a starting location. Constraints (21) ensure that a resource can only be at at
most one location at each time index. Constraints (22) maintain that the
movement of each resource from location to location is valid for the given
time indices. Constraints (23) enforce that a demand is met by a given
resource only if that resource is at the demand’s location for its entire
service duration. Constraints (24) state that a demand can only be satisfied
if it has been served by a resource of each of its required resource types.
Domain constraints for the variables are given in (25)-(27).

We test a small instance of $mRmD$ with 10 demands, 2 resource types (with 3
resources of each type), and demand start times randomly chosen in the
interval [0,100]. All other computational details remain the same as described
in Section 8. Table 8 presents the solution times for 10 runs of this instance
using both IPM and IPM-Alt. As shown, even with this very small instance, IPM
outperforms IPM-Alt significantly. When attempting to use IPM-Alt to solve the
smallest sized instance type described in Section 8 (e.g., 2 resource types,
100 demands, 10 resources), construction of the model did not finish in under
an hour due to a large number of variables and constraints.

Table 8: Comparison of run times (in seconds) Instance | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
IPM | 0.044 | 0.04 | 0.083 | 0.027 | 0.045 | 0.032 | 0.044 | 0.036 | 0.045 | 0.051
IPM-Alt | 4.47 | 4.15 | 6.33 | 3.57 | 3.58 | 5.82 | 7.22 | 4.20 | 6.19 | 3.19

##  11 Proofs of Theorems and Observations

###  11.1 Proof of Theorem 5.1

We prove that $2RmD$ is NP-hard by reduction using Numerical 3-Dimensional
Matching (N3DM). The construction is similar to the proof in Keskinocak and
Tayur (1998).
Instance of N3DM
Integers $t,d\text{ and }a_{t},b_{t},c_{t}$ for $i=1,\ldots,t$, satisfying the
following relations:

$\sum_{i=1}^{t}(a_{i}+b_{i}+c_{i})=td\text{ and }0<a_{i},b_{i},c_{i}<d\text{
for }i=1,\ldots,t$

The goal is to find permutations $\rho$ and $\sigma$ of $\\{1,\ldots,t\\}$,
such that:

$a_{i}+b_{\rho(i)}+c_{\sigma(i)}=d\text{ for }i=1,\ldots,t$

N3DM is shown to be NP-Complete in Garey and Johnson (1990). Given an instance
of N3DM, we define the following:
$A_{i}=i\text{ for }i=1,\ldots,t$
$B_{j}=t+j\text{ for }j=1,\ldots,t$
$C_{ij}=2t+(i-1)t+j\text{ for }i,j=1,\ldots,t$
$S=t^{2}+2t$
$T=S+2d+1$

An instance of $2RmD$ with $t^{2}+t$ resources and travel times between
demands equal to zero can be built as follows: resources $1,\ldots,t$ are of
type 1 and the remaining $t^{2}$ resources are of type $0$. Let demands be of
the form $(u_{j},v_{j})$, where $u_{j}$ is the start time, $v_{j}$ is the end
time, and $v_{j}-u_{j}$ is the service time of demand $j$. Define the reward
for demand $j$ to be the length of service times the number of resource types
required.

The following demands require resource type $0$ and $1$:

$(0,A_{i})\text{ for }i=1,\ldots,t$ $(A_{i},C_{ij})\text{ for }i,j=1,\ldots,t$
$(S+d-c_{k},T)\text{ for }k=1,\ldots,t$

The following demands require resource type $0$:

$t-1\text{ times }(0,B_{j})\text{ for }j=1,\ldots,t$ $(B_{j},C_{ij})\text{ for
}i,j=1,\ldots,t$ $(C_{ij},S+a_{i}+b_{j})\text{ for }i,j=1,\ldots,t$
$(S+a_{i}+b_{j},T-1)\text{ for }i,j=1,\ldots,t$ $t^{2}-t\text{ times }(T-1,T)$

The following demands require resource type 1:

$(C_{ij},S+a_{i}+b_{j})\text{ for }i,j=1,\ldots,t$

We now show that there exists a feasible solution to N3DM if and only if all
resources are serving demands during the interval [0,T] and there is no idle
time.

Suppose that there exists a feasible schedule for a subset of demands, such
that all resources are busy serving demands during the interval [0,T]. Demands
$(0,A_{i})$ must be scheduled to the first $t$ resources (since there are $t$
of these trips and they each require resource type 1) and resources
$t+1,\ldots,2t$ of type $0$. These demands must be followed by some
$(A_{i},C_{ij})$ demands. Similarly, the $t^{2}-t$ demands $(0,B_{j})$ must be
scheduled to the remaining $t^{2}-t$ resources of type $0$, followed by some
$(B_{j},C_{ij})$ demands.

The first $t$ resources of type 1 and the next $t+1,\ldots,2t$ resources of
type $0$ have the following schedules:

$(0,A_{i})(A_{i},C_{ij})(C_{ij},S+a_{i}+b_{j})(S+d-c_{k},T)$

where each $i$, $1\leq i\leq t$ occurs exactly once.

The remaining $t^{2}-t$ resources of type $0$ have schedules of the form

$(0,B_{j})(B_{j},C_{ij})(C_{ij},S+a_{i}+b_{j})(S+a_{i}+b_{j},T-1)(T-1,T)$

where each $j$, $1\leq j\leq t$ occurs exactly $t-1$ times. Thus, among the
demands $(C_{ij},S+a_{i}+b_{j})$ that are served by the first $t$ resources,
each $i$ and each $j$ occurs exactly once.

From the schedules of the first $t$ resources, we have
$S+a_{i}+b_{j}=S+d-c_{k}$, i.e., $a_{i}+b_{j}+c_{k}=d$. So we define
$\rho(i)=j$ and $\sigma(i)=k$ whenever demand $(C_{ij},S+a_{i}+b_{j})$ is
served followed by $(S+d-c_{k},T)$ by resource $i,i=1,\ldots,t$.

Conversely, given a feasible solution to N3DM, a feasible solution for this
instance of $2RmD$ can be found, which is clearly optimal, since the resources
are serving demand throughout the interval [0,T] with no idle time.

###  11.2 Proof of Lemma 5.5

We first show that IPM-R can be modeled and solved as a MCF with node
capacities. Define $G=(N,A,l,\mu,c,b,v)$ as follows, where $l,\mu$ are the
lower and upper bound functions on arc capacity, $c$ is the arc cost function,
$b$ is the node supplies function, and $v$ is the node capacities function:
Nodes
$N\coloneqq D^{r}\cup S^{r}\cup\\{s^{*},t\\}$
Arcs:
$(s^{*},t)$ at cost 0 with capacity $(0,\infty)$
$(s^{*},s)$ at cost 0 with capacity $(0,l_{s}^{r})$ $\forall s\in S^{r}$
$(d,t)$ at cost 0 with capacity $(0,1)$ $\forall d\in D^{r}$
$(s,d)$ if $B_{sd}=1$ at cost 0 with capacity $(0,1)$ $\forall s\in S^{r},d\in
D^{r}$
$(i,j)$ if $A_{ij}=1$ at cost 0 with capacity $(0,1)$ $\forall i,j\in D^{r}$
Supplies (b):
$b(i)=0$ $\forall i\in S^{r}\cup D^{r}$
$-b(t)=b(s^{*})=\sum_{s\in S^{r}}l_{s}^{r}$
Node Capacities (v):
$v(i)=y_{i}\text{ if }i\in D^{r}$

To convert this MCF with node capacities into a general MCF, we can perform
the following transformation (Ciupală (2009)). We redefine $G$ to be a MCF
$G^{\prime}=(N^{\prime},A^{\prime},l^{\prime},\mu^{\prime},c^{\prime},b^{\prime})$.
Nodes:
$N^{\prime}=N_{1}\cup N_{2}$ where $N_{1}\coloneqq\\{i^{\prime}|i\in N\\}$ and
$N_{2}\coloneqq\\{i^{\prime\prime}|i\in D^{r}\\}$.
Arcs:
$A^{\prime}=A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\cup A_{5}$ where
$A_{1}\coloneqq\\{(i^{\prime},j^{\prime})|(i,j)\in A,i,j\notin D^{r}\\}$
$A_{2}\coloneqq\\{(j^{\prime},i^{\prime})|(j,i)\in A,j\notin D^{r},i\in
D^{r}\\}$
$A_{3}\coloneqq\\{(i^{\prime\prime},j^{\prime})|(i,j)\in A,i,j\in D^{r}\\}$
$A_{4}\coloneqq\\{(i^{\prime\prime},j^{\prime})|(i,j)\in A,i\in D^{r},j\notin
D^{r}\\}$
$A_{5}\coloneqq\\{(i^{\prime},i^{\prime\prime})|i\in D^{r}\\}$
Note that for any arc $(i,j)\in A_{1}\cup A_{2}\cup A_{3}\cup A_{4}$, the cost
and capacities remain the same as previously defined for the corresponding
arcs in $A$. The new arcs $(i^{\prime},i^{\prime\prime})\in A_{5}$ have cost 0
and capacity $(v(i),v(i))$.
Supplies (b’):
$b^{\prime}(i^{\prime})=b(i)$ $\forall i^{\prime}\in N_{1}$
$b^{\prime}(i^{\prime\prime})=0$ $\forall i^{\prime\prime}\in N_{2}$
Then we have the following MCF formulation:

$\displaystyle\min$ $\displaystyle\hskip 10.00002pt0$

s.t.

$\displaystyle\sum_{j:(i,j)\in A^{\prime}}x_{ij}^{r}-\sum_{j:(j,i)\in
A^{\prime}}x_{ji}^{r}=b^{\prime}(i)$ $\displaystyle i\in N^{\prime}$
$\displaystyle l^{\prime}(i,j)\leq x_{ij}^{r}\leq\mu^{\prime}(i,j)$
$\displaystyle(i,j)\in A^{\prime}$

Thus, we have shown that IPM-R can be modeled and solved as a MCF.

###  11.3 Proof of Theorem 5.8

We prove that $mRmD$ cannot be approximated within
$O(\min\\{|R|^{\frac{1}{2}-\epsilon},|D|^{1-\epsilon}\\})$, where $|R|$ is the
number of resource types and $|D|$ is the number of demands, by reduction
using Maximum Set Packing.

Instance of Maximum Set Packing
Given a universe $U$, a family $S$ of subsets of $U$, and an integer $n$, is
there a subfamily $C\subseteq S$ of sets such that all sets in $C$ are
pairwise disjoint and $|C|\geq n$?

Maximum Set Packing is well known to be NP-Complete and cannot be approximated
within $O(N^{1-\epsilon})$ unless $NP\subseteq ZPP$ (Håstad (1996)). Given an
instance of Maximum Set Packing, we can create an instance of $mRmD$ with
$|U|$ resources and $|S|$ demands in polynomial time as follows:

Define $r_{u}$ as a resource of type $u$ $\forall u\in U$.
Define $d_{s}$ as a demand that requires resource type $i$ if $i\in s$
$\forall s\in S$.
Let all demands and resources be at the same location (i.e., zero travel
times) and all demand intervals be equivalent. Further, set all demand rewards
equal to 1.

We now show that there exists a feasible solution to Maximum Set Packing if
and only if there exists a feasible solution to our problem with an objective
value greater than or equal to $n$.

Suppose that we have a feasible solution to Maximum Set Packing. That is,
$\exists C\subseteq S$ such that $|C|\geq n$ and all sets in $C$ are pairwise
disjoint. Then, for each $x\in C$, $d_{x}$ can be served by our resources
since they are disjoint in the resources that they require. Therefore, we can
serve at least $n$ demands and since all rewards are equal to 1, our objective
must be greater than or equal to $n$.

Conversely, suppose we have a feasible solution to our problem such that the
objective is greater than or equal to $n$. Since all rewards are equal to 1,
this implies that we have met at least $n$ demands. Further, since we only
have one resource of each type, these $n$ demands must have disjoint resource
requirements. For each demand $d_{x}$ that was served, the corresponding set
of resource requirements $x\in S$ can be added to $C$. Therefore, we have
created a subfamily $C\subseteq S$ of disjoint sets where $|C|\geq n$ and so
Maximum Set Packing is feasible.

Since the transformation of Maximum Set Packing to an instance of $mRmD$
preserved the objective value, then approximation results are also preserved.
That is, $mRmD$ cannot be approximated within
$O(\min\\{|R|^{\frac{1}{2}-\epsilon},|D|^{1-\epsilon}\\})$ unless $NP\subseteq
ZPP$ (for every $\epsilon>0$), where $|R|$ is the number of resource types and
$|D|$ is the number of demands.

###  11.4 Proof of Theorem 5.10

We prove that the special case of $mR\\{\text{1 or 2}\\}D$ where there are an
arbitrary number of resource types $R$, a special resource $r^{\prime}\in R$,
and each demand requires either $r^{\prime},r$ or $\\{r^{\prime},r\\},r\in
R-r^{\prime}$ is NP-hard by reduction using N3DM. The construction is similar
to the proof in Keskinocak and Tayur (1998). Given an instance of N3DM, we
define the following:
$A_{i}=i\text{ for }i=1,\ldots,t$
$B_{j}=t+j\text{ for }j=1,\ldots,t$
$C_{ij}=2t+(i-1)t+j\text{ for }i,j=1,\ldots,t$
$S=t^{2}+2t$
$T=S+2d+t+1$

An instance of the special case of $mR\\{\text{1 or 2}\\}D$ with $t^{2}+t$
resources and travel times between demands equal to zero can be built as
follows: resources $1,\ldots,t$ are of type $i,i=1,\ldots,t$ and the remaining
$t^{2}$ resources are of type $t^{\prime}$. Let demands be of the form
$(u_{j},v_{j})$, where $u_{j}$ is the start time, $v_{j}$ is the end time, and
$v_{j}-u_{j}$ is the service time of demand $j$. Define the reward for demand
$j$ to be the length of service times the number of resource types required.

The following demands require resource type $t^{\prime}$ and $i$:

$(0,A_{i})\text{ for }i=1,\ldots,t$ $(A_{i},C_{ij})\text{ for }i,j=1,\ldots,t$
$(S+d-c_{k},T-k-1)\text{ for }i,k=1,\ldots,t$

The following demands require resource type $t^{\prime}$:

$t-1\text{ times }(0,B_{j})\text{ for }j=1,\ldots,t$ $(B_{j},C_{ij})\text{ for
}i,j=1,\ldots,t$ $(C_{ij},S+a_{i}+b_{j})\text{ for }i,j=1,\ldots,t$
$(S+a_{i}+b_{j},T-1)\text{ for }i,j=1,\ldots,t$ $t^{2}-t\text{ times }(T-1,T)$
$(T-k-1,T)\text{ for }k=1,\ldots,t$

The following demands require resource type $i$:

$(C_{ij},S+a_{i}+b_{j})\text{ for }i,j=1,\ldots,t$ $(T-k-1,T)\text{ for
}i,k=1,\ldots,t$

We now show that there exists a feasible solution to N3DM if and only if all
resources are serving demands during the interval [0,T] and there is no idle
time.

Suppose that there exists a feasible schedule for a subset of demands, such
that all resources are busy serving demands during the interval [0,T]. Demands
$(0,A_{i})$ must be scheduled to the first $t$ resources (since there are $t$
of these trips and they each require resource type $i,i=1,\ldots t$) and
resources $t+1,\ldots,2t$ of type $t^{\prime}$. These demands must be followed
by some $(A_{i},C_{ij})$ demands. Similarly, the $t^{2}-t$ demands $(0,B_{j})$
must be scheduled to the remaining $t^{2}-t$ resources of type $t^{\prime}$,
followed by some $(B_{j},C_{ij})$ demands.

The first $t$ resources of type $i,i=1,\ldots,t$ and the next $t+1,\ldots,2t$
resources of type $t^{\prime}$ have the following schedules:

$(0,A_{i})(A_{i},C_{ij})(C_{ij},S+a_{i}+b_{j})(S+d-c_{k},T-k-1)(T-k-1,T)$

where each $i$ and each $k$, $1\leq i,k\leq t$ occur exactly once.

The remaining $t^{2}-t$ resources of type $t^{\prime}$ have schedules of the
form

$(0,B_{j})(B_{j},C_{ij})(C_{ij},S+a_{i}+b_{j})(S+a_{i}+b_{j},T-1)(T-1,T)$

where each $j$, $1\leq j\leq t$ occurs exactly $t-1$ times. Thus, among the
demands $(C_{ij},S+a_{i}+b_{j})$ that are served by the first $t$ resources,
each $i,j,$ and $k$ occurs exactly once.

From the schedules of the first $t$ resources, we have
$S+a_{i}+b_{j}=S+d-c_{k}$, i.e., $a_{i}+b_{j}+c_{k}=d$. So we define
$\rho(i)=j$ and $\sigma(i)=k$ whenever demand $(C_{ij},S+a_{i}+b_{j})$ is
served followed by $(S+d-c_{k},T-k-1)$ by resource $i,i=1,\ldots,t$.

Conversely, given a feasible solution to N3DM, a feasible solution for this
instance of the special case of $mR\\{\text{1 or 2}\\}D$ can be found, which
is clearly optimal, since the resources are serving demand throughout the
interval [0,T] with no idle time.

###  11.5 Proof of Theorem 5.12

For an instance $\mathcal{I}$ of the special case of $mR\\{\text{1 or
all}\\}D$, let $m_{i}$ be the number of resources of type $i$ for
$i=1,\ldots,|R|$. Since there is zero travel time between demands (i.e., all
demands are at the same location), all demands have the same service start
time, and all service times are infinite, then each resource can only be
assigned a single job.

First, divide the list of demands $D$ into subsets
$D_{0},D_{1},\ldots,D_{|R|}$ where subset $D_{0}$ is the demands that require
all resource types and subsets $D_{i}$ for $i=1,\ldots,|R|$ are the demands
that only require resource type $i$. Order the demands in each subset by
decreasing reward. We can find the optimal objective value $OPT(\mathcal{I})$
and its corresponding solution by Algorithm $\mathcal{E}$, which runs
polynomially in number of resources. Note the solution is constructed by
serving all demands whose reward was added to the objective value
$OPT(\mathcal{I})$.

Input : $\mathcal{I}$, $m_{i}$, $i=1,2,\ldots,|R|$

1 $m\leftarrow\min\\{m_{i}|i\in\\{1,2,\ldots,|R|\\}\\}$

2 $Opt(\mathcal{I})\leftarrow 0$

3 for  _$1\leq i\leq|R|$_ do

4 if  _$m <m_{i}$_ then

5 Increase $OPT(\mathcal{I})$ by rewards of first $m_{i}-m$ entries of
$D_{i}$.

6 Remove first $m_{i}-m$ entries from $D_{i}$.

7 end if

8

9 end for

10for  _$1\leq i\leq m$_ do

11 Let $r(D_{i}[0])=$ reward of first entry in $D_{i}$ for $i=0,1,\ldots,|R|$.

12 if  _$\sum_{i=1}^{|R|}r(D_{i}[0])\leq r(D_{0}[0])$_ then

13 Increase $OPT(\mathcal{I})$ by $r(D_{0}[0])$.

14 Remove $D_{0}[0]$ from $D_{0}$.

15 end if

16 else

17 Increase $OPT(\mathcal{I})$ by $r(D_{i}[0])$ for $i=1,2,\ldots,|R|$.

18 Remove $D_{i}[0]$ from $D_{i}$ for $i=1,2,\ldots,|R|$.

19 end if

20

21 end for

Output: $OPT(\mathcal{I})$

Algorithm 5 $\mathcal{E}$

###  11.6 Proof of Theorem 5.16

We prove that $1R1D$ is solvable in polynomial time. Consider $m$ resources
and $n$ demands. Without loss of generality, assume that each resource has its
own starting location and are labeled by resource number (i.e.,
$s=1,\ldots,m$). This problem can be modeled as a MCF on a directed acyclic
graph with the following nodes and arcs:
Nodes:
For each resource there is a node $b_{i}$, $i=1,\ldots m$.
For each demand there are two nodes $u_{j}$ and $v_{j}$, $j=1,\ldots n$.
There is a dummy source node $s$ and a dummy sink node $t$.
Arcs:
$(s,b_{i})$ and $(b_{i},t)$ at cost $0$, $i=1,\ldots,m$.
$(v_{j},t)$ at cost $0$, $j=1,\ldots n$.
$(b_{i},u_{j})$ if $B_{ij}=1$ at cost 0, $i=1,\ldots,m,j=1,\ldots,n$.
$(v_{j},u_{k})$ if $A_{jk}=1$ at cost 0, $j,k=1,\ldots,n$.
$(u_{j},v_{j})$ at cost $-w_{j}$, $j=1,\ldots,n$.
All arcs have capacity 1. Let the supply at node $s$ be $m$, supply at node
$t$ be $-m$ and supply for all other nodes be zero. Further, note that since
the graph is directed and acyclic, we can transform the arc costs to be non-
negative. Because of the capacities of the arcs, each arc will have either no
flow or flow of 1 unit in the optimal solution. It is clear that there is a
one-to-one correspondence between the MCF from $s$ to $t$ on this constructed
graph and the optimum allocation for a single type of resource. If there is a
positive flow on the arc $(b_{i},t)$, this means that resource $i$ was not
used to meet demand. If there is a positive flow on the arc $(b_{i},u_{j})$,
this means that demand $j$ is the first demand met by resource $i$. Positive
flow on the arc $(v_{j},u_{k})$ means that demand $k$ is met immediately after
demand $j$ by the same resource. Finally, positive flow on the arc
$(u_{j},v_{j})$ means that demand $j$ was met.

###  11.7 Observation 1

Note that if travel times are zero, then $1R1D$ can be formulated as a maximum
weighted coloring problem on an interval graph. Consider $m$ resources and $n$
demands. We can now create an (undirected) interval graph $G=(N,A)$ as
follows:
Nodes:
For each demand, create a node $d_{i},i=1,\ldots,n$.
Arcs:
$(d_{i},d_{j})$ if $\tau_{i}+\Delta_{i}>\tau_{j}\hskip 10.00002pt\forall
i,j\in\\{1,2,\ldots,n\\}$
Then, we can solve the maximum weighted $m$-coloring problem on interval graph
$G$ using the following integer program:

$\displaystyle\max\sum_{i=1}^{n}w_{i}d_{i}$

s.t.

$\displaystyle\sum_{i\in S}d_{i}\leq m$ $\displaystyle\forall S\text{ s.t. $S$
is a maximal clique of size $\geq m$}$ $\displaystyle d_{i}\in\\{0,1\\}$
$\displaystyle\forall i=1,\ldots,n$

Since the nodes versus cliques matrix of an interval graph is totally
unimodular (Mertzios (2008)), then we can relax the above formulation to a
linear program and still maintain integral optimal solutions.

##  12 Computational Study

###  12.1 Bicriteria Results

Figures 2 and 2 present bicriteria results to compare the trade-off between
increasing the number of resources and its impact on the objective function
value (i.e., demands met). These results could provide insights for decision-
makers when determining resource capacity and desired levels of demand
satisfaction. In Figure 2, we examine the $mRmD$ problem with 3 resource
types, 400 demands, and 30 resources. Each line in the graph represents an
instance of this problem. Starting at 10 resources of each type, we increase
this amount by 0 to 15 and record the objective function value. As shown,
there is a diminishing return as resources are increased. On average, after
increasing the resources by about 6 or 7, we reach the maximum objective
function value for each instance studied. Figure 2 looks at the $2RmD$ problem
with 200 demands and 14 resources. In this case, we increase the number of
resources of each type separately by 0 to 11 and present the resulting
objective function value. Again, we see a diminishing return as resources are
increased. It is worth noting that jointly increasing resources (i.e.,
increasing both resource types) is more profitable than only increasing one
resource type. For example, increasing resource type 1 and type 2 by 3 and 4
resources, respectively, produced an objective of 13606 whereas only
increasing resource type 1 by 8 led to an objective of 12844.

Figure 1: Bicriteria results for $mRmD$

Figure 2: Bicriteria results for $2RmD$

###  12.2 Travel Costs

Let $BFlow$ and $CFlow$ represent solutions in which the flow variables ($x$)
are restricted to be binary and those in which the flow variables are relaxed
to be continuous, respectively. Tables 10 and 10 present a comparison of the
run times (in seconds) for $BFlow$ and $CFlow$ under all instances considered,
where $|R|$ is the number of resource types, $|D|$ is the number of demands,
and $L$ is the total number of resources. Note that Scaled Demands refers to
instances where reward for demand was multiplied by a factor of 100.

Computational experiments show that for small and medium sized problems (less
than 5 resource types), IPM-C can be efficiently solved by Gurobi and the
optimal solution can be found in reasonable time. As the size of the problem
increases (i.e., greater demands or larger number of resource types), the
instances become harder to solve. For 2-4 resource types, on average, $BFlow$
performs better than $CFlow$ when demands are not scaled, whereas when demands
are scaled, CFlow performs better than BFlow. For 5-7 resource types, on
average, $CFlow$ performs better than $BFlow$ in both scaled and unscaled
demand scenarios. However, for some instances, $BFlow$ is drastically better
than $CFlow$ (i.e., 7 resource types and 700/800 demands for unscaled/scaled
demands, respectively). In general instances with scaled demands perform
better than those in which demands are not scaled; this could be a result of
less importance given to travel costs in the objective.

Table 9: Results for number of resource types equal to 2,3 and 4

$|R|$ | $|D|$ | $L$ |  | Run time
---
(BFlow)
| Run time
---
(CFlow)
| Run time
---
(BFlow)
(Scaled Demands)
| Run time
---
(CFlow)
(Scaled Demands)
2 | 100 | 10 | 0.11 | 0.09 | 0.16 | 0.10
2 | 200 | 14 | 0.28 | 0.25 | 0.33 | 0.31
2 | 300 | 18 | 0.71 | 0.72 | 1.10 | 0.69
2 | 400 | 22 | 1.54 | 2.01 | 2.24 | 1.70
2 | 500 | 26 | 3.47 | 3.96 | 3.84 | 3.47
2 | 600 | 30 | 5.49 | 6.90 | 6.79 | 6.89
2 | 700 | 34 | 8.35 | 13.77 | 8.05 | 9.80
2 | 800 | 38 | 12.69 | 19.09 | 15.16 | 14.44
3 | 100 | 12 | 0.09 | 0.09 | 0.15 | 0.10
3 | 200 | 18 | 0.49 | 0.39 | 0.57 | 0.59
3 | 300 | 24 | 1.01 | 1.15 | 1.48 | 1.10
3 | 400 | 30 | 3.81 | 3.63 | 3.78 | 3.42
3 | 500 | 36 | 7.29 | 8.23 | 6.72 | 5.90
3 | 600 | 42 | 9.98 | 13.51 | 13.54 | 13.69
3 | 700 | 48 | 19.40 | 30.17 | 20.65 | 21.99
3 | 800 | 54 | 43.85 | 65.33 | 25.16 | 61.34
4 | 100 | 16 | 0.28 | 0.14 | 0.24 | 0.13
4 | 200 | 24 | 0.97 | 0.82 | 1.08 | 0.55
4 | 300 | 32 | 2.63 | 2.19 | 2.29 | 1.56
4 | 400 | 40 | 6.22 | 5.41 | 5.31 | 4.67
4 | 500 | 48 | 19.49 | 15.28 | 15.39 | 14.26
4 | 600 | 56 | 26.87 | 30.03 | 23.84 | 22.85
4 | 700 | 64 | 64.84 | 96.78 | 40.41 | 38.23
4 | 800 | 72 | 89.05 | 125.97 | 52.18 | 77.69

Table 10: Results for number of resource types equal to 5,6 and 7

$|R|$ | $|D|$ | $L$ |  | Run time
---
(BFlow)
| Run time
---
(CFlow)
| Run time
---
(BFlow)
(Scaled Demands)
| Run time
---
(CFlow)
(Scaled Demands)
5 | 100 | 20 | 0.19 | 0.19 | 0.13 | 0.18
5 | 200 | 30 | 2.00 | 1.01 | 1.10 | 0.80
5 | 300 | 40 | 6.36 | 3.68 | 3.39 | 2.74
5 | 400 | 50 | 14.79 | 9.20 | 9.04 | 7.76
5 | 500 | 60 | 35.01 | 32.58 | 21.28 | 17.83
5 | 600 | 70 | 50.66 | 70.35 | 51.90 | 73.11
5 | 700 | 80 | 96.25 | 172.39 | 47.01 | 53.80
5 | 800 | 90 | 453.05 | 1014.62 | 134.52 | 202.69
6 | 100 | 24 | 0.44 | 0.22 | 0.29 | 0.26
6 | 200 | 36 | 2.49 | 1.25 | 1.23 | 1.40
6 | 300 | 48 | 7.08 | 5.43 | 5.44 | 4.44
6 | 400 | 60 | 18.03 | 15.78 | 11.36 | 10.40
6 | 500 | 72 | 53.19 | 55.05 | 30.33 | 33.52
6 | 600 | 84 | 134.02 | 107.60 | 137.94 | 145.15
6 | 700 | 96 | 195.10 | 237.03 | 114.26 | 181.08
6 | 800 | 108 | 537.75 | 1039.68 | 232.16 | 285.46
7 | 100 | 28 | 0.33 | 0.25 | 0.29 | 0.20
7 | 200 | 42 | 2.06 | 1.63 | 1.85 | 1.27
7 | 300 | 56 | 13.76 | 8.58 | 9.92 | 5.92
7 | 400 | 70 | 125.48 | 55.14 | 23.67 | 17.23
7 | 500 | 84 | 161.38 | 112.70 | 67.47 | 51.95
7 | 600 | 98 | 421.19 | 389.39 | 133.33 | 167.05
7 | 700 | 112 | 989.80 | 1629.80 | 306.81 | 279.56
7 | 800 | 126 | 1485.61 | 1398.86 | 359.35 | 534.93

##  13 Extension 2

We present an extension to $mRmD$. In this extension, resource types have both
an origin and destination location, i.e., resources may not go directly from
demand incident to demand incident. For an overview of the additional notation
needed for this formulation, please refer to Table 11.

In order to construct feasible schedules for resources, we create 0-1 matrices
for each resource type $r\in R$, $A^{r}$, and a 0-1 matrix, $B$. Matrix
$A^{r}$ has a row and column for each demand incident and $A^{r}_{ij}=1$ if
and only if demand incident $j$ can be served after demand incident $i$ by
resource type $r$ and demands $i$ and $j$ both require resource type $r$.
Matrix $B$ has a row for each resource starting location and a column for each
demand incident and $B_{sd}=1$ if and only if a resource starting at location
$s$ can serve demand $d$ first. That is, we have the following pre-processing
matrices:

$\displaystyle A^{r}_{ij}$ $\displaystyle=\begin{cases}1\text{ iff}\hskip
10.00002pt\tau_{i}+\Delta_{i}+f(a_{i}^{r},b_{i}^{r})+f(b_{i}^{r},a_{j}^{r})\leq\tau_{j},\hskip
10.00002ptr\in M_{i}\cap M_{j}\\\ 0\text{ otherwise}\end{cases}$
$\displaystyle i,j\in D,r\in R$ $\displaystyle B_{sd}$
$\displaystyle=\begin{cases}1\text{ iff}\hskip
10.00002ptf(s,a_{d}^{r})\leq\tau_{d},s\in S^{r},r\in M_{d}\\\ 0\text{
otherwise}\end{cases}$ $\displaystyle s\in S^{r},r\in R,d\in D$

The formulation is the same as IPM, where variable construction relies on
matrices $A^{r}$ and $B$.

Table 11: Additional notation for Extension 2 $V$ | Set of nodes
---|---
$R$ | Set of resource types
$f(u,v)$ |  Travel time between $u,v\in V$
$(a_{d}^{r},b_{d}^{r})$ |  Origin-destination pair for resource type $r\in M_{d}$ needed by $d\in D$

## References

  * Ahuja et al. (1993) Ahuja R, Magnanti T, Orlin J (1993) _Network Flows: Theory, Algorithms, and Applications_ (Prentice Hall).
  * Altay (2013) Altay N (2013) Capability-based resource allocation for effective disaster response. _IMA Journal of Management Mathematics_ 24:253–266.
  * Amador Nelke and Zivan (2017) Amador Nelke S, Zivan R (2017) Incentivizing cooperation between heterogeneous agents in dynamic task allocation. _Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems_ , 1082–1090, AAMAS ’17 (Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems).
  * Baxter et al. (2020) Baxter AE, Wilborn Lagerman HE, Keskinocak P (2020) Quantitative modeling in disaster management: A literature review. _IBM Journal of Research and Development_ 64(1/2):3:1–3:13, URL http://dx.doi.org/10.1147/JRD.2019.2960356.
  * Bredström and Rönnqvist (2008) Bredström D, Rönnqvist M (2008) Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. _European Journal of Operational Research_ 191:19–31, URL http://dx.doi.org/10.1016/j.ejor.2007.07.033.
  * Carlisle and Lloyd (1995) Carlisle MC, Lloyd EL (1995) On the k-coloring of intervals. _Discrete Applied Mathematics_ 59(3):225 – 235.
  * Chen and Lee (1999) Chen J, Lee CY (1999) General multiprocessor task scheduling. _Naval Research Logistics (NRL)_ 46(1):57–74.
  * Ciupală (2009) Ciupală L (2009) About flow problems in networks with node capacities 8(8), ISSN 1109-2750.
  * De Angelis et al. (2007) De Angelis V, Mecoli M, Nikoi C, Storchi G (2007) Multiperiod integrated routing and scheduling of world food programme cargo planes in angola. _Computers & Operations Research_ 34(6):1601 – 1615, part Special Issue: Odysseus 2003 Second International Workshop on Freight Transportation Logistics.
  * Di Mascolo et al. (2014) Di Mascolo M, Espinouse ML, Ozkan CE (2014) Synchronization between human resources in home health care context. Matta A, Li J, Sahin E, Lanzarone E, Fowler J, eds., _Proceedings of the International Conference on Health Care Systems Engineering_ , 73–86 (Cham: Springer International Publishing), ISBN 978-3-319-01848-5.
  * Fang et al. (2017) Fang X, Luo J, Gao H, Wu W, Li Y (2017) Scheduling multi-task jobs with extra utility in data centers. _Eurasip Journal on Wireless Communications and Networking_ 2017\.
  * Garey and Johnson (1990) Garey MR, Johnson DS (1990) _Computers and Intractability; A Guide to the Theory of NP-Completeness_ (USA: W. H. Freeman & Co.).
  * Gauthier et al. (2015) Gauthier JB, Desrosiers J, Lübbecke ME (2015) About the minimum mean cycle-canceling algorithm. _Discrete Applied Mathematics_ 196:115 – 134, ISSN 0166-218X, URL http://dx.doi.org/https://doi.org/10.1016/j.dam.2014.07.005, advances in Combinatorial Optimization.
  * Gilmore and Hoffman (1964) Gilmore PC, Hoffman AJ (1964) A characterization of comparability graphs and of interval graphs. _Canadian Journal of Mathematics_ 16:539–548.
  * Gombolay et al. (2018) Gombolay MC, Wilcox RJ, Shah JA (2018) Fast scheduling of robot teams performing tasks with temporospatial constraints. _IEEE Transactions on Robotics_ 34(1):220–239.
  * Hashemi Doulabi et al. (2020) Hashemi Doulabi H, Pesant G, Rousseau LM (2020) Vehicle routing problems with synchronized visits and stochastic travel and service times: Applications in healthcare. _Transportation Science_ 54(4):1053–1072, URL http://dx.doi.org/10.1287/trsc.2019.0956.
  * Huang et al. (2012) Huang M, Smilowitz K, Balcik B (2012) Models for relief routing: Equity, efficiency and efficacy. _Transportation Research Part E: Logistics and Transportation Review_ 48(1):2 – 18.
  * Håstad (1996) Håstad J (1996) Clique is hard to approximate within $n^{1-\epsilon}$. _Acta Mathematica_ , 627–636.
  * Kartal et al. (2016) Kartal B, Nunes E, Godoy J, Gini M (2016) Monte carlo tree search for multi-robot task allocation. 4222–4223, AAAI’16 (AAAI Press).
  * Keskinocak and Tayur (1998) Keskinocak P, Tayur S (1998) Scheduling of time-shared jet aircraft. _Transportation Science_ 32(3):277–294.
  * Lee et al. (2013) Lee K, Lei L, Pinedo M, Wang S (2013) Operations scheduling with multiple resources and transportation considerations. _International Journal of Production Research_ 51(23-24):7071–7090.
  * Liu and Kroll (2012) Liu C, Kroll A (2012) A centralized multi-robot task allocation for industrial plant inspection by using a* and genetic algorithms. _ICAISC_.
  * Mao (1995) Mao W (1995) Multi-operation multi-machine scheduling. Hertzberger B, Serazzi G, eds., _High-Performance Computing and Networking_ , 33–38 (Berlin, Heidelberg: Springer Berlin Heidelberg).
  * Mertzios (2008) Mertzios GB (2008) A matrix characterization of interval and proper interval graphs. _Applied Mathematics Letters_ 21(4):332 – 337.
  * Olariu (1991) Olariu S (1991) An optimal greedy heuristic to color interval graphs. _Information Processing Letters_ 37(1):21 – 25.
  * Rauchecker and Schryen (2019) Rauchecker G, Schryen G (2019) An exact branch-and-price algorithm for scheduling rescue units during disaster response. _European Journal of Operational Research_ 272(1):352 – 363, ISSN 0377-2217.
  * Su et al. (2016) Su Z, Zhang G, Liu Y, Yue F, Jiang J (2016) Multiple emergency resource allocation for concurrent incidents in natural disasters. _International Journal of Disaster Risk Reduction_ 17:199 – 212, ISSN 2212-4209.
  * Viswanath and Peeta (2003) Viswanath K, Peeta S (2003) Multicommodity maximal covering network design problem for planning critical routes for earthquake response. _Transportation Research Record_ 1857(1):1–10.
  * Wright (2018) Wright D (2018) Conditions of participation for home health agencies interpretive guidelines. _Centers for Medicare and Medicaid Services_ .
  * Xu et al. (2016) Xu H, Satish Kumar TK, Johnke D, Ayanian N, Koenig S (2016) Sagl: A new heuristic for multi-robot routing with complex tasks. _2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)_ , 530–535.
  * Yannakakis and Gavril (1987) Yannakakis M, Gavril F (1987) The maximum k-colorable subgraph problem for chordal graphs. _Information Processing Letters_ 24(2):133 – 137.
  * Zheng and Koenig (2008) Zheng X, Koenig S (2008) Reaction functions for task allocation to cooperative agents. 559–566.