# Ecologically Valid Explanations for Label Variation in NLI

Nan-Jiang Jiang
Department of Linguistics
The Ohio State University
<EMAIL_ADDRESS>&Chenhao Tan
Department of Computer Science
The University of Chicago
<EMAIL_ADDRESS>&Marie-Catherine de Marneffe
FNRS, UCLouvain
marie-catherine.demarneffe
@uclouvain.be Now at Google.

###### Abstract

Human label variation exists in many natural language processing (NLP) tasks,
including natural language inference (NLI). To gain direct evidence of how NLI
label variation arises, we build LiveNLI, an English dataset of 1,415
ecologically valid explanations (annotators explain the NLI labels they chose)
for 122 MNLI Williams et al. (2018) items (at least 10 explanations per item).
The LiveNLI explanations confirm that people can systematically vary on their
interpretation and highlight within-label variation: annotators sometimes
choose the same label for different reasons. This suggests that explanations
are crucial for navigating label interpretations in general. We few-shot
prompt language models (LMs) to generate explanations but the results are
inconsistent: the models sometimes produce valid and informative explanations,
but they also generate implausible ones that do not support the label,
highlighting directions for improvement.

##  1 Introduction

Practices for operationalizing annotations in NLP datasets have largely
assumed one single label per item. However, human label variation (Plank,
2022) has been found in a wide range of NLP tasks (Plank et al., 2014; Poesio
et al., 2018; Pavlick and Kwiatkowski, 2019; Nie et al., 2020; Uma et al.,
2021; Jiang and de Marneffe, 2022, i.a.). Aroyo and Welty (2015), i.a., argued
that variation that is systematic in annotations should be considered signal,
not noise. Specifically, the NLI task – identifying whether a hypothesis is
true (Entailment), false (Contradiction), or neither (Neutral) given a premise
– has embraced label variation and set out to predict it Zhang et al. (2021);
Zhou et al. (2022). However, it remains an open question where label variation
in NLI stems from.

Ex.1 P: Most pundits side with bushy-headed George Stephanopoulos (This Week),
arguing that only air strikes would be politically palatable. H: Mr.
Stephanopoulos has a very large pundit following due to his stance on air
strikes only being politically palatable. LiveNLI [E,N,C]: [0.4, 0.3, 0.3]
---
QUD: Does Stephanopoulos have a very large pundit following?
Resp.1.1: E – This statement is most likely to be true because in the context
is stated that “Most pundits” would side with Mr. Stephanopoulos. Most pundits
could also mean a very large pundit following.
Resp.1.2: N – You cannot infer that the overall number of pundits following
the individual is large just because the majority of pundits follow the
individual. He could just have 2 out of 3 total pundits following him, for
instance. Furthermore, they may be following him for reasons outside his
stance on air strikes.
QUD: Do pundits follow Stephanopoulos due to his stance on air strikes?
Resp.1.3: N – George Stephanopoulos may have a follow from pundits, but it
might not be due to his support of drones.
Resp.1.4: C – He might have a large pundit following, but that would have to
be for something before the current issue of air strikes since one event
wouldn’t get people a large following overnight.
Ex.2 P: for a change i i got i get sick of winter just looking everything so
dead i hate that H: I’m so sick of summer. LiveNLI [E,N,C]: [0, 0.35, 0.65]
Resp.2.1: C – The context is stating how one is sick of winter, not summer, as
the statement describes.
Resp.2.2: C – The speaker hates winter because the foliage is dead, therefore
he likely loves summer when everything is alive.
Resp.2.3: N – The context mentions being sick of winter while the statement
mentions being sick of summer. These could both be true because the same
person may still complain of summer’s heat.
Table 1: Examples in LiveNLI. P: Premise. H: Hypothesis. [E,N,C]: the
probability distributions over the labels (E)ntailment, (N)eutral, and
(C)ontradiction, aggregated from the multilabel annotations in LiveNLI.

We introduce the LiveNLI 111Label Variation and Explanation in NLI, available
at https://github.com/njjiang/LiveNLI. dataset, containing 122 re-annotated
MNLI (Williams et al., 2018) items, each with at least 10 highlights and free-
text explanations for the labels chosen by the annotators, totaling 1,415
explanations. The dataset is relatively small because we intended it to be
suitable for few-shot evaluation, following recent trends in BIG-Bench authors
(2023).

The contribution of LiveNLI’s explanations is their ecological validity:
annotators provide both the label and the explanations, in contrast to many
explanation datasets (e.g., e-SNLI (Camburu et al., 2018)) in which
explanations were collected for a given “ground truth” label. LiveNLI hence
provides direct evidence for how label variation among annotators arises. In
addition, LiveNLI highlights another kind of variation, within-label
variation: in some cases, humans converge to the same label for different
reasons. Finally, we evaluate whether GPT-3 (Brown et al., 2020) can generate
explanations for label variation. We found that its explanations can be fluent
and informative but also implausible or not supporting the label.

##  2 Data Collection

We re-annotated 122 items from the MNLI dev set where each item originally had
5 annotations:

  * •

60 items where only 2 annotators agreed on the label in the original MNLI
annotations;

  * •

50 items where 3 annotators agreed on the label in the original MNLI
annotations, reannotated in Nie et al. (2020)’s ChaosNLI with 100 annotations;

  * •

12 items (4 for each NLI label) where all 5 annotators agreed on the label in
the original MNLI annotations.

The first 110 items were analyzed by Jiang and de Marneffe (2022) who proposed
a taxonomy of reasons for label variation.

#### Procedure

Annotators read the premise (context) and hypothesis (statement), and were
asked whether the statement is most likely to be true/false/either true or
false (corresponding to Entailment/Contradiction/Neutral, respectively).
Multiple labels were allowed. They were then asked to write a free-text
explanation for all the label(s) they chose. Inspired by Camburu et al.
(2020); Wiegreffe et al. (2022); Tan (2022), we asked annotators to give
explanations that provide new information and refer to specific parts of the
sentences, and to avoid simply repeating the sentences. Annotators were also
asked to highlight words from the premise/hypothesis most relevant for their
explanations. 48 native speakers of English were recruited from Surge AI
(surgehq.ai, details in A1).

##  3 Analysis of LiveNLI

#### Label descriptive statistics

Figure 1:  Average distributions from the normalized multilabel responses for
each item.

We normalize each multilabel response into a distribution, then average the
individual distributions to obtain the item’s label distribution. Figure 1,
where each set of stacked bars gives the distributions for one item, shows
that label variation is widespread, even on the 12 items that received full
agreement in MNLI (right panel). The annotators provided legitimate
explanations for the labels that differ from the original one (see A1 in A1),
suggesting that the variation is genuine and not noise. This reiterates Baan
et al. (2022)’s point that considering one distribution to govern all
judgments from the population is a simplification, and distributions can shift
with annotator pools.

#### Annotators’ reasons for label variation

Jiang and de Marneffe (2022) analyzed the reasons for NLI label variation from
a linguists’ perspective and built a taxonomy of linguistic phenomena that can
lead to different interpretations. For instance, in 1 (Table 1), does one
infer a large following in the hypothesis from most in the premise? They
hypothesized that such lexical indeterminacy contributes to the variation
reflected in the NLI label distribution. However, their taxonomy was built
post-hoc, detached from the annotators. Here we leverage LiveNLI’s ecological
validity: we analyze the reasons for label variation from the perspective of
linguistically-naive annotators.

For each pair of premise/hypothesis, one author assigned it one or more
taxonomy categories exhibited in its explanations (Table 5 in A2 shows the
frequency of the categories). Across the board, label variation arises in
similar reasons to what Jiang and de Marneffe (2022) hypothesized. We
calculated agreement between our taxonomy reannotations and the annotations
from Jiang and de Marneffe (2022). The Krippendorff’s $\alpha$ with MASI-
distance is 0.30, suggesting low agreement (contingency matrix in Figure 3 in
A2). Specifically, the average number of categories used here is higher – 1.33
per item vs. 1.22 in Jiang and de Marneffe (2022), suggesting nontrivial
differences between the annotators’ and linguists’ reasons for label
variation.

Furthermore, the explanations uncover more ways in which label variation can
occur. In particular, we found that label variation often stems from
annotators judging the truth of different at-issue content, which answers
different Questions Under Discussion (QUDs) (Roberts, 2012). For example, in
1, Responses 1 and (the first half of) 1 take the main point of the hypothesis
to be Stephanopoulos having a very large pundit following, but have different
judgments on whether this main point is true. On the other hand, 1 and 1 focus
on the reason for which pundits follow Stephanopoulos, and agree with 1 that
he has a large following. We thus added a “QUD” category to the taxonomy.222It
replaces two of Jiang and de Marneffe (2022)’s categories, “accommodating
minimally added content” and “high overlap”, which involve annotators having
different readings and ignoring certain parts of the items. The QUD category
occurred in 28 items (out of 122) and is the third most frequently used
category, thus an important aspect of language understanding. Incorporating
QUD into NLP tasks and modeling (De Kuthy et al., 2018; Narayan et al., 2022)
is an interesting direction.

#### Within-label variation

Our analysis reveals that there is also within-label variation: annotators may
vary in their text understanding when giving the same label. There are 16
instances of within-label variation: annotators chose the same labels but
provided very different explanations.333 We consider two explanations to be
different if they focus on different sentence parts or make different
assumptions. As mentioned earlier, 1 and 1 both chose Neutral but assumed
different QUDs (1 also encompasses 1).

As another example, in 1, the explanations indicate that the annotators differ
in whether to take the premise and hypothesis to be referring to the same
entity/event. Response 1 assumes that the premise and hypothesis refer to the
same season: since the premise talks about winter and not summer, the
hypothesis I’m so sick of summer is false. 1, on the other hand, does not
assume that the premise and the hypothesis refer to the same season, and
infers through probabilistic enrichment that the speaker likes summer, making
the hypothesis false. Thus both with and without the coreference assumption,
annotators label the item as Contradiction.

Within-label variation shows up in $\sim$13% of LiveNLI, and highlights the
diversity of human explanations. This suggests that model generated
explanations should be similarly diverse to imitate human decision-making.

##  4 Predict and Explain Label Variation

Models should capture inherent label variation to achieve robust
understanding. Explanations are essential for navigating the uncertainty
rising from such variation. Here we use LiveNLI to few-shot prompt LMs to
jointly predict and explain label variation. We used text-davinci-003, a
variant of GPT-3 (Brown et al., 2020) with few-shot prompting (example in
Table 7).444We did not receive access to GPT-4 and ChatGPT performed worse in
preliminary experiments. Label variation in NLI has been predicted either as a
distribution over three labels (Zhang et al., 2021; Zhou et al., 2022) or a
multilabel (Jiang and de Marneffe, 2022; Liu et al., 2023). Here we use the
multilabel approach for its greater interpretability compared to
distributions. We select as gold answers labels with probability (from LiveNLI
or ChaosNLI) above 0.2, similar to Jiang and de Marneffe (2022).

We use Predict-then-Explain (P-E) and Explain-then-Predict (E-P), a.k.a.
chain-of-thought prompting (Wei et al., 2022), which has been shown to improve
performance of reasoning tasks like NLI (Ye and Durrett, 2022). (P)redict-only
prompts the model without explanations for the same items, giving a baseline
measuring the effect of explanations.

#### Train/test items

Since Jiang and de Marneffe (2022) found that models are sensitive to label
imbalance, we used a label-balanced set of 11 training items from LiveNLI,
with one item per single-label and two items per multiple-label. The test set
includes the rest of LiveNLI, augmented with ChaosNLI for infrequent labels,
totaling 259 items.

#### Metrics

The metrics include exact-match accuracy and macro F1. To measure how well the
model can separate the agreement items from ones with label variation, we
calculate a 4way-F1 score by calculating macro F1 scores on a 4way
categorization of the multilabels: three single labels vs. a “complicated”
label if there are multiple labels.

| Accuracy | F1 | 4way F1 | # labels
---|---|---|---|---
P | 25.251.91 | 70.701.70 | 37.050.92 | 1.920.35
P-E | 24.73.25 | 69.003.68 | 37.151.77 | 1.780.32
E-P | 19.900.28 | 65.854.46 | 27.551.48 | 1.900.28
ENC | 14.30 | 72.70 | 18.20 | 3.00
Table 2: Metrics for each model and mean number (#) of predicted labels. The
average number of gold labels in the test split is 1.71. Each value is the
average of two random splits (standard deviation in subscript).

#### Classification Results

Table 2 shows the performance of each model, together with the uniform
baseline of always predicting all three labels ENC.555 The ENC baseline scores
high on F1 because it has a perfect recall, and a high precision given that
more than half of the items are multi-labeled. Both P and P-E significantly
outperforms E-P.666$p$ = 0.02 comparing P vs. E-P, $p$ = 0.03 for P-E vs. E-P,
$p$ = 0.84 for P vs. P-E, McNemar’s test. This adds to the series of results
where having post-prediction explanations outperforms chain-of-thought style
prompting (Lampinen et al., 2022; Zhou et al., 2023). In particular, P-E
predicts fewer labels than E-P, suggesting that the models consider more
labels to be possible when generating explanations first. P predicts the most
number of labels, which can potentially be due to the fact that it does not
need to generate an explanation for each label predicted, and hence does not
pay the long sequence penalty when generating more labels.

| Validity | Informativeness |
---|---|---|---
| Plausible |  Support | Specific | New Info | # Total
E-P | 75.0 | 80.9 | 38.2 | 10.3 | 68
P-E | 77.1 | 81.4 | 37.1 | 5.7 | 70

Table 3: Percentage of explanations (out of # Total) for 35 items marked as
Plausible, Support label, Specific, and introduce New Info.  Ex. 1 P: In Roman
times a temple to Jupiter stood here, followed in the fourth century by the
first Christian church, Saint-Etienne. H: Saint-Etienne, a Christian church,
had a temple to Jupiter and performed rituals during Roman times
---
ChaosNLI [E,N,C]: [0.25, 0.25, 0.50]
Generic, Plausible, Not Support, No new info
P-E: C – the context states that there was a temple to Jupiter before the
church was established, while the statement implies the church had a temple
and performed rituals. This may or may not have been true, but it is not
something that is stated in the context.
Specific, Plausible, Support, New info
E-P: N – it is possible that a church in Roman times may have done rituals for
Jupiter, as Christianity was still a nascent religion at that time, but it is
unknown based on the context.
Ex. 2 P: Most pundits side with bushy-headed George Stephanopoulos (This
Week), arguing that only air strikes would be politically palatable. H: Mr.
Stephanopoulos has a very large pundit following due to his stance on air
strikes only being politically palatable.
LiveNLI [E,N,C]: [0.4, 0.3, 0.3]
Generic, Plausible, Support, No new info
P-E: N – the context implies a large following but does not specify an exact
amount. Therefore it cannot be definitively stated if there is a large
following or not.
Generic, Implausible, Support, No new info
E-P: C – is is unknown to what extent the pundit’s following is and isn’t
large. It has only been alluded to that many pundits are agreeing with him.
Table 4: Generated explanations from both models.

#### Explanations Results

We performed a qualitative analysis to evaluate the models’ explanations on
four criteria inspired by Wiegreffe et al. (2022): do the explanations
plausibly describe sentence meaning (Plausible), support the label (Support),
go beyond restating the sentences (Specific), introduce new information about
the subject matter (New Info) (details in A4). The first two criteria target
the explanations’ validity, and the last two their informativeness (Leake,
1991).

For a random sample of 35 items, one author provided binary judgments on the
four criteria for both models’ explanations, with the model identity hidden.
As shown in Table 3, the models do not differ much in their explanations
quality, except for New Info. $\sim$80% of the explanations support the labels
they predict. Those not supporting the label are often Contradiction
explanations (across models, 67.8% Support for Contradiction vs. 88.2% for
other labels). In Ex. 1 in Table 4, the explanation only states that the
statement is not definitely true (hence not Entailment) but fails to state why
it is false, thus not supporting the Contradiction label. Furthermore, only
$\sim$60% of the explanations are both plausible and support the label (hence
valid).

The explanations are also lacking informativeness: over half of the
explanations are merely restating the premise/hypothesis (not Specific) and
rarely have new information. However, when the generated explanations are both
valid and informative (as in the Neutral one for Ex. 1 in Table 4), they do
contribute to further understanding of why the label applies by providing
interpretation.

Moreover, the generated explanations do not exhibit the range of within-label
variation found in the human explanations in Table 1. For Ex. 2 in Table 4,
both generated explanations focus on the aspect of whether “most” implies
“large”, while the human explanations in Table 1 identify two different QUDs
the sentences can address.

##  5 Conclusion and Discussion

We built LiveNLI providing ecologically valid explanations for NLI items with
label variation. We showed that LiveNLI’s explanations help us understand
where label variation stems from, and identify Question Under Discussion as an
additional source of label variation. We further emphasize a deeper level of
variation: within-label variation. Our work illustrates the utility of
explanations and provides future avenues for improving model capability of
leveraging and generating explanations.

## Limitations

The LiveNLI items comes from the MNLI dataset, which is known to contain
annotation artifacts and biases (Gururangan et al., 2018; Geva et al., 2019).
It is possible that those biases also contribute to the variation found here.
Further investigations on other datasets or tasks are needed to better
understand the prevalence of the label variation and within-label variation.

As shown in A1, filtering responses by answers to control items – the usual
technique for quality control and reducing noise – no longer works here. It is
possible that using a different set of control items, perhaps hand-written
instead of sourced from an existing corpus, would yield different results. In
any case, the most effective way to reduce noise is to control quality of the
workers, which is what Nie et al. (2020) and we did. Still, noise is
inevitable in any data collection process, and we did find some amount of
noise in LiveNLI: there are 6 responses from 3 items where the explanations
reveal that the annotators misread the sentences. Those 6 responses have
labels that differ from the rest of the responses for those 3 items.
Therefore, a small amount of label variation found here is contributed by
noise.

Our dataset is English-only. Studying label variation in other languages may
reveal new linguistic phenomena contributing to variation that are not seen in
English, and further reshape the taxonomy of reasons for label variation.

Our evaluation of the explanations generated are on a small sample and is
performed by one author. An evaluation scheme with multiple annotators would
provide a better assessment of the model quality. We only tested one model:
text-davinci-003, because it was the best model available to us at the time of
development. We have not received approval for access to GPT-4 from OpenAI.
Furthermore, due to the closed-nature of many commercial language models,
including text-davinci-003, we do not know what their training data contains.
It is possible that the training set for text-davinci-003 includes the items
from MNLI (where the LiveNLI items are sourced from) and therefore contributed
to some of the advantages of the models shown here.

## Broader Impact

We showed that GPT-3 can generate explanations that are detailed and closely
resembling the structure of human explanations. However, the explanations may
not be as grounded in the input premise/hypothesis and the labels they
predict. This can lead to potential misuse – the explanations can be used to
manipulate humans into believing the conclusion/label being explained,
especially when the explanations are specific and detailed, giving the
impression of correctness and authority. Therefore, these models should not be
deployed without further studying their social implications.

## Acknowledgments

We thank Michael White, Micha Elsner, the members of the Clippers group at
OSU, the C.Psyd group at Cornell, and the CHAI group at UChicago for their
insightful feedback. We thank the workers at Surge AI who provided valuable
data that enabled this work. This material is based upon work supported by the
National Science Foundation under grant no. IIS-1845122. Marie-Catherine de
Marneffe is a Research Associate of the Fonds de la Recherche Scientifique –
FNRS.

## References

  * Aroyo and Welty (2015) Lora Aroyo and Chris Welty. 2015.  Truth Is a Lie: Crowd Truth and the Seven Myths of Human Annotation.  _AI Magazine_ , 36(1):15.
  * BIG-Bench authors (2023) BIG-Bench authors. 2023.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _Transactions on Machine Learning Research_.
  * Baan et al. (2022) Joris Baan, Wilker Aziz, Barbara Plank, and Raquel Fernandez. 2022.  Stop measuring calibration when humans disagree.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 1892–1915, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Camburu et al. (2018) Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom. 2018\.  e-snli: Natural language inference with natural language explanations.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.
  * Camburu et al. (2020) Oana-Maria Camburu, Brendan Shillingford, Pasquale Minervini, Thomas Lukasiewicz, and Phil Blunsom. 2020.  Make up your mind! adversarial generation of inconsistent natural language explanations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4157–4165, Online. Association for Computational Linguistics.
  * De Kuthy et al. (2018) Kordula De Kuthy, Nils Reiter, and Arndt Riester. 2018.  QUD-based annotation of discourse structure and information structure: Tool and evaluation.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Geva et al. (2019) Mor Geva, Yoav Goldberg, and Jonathan Berant. 2019.  Are we modeling the task or the annotator? an investigation of annotator bias in natural language understanding datasets.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1161–1166, Hong Kong, China. Association for Computational Linguistics.
  * Gururangan et al. (2018) Suchin Gururangan, Swabha Swayamdipta, Omer Levy, Roy Schwartz, Samuel Bowman, and Noah A. Smith. 2018.  Annotation artifacts in natural language inference data.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 107–112, New Orleans, Louisiana. Association for Computational Linguistics.
  * Jiang and de Marneffe (2022) Nan-Jiang Jiang and Marie-Catherine de Marneffe. 2022.  Investigating Reasons for Disagreement in Natural Language Inference.  _Transactions of the Association for Computational Linguistics_ , 10:1357–1374.
  * Lampinen et al. (2022) Andrew Lampinen, Ishita Dasgupta, Stephanie Chan, Kory Mathewson, Mh Tessler, Antonia Creswell, James McClelland, Jane Wang, and Felix Hill. 2022.  Can language models learn from explanations in context? In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 537–563, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Leake (1991) David B. Leake. 1991.  Goal-based explanation evaluation.  _Cognitive Science_ , 15(4):509–545.
  * Liu et al. (2023) Alisa Liu, Zhaofeng Wu, Julian Michael, Alane Suhr, Peter West, Alexander Koller, Swabha Swayamdipta, Noah A. Smith, and Yejin Choi. 2023.  We’re afraid language models aren’t modeling ambiguity.
  * Narayan et al. (2022) Shashi Narayan, Joshua Maynez, Reinald Kim Amplayo, Kuzman Ganchev, Annie Louis, Fantine Huot, Dipanjan Das, and Mirella Lapata. 2022.  Conditional generation with a question-answering blueprint.
  * Nie et al. (2020) Yixin Nie, Xiang Zhou, and Mohit Bansal. 2020.  What can we learn from collective human opinions on natural language inference data? In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9131–9143, Online. Association for Computational Linguistics.
  * Pavlick and Kwiatkowski (2019) Ellie Pavlick and Tom Kwiatkowski. 2019.  Inherent disagreements in human textual inferences.  _Transactions of the Association for Computational Linguistics_ , 7:677–694.
  * Plank (2022) Barbara Plank. 2022.  The “problem” of human label variation: On ground truth in data, modeling and evaluation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 10671–10682, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Plank et al. (2014) Barbara Plank, Dirk Hovy, and Anders Søgaard. 2014.  Learning part-of-speech taggers with inter-annotator agreement loss.  In _Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 742–751.
  * Poesio et al. (2018) Massimo Poesio, Yulia Grishina, Varada Kolhatkar, Nafise Moosavi, Ina Roesiger, Adam Roussel, Fabian Simonjetz, Alexandra Uma, Olga Uryupina, Juntao Yu, and Heike Zinsmeister. 2018.  Anaphora resolution with the ARRAU corpus.  In _Proceedings of the First Workshop on Computational Models of Reference, Anaphora and Coreference_ , pages 11–22, New Orleans, Louisiana. Association for Computational Linguistics.
  * Roberts (2012) Craige Roberts. 2012.  Information structure in discourse: Towards an integrated formal theory of pragmatics.  _Semantics and Pragmatics_ , 5.
  * Tan (2022) Chenhao Tan. 2022.  On the diversity and limits of human explanations.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2173–2188, Seattle, United States. Association for Computational Linguistics.
  * Uma et al. (2021) Alexandra N Uma, Tommaso Fornaciari, Dirk Hovy, Silviu Paun, Barbara Plank, and Massimo Poesio. 2021.  Learning from disagreement: A survey.  _Journal of Artificial Intelligence Research_ , 72:1385–1470.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Wiegreffe et al. (2022) Sarah Wiegreffe, Jack Hessel, Swabha Swayamdipta, Mark Riedl, and Yejin Choi. 2022\.  Reframing human-AI collaboration for generating free-text explanations.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 632–658, Seattle, United States. Association for Computational Linguistics.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1112–1122, New Orleans, Louisiana. Association for Computational Linguistics.
  * Ye and Durrett (2022) Xi Ye and Greg Durrett. 2022.  The unreliability of explanations in few-shot prompting for textual reasoning.  In _Advances in Neural Information Processing Systems_.
  * Zhang et al. (2021) Yi Zhang, Sujay Kumar Jauhar, Julia Kiseleva, Ryen White, and Dan Roth. 2021.  Learning to decompose and organize complex tasks.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2726–2735, Online. Association for Computational Linguistics.
  * Zhou et al. (2022) Xiang Zhou, Yixin Nie, and Mohit Bansal. 2022.  Distributed NLI: Learning to predict human opinion distributions for language reasoning.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 972–987, Dublin, Ireland. Association for Computational Linguistics.
  * Zhou et al. (2023) Yangqiaoyu Zhou, Yiming Zhang, and Chenhao Tan. 2023.  Flame: Few-shot learning from natural language explanations.

## Appendix

###  A1 Details on Data Collection Procedure

Annotators were paid $0.6 per item (hourly wage: $12 to $18). Each item has at
least 10 annotations. On average, each annotator labeled 29.3 items. Our data
collection was performed with IRB approval. SurgeAI guarantees that the
annotators are native English speakers and have passed certain reading and
writing tests. Figure 2 shows a screenshot of the annotation interface.

shows an example where the original MNLI annotations are unanimously Neutral
but exhibiting genuine variation in LiveNLI annotations, together with the
LiveNLI explanations.

. P: The original wax models of the river gods are on display in the Civic
Museum. H: Thousands of people come to see the wax models.
original MNLI: [0,1,0]
LiveNLI [E,N,C]: [.23, .73, .04]
N – The context refers to the wax model displays in the museum. The context
makes no mention of the number of visitors mentioned in the statement.
E – Museums are generally places where many people come, so if the original
wax models are there it is likely thousands of people will come to see them.
Entailment | Contradiction – It’s unlikely a museum could stay open for very long without thousands of visitors, so it’s likely true that thousands of people come to see these wax mdoels. Unless, of course, it’s a big museum with many attractions more interesting than the models, in which case the statement is likely to be false.

Figure 2: Screenshot of the data collection interface.

###  A2 Details on Taxonomy Reannotations

Table 5 shows the frequency of taxonomy reannotations. Figure 3 compares our
reannotations with Jiang and de Marneffe (2022)’s annotations.

Combination of Taxonomy Categories | Frequency
---|---
Probabilistic | 28
Lexical | 21
QUD | 15
Coreference | 6
Lexical | Probabilistic | 5
Coreference | Probabilistic | 5
Imperfection | Lexical | 5
Implicature | 5
Imperfection | Probabilistic | 4
Probabilistic | QUD | 4
Coreference | Lexical | 3
Lexical | QUD | 3
Temporal | 2
Appear once: |
Implicature | Interrogative; Implicature | Lexical; Interrogative; Implicature | QUD; Imperfection | QUD; Interrogative | Lexical; Coreference | Temporal; Coreference | Imperfection; Coreference | QUD; Implicature | Interrogative; Implicature | Lexical; Interrogative; Implicature | Lexical | Probabilistic | QUD; Probabilistic | Temporal; Presupposition | QUD; QUD | Temporal
Table 5: Frequency of the taxonomy categories in LiveNLI. Label variation in
annotators arises for similar reasons as what Jiang and de Marneffe (2022)
hypothesized. QUD is a new category.  Figure 3: Contingency matrix of current
taxonomy reannotations vs. Jiang and de Marneffe (2022)’s annotations.

###  A3 Details on Prompting Setups

| train | test
---|---|---
| LiveNLI | total | LiveNLI | ChaosNLI
E | 1 | 37 | 18 | 19
N | 1 | 37 | 13 | 24
C | 1 | 37 | 8 | 29
NC | 2 | 37 | 26 | 11
EC | 2 | 37 | 1 | 36
EN | 2 | 37 | 35 | 2
ENC | 2 | 37 | 10 | 27
Total | 11 | 259 | 111 | 148

Table 6:  Number of items of each label in the train/test split from each
source.

Instruction Given a context, a statement can be true, false or either true or
false. Different people may interpret the sentences differently and have
different judgments. You are an assistant helping users identify what possible
judgments people can have and provide an explanation for each judgment. You
need to identify as many possible judgments as possible.
---
User:
Context: While it’s probably true that democracies are unlikely to go to war
unless they’re attacked, sometimes they are the first to take the offensive.
Statement: Democracies probably won’t go to war unless someone attacks them on
their soil
Assistant:
Given the context, some people consider the statement to be true, some people
consider the statement to be either true or false.
Explanations It can be true because if a nation is being attacked, odds are
it’s occuring on its soil (there’s far more of that than say, foreign military
bases or whatever). The context states it’s likely true democracies won’t go
to war unless they’re attacked, and since the context is taken as true that
means the statement must be so as well.
It can be either true or false because the statement adds an extra part with
“on their soil” which is not explicitly mentioned in the context. This could
be true or false since the context only mentions being attacked, not where the
attack would take place.

Table 7: Training example prompt for the Predict-then-Explain setup. The boxed
words indicate components of the prompt and do not appear in the actual
prompt. The Instruction only appears once before all the training items. The
Explain-then-Predict prompt has the Prediction following Explanations. The
Predict-only prompt does not include Explanations.

###  A4 Evaluating the Generated Explanations

Table 8 shows the definitions of the four binary criteria and examples of
explanations judged according to these criteria.

Note that the sentence content partially affects the ratings for Specificity
and New Information. If the label is straightforward and there is not much to
be explained, a good explanation does not necessarily need to be specific.
Similarly, for New Information, the sentences may not discuss any real world
events/entity, and there is not much new information that can or need to be
added.

Table 9 shows the evaluation results breakdown by labels.

#### Hide model identity for evaluation

The identity of the model is hidden by only presenting the portion of the text
that corresponds to the explanation and shuffling the order. The gold label /
distribution of the item is also hidden.

Specificity Specific / Generic
---
Is the explanation being detailed and specific in explaining the label, or is
it more generically describing what the sentences state (or do not state)
verbatim?
Plausibility Plausible / Implausible
Is the interpretation or inferences drawn from the context/statement
plausible, that is, can someone reading the context/statement possibly read
them in this way? If the explanation is generically describing what the
sentences state (or do not state), is the description accurate?
Support the label Support / Not Support
Does the explanation supports the label? Does the conclusion reasonably follow
the description of the premise/hypothesis? If the explanation is implausible
or inaccurately described the sentences, disregard the discrepancy and assume
the explanation to be true.
New Information New info / No new info
Does the explanation introduce new facts or information about the subject
matter?
P: and to have children and just get a day care or someone to take care of it
and not really have the bonding process that takes place with babies and stuff
you know
H: The day care is perfect for the children. |
Specific | Plausible | Support | New info |
N – it is not known from the context what the preference of the parent is
toward day care or having another person take care of the child and the
preference may vary from person to person. Furthermore, the statement does not
clarify what the definition of "perfect" is for that individual.
Specific | Plausible | Not Support | No new info |
C – taking care of children and the bonding process are two different things
and one cannot infer that the day care can provide the same process as the
natural bonding that takes place after the birth of a child.
Specific | Implausible | Not Support | No new info |
C – the bonding process with babies was not mentioned in the context,
suggesting that getting a day care would not be ideal for the children’s
needs. The statement implies that the day care is perfect, which may be false.
Generic | Implausible | Support | No new info |
N – the context is speaking in general and does not specify that the day care
is perfect. It just states that someone will take care of the children.
Table 8: Definitions of the four proposed criteria: Specificity, Plausibility, Support the label, and Introduce New Information, and examples of explanations judged according to these criteria. Setup | Label | Plausible | Support |  Plausible & Support | Specific | New Info | Total
---|---|---|---|---|---|---|---
| E | 76.5 | 88.2 | 70.6 | 35.3 | 5.9 | 17
E-P | N | 65.2 | 87.0 | 56.5 | 47.8 | 17.4 | 23
| C | 82.1 | 71.4 | 57.1 | 32.1 | 7.1 | 28
| E | 87.5 | 93.8 | 81.2 | 25.0 | 6.2 | 16
P-E | N | 68.0 | 88.0 | 60.0 | 44.0 | 4.0 | 25
| C | 79.3 | 69.0 | 55.2 | 37.9 | 6.9 | 29
Table 9:  Percentage of explanations of each model with each label, marked as
being Specific, Plausible, Supporting the label, and Introduce New
Information. An explanation is considered to be valid if it is both plausible
and supporting the label.


# Markovian Analysis of Coordination Strategies in Tandem Polling Queues with
Setups

Ravi Suman1*, Ananth Krishnamurthy2
Industrial and Systems Engineering Department
University of Wisconsin-Madison, Madison, WI-53726, USA

###### Abstract

We analyze a network of tandem polling queues with two stations operating
under synchronized polling (SP) and out-of-sync polling (OP) strategies, and
with nonzero setups. We conduct an exact analysis using a decomposition
approach to compare the performance in terms of throughput and mean waiting
times to investigate when one strategy might be preferred over the other. We
also numerically investigate the condition for network stability operating
under the two strategies and show that polling network is unstable when there
is bottleneck at downstream stations. We find that the SP strategy outperforms
the OP strategy in case of product and station symmetric networks while under
certain settings of product and station asymmetry, OP strategy outperforms the
SP strategy.

Keywords$\colon$ Polling Queues, Multi-products, Multi-station, Decomposition,
Polling Strategies

Markovian Analysis of Coordination Strategies in Tandem Polling Queues with
Setups
Ravi Suman1∗, Ananth Krishnamurthy2
1University of Wisconsin-Madison
2Indian Institute of Management Bangalore
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Polling queues find applications when multiple products compete for a common
resource. In a polling queue, a single server serves multiple queues of
products, visiting the queues one at a time in a fixed cyclic manner. In
manufacturing, polling queues have been used to model flow of multiple
products undergoing manufacturing operations in a factory. In healthcare,
polling queues have been used to model the flow of different types of patients
through various activities in a hospital or clinic. In transportation, polling
queues have been used to model multiple traffic flows in a transportation
network. Comprehensive survey on the analysis of polling queues can be found
in $\left(\text{Takagi
}\cite[cite]{[\@@bibref{}{Takagi2000}{}{}]},\text{Vishnevskii \& Semenova
}\cite[cite]{[\@@bibref{}{Vishnevskii2006}{}{}]}\right)$.

While a majority of existing research on polling queues focus on the single-
station polling queue, this work focuses on the analysis of coordination
strategies in tandem network of polling queues with setups. In tandem networks
of polling queues, coordination of service across different stations is
essential for achieving efficient network performance in terms of throughput,
queue lengths, and waiting times. One extreme, among the spectrum of
coordination mechanism, is the _Independent polling_ $(IP)$ strategy, where
each polling station acts independently and serves customers of various types
based on process characteristics, arrival patterns at that particular station
alone. Another strategy would be to synchronize the operations at consecutive
polling queues so that the same type of customer is being processed at the two
stations. For example, rolled aluminum plates need to be stretched soon after
they have been heat treated, before they cool down. This necessitates that
both stations process a particular type of alloy at the same time in their
respective cycles. In this case, these operations can be modeled as tandem
polling queues operating under _synchronous polling_ $(SP)$ strategy. Another
possibility is that downstream operations are deliberately kept out of sync
with the upstream operations to improve the flow. For example, it may be
desired that while the saws are processing one type of alloy, the downstream
inspection station is setup to inspect the parts after they got complete at
the saw. In this case, these operations can be modeled as tandem polling
queues operating under an _out-of-sync_ $(OS)$ strategy. Between these
extremes, and in addition to these specific strategies, several other
coordination strategies are possible. Further, such coordination can be both
essential and preferred in application of tandem polling queues to healthcare
and transportation settings.

Despite the importance of tandem network of polling queues, there has been
limited studies of such networks. Exact analysis of polling models is only
possible in some cases, and even then numerical techniques are usually
required to obtain waiting times at each queue. Our research focus aims to
investigate when such coordination will be beneficial in a network. We believe
that when there are significant differences between product types (in terms of
service times and demands) and stations (in terms of switchover times and
traffic intensities); designing and operating a tandem polling network with
suitable coordination strategy can significantly improve its performance. We
propose a decomposition approach and analyze the decomposed system using
matrix-geometrics approach to analyze the steady state of the system. We show
that this approach reduces computational complexity and provides reasonable
accuracy in performance estimation. Second, we investigate the impact of
different manufacturing settings, such as, location of bottleneck stations,
asymmetry in waiting times, and setup times on systems performance measures.
We find that the location of bottleneck station and differences in service
rates can have significant impact on the waiting times.

The rest of the paper is organized as follows. In Section 2, we provide a
brief literature review on polling queues and analysis of tandem network of
queues. We describe the system in Section 3 and the approach used to analyze
the two-station system in Section 4. In Section 5, we validate our approach
and provide useful numerical insights. Finally, we conclude and provide future
extensions in Section 6.

##  2 Literature Review

Polling queues and their applications have been an active field of research
for the past few decades. Takagi [17], Vishnevskii and Semenova [22], and
Boona et al. [2] provide a comprehensive survey on polling queues and their
applications. We group our discussion of the literature in three
categories$\colon$ polling queue with zero setups, polling queue with non-zero
setups, and network of polling queues.

Polling queue with zero setups$\colon$ One of the earliest techniques for
analyzing polling queues with zero setups uses a _server vacation model_ ,
where the server periodically leaves a queue and takes a vacation to serve
other queues. Fuhrmann et al. [8] uses such a vacation model to study a
symmetric polling station with $Q$ queues served in a cyclic order by a single
server and determines the expressions for sojourn times under exhaustive,
gated, and $k$-limited service discipline. They show that the stationary
number of customers in a single station polling queue (summed over all the
queues) can be written as the sum of three independent random
variables$\colon\left(i\right)$ the stationary number of customers in a
standard M/G/I queue with a dedicated server, $\left(ii\right)$ the number of
customers in the system when the server begins an arbitrary vacation
(changeover), and $\left(iii\right)$ number of arrivals in the system during
the changeover. Boxma et al. [4] use a stochastic decomposition to estimate
the amount of work (time needed to serve a specific number of customers) in
cyclic-service systems with hybrid service strategies (e.g., semi-exhaustive
for first product class, exhaustive for second and third product class, and
gated for remaining product classes) and use the decomposition results to
obtain a pseudo-conservation law for such cyclic systems.

Polling queue with non-zero setups$\colon$ Several studies have used transform
methods to find the distributions for waiting times, cycle times, and queue
lengths in a single-station polling queue with setups. Cooper et al. [6]
propose a decomposition theorem for polling queues with non-zero switchover
times and show that the mean waiting times is the sum of two
terms$\colon\left(\text{1}\right)$ the mean waiting time in a "corresponding"
model in which the switchover times are zero, and $\left(\text{2}\right)$ a
simple term that is a function of mean switchover times. Srinivasan et al.
[11] use Laplace–Stieltjes Transform $\left(\text{LST}\right)$ methods to
compute the moments of the waiting times in $R$ polling queues with nonzero-
setup-times for exhaustive and gated service. The algorithm proposed requires
estimation of parameters with $\log{\left(R\mathcal{E}\right)}$ complexity,
with $\mathcal{E}$ as the desired level of accuracy. Once the parameters have
been calculated, mean waiting times may be computed with
$\mathcal{O}\left(R\right)$ elementary operations. Borst and Boxma [3]
generalize the approach used by Srinivasan et al. [11] to derive the joint
queue length distribution for any service policy. Boxma et al. [5] analyzes a
polling system of $R$-queues with setup times operating under gated policy and
determine the LST for cycle times under different scheduling disciplines such
as FIFO and LIFO. They show that LST of cycle times is only dependent on the
polling discipline at each queue and is independent of the scheduling
discipline used within each queue.

In addition to LST techniques, mean value analysis has also been used to
estimate performance measures for polling queues with nonzero setups. Hirayama
et al. [9] developed a method for obtaining the mean waiting times conditioned
on the state of the system at an arrival epoch. Using this analysis, they
obtain a set of linear functional equations for the conditional waiting times.
By applying a limiting procedure, they derive a set of $R(R+1)$ linear
equations for the unconditional mean waiting times, which can be solved in
$\mathcal{O}\left(R^{6}\right)$ operations. Winands et al. [20] calculates the
mean waiting times in a single-station multi-class polling queue with setups
for both exhaustive and gated service disciplines. They use mean value
analysis to determine the mean waiting times at the polling queue. They derive
a set of $R^{2}$ and $R\left(R+1\right)$ linear equations for waiting time
figures in case of exhaustive and gated service. In these studies of polling
queues using LST techniques or mean value analysis, the authors have
restricted their scope of study to single-station polling queues. Extending
their approach to tandem network of polling queue will increase the
computational complexity. Therefore, in our work, we propose a decomposition
based approach.

$\textbf{Network of polling queues}\colon$ Altman and Yechiali [1] study a
closed queueing network for token ring protocols with $Q$ polling stations,
where a product upon completion of the service is routed to another queue
probabilistically. They determine explicit expressions for the probability
generating function for the number of products at various queues. However, the
system considered is closed system with $N$ products in circulation, which
could be a restrictive assumption in some applications. Jennings [10] conducts
a heavy traffic analysis of two polling queues for two stations in series and
prove limit theorems for exhaustive and gated discipline for the diffusion
scaled, two-dimensional total workload process using heavy traffic analysis.
Suman and Krishnamurthy ([12] – [16]) study a two-product two-station tandem
network of polling queues with finite buffers using Matrix-Geometric approach.
However, the analysis is restricted to systems with small buffer capacity. In
comparison, this paper analyzes an open network of two polling queues with
exogenous arrivals using decomposition.

##  3 System Description and Overview of Approach

In this section, we describe the system and provide an overview of the
approach to estimate performance measures for the system.

###  3.1 System Description

We analyze a two-product two-station tandem polling queue operating under two
different polling strategies$\colon$ 1) _Synchronous polling_ $(SP)$ and 2)
_Out-of-sync polling_ $(OP)$. There is an exogenous arrival of product of type
$i$ for $i={}1,2$ to their respective queue at station 1 according to
independent Poisson process with parameter $\lambda_{i}$. In the two polling
strategies, each product type is served by a single server at station $j$ for
$j={}1,2$ in a fixed cyclic order. After service at station 1, products move
from station 1 to station 2, and exit the system after the service is
completed at station 2. Service times at these stations for product type $i$
are iid exponential random variables with parameter $\mu_{i1}$ and $\mu_{i2}$
at station 1 and 2 respectively. We assume a common setup time for product $i$
at station 1 and station 2 when a server switches from queue $i^{\prime}$ to
queue $i$, for $i^{\prime}={}1,2$ and $i^{\prime}\neq i$. We denote this setup
time as $H_{i}$ that has an exponential distribution with rate $\mu_{s_{i}}$.
We assume that the setups are state independent for the queues at station 1,
i.e., the server incurs a setup time at the polled queue whether or not
products are waiting at the queue. We also assume that setup times are
independent of service times and queue type. Let $N_{1}$ and $N_{2}$ be the
respective maximum number of type 1 and type 2 products allowed to queue at
both stations. We assume that an arriving type $i$ product is lost if the
queue length of its type at that station is $N_{i}$ (including the product
being served) at the time of arrival. Next, we summarize the differences
between the two polling strategies below.

Synchronous polling strategy (SP)$\colon$ In this strategy, station 1 operates
under exhaustive policy, but the server at station 2 always serves the same
product type being served at station 1. In other words, if the server at
station 1 switches to perform setup for products of type 2 after emptying the
queue of product type 1, the server at station 2 also switches to perform
setup for products of type 2 even if its queue for type 1 product is not
empty. However, if station 1 is empty (in both the queues), station 2
continues to serve its queue until its queue is empty, or until station 1
begins to perform setup for a queue again after the arrival of a product. In
this event, the server at station 2 switches to setup for the same product
type being setup for at station 1. Figure 1 illustrates a possible scenario
under the synchronous polling strategy. Initially (in Figure 1a), the server
at both the stations are serving products of type 1. Subsequently, when the
server at station 1 empties its queues, it switches to do setup for products
of type 2 and the server at station 2 does the same (in Figure 1b).

(a) Both servers are serving type 1 products.

(b) Both servers are serving type 2 products.

Figure 1: Illustration of synchronous polling strategy (SP).

Out-of-sync polling strategy (OP)$\colon$ In this strategy, the server at
station 1 operates under exhaustive policy, but the server at station 2 always
serves a product type different from the product type being served at station
1. In other words, if the server of station 1 switches to do a setup for
products of type 2 after emptying the queue of product type 1, the server at
station 2 switches to do setups for products of type 1 even if its queue for
type 2 product is not empty. However, if station 1 is empty (in both the
queues), station 2 continues to serve its queue until its queue is empty or
until station 1 begins to perform setup for a queue again after the arrival of
a product. In this event, server at station 2 switches to setup for the other
product type. Figure 2 illustrates a possible scenario under the out-of-sync
polling strategy. Initially (in Figure 2a), the server at station 1 (2) is
serving products of type 1 (2). Subsequently, when the server at station 1
empties its queue, it switches to do setup for products of type 2, and the
server at station 2 switches to do a setup for products of type 1, even if the
queue of product of type 2 is not empty (in Figure 2b).

(a) Server at station 1 is serving type 1 products while server at station 2
is serving type 2 products.

(b) Server at station 1 is serving type 2 products while server at station 2
is serving type 1 products.

Figure 2: Illustration of out-of-sync polling strategy (OP).

In tandem networks of polling queues, coordination of service across different
stations is essential for achieving efficient network performance in terms of
throughput, queue lengths, and waiting times. One extreme, among the spectrum
of coordination mechanisms, is the SP strategy, where we have same operations
at consecutive stations so that same product type is processed at the two
stations. For example, in the manufacturing of rolled aluminum products,
aluminum plates need to be stretched soon after they have been heat treated,
before they cool down. This necessitates that both stations process a
particular type of alloy at the same time in their respective cycles. In this
case, these operations can be modeled as tandem polling queues operating under
SP strategy. Another possibility is that downstream operations are
deliberately kept out-of-sync with the upstream operations to improve the
flow. For example, it may be desired that while the saws are processing one
type of aluminum alloy, the downstream inspection station is inspecting the
plates processed at the saw earlier. In this case, these operations can be
modeled as tandem polling queues operating under OP strategy. Furthermore, to
reduce cost, manufacturers often process these plates in batches, and use an
exhaustive policy, i.e, serve all products waiting in a queue before switching
over to another product type. This practice is adopted to save on setup times.
Thus, determining the impact of setup times on waiting times is of key
interest.

The goal of this paperr is to compare the two strategies based on the
following system performance measures for a given maximum buffer level
$N_{i}\colon$ (i) average system throughput, $\mathbb{E}\left[TH_{i}\right]$,
defined as the average number of parts of product type $i$ produced by the
system in a time unit $\left[\text{parts/time unit}\right]$, (ii) average
queue length, $\mathbb{E}\left[L_{ij}\right]$, defined as the average amount
of material stored in buffer for product type $i$ at station
$j\left[\text{parts}\right]$, and (iii) average waiting time,
$\mathbb{E}\left[W_{i}\right]$, defined as the average time required by
products to go through station 1 and 2 $\left[\text{time units}\right]$.

To solve the system described above exactly using the conventional Markov
chain $\left(\text{MC}\right)$ approach, we would need to use six-tuple state
space resulting in over 0.6 million states for a system for a buffer size of
20 for either of the polling strategy. To address this curse-of-
dimensionality, we propose a decomposition technique to analyze the system. We
provide the overview of the approach below and provide the details in Section
4.

###  3.2 Overview of the Approach

The main idea is to decompose the system into two subsystems$\colon
SS\left(i\right)$ for $i={}1,2$ and study each subsystem independently.
Subsystem $SS\left(i\right)$ comprise of products of type 1 and type 2 at
station 1 and only product $i$ at station 2. We use subsystem
$SS\left(i\right)$ to obtain exact estimates of the performance measures for
type $i$ products at station 1 and station 2. In solving the subsystem
$SS\left(i\right)$, we make use of the fact that the server at station 1
drives the corresponding coordination strategy at station 2, i.e., the server
at station 2 makes the switch from one product to another at the same time
when the server at station 1 makes the switch. Therefore, we keep track of the
queue lengths for both the product type at station 1 and the queue length of
only product type $i$ at station 2 when we need to compute the performance
measures for product $i$. This decomposition helps reduce the state complexity
of the system and yet obtain exact solutions for the performance measures of
station 1 and station 2.

##  4 Queueing Analysis

In this section, we present the queueing analysis for SP strategy in
subsection 4.1. Then, we describe how the queueing analysis can be extended to
analyze OP strategy in subsection 4.2. Finally, we propose solution algorithm
to estimate system throughput, expected queue lengths, and expected waiting
times.

###  4.1 SP Strategy

The state of the subsystem $SS\left(i\right)$ with SP strategy at a given time
epoch forms a continuous time Markov chain defined by the tuple
$\Big{(}\,l_{11},l_{21},r_{i},l_{12}\,\Big{)}$, where $l_{ij}$ is the number
of products of type $i$ at station $j$, and $r_{i}$ takes value of $S_{i}$ or
$U_{i}$, for $i=1,2$, depending on if it is doing a setup for product $i$ or
is processing product $i$ respectively. Note that $l_{ij}$ is assumed to be
positive integer and 0 when stated. Let
$q\Big{[}\left(l_{11},l_{21},r_{i},l_{12}\right),\left(l_{11}^{\prime},l_{21}^{\prime},r_{i}^{\prime},l_{12}\right)\Big{]}$
denote the transitions from the state
$\left(l_{11},l_{21},r_{i},l_{12}\right)$ to the state
$\left(l_{11}^{\prime},l_{21}^{\prime},r_{i}^{\prime},l_{12}\right)$ for
$\left(r_{i},r_{i}^{\prime}\right)\in\\{S_{1},S_{2},U_{1},U_{2}\\}$. The
transitions for the subsystem $SS\left(i\right)$ with SP strategy are
summarized below in Table 1.

Table 1: Transitions for subsystem $SS\left(i\right)$ with SP strategy. From state |  To state |  Condition |  Transition rate out
---|---|---|---
$\left(l_{11},l_{21},S_{i},l_{12}\right)$ |  $\left(l_{11},l_{21},S_{i^{\prime}},l_{12}\right)$ |  $l_{i1}={}0$ |  $\mu_{s_{i}}$
$\left(l_{11},l_{21},S_{i},l_{12}\right)$ |  $\left(l_{11},l_{21},U_{i},l_{12}\right)$ |  $l_{i1}>0$ |
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ |  $\left(0,l_{21},S_{2},l_{12}+1\right)$ |  $l_{11}={}1$ |  $\mu_{11}$
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ |  $\left(l_{11}-1,l_{21},U_{1},l_{12}+1\right)$ |  $l_{11}>1$ |
$\left(l_{11},l_{21},U_{2},l_{12}\right)$ |  $\left(l_{11},0,S_{1},l_{12}\right)$ |  $l_{21}={}1$ |  $\mu_{21}$
$\left(l_{11},l_{21},U_{2},l_{12}\right)$ |  $\left(l_{11},l_{21}-1,U_{2},l_{12}\right)$ |  $l_{21}>1$ |
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ |  $\left(l_{11},l_{21},U_{1},l_{12}-1\right)$ |  $l_{12}\geq{}1$ |  $\mu_{12}$
$\left(l_{11},l_{21},S_{1},l_{12}\right)$ |  $\left(l_{11}+1,l_{21},S_{1},l_{12}\right)$ |  – |  $\lambda_{1}$
$\left(l_{11},l_{21},S_{2},l_{12}\right)$ |  $\left(l_{11}+1,l_{21},S_{2},l_{12}\right)$ |  |
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ |  $\left(l_{11}+1,l_{21},U_{1},l_{12}\right)$ |  |
$\left(l_{11},l_{21},U_{2},l_{12}\right)$ |  $\left(l_{11}+1,l_{21},U_{2},l_{12}\right)$ |  |
$\left(l_{11},l_{21},S_{1},l_{12}\right)$ |  $\left(l_{11},l_{21}+1,S_{1},l_{12}\right)$ |  – |  $\lambda_{2}$
$\left(l_{11},l_{21},S_{2},l_{12}\right)$ |  $\left(l_{11},l_{21}+1,S_{2},l_{12}\right)$ |  |
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ |  $\left(l_{11},l_{21}+1,U_{1},l_{12}\right)$ |  |
$\left(l_{11},l_{21},U_{2},l_{12}\right)$ |  $\left(l_{11},l_{21}+1,U_{2},l_{12}\right)$ |  |

Let $\pi\left(l_{11},l_{21},r_{i},l_{12}\right)$ be the steady-state
probability of state $\left(l_{11},l_{21},r_{i},l_{12}\right)$. The Chapman-
Kolmogorov equations for the Markov chain for subsystem $SS\left(i\right)$
with SP strategy to and from states $\left(l_{11},l_{21},S_{1},l_{12}\right)$
and $\left(l_{11},l_{21},U_{1},l_{12}\right)$ are given by Equations
$\left(\ref{eqn7.1}\right)-\left(\ref{eqn7.12}\right)$.

For $l_{11}={}0,l_{21}={}0,l_{12}\geq 0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{s_{1}}\right)\pi\left(0,0,S_{1},0\right)={}\mu_{s_{2}}\pi\left(0,0,S_{2},l_{12}\right)+\mu_{21}\pi\left(0,1,U_{2},l_{12}\right)$
(1) For $l_{11}={}0,l_{21}>{}0,l_{12}\geq 0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{s_{1}}\right)\pi\left(0,l_{21},S_{1},l_{12}\right)={}\lambda_{2}\pi\left(0,l_{21}-1,S_{1},l_{12}\right)$
(2) For $l_{11}>{}0,l_{21}={}0,l_{12}\geq 0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{s_{1}}\right)\pi\left(l_{11},0,S_{1},l_{12}\right)={}\lambda_{1}\pi\left(l_{11}-1,0,S_{1},l_{12}\right)+\mu_{s_{2}}\pi\left(l_{11},0,S_{2},l_{12}\right)+\mu_{21}\pi\left(l_{11},1,U_{2},l_{12}\right)$
(3) For $l_{11}>{}0,l_{21}>{}0,l_{12}\geq 0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{s_{1}}\right)\pi\left(l_{11},l_{21},S_{1},l_{12}\right)={}\lambda_{1}\pi\left(l_{11}-1,l_{21},S_{1},l_{12}\right)+\lambda_{2}\pi\left(l_{11},l_{21}-1,S_{1},l_{12}\right)$
(4) For $l_{11}={}1,l_{21}={}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,0,U_{1},0\right)={}\mu_{s_{1}}\pi\left(1,0,S_{1},0\right)+\mu_{12}\pi\left(1,0,U_{1},1\right)$
(5) For $l_{11}={}1,l_{21}={}0,l_{12}>{}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}+\mu_{12}\right)\pi\left(1,0,U_{1},l_{12}\right)=$
$\displaystyle{}\mu_{s_{1}}\pi\left(1,0,S_{1},l_{12}\right)+\mu_{11}\pi\left(2,0,U_{1},l_{12}-1\right)+\mu_{12}\pi\left(1,0,U_{1},l_{12}+1\right)$
(6) For $l_{11}={}1,l_{21}>{}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,l_{21},U_{1},0\right)={}\mu_{s_{1}}\pi\left(1,l_{21},S_{1},0\right)+\lambda_{2}\left(1,l_{21}-1,U_{1},0\right)+\mu_{12}\pi\left(1,l_{21},U_{1},1\right)$
(7) For $l_{11}={}1,l_{21}>{}0,l_{12}>{}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}+\mu_{12}\right)\pi\left(1,l_{21},U_{1},l_{12}\right)=$
$\displaystyle{}\mu_{s_{1}}\pi\left(1,l_{21},S_{1},l_{12}\right)+\lambda_{2}\left(1,l_{21}-1,U_{1},l_{12}\right)+\mu_{11}\pi\left(2,l_{21},U_{1},l_{12}-1\right)+\mu_{12}\pi\left(1,l_{21},U_{1},l_{12}+1\right)$
(8) For $l_{11}>{}1,l_{21}={}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},0,U_{1},0\right)={}\mu_{s_{1}}\pi\left(l_{11},0,S_{1},0\right)+\lambda_{1}\left(l_{11}-1,0,U_{1},0\right)+\mu_{12}\pi\left(l_{11},0,U_{1},1\right)$
(9) For $l_{11}>{}1,l_{21}={}0,l_{12}>0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}+\mu_{12}\right)\pi\left(l_{11},0,U_{1},l_{12}\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},0,S_{1},l_{12}\right)+\lambda_{1}\left(l_{11}-1,0,U_{1},l_{12}\right)+\mu_{11}\pi\left(l_{11}+1,0,U_{1},l_{12}-1\right)+\mu_{12}\pi\left(l_{11},0,U_{1},l_{12}+1\right)$
(10) For $l_{11}>{}1,l_{21}>{}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},l_{21},U_{1},0\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},l_{21},S_{1},0\right)+\lambda_{1}\left(l_{11}-1,l_{21},U_{1},0\right)+\lambda_{2}\left(l_{11},l_{21}-1,U_{1},0\right)+\mu_{12}\pi\left(l_{11},l_{21},U_{1},1\right)$
(11) For $l_{11}>{}1,l_{21}>{}0,l_{12}>0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}+\mu_{12}\right)\pi\left(l_{11},l_{21},U_{1},l_{12}\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},l_{21},S_{1},l_{12}\right)+\lambda_{1}\left(l_{11}-1,l_{21},U_{1},l_{12}\right)+\lambda_{2}\left(l_{11},l_{21}-1,U_{1},l_{12}\right)+$
$\displaystyle\mu_{11}\pi\left(l_{11}+1,l_{21},U_{1},l_{12}-1\right)+\mu_{12}\pi\left(l_{11},l_{21},U_{1},l_{12}+1\right)$
(12)

Similarly, we can write the balance equations for states of the form
$\left(l_{11},l_{21},S_{2},l_{12}\right)$ and
$\left(l_{11},l_{21},U_{2},l_{12}\right)$. The normalization condition is
written as$\colon$

$\displaystyle\mathop{\sum\sum\sum\sum}_{\begin{subarray}{c}S_{i}\in\\{S_{1},S_{2}\\}\\\
\left(l_{11},l_{21},l_{12}\right)\in\mathbb{Z}\end{subarray}}\pi\left(l_{11},l_{21},S_{i},l_{12}\right)+\mathop{\sum\sum\sum\sum}_{\begin{subarray}{c}U_{i}\in\\{U_{1},U_{2}\\}\\\
l_{i1}\in\mathbb{Z}^{+},\text{
}\left(l_{i^{\prime}1},l_{i2}\right)\in\mathbb{Z}\end{subarray}}\pi\left(l_{11},l_{21},U_{i},l_{12}\right)={}1$
(13)

Using Equations $\left(\ref{eqn7.1}\right)-\left(\ref{eqn7.13}\right)$, we
obtain the values of all steady state probabilities for subsystem
$SS\left(i\right)$ for $i={}1,2$ when operating under the SP strategy. We
independently analyze subsystem $SS\left(i^{\prime}\right)$ with SP strategy
to obtain the values of all steady state probabilities to estimate performance
measures of product $i^{\prime}$. Using the steady state probabilities, we
obtain expressions for average throughput $TH_{ij}$, average queue length
$L_{ij}$, and average waiting time $W_{ij}$, of product type $i$, for
$i={}1,2$ at station j, for $j={}1,2$ and are given by Equation
$\left(\ref{eqn7.14}\right)$, Equation $\left(\ref{eqn7.15}\right)$, and
Equation $\left(\ref{eqn7.16}\right)$ respectively.

$\displaystyle TH_{i1}$
$\displaystyle={}\mu_{i1}\mathop{\sum\sum\sum}\limits_{l_{11}\in\mathbb{Z}^{+},\text{
}\left(l_{21},l_{12}\right)\in\mathbb{Z}}\pi\left(l_{11},l_{21},U_{i},l_{12}\right)$
$\displaystyle TH_{i2}$
$\displaystyle={}\mu_{i2}\mathop{\sum\sum\sum}\limits_{\left(l_{11},l_{12}\right)\in\mathbb{Z}^{+},\text{
}l_{21}\in\mathbb{Z}}\pi\left(l_{11},l_{21},U_{i},l_{12}\right)$
$\displaystyle i={}1,2.$ (14)

$\displaystyle L_{i1}$
$\displaystyle={}\mathop{\sum\sum\sum\sum}_{\begin{subarray}{c}r\in\\{{S_{1},S_{2},U_{1},U_{2}\\}}\\\
\left(l_{11},l_{21},l_{i2}\right)\in\mathbb{Z}\end{subarray}}l_{i1}\cdot\pi\left(l_{11},l_{21},r,l_{i2}\right)$
$\displaystyle L_{i2}$
$\displaystyle={}\mathop{\sum\sum\sum\sum}_{\begin{subarray}{c}r\in\\{{S_{1},S_{2},U_{1},U_{2}\\}}\\\
\left(l_{11},l_{21},l_{i2}\right)\in\mathbb{Z}\end{subarray}}l_{i1}\cdot\pi\left(l_{11},l_{21},r,l_{i2}\right)$
$\displaystyle i={}1,2.$ (15) $\displaystyle W_{ij}$
$\displaystyle={}L_{ij}TH_{ij}^{-1}$ $\displaystyle i={}1,2.$ (16)

The mean waiting time for product $i$, for $i={}1,2$ in the system is given by
Equation $\left(\ref{eqn7.17}\right)$.

$\displaystyle W_{i}$ $\displaystyle={}W_{i1}+W_{i2}$ $\displaystyle i={}1,2.$
(17)

###  4.2 OP Strategy

The state of the subsystem $SS\left(i\right)$ with OP strategy at a given time
epoch forms a continuous time Markov chain defined by the tuple
$\Big{(}\,l_{11},l_{21},r_{i},l_{12}\,\Big{)}$. This state-space
representation for OP strategy is identical to state-space representation of
SP strategy. The transitions for the subsystem $SS\left(i\right)$ with OP
strategy are also same for all except one instance. This difference in the
transition is for the service of products at station 2, i.e., the transition
$q\Big{[}\left(l_{11},l_{21},U_{2},l_{12}\right),\left(l_{11},l_{21},U_{2},l_{12}-1\right)\Big{]}$.
This transition in OP strategy occurs with rate $\mu_{12}$.

Let $\pi\left(l_{11},l_{21},r_{i},l_{12}\right)$ be the steady-state
probability of state $\left(l_{11},l_{21},r_{i},l_{12}\right)$. The Chapman-
Kolmogorov equations for the Markov chain for subsystem $SS\left(i\right)$
unique to OP strategy to and from states
$\left(l_{11},l_{21},S_{1},l_{12}\right)$ and
$\left(l_{11},l_{21},U_{1},l_{12}\right)$ are given by Equations
$\left(\ref{eqn7.18}\right)-\left(\ref{eqn7.25}\right)$. The Equations
$\left(\ref{eqn7.1}\right)-\left(\ref{eqn7.4}\right)$ are also valid for SP
strategy.

For $l_{11}={}1,l_{21}={}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,0,U_{1},0\right)={}\mu_{s_{1}}\pi\left(1,0,S_{1},0\right)$
(18) For $l_{11}={}1,l_{21}={}0,l_{12}>{}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,0,U_{1},l_{12}\right)=$
$\displaystyle{}\mu_{s_{1}}\pi\left(1,0,S_{1},l_{12}\right)+\mu_{11}\pi\left(2,0,U_{1},l_{12}-1\right)$
(19) For $l_{11}={}1,l_{21}>{}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,l_{21},U_{1},0\right)={}\mu_{s_{1}}\pi\left(1,l_{21},S_{1},0\right)+\lambda_{2}\left(1,l_{21}-1,U_{1},0\right)$
(20) For $l_{11}={}1,l_{21}>{}0,l_{12}>{}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(1,l_{21},U_{1},l_{12}\right)=$
$\displaystyle{}\mu_{s_{1}}\pi\left(1,l_{21},S_{1},l_{12}\right)+\lambda_{2}\left(1,l_{21}-1,U_{1},l_{12}\right)+\mu_{11}\pi\left(2,l_{21},U_{1},l_{12}-1\right)$
(21) For $l_{11}>{}1,l_{21}={}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},0,U_{1},0\right)={}\mu_{s_{1}}\pi\left(l_{11},0,S_{1},0\right)+\lambda_{1}\left(l_{11}-1,0,U_{1},0\right)$
(22) For $l_{11}>{}1,l_{21}={}0,l_{12}>0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},0,U_{1},l_{12}\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},0,S_{1},l_{12}\right)+\lambda_{1}\left(l_{11}-1,0,U_{1},l_{12}\right)+\mu_{11}\pi\left(l_{11}+1,0,U_{1},l_{12}-1\right)$
(23) For $l_{11}>{}1,l_{21}>{}0,l_{12}={}0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},l_{21},U_{1},0\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},l_{21},S_{1},0\right)+\lambda_{1}\left(l_{11}-1,l_{21},U_{1},0\right)+\lambda_{2}\left(l_{11},l_{21}-1,U_{1},0\right)$
(24) For $l_{11}>{}1,l_{21}>{}0,l_{12}>0\colon$
$\displaystyle\left(\lambda_{1}+\lambda_{2}+\mu_{11}\right)\pi\left(l_{11},l_{21},U_{1},l_{12}\right)={}$
$\displaystyle\mu_{s_{1}}\pi\left(l_{11},l_{21},S_{1},l_{12}\right)+\lambda_{1}\left(l_{11}-1,l_{21},U_{1},l_{12}\right)+\lambda_{2}\left(l_{11},l_{21}-1,U_{1},l_{12}\right)+$
$\displaystyle\mu_{11}\pi\left(l_{11}+1,l_{21},U_{1},l_{12}-1\right)$ (25)

The normalization equation in OP strategy is similar to the normalization
equation for SP and is given by Equation $\left(\ref{eqn7.13}\right)$. Using
Equations $\left(\ref{eqn7.18}\right)-\left(\ref{eqn7.25}\right)$, we obtain
the values of all steady state probabilities for subsystem $SS\left(i\right)$
for $i={}1,2$ when operating under the OP strategy. We independently analyze
subsystem $SS\left(i^{\prime}\right)$ with OP strategy to obtain the values of
all steady state probabilities to estimate performance measures of product
$i^{\prime}$. Using the steady state probabilities, we obtain expressions for
average throughput $TH_{ij}$, average queue length $L_{ij}$, and average
waiting time $W_{ij}$, of product type $i$, for $i={}1,2$ at station j, for
$j={}1,2$ and are given by Equation $\left(\ref{eqn7.14}\right)$, Equation
$\left(\ref{eqn7.15}\right)$, and Equation $\left(\ref{eqn7.16}\right)$
respectively.

##  5 Comparison of SP and OP Strategy

In this section, we discuss the results of numerical experiments conducted to
compare the performance of polling queues under SP and OP strategies. We
conduct three sets of experiments pertaining to four different settings. In
the first set, we analyze the performance of the two strategies under a
symmetric setting. In the second set, we investigate the effect of station
asymmetry on system performance. In the third set of experiment, we
investigate the impact of different types of product asymmetry on system
performance.

###  5.1 Comparison for Symmetric Networks

In this experiment setting, we study the effects of variation of buffer size
on symmetric tandem polling systems and analyze the performance of the two
strategies for a symmetric system. Let
$\rho_{{j}_{\mathcal{N}_{1},\mathcal{N}_{2}}}$ be the traffic intensity at
station $j$ when the buffer size considered is $N_{1}$ and $N_{2}$ for type 1
and type 2 products, such that $\rho_{j_{\infty,\infty}}$ represents traffic
intensity at a station when $\mathcal{N}_{1}={}\mathcal{N}_{2}={}\infty$. We
set the arrival rate $\lambda_{i}$ to 1 for both the product types. We vary
the service rates and the buffer levels, and the results of this analysis are
summarized in Table 2. Note that, as we analyze symmetric system under this
setting, $W_{1}={}W_{2}$, $TH_{11}={}TH_{21}$, and $TH_{12}={}TH_{22}$.

Table 2: Performance analysis of symmetric systems. System parameters$\colon$
$\lambda_{i}={}1,\mu_{ij}={}4.00,\mu_{s_{j}}={}5.00,\rho_{j_{\infty,\infty}}={}0.50$
---
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |
$N_{i}$ |  $TH_{i1}$ |  $TH_{i2}$ |  $W_{i}$ |  $TH_{i1}$ |  $TH_{i2}$ |  $W_{i}$
3 |  0.94 |  0.70 |  3.85 |  0.94 |  0.54 |  4.02
6 |  1.00 |  0.85 |  5.31 |  1.00 |  0.71 |  5.58
9 |  1.00 |  0.90 |  6.84 |  1.00 |  0.80 |  7.08
12 |  1.00 |  0.92 |  8.35 |  1.00 |  0.84 |  8.57
15 |  1.00 |  0.94 |  9.86 |  1.00 |  0.87 |  10.07
System parameters$\colon$
$\lambda_{i}={}1,\mu_{ij}={}2.50,\mu_{s_{j}}={}5.00,\rho_{j_{\infty,\infty}}={}0.80$
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |
$N_{i}$ |  $TH_{i1}$ |  $TH_{i2}$ |  $W_{i}$ |  $TH_{i1}$ |  $TH_{i2}$ |  $W_{i}$
3 |  0.85 |  0.64 |  4.61 |  0.85 |  0.47 |  4.97
6 |  0.95 |  0.81 |  6.43 |  0.95 |  0.61 |  7.23
9 |  0.98 |  0.88 |  8.18 |  0.98 |  0.70 |  9.16
12 |  0.99 |  0.91 |  9.85 |  0.99 |  0.77 |  10.91
15 |  1.00 |  0.93 |  11.45 |  1.00 |  0.81 |  12.55

As expected, we observe that the mean waiting times $W_{i}$ and systems
throughput $TH_{ij}$ increases with increase in buffer size for both the
polling strategies. Higher buffers result in lower loss probability of
arriving products at each station resulting in more throughput. We also note
that the SP strategy outperforms OP strategy in terms of systems throughput
and waiting times. One explanation for this performance of OP strategy in
terms of throughout is its orthogonal service policy at the two stations. As
the server is always serving opposite product type at station 2 in case of OP
strategy, the queue length becomes equal to the buffer size at station 2 more
often in case of OP strategy leading to higher throughput loss, as opposed to
SP strategy. In case of SP strategy, since same product type is served at both
the stations, the arriving products at station 2 is processed in the same
cycle leading to lower throughput loss. The reason for lower waiting times for
SP strategy is that most of the products after receiving service at station 1,
do not need to wait for an additional cycle at station 2 as they are processed
in the same cycle. However, in case of OP strategy, the products need to wait
for at least an additional half of a cycle thereby increasing the waiting
times.

###  5.2 Comparison for Networks with Station Asymmetry

In this experiment setting, we analyze the impact of station asymmetry by
examining the effects of upstream bottlenecks and downstream bottlenecks. To
analyze the effect of upstream bottleneck, we set the service rate $\mu_{i1}$
at station 1 to 2.50 and the service rates $\mu_{i2}$ at station 2 for both
the products types to 4.00. Under this setting of service rates, we vary the
buffer size and record the performance measures. Next, to study the effects of
downstream bottlenecks, we set the service rate $\mu_{i1}$ at station 1 to
4.00 and the service rates $\mu_{i2}$ at station 2 for both the products types
to 2.50. Under this setting of service rates, we vary the buffer size and
record the performance measures. The results of this analysis are summarized
in Table 3. Since we have only station asymmetry, $W_{1j}={}W_{2j}$ for
$j={}1,2$ and $W_{1}={}W_{2}$.

Table 3: Analysis of impact of upstream bottleneck station. System
parameters$\colon$
$\lambda_{i}={}1,\mu_{i1}={}2.50,\mu_{i2}={}4.00,\mu_{s_{ij}}=5.00,\rho_{1_{\infty,\infty}}={}0.80,\rho_{2_{\infty,\infty}}={}0.50$
---
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |  |  |
$N_{i}$ |  $TH_{i2}$ |  $W_{i1}$ |  $W_{i2}$ |  $W_{i}$ |  $TH_{i2}$ |  $W_{i1}$ |  $W_{i2}$ |  $W_{i}$
3 |  0.76 |  1.34 |  2.15 |  3.49 |  0.53 |  1.34 |  2.63 |  3.97
6 |  0.93 |  1.88 |  2.32 |  4.20 |  0.70 |  1.88 |  3.65 |  5.54
9 |  0.97 |  2.21 |  2.40 |  4.61 |  0.80 |  2.21 |  4.43 |  6.64
12 |  0.99 |  2.42 |  2.43 |  4.84 |  0.87 |  2.42 |  5.03 |  7.44
15 |  1.00 |  2.54 |  2.43 |  4.96 |  0.91 |  2.54 |  5.48 |  8.02
System parameters$\colon$
$\lambda_{i}={}1,\mu_{i1}={}4.00,\mu_{i2}={}2.50,\mu_{s_{ij}}=5.00,\rho_{1_{\infty,\infty}}={}0.50,\rho_{2_{\infty,\infty}}={}0.80$
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |  |  |
$N_{i}$ |  $TH_{i2}$ |  $W_{i1}$ |  $W_{i2}$ |  $W_{i}$ |  $TH_{i2}$ |  $W_{i1}$ |  $W_{i2}$ |  $W_{i}$
3 |  0.52 |  0.80 |  4.84 |  5.64 |  0.52 |  0.80 |  3.97 |  4.77
6 |  0.61 |  0.88 |  8.48 |  9.36 |  0.60 |  0.88 |  7.26 |  8.14
9 |  0.62 |  0.90 |  12.86 |  13.76 |  0.61 |  0.90 |  11.11 |  12.01
12 |  0.62 |  0.90 |  17.51 |  18.41 |  0.62 |  0.90 |  15.30 |  16.20
15 |  0.62 |  0.90 |  22.27 |  22.27 |  0.62 |  0.90 |  19.72 |  20.62

Table 3 show that SP strategy performs better than OP strategy in terms of
waiting times and throughput when upstream station is the bottleneck. However,
when downstream station is the bottleneck, OP strategy outperforms SP
strategy. We also observe that in the case of bottleneck at downstream
station, the throughput converges to a value which is less than the arrival
rate to the system. This is because bottleneck at downstream station in
synchronization leads to instability in the queue. As a result of the
instability, there is no gain in systems throughput with the increase in
buffer size.

###  5.3 Comparison for Networks with Product Asymmetry

In this experiment setting, we study the effects of product asymmetry. To
study this, we fix the service rates $\mu_{1j}$ of type 1 products at both the
stations to 2.50 and vary the service rates $\mu_{2j}$ of type 2 products at
both the stations such such that $\mu_{1j}/\mu_{2j}$ varies between 0.40 to
0.80. Note that for this setting, product 2 has faster service rate at both
the stations. We list the results in Table 4.

Table 4: Performance analysis of networks with product asymmetry.
$\textbf{System
parameters}\colon\lambda_{i}={}1,\mu_{1j}={}2.50,\mu_{2j}={}3.13,\mu_{1j}/\mu_{2j}={}0.80,\mu_{s_{ij}}=5.00,\rho_{j_{\infty,\infty}}={}0.72$
---
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |  |  |
$N_{i}$ |  $TH_{12}$ |  $TH_{22}$ |  $W_{1}$ |  $W_{2}$ |  $TH_{12}$ |  $TH_{22}$ |  $W_{1}$ |  $W_{2}$
3 |  0.66 |  0.65 |  4.31 |  4.44 |  0.44 |  0.52 |  5.36 |  4.15
6 |  0.84 |  0.82 |  5.93 |  6.14 |  0.59 |  0.70 |  7.86 |  5.76
9 |  0.89 |  0.89 |  7.55 |  7.76 |  0.67 |  0.80 |  10.23 |  7.01
12 |  0.92 |  0.92 |  9.12 |  9.32 |  0.71 |  0.87 |  12.67 |  6.15
15 |  0.94 |  0.94 |  10.66 |  10.85 |  0.74 |  0.91 |  15.24 |  8.88
$\textbf{System
parameters}\colon\lambda_{i}={}1,\mu_{1j}={}2.50,\mu_{2j}={}6.25,\mu_{1j}/\mu_{2j}={}0.80,\mu_{s_{ij}}=5.00,\rho_{j_{\infty,\infty}}={}0.56$
Input | Synchronous (SP) | Out-of-sync (OP)
|  |  |  |  |  |  |  |
$N_{i}$ |  $TH_{12}$ |  $TH_{22}$ |  $W_{1}$ |  $W_{2}$ |  $TH_{12}$ |  $TH_{22}$ |  $W_{1}$ |  $W_{2}$
3 |  0.69 |  0.68 |  3.94 |  4.16 |  0.31 |  0.65 |  8.47 |  2.83
6 |  0.85 |  0.83 |  5.44 |  5.72 |  0.38 |  0.85 |  14.31 |  3.50
9 |  0.90 |  0.89 |  7.00 |  7.22 |  0.39 |  0.94 |  20.98 |  3.85
12 |  0.92 |  0.92 |  8.53 |  8.72 |  0.40 |  0.98 |  28.14 |  4.03
15 |  0.94 |  0.94 |  10.05 |  10.22 |  0.40 |  0.99 |  35.52 |  4.12

As expected, we observe that the systems throughput $TH_{i2}$ increases with
increase in buffer size. Table 4 shows that for both the coordination
strategies, $W_{2}$ (for the product type having the faster service rate) is
higher as compared to $W_{1}$. A possible explanation for this is that since
the servers at both the stations are faster in serving products of type 2,
when they switch to serve products of type 1, because of lower service rates
for type 1 products, the server processes products from that queue for a
longer duration. As a consequence, the products of type 2 wait longer. We note
that the total WIP $\left(\sum\sum_{ij}L_{ij}\right)$ is lower in OP strategy
as compared to SP strategy for a given buffer level. The reason for lower WIP
in case of OP strategy is higher loss in throughput at station 2 as compared
to SP strategy. We also note that $W_{1}$ is lower for SP strategy while
$W_{2}$ is lower for OP strategy.

##  6 Conclusions

In this paper, we analyze the performance of tandem polling queues with finite
buffers operating under two different coordination strategies, namely the
synchronous polling and and out-of-sync polling strategies. Under Markovian
settings, we conduct an exact analysis to determine steady state
probabilities, throughput, and mean waiting times for each type of product at
each station using a decomposition approach. Recognizing that these strategies
could yield substantially different performances, we conduct numerical
experiments to evaluate performance under a variety of settings. We study the
effect of symmetry and asymmetry in processing characteristics of the products
at an individual station and across the stations in the network. We also
evaluate performance when stations are balanced and unbalanced in terms of
traffic intensities.

In all the experiment settings, we observed that the mean waiting times and
system throughput increases with the increase in buffer size. In settings with
product and station symmetry, we observed that the SP strategy outperforms the
OP strategy. In settings with station asymmetry, we observed that SP strategy
performs better than OP strategy when the bottleneck is upstream. In case when
the bottleneck is downstream, we observe that OP performs better than SP
strategy. However, downstream at bottleneck leads to instability in the
system. We also observed that in case of product asymmetry, the total WIP is
lower in OP strategy as compared to SP strategy for a given buffer level.

## References

  * [1] Altman, E., & Yechiali, U. (1994).  “Polling in a Closed Network”  _Probability in the Engineering and Informational Sciences_ , vol 8: 3, pp. 327 – 343.
  * [2] Boona, M.M.A., van der Mei, R.D., & Winands, E.M.M. (2011).  “Applications of Polling Systems”  _Surveys in Operations Research and Management Science_ , vol 16: 2, pp. 67 – 82.
  * [3] Borst, S.C., & Boxma, O. (1997).  “Polling Models With and Without Switchover Times”,  _Operations Research_ , vol 45: 4, pp. 536 – 543.
  * [4] Boxma, O.J., & Groenendijk, W. P. (1987).  “Pseudo-Conservation Laws in Cyclic-Service Systems”  _Journal of Applied Probability_ , vol 24: 4, pp. 949 – 964.
  * [5] Boxma, O., Bruin, J., & Fralix, B. (2009).  “Sojourn Times in Polling Systems With Various Service Disciplines”,  _Performance Evaluation_ , vol 66: 3, pp. 621 – 639.
  * [6] Cooper, R.B., Niu, S.C., & Srinivasan, M.M. (1996).  “A Decomposition Theorem for Polling Models: The Switchover Times are Effectively Additive”,  _Operations Research_ , vol 44: 4, pp. 629 – 633.
  * [7] Eisenberg, M. (1972).  “Queues with Periodic Service and Changeover Time”  _Operations Research_ , vol 20: 2, pp. 440 – 451.
  * [8] Fuhrmann, S.W., & Cooper, R.B. (1985).  “Stochastic Decomposition in the M/G/1 Queue with Generalized Vacations”,  _Operations Research_ , vol 33: 5, pp. 1117 – 1129.
  * [9] Hirayama, T., Hong, S.J., & Krunz, M. (2004).  “A New Approach to Analysis of Polling Systems”  _Queueing Systems_ , vol 48: 1, pp. 135–158.
  * [10] Jennings, O.B. (2008).  “Heavy-Traffic Limits of Queueing Networks with Polling Stations: Brownian Motion in a Wedge”  _Mathematics of Operations Research_ , vol 33: 1, pp. 12 – 35.
  * [11] Srinivasan, M.M., Niu, S.C., & Cooper, R.B. (1995).  “Relating Polling Models With Zero and Nonzero Switchover Times”,  _Queueing Systems_ , vol 19: 1, pp. 149 – 168.
  * [12] Suman, R., & Krishnamurthy, A. (2020).  “Waiting Time Analysis in a Network of Polling Queues”,  _IISE Annual Conference and Expo 2018_ , pp.1205–1210.
  * [13] Suman, R. (2019)  “Stochastic Analysis of Tandem Network of Polling Queues with Applications in Manufacturing”,  _The University of Wisconsin - Madison_.
  * [14] Suman, R., & Krishnamurthy, A. (2020).  “Analysis of Tandem Polling Queues with Finite Buffers”,  _Annals of Operations Research_ , pp. 1 – 27.
  * [15] Suman, R., & Krishnamurthy, A. (2021).  “Conditional Waiting Time Analysis in Tandem Polling Queues”,  _ArXiv Preprint_
  * [16] Suman, R., & Krishnamurthy, A. (2022).  “Analysis of Two-Station Polling Queues with Setups using Continuous Time Markov Chain”,  _ArXiv Preprint_
  * [17] Takagi, H. (2000).  “Analysis and Application of Polling Models”,  _Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science_ , vol 1769, pp. 423 – 442, Springer, Berlin, Heidelberg.
  * [18] Olsen, T.L. (2001).  “Approximations for the Waiting Time Distribution in Polling Models With and Without State-Dependent Setups”,  _Operations Research Letters_ , vol 28, pp. 113 – 123.
  * [19] Tijms, H.C. (1994).  “Stochastic Models: An Algorithmic Approach”, _Chichester: Wiley_.
  * [20] Winands, E.M.M., Adan, I.J.B.F. & van Houtum, G. (2006).  “Mean Value Analysis for Polling Systems”  _Queueing Systems_ , vol 54: 35, pp. 35 – 44.
  * [21] Winands, E.M.M. (2011).  “Branching-Type Polling Systems with Large Setups”  _OR Spectrum_ , vol 33: 1, pp. 77 – 97.
  * [22] Vishnevskii, V.M., & Semenova, O.V. (2006).  “Mathematical Methods to Study the Polling Systems”,  _Automation and Remote Control_ , vol 67: 2, pp. 173 – 220.