Appendix 2
In order to prove Lemma 11, a simple arithmetic argument is required as presented in Lemma 15.
Now we give a proof for Lemma 11 as follows.
Case 1: \(x_1 \le x_1^{\prime }\)
We construct a new schedule by exchanging
\(\widetilde{\mu }_1\) clients with the periodicity of
\(q_1\) from
\(\Lambda _l\) with
\(\widetilde{\mu }_3\) clients with the periodicity of
\(q_3\) from
\(\Lambda _{l^{\prime }}\), where
\(\widetilde{\mu }_1 = \min \{\mu _1, x_1\}\) and
\(\widetilde{\mu }_3 = \min \{\mu _3^{\prime }, g_{23} - \left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \}\). Consider the set
\(\Lambda _l\) after the interchange. Observe that
\(1 \le \widetilde{\mu }_1 \le x_1\), and from (
43),
\(\widetilde{\mu }_3 \le g_{23} - \left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \le g_{23} - \left\lceil \mu _2/x_2\right\rceil \). Thus, applying inequality (
41),
$$\begin{aligned} \mu _3 + \widetilde{\mu }_3&\le \left( g_{31} - \left\lceil \frac{\mu _1}{x_1}\right\rceil + 1 \right) \left( g_{23} - \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) \\&= \left( g_{31} - \left\lceil \frac{\mu _1}{x_1}\right\rceil + \left\lceil \frac{\widetilde{\mu }_1}{x_1}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) \\&= \left\{ {\begin{array}{*{20}l} \;g_{31}\left( g_{23} - \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) &{} {\mathrm{{if}}\;\;\widetilde{\mu }_1 \!=\! \mu _1} \\ \left( g_{31} - \left\lceil \frac{\mu _1-\widetilde{\mu }_1}{x_1}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) &{} {\mathrm{{if}}\;\;\widetilde{\mu }_1 \!\ne \! \mu _1. } \\ \end{array}} \right. \end{aligned}$$
The former expression implies that
$$\begin{aligned} \left\lceil \frac{\mu _2}{g_{12}}\right\rceil + \left\lceil \frac{\mu _3+\widetilde{\mu }_3}{g_{31}}\right\rceil \le \left\lceil \frac{\mu _2}{x_2}\right\rceil + \left\lceil \frac{\mu _3+\widetilde{\mu }_3}{g_{31}}\right\rceil \le g_{23}, \end{aligned}$$
and hence
\(\mu _2\) and
\(\mu _3 + \widetilde{\mu }_3\) clients with the periodicity of
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}-\)set, by Theorem 1. The latter expression implies that
\(\mu _1 - \widetilde{\mu }_1\),
\(\mu _2\) and
\(\mu _3 + \widetilde{\mu }_3\) satisfy condition (
7) of Theorem 3. Moreover,
\(\mu _1 - \widetilde{\mu }_1\) and
\(\mu _2\) satisfy conditions (
5) and (
6) of Theorem 3 from (
37) and (
38) above. Thus,
\(\mu _1 - \widetilde{\mu }_1\),
\(\mu _2\) and
\(\mu _3 + \widetilde{\mu }_3\) clients with the periodicity of
\(q_1\),
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set, by Theorem 3.
Now consider the set
\(\Lambda _{l^{\prime }}\) after the interchange. Suppose first that
\(\widetilde{\mu }_3 \ne \mu _3^{\prime }\). Then
\(\widetilde{\mu }_3=g_{23} - \left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \), and from (
42),
$$\begin{aligned} \mu _3^{\prime }\! \!-\!\! \widetilde{\mu }_3&\!\le \! \left( g_{31} \!\!-\!\! \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil \right) \left( g_{23} \!-\! \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) \!-\!\! \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) \\&= \left( g_{31} - \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil - 1\right) \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) . \end{aligned}$$
Hence, since
\(1 \le \widetilde{\mu }_1 \le x_1 \le x_1^{\prime }\),
$$\begin{aligned} \mu _3^{\prime } - \widetilde{\mu }_3&\le \left( g_{31} - \left\lceil \frac{\mu _1^{\prime }+\widetilde{\mu }_1}{x_1^{\prime }}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) . \end{aligned}$$
Thus,
\(\mu _1^{\prime } + \widetilde{\mu }_1,\;\mu _2^{\prime }\) and
\(\mu _3^{\prime } - \widetilde{\mu }_3\) satisfy condition (
7) of Theorem 3. Moreover,
\(\mu _1^{\prime } + \widetilde{\mu }_1\) and
\(\mu _2^{\prime }\) satisfy conditions (
5) and (
6) of Theorem 3 from (
39) and (
40) above. Thus,
\(\mu _1^{\prime } + \widetilde{\mu }_1\),
\(\mu _2^{\prime }\) and
\(\mu _3^{\prime } - \widetilde{\mu }_3\) clients with the periodicity of
\(q_1\),
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}-\)set, by Theorem 3. On the other hand, suppose that
\(\widetilde{\mu }_3= \mu _3^{\prime }\). Recall that
\(1 \le \widetilde{\mu }_1 \le x_1 \le x_1^{\prime }\) in this case, and hence by (
39)
$$\begin{aligned} \frac{\mu _1^{\prime } + \widetilde{\mu }_1}{x_1^{\prime }} \le \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil + 1 \le g_{31}, \end{aligned}$$
which combines with (
40) to give
$$\begin{aligned} \left\lceil \frac{\mu _1^{\prime }+\widetilde{\mu }_1}{g_{31}}\right\rceil + \left\lceil \frac{\mu _2^{\prime }}{g_{23}}\right\rceil \le x_1^{\prime } + x_2^{\prime } \;=\; g_{12}. \end{aligned}$$
Thus,
\(\mu _1^{\prime } + \widetilde{\mu }_1\) and
\(\mu _2^{\prime }\) clients with the periodicity of
\(q_1\) and
\(q_2\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set, by Theorem 1.
Therefore, the feasibility of the schedule is preserved. Repeating this argument, we obtain a feasible schedule with \(\lambda _{123} \le 1\).
Case 2: \(x_1 > x_1^{\prime }\) and \(\left\lceil \mu _1/x_1\right\rceil \le \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \)
From \(x_1 > x_1^{\prime }\) and \(\left\lceil \mu _1/x_1\right\rceil \le \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \), we have that \(x_2 < x_2^{\prime }\) and \((g_{31}- \left\lceil \mu _1/x_1\right\rceil ) \ge (g_{31}- \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil )\). These conditions are covered by Case 1 when the periodicities 1 and 2 are interchanged.
Case 3: \(x_1 > x_1^{\prime }\) and \(\left\lceil \mu _1/x_1\right\rceil > \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \)
First consider the case when
\(x_1^{\prime } \ge x_2\). We construct a new schedule by exchanging
\(\mu _2\) clients with the periodicity of
\(q_2\) from
\(\Lambda _l\) with
\(\widetilde{\mu }_1\) clients with the periodicity of
\(q_1\) from
\(\Lambda _{l^{\prime }}\), where
\(\widetilde{\mu }_1 = \min \{\mu _1^{\prime }, \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil x_2\} \). Consider the set
\(\Lambda _l\) after the interchange. Since
\(\left\lceil \mu _1/x_1\right\rceil > \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \ge \widetilde{\mu }_1/x_2\), from Lemma 15,
\(\left\lceil \mu _1/x_1\right\rceil \ge \left\lceil (\mu _1+\widetilde{\mu }_1)/(x_1+x_2)\right\rceil \), and hence, from (
41),
$$\begin{aligned} \mu _3 \!\!\le \!\! \left( g_{31} \!\!\!-\!\!\! \left\lceil \frac{\mu _1}{x_1}\right\rceil \right) \left( g_{23} \!-\! \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) \!\le \! \left( g_{31} \!-\! \left\lceil \frac{\mu _1\!+\!\widetilde{\mu }_1}{x_1\!+\!x_2}\right\rceil \right) g_{23}. \end{aligned}$$
Thus,
$$\begin{aligned} \left\lceil \frac{\mu _1+\widetilde{\mu }_1}{g_{12}}\right\rceil + \left\lceil \frac{\mu _3}{g_{23}}\right\rceil&\le \left\lceil \frac{\mu _1+\widetilde{\mu }_1}{x_1+x_2}\right\rceil \\&+ \left( g_{31} - \left\lceil \frac{\mu _1+\widetilde{\mu }_1}{x_1+x_2}\right\rceil \right) = g_{31}. \end{aligned}$$
This implies that
\(\mu _1+\widetilde{\mu }_1\) and
\(\mu _3\) clients with the periodicity of
\(q_1\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set by Theorem 1. Now consider the set
\(\Lambda _{l^{\prime }}\) after the interchange. Observe that
$$\begin{aligned} \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil = \left\lceil \frac{\left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil (x_1^{\prime } - x_2)}{x_1^{\prime } - x_2}\right\rceil \ge \left\lceil \frac{\mu _1^{\prime } - \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil x_2}{x_1^{\prime } - x_2}\right\rceil \end{aligned}$$
and from (
43) and Lemma 15,
\(\left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \ge \left\lceil (\mu _2^{\prime }+\mu _2)\right. / \left. (x_2^{\prime }+x_2)\right\rceil .\) Thus, substituting the above two constraints into (
42),
$$\begin{aligned} \mu _3^{\prime }&\le \left( g_{31} - \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) \\&\le \left\{ {\begin{array}{*{20}l} \;g_{31}\left( g_{23} - \left\lceil \frac{\mu _2^{\prime }+\mu _2}{x_2^{\prime }+x_2}\right\rceil \right) &{} {\mathrm{{if}}\;\;\widetilde{\mu }_1 = \mu _1} \\ \left( g_{31} - \left\lceil \frac{\mu _1^{\prime }-\widetilde{\mu }_1}{x_1^{\prime }-x_2}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }+\mu _2}{x_2^{\prime }+x_2}\right\rceil \right) &{} {\mathrm{{if}}\;\;\widetilde{\mu }_1 \ne \mu _1. } \\ \end{array}} \right. \end{aligned}$$
The latter expression implies that
\(\mu _1^{\prime }-\widetilde{\mu }_1\),
\(\mu _2^{\prime }+\mu _2\) and
\(\mu _3^{\prime }\) satisfy condition (
7) of Theorem 3. Moreover,
\(\left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \ge \left\lceil (\mu _1^{\prime }+\widetilde{\mu }_1)/(x_1^{\prime }\!-\!x_2)\right\rceil \) when
\(\widetilde{\mu }_1 \ne \mu _1\) and
\(\left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \ge \left\lceil (\mu _2^{\prime }\!+\!\mu _2)/(x_2^{\prime }\!+\!x_2)\right\rceil \), and hence by letting
\(x=x_1^{\prime }-x_2\),
\(\mu _1^{\prime }-\widetilde{\mu }_1\) and
\(\mu _2^{\prime }+\mu _2\) satisfy conditions (
5) and (
6) of Theorem 3 from (
39) and (
40) above. Thus,
\(\mu _1^{\prime }-\widetilde{\mu }_1\),
\(\mu _2^{\prime }+\mu _2\) and
\(\mu _3^{\prime }\) clients with the periodicity of
\(q_1\),
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set by Theorem 3 when
\(\widetilde{\mu }_1 \ne \mu _1\). On the other hand, when
\(\widetilde{\mu }_1 = \mu _1\), the former expression implies that
$$\begin{aligned} \left\lceil \frac{\mu _2^{\prime }+\mu _2}{g_{12}}\right\rceil + \left\lceil \frac{\mu _3^{\prime }}{g_{31}}\right\rceil&\le \left\lceil \frac{\mu _2^{\prime }+\mu _2}{x_2^{\prime }+x_2}\right\rceil \\&+ \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }+\mu _2}{x_2^{\prime }+x_2}\right\rceil \right) = g_{23}, \end{aligned}$$
since
\(x_2^{\prime }+x_2^{\prime }\le x_2^{\prime } + x_1^{\prime } = g_{12}\). Hence, by Theorem 1,
\(\mu _2^{\prime }+\mu _2\) and
\(\mu _3^{\prime }\) clients with the periodicity of
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set.
Now consider the alternative case, when
\(x_1^{\prime } < x_2\). We construct a new schedule by exchanging
\(\widetilde{\mu }_2\) clients with the periodicity of
\(q_2\) from
\(\Lambda _l\) with
\(\mu _1^{\prime }\) clients with the periodicity of
\(q_1\) from
\(\Lambda _{l^{\prime }}\), where
\(\widetilde{\mu }_2 = \min \{\mu _2, \left\lceil \mu _2/x_2\right\rceil x_1^{\prime }\}\). Consider the set
\(\Lambda _{l^{\prime }}\) after the interchange. Since (
43),
\(\left\lceil \mu _2^{\prime }/x_2^{\prime }\right\rceil \ge \left\lceil \mu _2/x_2\right\rceil \ge \widetilde{\mu }_2/x_1^{\prime }\). From Lemma 15,
\(\left\lceil \mu _2^{\prime }/\!x\!_2^{\prime }\right\rceil \ge \left\lceil (\mu _2^{\prime }\!+\!\widetilde{\mu }_2)/(x_2^{\prime }\!+\!x_1^{\prime })\right\rceil ,\) and hence,
$$\begin{aligned} \mu _3^{\prime }&\le \left( g_{31} - \left\lceil \frac{\mu _1^{\prime }}{x_1^{\prime }}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }}{x_2^{\prime }}\right\rceil \right) \\&\le g_{31}\left( g_{23} - \left\lceil \frac{\mu _2^{\prime }+\widetilde{\mu }_2}{x_2^{\prime }+x_1^{\prime }}\right\rceil \right) . \end{aligned}$$
Thus,
$$\begin{aligned}&\left\lceil \frac{\mu _2^{\prime }+\widetilde{\mu }_2}{g_{12}}\right\rceil + \left\lceil \frac{\mu _3^{\prime }}{g_{31}}\right\rceil \le \left\lceil \frac{\mu _2^{\prime }+\widetilde{\mu }_2}{x_2^{\prime }+x_1^{\prime }}\right\rceil \\&\quad \quad \qquad \qquad \quad \qquad \qquad \quad + \left( g_{23} - \left\lceil \frac{\mu _2^{\prime }+\widetilde{\mu }_2}{x_2^{\prime }+x_1^{\prime }}\right\rceil \right) = g_{23}, \end{aligned}$$
which implies that
\(\mu _2^{\prime } + \widetilde{\mu }_2\) and
\(\mu _3^{\prime }\) clients with the periodicity of
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set by Theorem 1. Now consider the set
\(\Lambda _l\) after the interchange. Since
\(\left\lceil \mu _1/x_1\right\rceil > \left\lceil \mu _1^{\prime }/x_1^{\prime }\right\rceil \ge \mu _1^{\prime }/x_1^{\prime }\), from Lemma 15,
\(\left\lceil \mu _1/x_1\right\rceil \ge \left\lceil (\mu _1+\mu _1^{\prime })/(x_1+x_1^{\prime })\right\rceil \), and
$$\begin{aligned} \left\lceil \frac{\mu _2}{x_2}\right\rceil = \left\lceil \frac{\left\lceil \frac{\mu _2}{x_2}\right\rceil (x_2 - x_1^{\prime })}{x_2 - x_1^{\prime }}\right\rceil \ge \left\lceil \frac{\mu _2 - \left\lceil \frac{\mu _2}{x_2}\right\rceil x_1^{\prime }}{x_2 - x_1^{\prime }}\right\rceil . \end{aligned}$$
Thus, substituting the above two constraints into (
41),
$$\begin{aligned} \mu _3&\le \left( g_{31} - \left\lceil \frac{\mu _1}{x_1}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2}{x_2}\right\rceil \right) \\&\le \left\{ {\begin{array}{*{20}l} \left( g_{31} - \left\lceil \frac{\mu _1+\mu _1^{\prime }}{x_1+x_1^{\prime }}\right\rceil \right) g_{23} &{} {\mathrm{{if}}\;\;\widetilde{\mu }_2 = \mu _2} \\ \left( g_{31} - \left\lceil \frac{\mu _1+\mu _1^{\prime }}{x_1+x_1^{\prime }}\right\rceil \right) \left( g_{23} - \left\lceil \frac{\mu _2- \widetilde{\mu }_2}{x_2-x_1^{\prime }}\right\rceil \right) &{} {\mathrm{{if}}\;\;\widetilde{\mu }_2 \ne \mu _2. } \\ \end{array}} \right. \end{aligned}$$
The latter expression implies that
\(\mu _1+\mu _1^{\prime }\),
\(\mu _2-\widetilde{\mu }_2\) and
\(\mu _3\) satisfy condition (
7) of Theorem 3. Moreover,
\(\left\lceil \mu _1/x_1\right\rceil \!\ge \! \left\lceil (\mu _1\!+\!\mu _1^{\prime })/(x_1\!+\!x_1^{\prime })\right\rceil \) and
\(\left\lceil \mu _2/x_2\right\rceil \!\ge \! \left\lceil (\mu _2\!-\!\widetilde{\mu }_2)/(x_2\!-\!x_1^{\prime })\right\rceil \) when
\(\widetilde{\mu }_2 \ne \mu _2\), and hence by letting
\(x=x_1 +x_1^{\prime }\),
\(\mu _1\!+\!\mu _1^{\prime }\) and
\(\mu _2-\widetilde{\mu }_2\) satisfy conditions (
5) and (
6) of Theorem 3 from (
37) and (
38) above. Thus,
\(\mu _1+\mu _1^{\prime }\),
\(\mu _2-\widetilde{\mu }_2\) and
\(\mu _3\) clients with the periodicity of
\(q_1\),
\(q_2\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set by Theorem 3 when
\(\widetilde{\mu }_2 \ne \mu _2\). On the other hand, when
\(\widetilde{\mu }_2 = \mu _2\), the former expression implies that
$$\begin{aligned} \left\lceil \frac{\mu _1+\mu _1^{\prime }}{g_{12}}\right\rceil + \left\lceil \frac{\mu _3}{g_{23}}\right\rceil&\le \left\lceil \frac{\mu _1+\mu _1^{\prime }}{x_1+x_1^{\prime }}\right\rceil \\&+ \left( g_{31} - \left\lceil \frac{\mu _1+\mu _1^{\prime }}{x_1+x_1^{\prime }}\right\rceil \right) = g_{31}, \end{aligned}$$
since
\(x_1+x_1^{\prime }< x_1 + x_2 = g_{12}\). Hence, by Theorem 1,
\(\mu _1 + \mu _1^{\prime }\) and
\(\mu _3\) clients with the periodicity of
\(q_1\) and
\(q_3\), respectively, fit into a single
\({\varvec{\Lambda }}\)-set.
Therefore, the feasibility of the schedule is preserved. Repeating this argument, we obtain a feasible schedule with \(\lambda _{123} \le 1\). \(\square \)