11institutetext: 1University of Massachusetts Amherst, 2Rice University
Contact Email: 11email<EMAIL_ADDRESS>
# Automated Scoring for Reading Comprehension via In-context BERT Tuning

Nigel Fernandez 11 Aritra Ghosh 11 Naiming Liu 22 Zichao Wang 22 Benoît
Choffin  Richard Baraniuk 22 Andrew Lan 11

###### Abstract

Automated scoring of open-ended student responses has the potential to
significantly reduce human grader effort. Recent advances in automated scoring
often leverage textual representations based on pre-trained language models
such as BERT and GPT as input to scoring models. Most existing approaches
train a separate model for each item/question, which is suitable for scenarios
such as essay scoring where items can be quite different from one another.
However, these approaches have two limitations: 1) they fail to leverage item
linkage for scenarios such as reading comprehension where multiple items may
share a reading passage; 2) they are not scalable since storing one model per
item becomes difficult when models have a large number of parameters. In this
paper, we report our (grand prize-winning) solution to the National Assessment
of Education Progress (NAEP) automated scoring challenge for reading
comprehension. Our approach, in-context BERT fine-tuning, produces a single
shared scoring model for all items with a carefully-designed input structure
to provide contextual information on each item. We demonstrate the
effectiveness of our approach via local evaluations using the training dataset
provided by the challenge. We also discuss the biases, common error types, and
limitations of our approach.

###### Keywords:

Automated Scoring BERT Reading Comprehension

##  1 Introduction

Automated scoring (AS) refers to the problem of using algorithms to
automatically score student responses to open-ended items. AS approaches have
the potential to significantly reduce the amount of human grading effort and
scale well to an ever-increasing student population. AS has been studied in
many different contexts, especially essays, known as automated essay scoring
(AES) [1, 18], but also in other contexts such as automatic short answer
grading (ASAG) [23, 31] for domains including humanities, social sciences
[21], and math [3].

Existing approaches for AS include feature engineering, i.e., developing
features that summarize the length, syntax [4, 9, 18], cohesion [11],
relevance to the item [19], and semantics [25] of student responses combined
with machine learning-based classifiers [2, 16] to predict the score. These
approaches have excellent interpretability but require human expertise in
feature development. Recent approaches leverage advances in deep learning to
produce better textual representations of student responses, alleviating the
need to rely on human-engineered features. Examples include combining neural
networks with human-engineered features for score prediction [24] and
especially approaches that fine-tune neural language models (LMs) such as BERT
[8] and GPT-2 [20] on the downstream AS task [14, 15, 22, 28]. Despite
concerns on the vulnerability against gaming input [14] and fairness aspects
[13] of these approaches, they have performed well in terms of scoring
accuracy on publicly available benchmark datasets such as the automated
student assessment prize (ASAP) for essay scoring [1].

However, existing AS approaches are limited in many ways, including a
significant one we address in this paper: They almost always train a separate
AS model for each item. This approach is acceptable in contexts such as AES
since the items (essay prompts) are likely not highly related to each other.
However, in other contexts such as reading comprehension, multiple items may
share the same background passage; Training a separate model for each item
fails to leverage this shared background information. More importantly, this
approach results in a separate model for each item; for LM-based models that
have millions of parameters, this approach creates a significant model storage
problem.

####  1.0.1 Contributions

In this paper, we detail a novel AS approach for reading comprehension items
via in-context fine-tuning of LMs, which is our (grand prize-winning) solution
to the item-specific part of the National Assessment of Educational Progress
(NAEP) automated scoring challenge.111Ran by the US Dept. of Education:
https://github.com/NAEP-AS-Challenge/info We make our implementation publicly
available222Our code can be found at: https://github.com/ni9elf/automated-
scoring to facilitate future work on automated scoring. Our contributions are
listed below:

  * •

We develop an AS approach based on multi-task and meta-learning ideas, which
fine-tunes an LM with a carefully designed input format that captures the
context of each individual item. Our approach effectively leverages potential
linkage across all items.

  * •

We demonstrate the effectiveness of our AS approach through experimental
evaluation on the NAEP challenge training dataset. Our approach outperforms
existing LM-based AS approaches and significantly outperforms other non-LM-
based baselines.

  * •

We qualitatively analyze the cause of scoring errors made by our approach. We
also show that our AS approach exhibits modest bias towards different student
demographic groups. We outline a series of avenues for future work to improve
the applicability of our approach in real-world settings.

##  2 Methodology

In this section, we first introduce the problem setup for the NAEP AS
challenge (Section 2.1) and then detail our meta-trained BERT with in-context
tuning approach for reading comprehension AS (Section 2.2).

###  2.1 Problem Formulation

Table 1: Text snippets from an example grade 8 reading comprehension item. Passage |  Long ago, a poor country boy left home to seek his fortune. Day and night he traveled, stopping to eat at inns along … |
---|---|---
Question |  Describe what kind of person the merchant is. Give one detail from the story to support your answer. |
Dataset | Student Responses | Scores
“The merchant is a very optimistic and persevering person. For example, it states how he kept walking on even with an empty stomach. This shows that he is hopeful and not willing to give up after he had come so far.” | 3
“the merchant is a determined and honest person” | 2
“Dishonest because he didn’t want to pay for the eggs.” | 1

The NAEP AS challenge features $20$ reading comprehension items from grade 4
and grade 8. Each reading comprehension item, indexed by $i$, is associated
with 1) a long reading passage text $P_{i}$, 2) a short question text $Q_{i}$,
3) a scoring rubric, and 4) a large training dataset of human scored student
responses $D_{i}^{train}=\\{(x_{j},y_{j})\\}$. The goal is for trained models
to predict human scores for student responses in the test dataset
$D_{i}^{test}=\\{(x_{j}^{target})\\}$ for all tasks $i$. A key observation is
that pairs of items $(l,m)$, one from grade 4 ($l$) and one from grade 8
($m$), often share passage $(P_{l}=P_{m})$ and question $(Q_{l}=Q_{m})$ texts.
This linkage across items motivates our approach of leveraging shared item
semantics by not treating items independently. Instead of training a separate
model for each item, as in existing approaches, we meta-train a single shared
AS model to perform in-context learning across all items. A snapshot of an
example item from the NAEP question
tool333https://nces.ed.gov/NationsReportCard/nqt/Search is shown in Table 1.

###  2.2 Our Approach: Meta-trained BERT with In-context Tuning

####  2.2.1 LM Fine-tuning Setup.

We first describe our LM fine-tuning approach for reading comprehension AS. We
use a pre-trained BERT [8] model as the base LM for AS.444We also tried GPT-2
[20] and reached similar scoring performance. Therefore, for simplicity of
exposition, we only detail our approach with BERT as the base LM. We use a
combination of the passage $P_{i}$, question $Q_{i}$, and student response
text $x_{j}^{target}$ as input to the BERT model. We add [SEP], the separator
token in BERT’s vocabulary, between these parts to help the model
differentiate input text segments with different purposes. Since the average
passage length was $657$ words, directly inputting every token in the passage
text exceeds the maximum input length of $512$ tokens for BERT. As a
workaround, we use a separate, fixed BERT model (we do not fine-tune its
parameters) to encode the passage text and use its [CLS] embedding vector as
input to the BERT model for AS. We experiment with two ways to encode the
passage text: either the entire passage as one token, or each sentence as one
token. For the downstream AS task, we feed the [CLS] embedding vector of the
BERT AS model to a linear classification layer followed by softmax [10] during
fine-tuning.

####  2.2.2 Meta-training BERT with In-context Learning.

Figure 1: Meta-trained BERT via in-context tuning. Best viewed in color.

We now detail the key component of our approach, in-context learning of a
shared BERT AS model across all items. Our approach is to use a carefully-
designed input structure to provide context to the shared BERT AS model and
associate it with each specific item. To achieve this, following recent
approaches for meta-training-based in-context learning [6, 17], we add in-
context examples which are (response, score) pairs from the training set, to
the input. Intuitively, these examples provide further context about each item
and enable the BERT AS model to focus on learning to associate responses to
scores given the passage and the question, thus enabling knowledge sharing
across items.

Figure 1 shows the input structure to the BERT AS model. We build the model
input by concatenating the target student response text $x_{j}^{target}$ that
needs to be scored, passage $P_{i}$, question $Q_{i}$, and $K$ response-score
examples $E_{i}\subseteq D_{i}^{train},|E_{i}|=K$. Moreover, we convert the
numeric scores $y_{j}$ in the in-context examples $E_{i}$ to meaningful words
as: $\\{1:\text{poor},2:\text{fair},3:\text{good},4:\text{excellent}\\}$
before adding them to the model input. We add semantically meaningful task
instructions to each input component as shown in Figure 1.

Since each item $i$ has a different range of possible scores
$y_{j}\in[s_{min}=\\{1\\},s_{max}=\\{2,3,4\\}]$, we add possible score classes
for $x_{j}^{target}$ as explicit options [26] in the input to make the model
aware of valid scores as seen in the answer template in Figure 1. Furthermore,
we mask out the invalid score classes for each response before computing the
softmax. This masking procedure ensures that training loss is backpropagated
over valid score classes only, enabling us to meta-train a single shared model
for all items.

####  2.2.3 Meta-training.

We train our AS model on the union of training datasets for all items
$\bigcup_{i=1}^{20}D_{i}^{train}$. Let $\theta$ represent the model parameters
to be learned, i.e., BERT parameters which are fine-tuned after initialization
from their pre-trained values and the classification layer parameters which
are learned from scratch. The in-context learning objective $\mathcal{L}_{i}$
for an item is simply the cross entropy, i.e., negative log-likelihood loss
[10]:

$\mathcal{L}_{i}(\theta)=\sum_{(x_{j}^{target},y_{j}^{target})\in
D_{i}^{train}}[-\log
p_{\theta}(y_{j}^{target}|x_{j}^{target},P_{i},Q_{i},E_{i})],$

while the objective across all $20$ items is given by:

$\mathcal{L}(\theta)=\sum_{i=1}^{20}\mathcal{L}_{i}(\theta).$

In contrast, existing approaches result in a separate set of model parameter
$\theta_{i}$ for each item, which increases the number of model parameters and
thus storage space requirement by $20\times$.

##  3 Experimental Evaluation

In this section, we detail our experiments on the training dataset provided by
the NAEP AS challenge. We conduct both quantitative evaluations on scoring
accuracy of our approach and qualitative evaluations on the error types and
fairness aspects of our approach.

###  3.1 Dataset Details

Each item in the NAEP AS Challenge has responses from either one of two
formats: short (around one sentence) or extended (up to around five sentences)
responses, leading to different score classes. The minimum score for all items
is $1$, with the maximum being either $2$ or $3$ for short responses and $3$
or $4$ for extended responses. Passages and questions have around $657$ and
$27$ words on average, respectively. Our training dataset (combined from the
challenge’s training and validation datasets) contains on average more than
$18,000$ human-scored student responses per item. Each response in the
training dataset is scored by either one or two human raters. We are also
provided with the gender and ethnicity of the student who submitted each
response. The average student response length is $19$ and $37$ words for
grades $4$ and $8$, respectively. There are $4$ unique passages and $12$
unique questions; $8$ pairs of items (one from grade $4$ and one from grade
$8$) share the same passage and question text. The $4$ remaining items have
unique questions.

###  3.2 Metrics and Baselines

Following the NAEP AS challenge, we use quadratic weighted Kappa (QWK), a
popular metric for AES, as the accuracy metric. QWK examines the agreement
between the predicted scores and the ground truth human scores for ordered
score classes. We compare our approach, dubbed meta-trained BERT with in-
context tuning, to various baselines including existing approaches for AES and
several variants of our approach, listed below. The latter serves as an
ablation study to verify the importance of each component of our approach.

  * •

Human provides an estimated upper bound on scoring accuracy given by the
inter-rater agreement. For each item, we calculate the QWK on around $550$
training responses that are scored by two human raters.

  * •

Majority simply scores each response by the most frequent score for that item
in the training dataset.

  * •

Feature Engineering uses a feature-engineering approach with a selected set of
features listed in Table 2 for a random forest classifier.

  * •

Stacked LSTM uses a stack of two LSTMs on Word2Vec embeddings followed by a
non-linear output layer using ReLU activation.

  * •

Clusering + Classification, uses cluster indicators of student responses
(computed via K-means clustering on their Word2Vec embeddings) in conjunction
with other features for a random forest classifier.

  * •

BERT (response) fine-tunes a BERT model for each item independently using only
response text as input, resulting in $20$ different AS models.

  * •

BERT (passage+question+response) adds passage and question information as
input to the setup of BERT (response).

  * •

BERT in-context adds in-context examples as input to the setup of BERT
(passage+question+response) providing further context on each item.

  * •

BERT multi-task uses a multi-task learning approach and fine-tunes a single
shared BERT AS model with $20$ separate classification layers, one for each
item. We backpropagate the loss for a student response from item $i$ to train
only the corresponding classification layer while fine-tuning the shared BERT
model on all items.

Table 2:  Human-designed features used in baseline models. Type |  Features
---|---
Length |  Counts of words, characters, stop words, and punctuation. Character to word ratio.
Syntax |  Counts of lemmas, nouns, verbs, adjectives, adverbs, and conjunctives.
Readability |  Automated Readability Index, Coleman Liau Index, Dale Chall Score, Smog Index, and Flesch Score.

###  3.3 Implementation Details

####  3.3.1 Preprocessing: Spell Check.

We automatically correct spelling errors in student responses for two reasons:
1) the scoring rubrics have clear instructions on ignoring such errors and 2)
to transform the response text written by students to be similar to what BERT
uses in pre-training. Spelling errors are frequently seen in grade $4$
responses but are less frequent in grade $8$. We experiment with training
models on student responses with and without spell checking; The spell checked
version leads to an improvement of around $0.5\%$ on QWK. We use NeuSpell’s
BERT based checker [12] to correct spelling errors on all student responses.

####  3.3.2 Experimental Setup.

For our local evaluation, we perform five-fold cross-validation on the
training dataset for each item and use three folds for training, one fold for
validation to perform early stopping, and one fold for testing. For double-
scored student responses where the human-rater scores do not agree, we use the
score by the first rater, following the challenge specification.

Table 3:  Experimental results averaged across reading comprehension items in the NAEP AS challenge dataset. Model performance in Quadratic Weighted Kappa (higher is better). Bold indicates best result except human performance. Approach |  Avg. QWK |  p-value
---|---|---
Human |  $0.878$ |  -
Majority |  $0.527$ |  -
Feature Engineering + Random Forest |  $0.443$ |  -
Stacked LSTM |  $0.657$ |  -
Clustering + Classification |  $0.709$ |  -
BERT (response) |  $0.828$ |  -
BERT (passage+question+response) |  $0.828$ |  $0.414$
BERT in-context |  $0.833$ |  $0.001$
BERT multi-task |  $0.833$ |  $1.6\text{\times}{10}^{-4}$
Meta-trained BERT in-context |  $\mathbf{0.841}$ |  $9.6\text{\times}{10}^{-5}$

We use a pre-trained BERT [8] model with $110M$ parameters; all implementation
was done using the HuggingFace [27] transformers library. We use the Adam
optimizer, a batch size of $32$, a learning rate of $2\cdot 10^{-5}$, and a
maximum input length of $512$ tokens. We do not perform any hyperparameter
tuning and simply use the default parameters for BERT. We fine-tune all BERT-
based models for $10$ epochs since they reach optimal performance on the
validation set by around $5$ epochs. Our meta-trained BERT with in-context
tuning takes $6$ hours per training epoch on a single NVIDIA RTX $8000$ GPU.

For our meta-trained BERT model with in-context tuning, for each training
response, we randomly sample up to $25$ in-context examples per score class
from the training dataset of the corresponding item. We ensure at least one
example from each valid scoring class so that the set of examples cover all
classes and is diverse. Given the restriction on input length for BERT, we
truncate each example to $70$ tokens. At test time, for a target student
response to be scored, we repeat the aforementioned process of randomly
sampling examples for $8$ times and average the predicted score class
probabilities.

Table 4:  Results averaged over shared vs. non-shared reading comprehension items from grade 4 (G4) and grade 8 (G8). Model performance in Quadratic Weighted Kappa (higher is better). Bold indicates best result except human performance. Approach |  Non-shared G4 |  Shared G4 |  Non-shared G8 |  Shared G8
---|---|---|---|---
Human |  $0.860$ |  $0.899$ |  $0.809$ |  $0.885$
BERT (response) |  $0.825$ |  $0.842$ |  $0.763$ |  $0.840$
BERT (passage+question+response) |  $0.820$ |  $0.843$ |  $0.762$ |  $0.839$
BERT in-context |  $0.822$ |  $0.847$ |  $\mathbf{0.771}$ |  $0.843$
BERT multi-task |  $0.817$ |  $0.848$ |  $0.765$ |  $0.845$
Meta-trained BERT in-context |  $\mathbf{0.826}$ |  $\mathbf{0.856}$ |  $\mathbf{0.771}$ |  $\mathbf{0.853}$

###  3.4 Results and Analysis

We report the average QWK across all items and all cross validation folds for
all approaches in Table 3. LM-based approaches consistently outperform non-LM-
based approaches, by a significant margin, while our approach, meta-trained
BERT in-context, performs best. We perform paired t-tests among LM-based
approaches using BERT (response) as the baseline; We see that learning a
single shared model across items achieves statistically significant
improvement over learning one model per item. This observation validates our
intuition that we can leverage shared information across reading comprehension
items to improve AS accuracy. We also observe that, surprisingly, adding
passage and question text as input in addition to response text does not lead
to improved performance. This observation suggests that our models are trained
for AS but cannot perform reading comprehension; We discuss this in detail in
Section 4. Table 4 lists performance of LM-based approaches on shared vs. non-
shared items. Overall, our approach performs better than BERT (response), more
on items that are shared across grades $4$ and $8$ and less on items that are
not shared. This observation suggests that our approach may struggle to
generalize to previously unseen items, which is an important avenue for future
work. For most items, some LM-based approach reach a level of AS accuracy
close to that for humans (as measured in QWK between two human scorers). While
there is still room for improvement, it is important to gauge the limit of AS
approaches due to intrinsic noise in data.

####  3.4.1 Qualitative Error Analysis.

We randomly sample $100$ responses to the item “describe what kind of person
the merchant is …” as seen in Table 1 that our approach scores incorrectly. We
identify $5$ main error types and list them in Table 5 with made-up examples
that reflect our observation: 1) spelling and grammar errors (not caught by
spell check), 2) human error and subjectivity, 3) infrequent correct responses
(our approach struggles at recognizing correct responses that do not occur
frequently), 4) imitation (incorrect responses with content/structure that
mimic correct responses), 5) character coreference (referring to a character
different than the one that the item asks about). These observations reveal
further ways to improve LM-based AS approaches for reading comprehension.

Table 5:  Illustration of responses that our approach tends to score incorrectly. Error Type |  Example Student Response |  Predicted Score |  Ground Truth
---|---|---|---
Spelling/grammar |  “mearchant are a good man because he played the innkeeper and kept his …” | 2 | 3
Human error & subjectivity |  “Long ago a poor country boy left home to seek his fortune. Day and night he …” | 1 | 3
Infrequent correct answers |  “merchant is described as brave as he got on a ship and visited multiple ports …” | 2 | 4
Imitation |  “The merchant is dishonest because he doesn’t want to pay for the eggs …” | 3 | 1
Character coreference |  “The merchant is greedy because he gives the innkeeper eggs but when the boy …” | 4 | 1

####  3.4.2 Fairness Studies.

We conduct a preliminary investigation into the fairness aspects of our
approach using the demographic information in the NAEP AS challenge dataset.
There are a total of 9 demographic groups, each corresponding to a gender or
an ethnicity group. For students in each group, we compute the average
prediction bias, i.e., the average difference between the predicted score and
the actual score. A positive bias means that the model overestimates the score
for the group while a negative bias means that the model underestimates the
score. We experiment with two settings: not using the demographic information
(gender/ethnicity) as input vs. using it as input to the BERT model. We test
both settings since it is not clear whether leaving out demographic
information or other sensitive attributes results in more fair models [29].
When using demographic information as input, we prepend the input with textual
instructions such as “score this answer written by a Female Asian student”,
according to the demographics of the student. Figure 2 shows the prediction
biases for a shared item in both grades 4 and 8. We see that our approach
tends to overestimate the score, except for Pacific Islanders/American Indians
on grade 4, which is possibly due to the small number of such students in the
training data. In general, the biases are within an acceptable range (the same
conclusion is also reached on the official challenge test set).

Figure 2: Prediction biases grouped by student demographics with and without
demographic data as input for a shared item used in both grade 4 (left) and
grade 8 (right).

##  4 Discussion, Conclusions, and Future Work

In this paper, we detailed our solution to the NAEP automated scoring
challenge, an in-context BERT fine-tuning approach that is suitable for
reading comprehension items. We now discuss some important observations and
outline several avenues for future work towards the scalable deployment of
language model-based automated scoring approaches in real-world scenarios.

First and foremost, we observe that our best-performing model takes as input
only the in-context examples, question text and the target response but not
the reading comprehension passage. Although this approach is due to the
technical limitation that these passages are often longer than what language
models can input, this observation means that our model does not master the
task of reading comprehension; instead, it only learns to assess how
appropriate the response is given the item. Future work should find ways to
efficiently pass information contained in the passage to the model using a
small number of tokens, such as retrieving only relevant sentences [5]. Models
that learn to score responses in the context of the passage will be better
suited for generalization to new items.

Second, we observe that adding an additional spell checking step improved
automated scoring accuracy and that using BERT only as a text featurization
tool without fine-tuning leads to a significant drop in scoring accuracy.
These observation suggest that BERT is not adept at student-generated text.
Future work should pre-train base language models on student-generated text
before applying them to downstream tasks.

Third, we observe that our models do not offer any explanation on their score
predictions due to the black-box nature of language models. Future work should
incorporate grading rubrics into the scoring model or use other ways to
improve model interpretability, such as using attention maps [7].

Fourth, we observe that our models, without explicitly controlling for
fairness, exhibit unavoidable but modest biases toward students in different
demographic groups. Future work should incorporate fairness regularization
into the training objective to promote fairness across students [30].

####  4.0.1 Acknowledgements.

Fernandez, Ghosh, and Lan are partially supported by the National Science
Foundation under grants IIS-1917713 and IIS-2118706.

## References

  * [1] The hewlett foundation: Automated essay scoring. Online: https://www.kaggle.com/c/asap-aes, accessed: May 2022
  * [2] Attali, Y., Burstein, J.: Automated essay scoring with e-rater® v.2. The Journal of Technology, Learning and Assessment 4(3) (2006)
  * [3] Baral, S., Botelho, A.F., Erickson, J.A., Benachamardi, P., Heffernan, N.T.: Improving automated scoring of student open responses in mathematics. In: 14th International Conference on Educational Data Mining (EDM) (2021)
  * [4] Burstein, J.: The e-rater® scoring engine: Automated essay scoring with natural language processing. (2003)
  * [5] Chen, D., Fisch, A., Weston, J., Bordes, A.: Reading wikipedia to answer open-domain questions. In: 55th Annual Meeting of the Association for Computational Linguistics (ACL). pp. 1870–1879 (2017)
  * [6] Chen, Y., Zhong, R., Zha, S., Karypis, G., He, H.: Meta-learning via language model in-context tuning. In: 60th Annual Meeting of the Association for Computational Linguistics (ACL) (2022)
  * [7] Clark, K., Khandelwal, U., Levy, O., Manning, C.D.: What does bert look at? an analysis of bert’s attention. In: BlackBoxNLP@ACL (2019)
  * [8] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: NAACL-HLT (2019)
  * [9] Foltz, P.W., Laham, D., Landauer, T.K.: The intelligent essay assessor: Applications to educational technology. Interactive Multimedia Electronic Journal of Computer-Enhanced Learning 1(2), 939–944 (1999)
  * [10] Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press (2016)
  * [11] Graesser, A.C., McNamara, D.S., Louwerse, M.M., Cai, Z.: Coh-Metrix: Analysis of text on cohesion and language. Behavior research methods, instruments, & computers 36(2), 193–202 (2004)
  * [12] Jayanthi, S.M., Pruthi, D., Neubig, G.: NeuSpell: A neural spelling correction toolkit. In: 25th Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 158–164 (2020)
  * [13] Litman, D., Zhang, H., Correnti, R., Matsumura, L.C., Wang, E.: A fairness evaluation of automated methods for scoring text evidence usage in writing. In: 22nd Conference on Artificial Intelligence in Education (AIED). pp. 255–267 (2021)
  * [14] Lottridge, S., Godek, B., Jafari, A., Patel, M.: Comparing the robustness of deep learning and classical automated scoring approaches to gaming strategies. Tech. rep., Cambium Assessment Inc. (2021)
  * [15] Mayfield, E., Black, A.W.: Should you fine-tune bert for automated essay scoring? In: 15th Workshop on Innovative Use of NLP for Building Educational Applications. pp. 151–162 (2020)
  * [16] McNamara, D.S., Crossley, S.A., Roscoe, R.D., Allen, L.K., Dai, J.: A hierarchical classification approach to automated essay scoring. Assessing Writing 23, 35–59 (2015)
  * [17] Min, S., Lewis, M., Zettlemoyer, L., Hajishirzi, H.: MetaICL: Learning to learn in context. In: NAACL-HLT (2022)
  * [18] Page, E.B.: The imminence of… grading essays by computer. The Phi Delta Kappan 47(5), 238–243 (1966)
  * [19] Persing, I., Ng, V.: Modeling prompt adherence in student essays. In: 52nd Conference of the Association for Computational Linguistics (ACL) (2014)
  * [20] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I.: Language models are unsupervised multitask learners. OpenAI blog (2019)
  * [21] Sung, C., Dhamecha, T., Saha, S., Ma, T., Reddy, V., Arora, R.: Pre-training BERT on domain resources for short answer grading. In: 24th Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 6071–6075 (2019)
  * [22] Taghipour, K., Ng, H.T.: A neural approach to automated essay scoring. In: 21st Conference on Empirical methods in natural language processing (EMNLP). pp. 1882–1891 (2016)
  * [23] Uto, M., Uchida, Y.: Automated short-answer grading using deep neural networks and item response theory. In: 21st International Conference on Artificial Intelligence in Education (AIED). pp. 334–339 (2020)
  * [24] Uto, M., Xie, Y., Ueno, M.: Neural automated essay scoring incorporating handcrafted features. In: 28th Conference on Computational Linguistics (COLING). pp. 6077–6088 (2020)
  * [25] Valenti, S., Neri, F., Cucchiarelli, A.: An overview of current research on automated essay grading. Journal of Information Technology Education: Research 2(1), 319–330 (2003)
  * [26] Wei, J., Bosma, M., Zhao, V.Y., Guu, K., Yu, A.W., Lester, B., Du, N., Dai, A.M., Le, Q.V.: Finetuned language models are zero-shot learners. In: 10th International Conference on Learning Representations (ICLR) (2022)
  * [27] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Scao, T.L., Gugger, S., Drame, M., Lhoest, Q., Rush, A.M.: Transformers: State-of-the-art natural language processing. In: EMNLP: System Demonstrations. pp. 38–45 (2020)
  * [28] Yang, R., Cao, J., Wen, Z., Wu, Y., He, X.: Enhancing automated essay scoring performance via fine-tuning pre-trained language models with combination of regression and ranking. Findings of the Association for Computational Linguistics: EMNLP pp. 1560–1569 (2020)
  * [29] Yu, R., Lee, H., Kizilcec, R.F.: Should college dropout prediction models include protected attributes? In: 8th ACM Conference on Learning at Scale (L@S). pp. 91–100 (2021)
  * [30] Zafar, M.B., Valera, I., Gomez Rodriguez, M., Gummadi, K.P.: Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In: 26th International Conference on World Wide Web (WWW). pp. 1171–1180 (2017)
  * [31] Zhang, Y., Shah, R., Chi, M.: Deep learning + student modeling + clustering: A recipe for effective automatic short answer grading. In: 9th International Conference on Educational Data Mining (EDM) (2016)


# Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using
Drones

L. Sunil Chandran  Indian Insitute of Science, Bengaluru, India  Rishikesh
Gajjala  Indian Insitute of Science, Bengaluru, India  Shravan Mehra  Indian
Insitute of Science, Bengaluru, India  University of Birmingham, UK  Saladi
Rahul  Indian Insitute of Science, Bengaluru, India

###### Abstract

The focus of this paper is to increase our understanding of the Longest
Processing Time First (LPT) heuristic. LPT is a classical heuristic for the
fundamental problem of uniform machine scheduling. For different machine
speeds, LPT was first considered by Gonzalez et al. (SIAM J. Comput.
6(1):155–166, 1977). Since then, extensive work has been done to improve the
approximation factor of the LPT heuristic. However, all known implementations
of the LPT heuristic take $O(mn)$ time, where $m$ is the number of machines
and $n$ is the number of jobs. In this work, we come up with the first near-
linear time implementation for LPT. Specifically, the running time is
$O((n+m)(\log^{2}{m}+\log{n}))$. Somewhat surprisingly, the result is obtained
by mapping the problem to dynamic maintenance of lower envelope of lines,
which has been well studied in the computational geometry community.

Our second contribution is to analyze the performance of LPT for the Drones
Warehouse Problem (DWP), which is a natural generalization of the uniform
machine scheduling problem motivated by drone-based parcel delivery from a
warehouse. In this problem, a warehouse has multiple drones and wants to
deliver parcels to several customers. Each drone picks a parcel from the
warehouse, delivers it, and returns to the warehouse (where it can also get
charged). The speeds and battery lives of the drones could be different, and
due to the limited battery life, each drone has a bounded range in which it
can deliver parcels. The goal is to assign parcels to the drones so that the
time taken to deliver all the parcels is minimized. We prove that the natural
approach of solving this problem via the LPT heuristic has an approximation
factor of $\phi$, where $\phi\approx 1.62$ is the golden ratio.

##  1 LPT heuristic for uniform scheduling

Uniform machine scheduling with the minimum makespan objective is a
fundamental problem. In this problem, we are given a set of $n$ jobs (not
necessarily of the same size) and a set of $m$ machines (not necessarily of
the same speeds). The goal is to schedule the $n$ jobs on $m$ machines so that
the time required to execute the schedule (makespan) is minimised. This is an
NP-hard problem even for two machines [13] of the same speed, but polynomial
time approximation schemes (PTASs) are known [20, 21].

A commonly studied heuristic for this problem is the Longest Processing Time
First (LPT) heuristic. In the LPT heuristic, each job is assigned one by one,
in non-increasing order of size, so that every job is assigned to a machine
where it will be completed earliest (with ties being broken arbitrarily). Note
that a machine might already have some jobs assigned to it and the execution
of the current job happens only after finishing the already assigned jobs.

More intricate algorithms were designed in the literature to get a good
approximation factor for uniform scheduling. For example, Horowitz and Sahni
gave an exact dynamic programming algorithm which runs in exponential time
[22]. When there are only two machines, they could build upon this algorithm
to obtain a Polynomial-time approximation scheme (PTAS). Later, Hochbaum and
Schmoys gave a PTAS when all the machines had identical speeds [20]. This was
later extended to obtain a PTAS for the uniform scheduling problem [21].

However, the LPT algorithm remains popular in practice due to its simplicity
and scalability (compared to the PTAS-type results which are relatively
complicated and have expensive running time). As a result, there has been a
long line of research on improving the approximation ratio of the LPT
algorithm for USP. In two independent works, the ratio of the LPT algorithm
was improved by Dobson [10] to $\frac{19}{12}$ and by Friesen [12] to
$\frac{5}{3}$. Kovacs [28] further improved the approximation factor of the
LPT algorithm to $1.58$ and proved that the LPT algorithm cannot give an
approximation factor better than $1.54$.

##  2 First result: A near-linear time implementation of LPT

In spite of all the focus in the literature on adapting LPT to various
settings of machine scheduling and analyzing its approximation factor, to the
best of our knowledge, there has been no work on fast implementation of LPT.
The known implementation of the LPT heuristic takes $O(mn)$ time (via the
naive approach). In this work, we give the first near-linear time
implementation of the LPT heuristic.

######  Theorem 2.1.

There is an $O((n+m)(\log^{2}{m}+\log{n}))$ time implementation of the LPT
heuristic.

For a set of given lines in 2- D, the lower envelope is the point-wise minimum
of the lines (a more formal definition will follow later). In the dynamic
maintenance of the lower envelope problem, in each step, a new line is added
(or removed), as shown in fig. 5.1, and one has to maintain the lower envelope
with a small update time. This has been well-studied in the computational
geometry community. We establish a connection from LPT to the dynamic
maintenance of the lower envelope of lines to prove theorem 2.1 in section 5.

Our second contribution is to analyze the performance of LPT for the Drones
warehouse problem (DWP) (formally defined in section 3.1) which is a natural
generalization of the uniform scheduling problem to drone-based parcel
delivery from a warehouse.

##  3 Second result: LPT for drones warehouse problem (DWP)

Vehicle routing [14, 47] is a classical problem in which parcel deliveries are
done by a single truck or a collection of trucks. Researchers have explored
variations with different vehicle velocities [15] or scenarios where each
parcel can only be delivered by a specific subset of vehicles [49]. With the
advent of drones, a generalization of the vehicle routing problem has been
studied in the literature in which a truck is carrying drones along with it.
The drones pick up parcels from the truck, deliver the package and return to
the truck (the truck might have now moved to a different location). This
problem is more challenging than the traditional vehicle routing problem [8].
Several MIP (mixed integer programming) formulations and heuristics have been
used to solve this problem [38, 2]. Theoretical guarantees have also been
proved for this problem by Carlsson and Song using geometric methods [8].

The transition towards using only drones like in DWP (instead of trucks with
drones) is evident in the gradual shift within the research community, as it
is a more sustainable option for the future. Extensive efforts have been
dedicated to developing algorithms for scheduling drones under various
constraints [44]. Some MIP formulations were studied to minimize various
objectives like the number of drones [18, 24] and bio-inspired algorithms were
used to manage large fleets of drones [40]. As drones have a limited battery
life, considerations for fuel stations were explored in [25]. Further, all
drones might not have the same features like speed and battery life and this
was taken into account in [46]. For a comprehensive review of research in
several related problems involving only drones, the reader can refer to the
survey presented in [41]. There has also been a lot of work by the multi-agent
community for scheduling [26], pathfinding [9, 19] and coordinating drones
[39, 36, 6, 48].

In this paper, we consider the problem where a warehouse wants to use drones
to deliver a large number of parcels to customers around it. Due to limited
battery life, each drone has a restricted range around the warehouse in which
it can deliver parcels. Also, depending on the manufacturer, the speed of each
drone can vary. We will now formally define the DWP problem, state the result
obtained by applying the LPT heuristic for DWP and provide a high-level
overview of the analysis. We also provide a detailed literature review on the
use of LPT for several other machine scheduling problems and connect it to our
result on DWP in section 4.

###  3.1 Drones warehouse problem (DWP)

The warehouse has a set of $m$ drones $\mathcal{D}=\\{D_{1},D_{2}\cdots
D_{m}\\}$ and a set of $n$ parcels $\mathcal{P}=\\{P_{1},P_{2}\cdots
P_{n}\\}$. Parcels in set $\mathcal{P}$ need to be delivered by drones in set
$\mathcal{D}$. Each drone can pick up one parcel at a time from the warehouse,
deliver it and return to the warehouse. For all $1\leq j\leq n$, let the
distance at which parcel $J_{j}$ needs to be delivered be $\ell_{j}/2$. So
each drone must travel a distance of $\ell_{j}$ in total to deliver the parcel
$P_{j}$ and come back to the warehouse.

Additionally, the drones have a limited battery life and let $d_{i}$ be the
distance which drone $M_{i}$ can travel, for all $1\leq i\leq m$. Therefore,
for a parcel $P_{j}$ to be delivered by a drone $D_{i}$, it must be the case
that $\ell_{j}\leq d_{i}$. The speed at which the drone $D_{i}$ travels is
$v_{i}$, for all $1\leq i\leq m$. After each delivery, the drone recharges its
battery in the warehouse and for the sake of simplicity, we assume the time
taken to recharge is negligible. Our goal is to assign each parcel to a drone
such that the time taken to execute the schedule is minimised.

More precisely, we define a valid schedule $f:\mathcal{D}\rightarrow
2^{\mathcal{P}}$ (power set of $\mathcal{P}$) such the following properties
hold

  * •

Each parcel is assigned to exactly one drone, i.e., $f(D_{i})\cap
f(D_{j})=\emptyset$ for all $i\neq j$ and
$\bigcup_{D\in\mathcal{D}}f(D)=\mathcal{P}$.

  * •

Each drone must be able to deliver the parcel assigned to it, i.e.,
$\ell_{i}\leq d_{j}$ for all $j\in[m]$ and $i:P_{i}\in f(D_{j})$.

Our goal is to find a valid schedule such that $T(f)$ is minimised where

$T(f)=\max\limits_{j\in[m]}\sum_{i:P_{i}\in f(D_{j})}\frac{\ell_{i}}{v_{j}}$

We assume that there is at least one drone capable of delivering all parcels.
Otherwise, there would be no valid solution (this can be checked in linear
time).

###  3.2 Our results and techniques

We implement LPT algorithm with additional battery life constraints to solve
DWP in near-linear time. Our key contribution is to prove that this algorithm
always returns a solution which is at most $\phi$ times the optimal solution,
where $\phi\approx 1.62$ is the golden ratio. We summarize our results and
compare them with the previous work in fig. 4.1 (discussed in more detail in
section 4)

######  Theorem 3.1.

There is a $\phi$-approximation algorithm for the DWP problem where
$\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. The algorithm runs in
$O((n+m)(\log^{2}{m}+\log{n}))$ time, where $m$ and $n$ are the number of
drones and parcels, respectively.

At a high level, our proof is inspired by the analysis of the LPT algorithm
for the uniform scheduling problem (USP) [28]. However, the constraint of
battery life makes our problem significantly more challenging. As the total
distance travelled by the drones is the same for any valid schedule, if some
drone in the LPT algorithm travels more distance than its counterpart in the
optimal assignment, then some other drone in the LPT algorithm must travel
lesser distance than its counterpart in the optimal assignment as a
compensation. However, if we assume that the approximation factor is greater
than $\phi$, we can create instances for which such compensation does not
occur, which leads to the contradiction. The proof requires ideas such as (a)
working with a minimal instance, (b) removing the parcel which is closest to
the warehouse from the schedule, (c) classifying the parcels into three
categories based on their distance and (d) truncating the parcel distances. We
give the complete proof in section 6.

We will now give a detailed literature review of the use of LPT for machine
scheduling and connect our problem DWP with the other variants in section 4.

##  4 Related work on machine scheduling

ISPUSPDWPUSP-CUnrelSP$=4/3$ [16] $[1.54,1.58]$ [28] $[1.54,\phi]$ [This work]
$\geq 2$ [Folklore] Not Applicable $\subset$$\subset$$\subset$$\subset$ Figure
4.1: Landscape of the approximation ratio of LPT heuristic for machine
scheduling problems and our drone warehouse problem (DWP). The relation
$A\subset B$ in the figure implies that $A$ is a special case of $B$.
Therefore, the approximation factor increases from left to right in the
figure. The interval $[a,b]$ means that the approximation ratio of the LPT
heuristic is at least $a$ and at most $b$. As there is no total order among
jobs in UnrelSP, LPT is not applicable for UnrelSP.

###  4.1 Uniform machines scheduling problem (USP)

In the uniform machines scheduling problem, let
$\mathcal{P}=\\{P_{1},P_{2},\ldots,P_{n}\\}$ be a set of $n$ jobs of size
$\\{\ell_{1},\ell_{2},\ldots,\ell_{n}\\}$ respectively and
$\mathcal{D}=\\{D_{1},D_{2},\ldots,D_{m}\\}$ be a set of $m$ machines of speed
$\\{v_{1},v_{2},\ldots,v_{m}\\}$ respectively. Our goal is to schedule the $n$
jobs to the $m$ machines so that the completion time of the schedule is
minimised. We will now formally define the problem.

We define schedule as a function $f:\mathcal{D}\rightarrow 2^{\mathcal{P}}$
(power set of $\mathcal{P}$ ) where $f(D_{i})$ represents the set of all jobs
assigned to machine $D_{i}$. We call a schedule a valid schedule if each job
is assigned to exactly one machine, i.e., $f$ is a valid schedule if and only
if $f(D_{i})\cap f(D_{j})=\emptyset$ for all $i\neq j$ and
$\bigcup_{D\in\mathcal{D}}f(D)=\mathcal{P}$. Each schedule $f$ has an
associated completion time

$T(f)=\max\limits_{j\in[m]}\sum_{i:P_{i}\in f(D_{j})}\frac{\ell_{i}}{v_{j}}$

Our goal is to find a valid schedule $f$ such that $T(f)$ is minimised.

###  4.2 ISP $\subset$ USP $\subset$ DWP

The special case of USP when all the machines have equal speed is called the
identical-machines scheduling problem (ISP). Therefore, we denote ISP
$\subset$ USP, where the notation $A\subset B$ implies that $A$ is a special
case of $B$ (See fig. 4.1) and therefore, lower bound of $A$ is also a lower
bound for $B$ and upper bound of $B$ is also a lower bound for $A$. Graham
[16, 17] proved that the approximation factor of the LPT algorithm is
$\frac{4}{3}$ for ISP. For USP, after a series of works, Kovacs [28] proved
that the approximation factor of the LPT algorithm is at most $1.58$ and at
least $1.54$. It is easy to see that USP is a special instance of DWP (USP
$\subset$ DWP) when all battery lives are equal (and large enough to deliver
all parcels). So, the approximation factor for DWP can not be better than
$1.54$. On the other hand, due to theorem 3.1, we get that LPT heuristic is a
$\phi$-approximation, which is one of the main contributions of this work.

###  4.3 DWP $\subset$ USP-C $\subset$ UnrelSP.

A lot of work in the literature has been devoted to a generalization of USP,
namely uniform scheduling problems with processing constraints (USP-C) [30].
We are given a set of jobs $\mathcal{J}=\\{J_{1},J_{2},\ldots,J_{n}\\}$ and a
set of machines $\mathcal{M}$, where each job $J_{j}$ has a set of machines
$\mathcal{M}_{j}\subseteq\mathcal{M}$ to which they can be assigned to.
Different structural restrictions of $\mathcal{M}_{j}$ would lead to different
models in USP-C, like the inclusive processing set [42, 35], nested processing
set [37, 11], interval processing set [45, 23], and tree-hierarchical
processing set restrictions [34, 33]. The goal is to assign each job to a
machine to minimize the completion time.

DWP is also a special case of USP-C as each parcel can only be delivered by a
subset of drones determined by its battery life. Therefore, DWP $\subset$
USP-C. We emphasise that both these classes are strictly different (and DWP is
also different from all known variants of USP-C, including nested intervals).
Consider two machines and two jobs. Let the size of $J_{1},J_{2}$ be
$10,10+\epsilon$ respectively and speeds of $M_{1},M_{2}$ be $10,10+\epsilon$
respectively for $\epsilon>0$. Moreover, the job $J_{1}$ can only be done by
$M_{2}$, but $J_{2}$ can be done by both $M_{1}$ and $M_{2}$. The LPT
heuristic would take $\frac{20+\epsilon}{10+\epsilon}$ time, while the optimum
assignment would take only $\frac{10+\epsilon}{10}$ time. This gives us an
approximation ratio of $2$ as $\epsilon$ approaches zero in this example
(whether this ratio is optimal or not for the LPT heuristic on USP-C is an
open question). We also note that this case does not hold to DWP as any drone
which can do a job at a distance of $10+\epsilon$ can also do the job at a
distance of $10$.

Unrelated Scheduling Problem (UnrelSP) is the scheduling problem in which the
time taken by machine $D\in\mathcal{D}$ to complete job $P\in\mathcal{P}$ is
determined by an arbitrary function
$f:\mathcal{D}\times\mathcal{P}\rightarrow\mathbb{R}$. Note that USP-C
$\subset$ UnrelSP and the LPT heuristic is not applicable as there is no total
order among the jobs to sort. This finishes the description of fig. 4.1.

###  4.4 Other algorithms and optimization measures.

A PTAS for ISP was given by Hochbaum and Schmoys [20]. This was later extended
to obtain a PTAS for USP [21]. Due to the seminal result of Lenstra, Shmoys
and Tardos [29], there is an Linear programming-based 2-approximation
algorithm for UnrelSP. This is also the best known approximation algorithm for
USP-C. For a special case of USP-C with nested intervals [32], there is $4/3$
approximation algorithm for DWP. For more results on USP-C, we refer the
reader to the latest survey [31]. We emphasise that despite knowing PTAS and
other algorithms with a better approximation ratio, the LPT heuristic remains
popular in practice due to its simplicity and scalability. This motivated
researchers from the algorithms and operations research community to
extensively study it as described in fig. 4.1.

Instead of optimizing the time taken to complete all jobs (makespan), other
objectives like average completion time [7], weighted-average completion time
[22] and Monotonicity and Truthfulness have also been studied [5, 27, 4, 3].

##  5 Near linear time implementation

###  5.1 Longest processing time first (LPT) scheduling

A classical approach for the Uniform Scheduling problem is using a greedy
algorithm called LPT scheduling which gives a $1.58$-approximate solution[28].
First, we sort the jobs $\mathcal{P}$ in decreasing order of their size and
let $P_{1},P_{2},\ldots,P_{n}$ be the sorted sequence. Then we initiate
$T_{j}$, the time taken by the $j$th machine to be zero for all $j\in[m]$. Now
we assign the jobs sequentially from $P_{1}$ to $P_{n}$. We assign job $P_{i}$
to machine $D_{j}$ for which the value of $T_{j}+(\ell_{i}/v_{j})$ is minimum
and we update the value $T_{j}$ to $T_{j}+(\ell_{i}/v_{j})$ for this specific
$j$ (refer algorithm 1).

Algorithm 1 LPT algorithm in $O(nm)$ time

Input: List of jobs $\mathcal{P}$ and machines $\mathcal{D}$.

Output: Time required for LPT scheduling.

Sort $\mathcal{P}$ in non-increasing order of size.

Initialise $T_{j}=0$ for all $j\in[m]$

for $i$ in $\\{1\ldots n\\}$ do

$\alpha=\operatorname*{arg\,min}_{j\in[m]}T_{j}+\frac{\ell_{i}}{v_{j}}$

$T_{\alpha}\leftarrow T_{\alpha}+\frac{\ell_{i}}{v_{\alpha}}$

end for

return $\max\limits_{j\in[m]}T_{j}$

As $\operatorname*{arg\,min}_{j\in[m]}T_{j}+\frac{\ell_{i}}{v_{j}}$ can be
found in $O(m)$ time, we can implement the above algorithm to run in $O(nm)$
time. To improve the run time of this algorithm, we implement a faster way to
find $\operatorname*{arg\,min}_{j\in[m]}T_{j}+\frac{\ell_{i}}{v_{j}}$.

###  5.2 Dynamic Lower Envelope

$L_{1}$$L_{2}$

$L_{1}$$L_{2}$$L_{3}$

$L_{1}$$L_{2}$$L_{3}$$L_{4}$

Figure 5.1: Dynamic lower envelope is shown in black for the lines
$L_{1}:y=-x+4$, $L_{2}:y=x$, $L_{3}:y=2x$, $L_{4}:y=1$.

One can visualise the step in which
$\operatorname*{arg\,min}_{j\in[m]}T_{j}+\frac{\ell_{i}}{v_{j}}$ is computed
in the following way: Consider $m$ linear functions $f_{1},f_{2},\ldots,f_{m}$
where where $f_{j}(x)=\dfrac{1}{v_{j}}\cdot x+T_{j}$. We need to find the
value of $j\in[m]$ for which $f_{j}(x)=\dfrac{1}{v_{j}}\cdot x+T_{j}$ is
minimum at
$x={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\ell_{i}}$.
This is exactly the same as finding the line in the lower envelope for
$f_{1},f_{2}\cdots f_{m}$ at
$x={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\ell_{i}}$.
Our idea now is to maintain a dynamic lower envelope data structure capable of
inserting and deleting functions. We will now describe this formally.

Let $\mathcal{F}$ be a set of functions where $f\in\mathcal{F}$ is of the form
$f:\mathbb{R}\rightarrow\mathbb{R}$. Then the lower envelope is the function
$f_{min}:\mathbb{R}\rightarrow\mathbb{R}$ such that
$f_{min}(x)=\min_{f\in\mathcal{F}}f(x)$. We are interested in the case when
these functions correspond to straight lines, i.e., they are of the form
$f_{i}(x)=m_{i}x+c_{i}$. More particularly, we are interested in dynamically
maintaining the lower envelope problem of lines, i.e., in each step, a new
line is added (or removed), as shown in fig. 5.1, and one has to maintain the
lower envelope with a small update time. This has been well-studied in the
computational geometry community. From [43], there is a data structure to
maintain a dynamic lower envelope of lines (further extended to dynamic lower
envelope of pseudo lines in [1]):

  * •

$\mathcal{F}.Insert(f)$: Adds the linear function $f$ to set $\mathcal{F}$ in
$O(\log^{2}{|\mathcal{F}|})$ time.

  * •

$\mathcal{F}.Delete(f)$: Removes the function $f$ from set $\mathcal{F}$ in
$O(\log^{2}{|\mathcal{F}|})$ time.

  * •

$\mathcal{F}.LowerEnvelope(x)$: Returns
$f^{*}=\operatorname*{arg\,min}_{f\in\mathcal{F}}f(x)$ in
$O(\log{|\mathcal{F}|})$ time.

Algorithm 2 LPT algorithm in $O((n+m)(\log^{2}{m}+\log{n})$ time

Input: List of jobs $\mathcal{P}$ and machines $\mathcal{D}$.

Output: Time required for LPT scheduling.

Sort $\mathcal{P}$ in non-increasing order of size.

Initialise lower envelope data structure $\mathcal{F}$

for $j$ in $\\{1\ldots m\\}$ do

$f_{j}(x)=\frac{1}{v_{j}}x$

$\mathcal{F}.Insert(f_{j})$

end for

for $i$ in $\\{1\ldots n\\}$ do

$f_{j}=\mathcal{F}.LowerEnvelope(\ell_{i})$

Let $f_{j}(x)=\frac{1}{v_{j}}x+T_{j}$

Set $f_{j}^{\prime}(x)=\frac{1}{v_{j}}x+T_{j}+\frac{\ell_{i}}{v_{j}}$

$\mathcal{F}.Delete(f_{j})$

$\mathcal{F}.Insert(f_{j}^{\prime})$

end for

return $\max\limits_{j\in[m]}f_{j}(0)$

Using this, we can implement LPT algorithm in $O((n+m))\log^{2}{m})$ time
(algorithm 2). We initialise lower envelope data structure $\mathcal{F}$ and
store lines $f_{j}(x)=\frac{1}{v_{j}}x+0$ (initially $T_{j}=0$) for all
$j\in[m]$. To assign parcel $P_{i}$ to drone $D_{j}$, we remove the line
$f_{j}(x)=\frac{1}{v_{j}}x+T_{j}$ from $\mathcal{F}$ and replace it with
$f_{j}^{\prime}(x)=\frac{1}{v_{j}}x+T_{j}+\frac{\ell_{i}}{v_{j}}$. To find out
which drone $P_{j}$ is assigned to, we have to find
$\operatorname*{arg\,min}_{j\in[m]}T_{j}+\frac{\ell_{i}}{v_{j}}$, which is the
same as querying $\mathcal{F}.LowerEnvelope(\ell_{i})$.

Observe that sorting $\mathcal{P}$ takes $O(n\log{n})$ time. We have called
$\mathcal{F}.Insert(\cdot)$ $O(n+m)$ times and $\mathcal{F}.Delete(\cdot)$
$O(n)$ times. Therefore, the runtime of the algorithm
$O((n+m)\log^{2}{m}+n\log{n})$ or $O((n+m)(\log^{2}{m}+\log{n}))$

##  6 $\phi$-approximation for Drone Warehouse Problem

In this section, we will prove theorem 3.1.

###  6.1 Algorithm

We use an algorithm similar to LPT but modify it slightly so that the battery
constraints are respected. First, we sort the parcels $\mathcal{P}$ in non-
increasing order of their distance. Then, we initiate $T_{j}$, the time taken
by the $j$th drone to be zero for all $j\in[m]$. We now assign the parcels
sequentially from $P_{1}$ to $P_{n}$. We assign parcel $P_{i}$ to a drone
$D_{j}$ for which $\ell_{i}\leq d_{j}$ and the value of
$T_{j}+(\ell_{i}/v_{j})$ is minimum. We update the value $T_{j}$ to
$T_{j}+(\ell_{i}/v_{j})$ (refer algorithm 3). It is easy to see that the
running time of the MLPT algorithm is $O(mn+n\log{n})$

###  6.2 Implementation

Let us sort all the drones in decreasing order of their battery life. Observe
that if drone $D_{j}$ is capable of delivering parcel $P_{i}$, then all drones
$D_{j^{\prime}},j^{\prime}\leq j$ are capable of delivering parcel $P_{i}$.
Therefore, we can represent all the drones capable of delivering $P_{i}$ by a
pointer $ptr$, i.e., all drones $D_{j},j\in\\{1,\ldots,ptr\\}$ can deliver
parcel $P_{i}$. Also, as the parcels are sorted in decreasing order of
distance, the value of $ptr$ will only increase in each iteration (as any
drone capable of delivering $P_{i}$ can also deliver
$P_{i^{\prime}},i^{\prime}>i$). We again use lower envelope data structure to
implement LPT. (algorithm 3).

Algorithm 3 LPT algorithm

Input: List of drones $\mathcal{D}$ and parcels $\mathcal{P}$.

Output: Minimum time required to deliver all parcels.

Sort $\mathcal{P}$ in non-increasing order of distance.

Sort $\mathcal{D}$ in non-increasing order of battery life

Initialise lower envelope data structure $\mathcal{F}$

$ptr\leftarrow 0$

for $i$ in $\\{1\ldots n\\}$ do

while $ptr<n$ and $d_{ptr+1}\geq\ell_{i}$ do

$ptr\leftarrow ptr+1$

$f_{ptr}(x)=\frac{1}{v_{ptr}}x$

$\mathcal{F}.Insert(f_{ptr})$

end while

$f_{j}=\mathcal{F}.LowerEnvelope(\ell_{i})$

Let $f_{j}(x)=\frac{1}{v_{j}}x+T_{j}$

Set $f_{j}^{\prime}(x)=\frac{1}{v_{j}}x+T_{j}+\frac{\ell_{i}}{v_{j}}$

$\mathcal{F}.Remove(f_{j})$

$\mathcal{F}.Insert(f_{j}^{\prime})$

end for

return $\max\limits_{j\in[m]}f_{j}(0)$

Observe, that sorting $\mathcal{P}$ and $\mathcal{D}$ takes
$O(n\log{n}+m\log{m})$ time. We call $E.Insert(\cdot)$ $O(n+ptr)=O(n+m)$ times
and $E.Delete(\cdot)$ $O(n)$ times. As these function calls only use
$O(\log^{2}{m})$ time, the above algorithm runs in
$O((n+m)(\log^{2}{m}+log{n}))$ time.

###  6.3 Proof for $\phi$-approximation

##### Simplifying steps.

Without loss of generality, we will assume that the parcels are sorted in
decreasing order of distance, i.e., if $i<j$ then $\ell_{i}\geq\ell_{j}$ for
all $i,j\in[n]$. Let $Alg_{I}$ represent the valid schedule obtained from
MLPT-algorithm and let $Opt_{I}$ represent any optimal valid schedule on
instance $I=\\{\mathcal{D},\mathcal{P}\\}$. We show that
$\frac{T(Alg_{I})}{T(Opt_{I})}\leq\phi$. We will start by performing some
simplifying steps on $I$.

######  Lemma 6.1.

For any instance $I=\\{\mathcal{D},\mathcal{P}\\}$, we can assume that
$\ell_{n}=1$, $T(Opt_{I})=1$ and no drone has battery life less than
$\ell_{n}$.

###### Proof:

Observe that scaling all values
$\\{\ell_{i}\\}_{i\in[n]},\\{d_{j}\\}_{j\in[m]}$ by some constant $\alpha$
scales $T(Alg_{I})$ and $T(Opt_{I})$ by $\alpha$. Similarly, scaling all
values $\\{v_{j}\\}_{j\in[m]}$ by some constant $\beta$ scales $T(Alg_{I})$
and $T(Opt_{I})$ by $\beta^{-1}$. However, this procedure does not affect the
value of the approximation factor $\frac{T(Alg_{I})}{T(Opt_{I})}$. Therefore,
we can choose values $\alpha,\beta$ such that $\ell_{n}=1$ and $T(Opt_{I})=1$
(choosing $\alpha=\ell_{n}^{-1},\beta=\ell_{n}^{-1}T(Opt_{I})$ gives us the
desired result). Also, as $P_{n}$ is the smallest job, we can remove all
drones which do not have enough battery life to deliver it as such drones
would be empty in any schedule.

####  6.3.1 Idea-1: Working with minimal instance.

Our goal is to prove that $T(Alg_{I})\leq\phi$ for all instances $I$. Towards
a contradiction, assume that there exists an instance $I$ for which
$\frac{T(Alg_{I})}{T(Opt_{I})}>\phi$. Among all such contradicting instances,
let $\mathcal{I}$ be the contradicting instance which has the minimum number
of parcels. We will sometimes drop the subscripts in $Alg_{\mathcal{I}}$ and
$Opt_{\mathcal{I}}$ and write them as $Alg$ and $Opt$, respectively, for
simplicity.

####  6.3.2 Idea-2: A schedule without the last parcel.

As $\mathcal{I}=\\{\mathcal{D},\mathcal{P}\\}$ is a contradicting instance
with the least number of parcels, it means that for any other instance
$\mathcal{I}^{\prime}$ with less number of parcels that $\mathcal{I}$ is not a
contradicting instance. In particular, this is true for
$\mathcal{I}^{\prime}=\\{\mathcal{D},\mathcal{P}\setminus\\{P_{n}\\}\\}$.
Intuitively, this implies $T(Alg_{\mathcal{I}^{\prime}})\leq\phi$ and
$T(Alg)>\phi$, and adding parcel $P_{n}$ causes the increase in time. We will
now prove this rigorously.

######  Definition 6.2.

Let $Alg_{0}$ be the schedule obtained by removing parcel $P_{n}$ from the
schedule $Alg$, i.e., $Alg_{0}$ is a schedule such that
$Alg_{0}(D_{i})=Alg(D_{i})\setminus\\{P_{n}\\}$ for all $i\in[m]$.

######  Definition 6.3.

Let $L_{j}(f)$ represent the total distance travelled by drone $D_{j}$ in
schedule $f$. Then,

$L_{j}(f)=\sum_{i:P_{i}\in f(D_{j})}\ell_{i}.$

######  Definition 6.4.

The completion time of a drone in schedule $f$ is the time taken by the drone
to deliver all parcels assigned to it by the schedule $f$.

######  Lemma 6.5.

$\ell_{n}+L_{i}(Alg_{0})=1+L_{i}(Alg_{0})>\phi v_{i}$, for all $i\in[m]$.

###### Proof:

We claim that $T(Alg_{0})\leq\phi$. Suppose not. Then consider the instance
$\mathcal{I}^{\prime}=\\{\mathcal{D},\mathcal{P}\setminus\\{P_{n}\\}\\}$
obtained from the minimal instance
$\mathcal{I}=\\{\mathcal{D},\mathcal{P}\\}$. Observe that the schedule
$Alg_{\mathcal{I}^{\prime}}$ and schedule $Alg_{0}$ are the same (as the
assignment of the first $n-1$ parcels is independent of the $n^{th}$ parcel).
Therefore, $T(Alg_{\mathcal{I}^{\prime}})>\phi$. Also, observe that
$T(Opt_{\mathcal{I}^{\prime}})\leq T(Opt_{\mathcal{I}})=1$. This implies that
$\frac{T(Alg_{\mathcal{I}^{\prime}})}{T(Opt_{\mathcal{I}^{\prime}})}>\phi$
which contradicts the fact that $\mathcal{I}$ is the instance with the least
number of parcels such that
$\frac{T(Alg_{\mathcal{I}})}{T(Opt_{\mathcal{I}})}>\phi$.

Now as $T(Alg)>\phi$ and $T(Alg_{0})\leq\phi$, this means that only the drone
which delivers $P_{n}$ has completion time greater than $\phi$. Also as the
MLPT algorithm assigns parcels to drones which has the least completion time,
this implies that assigning $P_{n}$ to any drone in $Alg_{0}$ would result in
its completion time being greater than $\phi$. Note that $P_{n}$ can be
assigned to any drone as all drones have battery life at least $\ell_{n}$
(from lemma 6.1).

Therefore, $(L_{i}(Alg_{0})+\ell_{n})/v_{i}>\phi$. As $\ell_{n}=1$, it follows
that $L_{i}(Alg_{0})+1>\phi v_{i}$.

####  6.3.3 Idea-3: Classification of parcels.

We classify parcels for which the drone travels a distance in the range
$[1,\phi)$ as small jobs, $[\phi,2)$ as medium jobs and $[2,\infty)$ as large
jobs. We first define a rounding function $R(x)$ such that

$x\geq R(x)\geq x/\phi\text{ for all }x\geq 1$

Where $R$ is a function such that

$R(x)=\begin{cases}1&\text{ if }x\in[1,\phi)\\\ 1.5&\text{ if }x\in[\phi,2)\\\
\lfloor x\rfloor&\text{ if }x\in[2,\infty)\end{cases}$

Define $L^{\prime}_{i}(f)=\sum_{j:P_{j}\in f(D_{i})}R(\ell_{j})$. The
motivation for defining $R(x)$ is that the value of $L^{\prime}_{i}(f)$ can
only be integer multiples of 0.5 whereas $L_{i}(f)$ can take any arbitrary
value depending on the input.

####  6.3.4 Idea-4: Discretizing Distances.

Ideally, we want to show that each drone in $Alg_{0}$ travelled more distance
than its counterpart in $Opt$. This would show that the total distance
travelled by drones in $Alg_{0}$ is greater than that of drones in $Opt$ which
is a contradiction as fewer parcels have been delivered in $Alg_{0}$ than in
$Opt$. Unfortunately, it turns out that $L_{i}(Alg_{0})$ can be lesser than
$L_{i}(Opt)$. Instead, we show that $L^{\prime}_{i}(Opt)\leq
L^{\prime}_{i}(Alg_{0})$ for all $i\in[m]$ and arrive at a similar
contradiction.

######  Lemma 6.6.

$L^{\prime}_{i}(Alg_{0})+\phi-1>v_{i}$ for all $i\in[m]$

###### Proof:

From lemma 6.5, we get that

$\displaystyle v_{i}$
$\displaystyle<\frac{1+L_{i}(Alg_{0})}{\phi}\leq\frac{1}{\phi}+L^{\prime}_{i}(Alg_{0})=\phi-1+L^{\prime}_{i}(Alg_{0})$

The second inequality and the third equality follows from $x/\phi\leq R(x)$
and $\phi$ being the golden ratio, respectively.

######  Lemma 6.7.

If a drone $D_{i}$ has a medium job assigned to it, then
$L^{\prime}_{i}(Alg_{0})+0.5>v_{i}$

###### Proof:

Let a medium-sized job of size $y$ be assigned to drone $D_{i}$. Then,

$\displaystyle L^{\prime}_{i}(Alg_{0})$ $\displaystyle=R(y)+\sum_{z\in
Alg(D_{i})\setminus\\{y\\}}R(z)$ Since $y\in[\phi,2)$, we get $R(y)=1.5>y-0.5$
$\displaystyle>y-0.5+\sum_{z\in Alg(D_{i})\setminus\\{y\\}}R(z)\geq
y-0.5+\frac{L_{i}(Alg)-y}{\phi}$ Using lemma 6.5 and $y\geq\phi$, we get
$\displaystyle>y-0.5+\frac{\phi
v_{i}-1-y}{\phi}=y(1-\frac{1}{\phi})-0.5-\frac{1}{\phi}+v_{i}$
$\displaystyle\geq\phi-1-\frac{1}{\phi}+v_{i}-0.5=v_{i}-0.5$

######  Lemma 6.8.

$L^{\prime}_{i}(Opt)\leq L^{\prime}_{i}(Alg_{0})$ for all $i\in[m]$

###### Proof:

Towards a contradiction, let us assume that
$L^{\prime}_{j}(Opt)>L^{\prime}_{j}(Alg_{0})$ for some drone $D_{j}$. Observe
that $L^{\prime}_{j}(Opt)\leq L_{j}(Opt)\leq v_{j}$ as $T(Opt)=1$. Using this
and lemma 6.6 we get,

$\displaystyle L^{\prime}_{j}(Alg_{0})<L^{\prime}_{j}(Opt)$ $\displaystyle\leq
v_{j}<\phi-1+L^{\prime}_{j}(Alg_{0})$

As $L^{\prime}_{j}(Alg_{0})$ and $L^{\prime}_{j}(Opt)$ are both integer
multiples of $0.5$, the only value which satisfies the inequality is,
$L^{\prime}_{j}(Opt)=L^{\prime}_{j}(Alg_{0})+0.5$. Let
$L^{\prime}_{j}(Alg_{0})=k/2$ where $k$ is an integer.

Case 1: $L^{\prime}_{j}(Alg_{0})=k/2$ is not an integer.
This can only happen if $D_{j}$ contains at least one medium job in $Alg_{0}$
(as small and large sized jobs have integral values and cannot add to give a
non-integer). But then by lemma 6.7, we get
$L^{\prime}_{j}(Opt)=L^{\prime}_{j}(Alg_{0})+0.5>v_{j}$, which is a
contradiction as $L^{\prime}_{j}(Opt)\leq v_{j}$.

Case 2: $L^{\prime}_{j}(Alg_{0})=k/2$ is an integer.
This means that $L^{\prime}_{j}(Opt)=(k+1)/2$ is not an integer and hence,
$D_{j}$ has at least one medium job assigned to it in $Opt$. Therefore, by
definition of the $R(\cdot)$ function, we get $L_{j}(Opt)\geq
L^{\prime}_{j}(Opt)+\phi-1.5=L^{\prime}_{j}(Alg_{0})+\phi-1$. Using lemma 6.6,
we get $L_{j}(Opt)>v_{j}$, which is a contradiction as $L_{j}(Opt)\leq v_{j}$.

Using lemma 6.8, we get that

$\sum_{i=1}^{m}L^{\prime}_{i}(Opt)\leq\sum_{i=1}^{m}L^{\prime}_{i}(Alg_{0})$

observe that $\sum_{i=1}^{m}L^{\prime}_{i}(Opt)=\sum_{1}^{n}R(\ell_{i})$ and
$\sum_{i=1}^{m}L^{\prime}_{i}(Alg_{0})=\sum_{1}^{n-1}R(\ell_{i})$.
Substituting this, we get,

$\sum_{1}^{n}R(\ell_{i})\leq\sum_{1}^{n-1}R(\ell_{i})$

which is a contradiction. Therefore, our initial assumption must be wrong,
implying that $T(Alg)\leq\phi$.

###  6.4 How much can LPT analysis be improved?

Recall that the special case of DWP when all drones have the same battery life
($d_{i}=d_{j}\geq\max_{k}(\ell_{k})$ for all $i,j\in[m]$) is equivalent to
USP. It is known that LPT cannot give an approximation better than $1.54$ for
USP [28]. Therefore, the LPT algorithm can also not give an approximation
ratio better than $1.54$ for DWP.

##  7 Future work

A couple of immediate open problems are the following:

  1. 1.

Can the implementation of the LPT heuristic be done in optimal time, i.e.
$O((n+m)\cdot(\log m+\log n)$ time? We believe that it should be possible,
since the jobs are known upfront, i.e., it is actually an offline problem.

  2. 2.

Can the approximation ratio of the LPT heuristic be improved for DWP from
$\phi$?

In general, delivering parcels from the warehouse using drones is a rich
source of scheduling and vehicle routing problems. We mention two general
directions:

  1. 1.

As a concrete setting, consider a warehouse which has a truck and a drone,
both of which operate independently. As in the paper, the goal is to assign
parcels to the truck and the drone so that time taken to deliver is minimized.
A generalized version of the problem would involve multiple trucks and drones.

  2. 2.

Some companies might have multiple warehouses and as such, a parcel can be
delivered by any of the warehouses. As a concrete setting, consider the
generalization of the DWP studied in this paper to the setting where there are
two warehouses at different locations. The goal is to perform a two-level
partition: first partition the parcels among the warehouses and then partition
them among the drones. The goal is to deliver all the parcels as quickly as
possible.

## References

  * [1] Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer.  Maintaining the union of unit discs under insertions with near-optimal overhead.  In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, volume 129 of LIPIcs, pages 26:1–26:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.26, doi:10.4230/LIPICS.SOCG.2019.26.
  * [2] Niels A. H. Agatz, Paul C. Bouman, and Marie Schmidt.  Optimization approaches for the traveling salesman problem with drone.  Transp. Sci., 52(4):965–981, 2018.
  * [3] Pasquale Ambrosio and Vincenzo Auletta.  Deterministic monotone algorithms for scheduling on related machines.  Theor. Comput. Sci., 406(3):173–186, 2008.  URL: https://doi.org/10.1016/j.tcs.2008.06.050, doi:10.1016/J.TCS.2008.06.050.
  * [4] Nir Andelman, Yossi Azar, and Motti Sorani.  Truthful approximation mechanisms for scheduling selfish related machines.  Theory Comput. Syst., 40(4):423–436, 2007.  URL: https://doi.org/10.1007/s00224-006-1316-9, doi:10.1007/S00224-006-1316-9.
  * [5] Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano.  Deterministic truthful approximation mechanisms for scheduling related machines.  In Volker Diekert and Michel Habib, editors, STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, volume 2996 of Lecture Notes in Computer Science, pages 608–619. Springer, 2004.  doi:10.1007/978-3-540-24749-4\\_53.
  * [6] François Bodin, Tristan Charrier, Arthur Queffelec, and François Schwarzentruber.  Generating plans for cooperative connected uavs.  In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 5811–5813. ijcai.org, 2018.  URL: https://doi.org/10.24963/ijcai.2018/846, doi:10.24963/IJCAI.2018/846.
  * [7] John L. Bruno, Edward G. Coffman Jr., and Ravi Sethi.  Scheduling independent tasks to reduce mean finishing time.  Commun. ACM, 17(7):382–387, 1974.  doi:10.1145/361011.361064.
  * [8] John Gunnar Carlsson and Siyuan Song.  Coordinated logistics with a truck and a drone.  Manag. Sci., 64(9):4052–4069, 2018.
  * [9] Shushman Choudhury, Kiril Solovey, Mykel J. Kochenderfer, and Marco Pavone.  Coordinated multi-agent pathfinding for drones and trucks over road networks.  In 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022, pages 272–280. IFAAMAS, 2022.
  * [10] Gregory Dobson.  Scheduling independent tasks on uniform processors.  SIAM Journal on Computing, 13(4):705–716, 1984.
  * [11] Leah Epstein and Asaf Levin.  Scheduling with processing set restrictions: Ptas results for several variants.  International Journal of Production Economics, 133(2):586–595, 2011\.  Towards High Performance Manufacturing.  URL: https://www.sciencedirect.com/science/article/pii/S092552731100199X, doi:https://doi.org/10.1016/j.ijpe.2011.04.024.
  * [12] Donald K. Friesen.  Tighter bounds for lpt scheduling on uniform processors.  SIAM Journal on Computing, 16(3):554–560, 1987.
  * [13] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [14] Michel Gendreau, Alain Hertz, and Gilbert Laporte.  A tabu search heuristic for the vehicle routing problem.  Management Science, 40(10):1276–1290, 1994.
  * [15] Inge Li Gørtz, Marco Molinaro, Viswanath Nagarajan, and R. Ravi.  Capacitated vehicle routing with non-uniform speeds.  In Oktay Günlük and Gerhard J. Woeginger, editors, Integer Programming and Combinatoral Optimization, pages 235–247, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [16] R. L. Graham.  Bounds for certain multiprocessing anomalies.  Bell System Technical Journal, 45(9):1563–1581, 1966.
  * [17] R. L. Graham.  Bounds on multiprocessing timing anomalies.  SIAM Journal on Applied Mathematics, 17(2):416–429, 1969.
  * [18] F. Guerriero, R. Surace, V. Loscrí, and E. Natalizio.  A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints.  Applied Mathematical Modelling, 38(3):839–852, 2014.
  * [19] Erez Hartuv, Noa Agmon, and Sarit Kraus.  Scheduling spare drones for persistent task performance under energy constraints.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 532–540. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018.
  * [20] Dorit S. Hochbaum and David B. Shmoys.  Using dual approximation algorithms for scheduling problems theoretical and practical results.  J. ACM, 34(1):144–162, 1987.  doi:10.1145/7531.7535.
  * [21] Dorit S. Hochbaum and David B. Shmoys.  A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach.  SIAM J. Comput., 17(3):539–551, 1988.  doi:10.1137/0217033.
  * [22] Ellis Horowitz and Sartaj Sahni.  Exact and approximate algorithms for scheduling nonidentical processors.  J. ACM, 23(2):317–327, 1976.  doi:10.1145/321941.321951.
  * [23] Shlomo Karhi and Dvir Shabtay.  Online scheduling of two job types on a set of multipurpose machines.  International Journal of Production Economics, 150:155–162, 2014\.  URL: https://www.sciencedirect.com/science/article/pii/S0925527313005744, doi:https://doi.org/10.1016/j.ijpe.2013.12.015.
  * [24] Jonghoe Kim and James R. Morrison.  On the concerted design and scheduling of multiple resources for persistent uav operations.  In 2013 International Conference on Unmanned Aircraft Systems (ICUAS), pages 942–951, 2013.
  * [25] Jonghoe Kim, Byung Duk Song, and James R. Morrison.  On the scheduling of systems of uavs and fuel service stations for long-term mission fulfillment.  J. Intell. Robotic Syst., 70(1-4):347–359, 2013.
  * [26] David Klaska, Antonín Kucera, and Vojtech Rehák.  Adversarial patrolling with drones.  In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, pages 629–637, 2020.
  * [27] Annamária Kovács.  Fast monotone 3-approximation algorithm for scheduling related machines.  In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, volume 3669 of Lecture Notes in Computer Science, pages 616–627. Springer, 2005.  doi:10.1007/11561071\\_55.
  * [28] Annamária Kovács.  New approximation bounds for lpt scheduling.  Algorithmica, 57(2):413–433, 2010.
  * [29] Jan Karel Lenstra, David B. Shmoys, and Éva Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  Math. Program., 46:259–271, 1990.  doi:10.1007/BF01585745.
  * [30] Joseph Y.-T. Leung and Chung-Lun Li.  Scheduling with processing set restrictions: A survey.  International Journal of Production Economics, 116(2):251–262, 2008\.  URL: https://www.sciencedirect.com/science/article/pii/S0925527308003071, doi:https://doi.org/10.1016/j.ijpe.2008.09.003.
  * [31] Joseph Y.-T. Leung and Chung-Lun Li.  Scheduling with processing set restrictions: A literature update.  International Journal of Production Economics, 175:1–11, 2016.  URL: https://www.sciencedirect.com/science/article/pii/S0925527316000190, doi:https://doi.org/10.1016/j.ijpe.2014.09.038.
  * [32] Joseph Y.-T. Leung and C. T. Ng.  Fast approximation algorithms for uniform machine scheduling with processing set restrictions.  Eur. J. Oper. Res., 260(2):507–513, 2017.  URL: https://doi.org/10.1016/j.ejor.2017.01.013, doi:10.1016/J.EJOR.2017.01.013.
  * [33] Chung-Lun Li and Kangbok Lee.  A note on scheduling jobs with equal processing times and inclusive processing set restrictions.  J. Oper. Res. Soc., 67(1):83–86, 2016.  URL: https://doi.org/10.1057/jors.2015.56, doi:10.1057/JORS.2015.56.
  * [34] Chung-Lun Li and Qingying Li.  Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions.  J. Oper. Res. Soc., 66(3):516–523, 2015.  URL: https://doi.org/10.1057/jors.2014.22, doi:10.1057/JORS.2014.22.
  * [35] Chung-Lun Li and Xiuli Wang.  Scheduling parallel machines with inclusive processing set restrictions and job release times.  Eur. J. Oper. Res., 200(3):702–710, 2010.  URL: https://doi.org/10.1016/j.ejor.2009.02.011, doi:10.1016/J.EJOR.2009.02.011.
  * [36] Amith Manoharan.  Strategies for cooperative uavs using model predictive control.  In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 5196–5197. ijcai.org, 2020.  URL: https://doi.org/10.24963/ijcai.2020/738, doi:10.24963/IJCAI.2020/738.
  * [37] Gabriella Muratore, Ulrich M. Schwarz, and Gerhard J. Woeginger.  Parallel machine scheduling with nested job assignment restrictions.  Operations Research Letters, 38(1):47–50, 2010.  URL: https://www.sciencedirect.com/science/article/pii/S0167637709001126, doi:https://doi.org/10.1016/j.orl.2009.09.010.
  * [38] Chase C. Murray and Amanda G. Chu.  The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery.  Transportation Research Part C: Emerging Technologies, 54:86–109, 2015.
  * [39] Ty Nguyen and Tsz-Chiu Au.  Extending the range of delivery drones by exploratory learning of energy models.  In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, pages 1658–1660. ACM, 2017.
  * [40] Marta Niccolini, Mario Innocenti, and Lorenzo Pollini.  Multiple uav task assignment using descriptor functions.  IFAC Proceedings Volumes, 43(15):93–98, 2010.  18th IFAC Symposium on Automatic Control in Aerospace.
  * [41] Alena Otto, Niels A. H. Agatz, James F. Campbell, Bruce L. Golden, and Erwin Pesch.  Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey.  Networks, 72(4):411–458, 2018.
  * [42] Jinwen Ou, Joseph Leung, and Chung-Lun Li.  Scheduling parallel machines with inclusive processing set restrictions.  Naval Research Logistics (NRL), 55:328 – 338, 06 2008.  doi:10.1002/nav.20286.
  * [43] Mark H. Overmars and Jan van Leeuwen.  Maintenance of configurations in the plane.  J. Comput. Syst. Sci., 23(2):166–204, 1981.  doi:10.1016/0022-0000(81)90012-X.
  * [44] Sivakumar Rathinam and Raja Sengupta.  Algorithms for routing problems involving uavs.  In Innovations in Intelligent Machines - 1, volume 70 of Studies in Computational Intelligence, pages 147–172. Springer, 2007.
  * [45] Dvir Shabtay and Shlomo Karhi.  Online scheduling of two job types on a set of multipurpose machines with unit processing times.  Computers and Operations Research, 39(2):405–412, 2012.  URL: https://www.sciencedirect.com/science/article/pii/S0305054811001262, doi:https://doi.org/10.1016/j.cor.2011.05.002.
  * [46] Kaarthik Sundar and Sivakumar Rathinam.  Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems.  J. Intell. Robotic Syst., 88(2-4):513–526, 2017.
  * [47] Paolo Toth and Daniele Vigo.  The Vehicle Routing Problem.  Society for Industrial and Applied Mathematics, 2002.
  * [48] Feng Wu, Sarvapali D. Ramchurn, and Xiaoping Chen.  Coordinating human-uav teams in disaster response.  In Subbarao Kambhampati, editor, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 524–530. IJCAI/AAAI Press, 2016.  URL: http://www.ijcai.org/Abstract/16/081.
  * [49] Miao Yu, Viswanath Nagarajan, and Siqian Shen.  An approximation algorithm for vehicle routing with compatibility constraints.  Operations Research Letters, 46(6):579–584, 2018.  URL: https://www.sciencedirect.com/science/article/pii/S0167637718302256, doi:https://doi.org/10.1016/j.orl.2018.10.002.