INR-TH-2024-001

# NICA prospects in searches for light exotics from hidden sectors: the cases
of hidden photons and axion-like particles

Dmitry Gorbunov<EMAIL_ADDRESS>Dmitry Kalashnikov
<EMAIL_ADDRESS>Institute for Nuclear Research of Russian Academy
of Sciences, 117312 Moscow, Russia  Moscow Institute of Physics and
Technology, 141700 Dolgoprudny, Russia

###### Abstract

We present first estimates of NICA sensitivity to Standard Model extensions
with light hypothetical particles singlet under the known gauge
transformations. Our analysis reveals that NICA can explore new regions in the
parameter spaces of models with a hidden vector and models with an axion-like
particle of masses about 30-500 MeV. Some of these regions seem unreachable by
other ongoing and approved future projects. NICA has good prospects in
discovery ($5\sigma$) of the new physics after 1 year of data taking.

1. Nuclotron based Ion Collider fAcility (NICA) 111NICA website nica.jinr.ru is a new accelerator complex designed at Joint Institute for Nuclear Research in Dubna, Moscow region. The construction took about 10 years with active participation of thousands scientists and technicians from several tens of institutions all over the World. NICA plans operaion with colliding beams of $p$, Au, Zn and the ion energy per nucleon will vary in the range 4-11 GeV.

Being a circular collider, NICA will operate with two collision points where
two different instruments, Multi-Purpose Detector (MPD) [1] and Spin Physics
Detector (SPD) [2] are installed. While its main goal is investigating the
hadronic matter — nucleus structure, quark-gluon plasma, high baryonic
density, etc — it can be used for probing fundamental new physics which can
show up in the heavy ion collisions.

The kinematics implies that the most promising mass range for the new
hypothetical particles to be produced by collisions at NICA is subGeV. The new
physics, needed to explain neutrino oscillations, dark matter, baryon
asymmetry of the Universe, inflation, etc, can indeed be at such low energy
scale, provided by only feeble interaction with known ingredients of the
Standard Model of particle physics (SM), for examples see correspondingly
Refs. [3, 4, 5, 6]. Likewise, the large electric charge of the colliding ions
favors models with the light particles coupled to photons as models to be
explored to a larger extent.

Hence, in this Letter we consider models with hypothetical light vectors
(hidden photons) and models with axion-like particles (ALPs), both exhibiting
direct interactions with photons. Physical motivation for these models,
various concrete realisations, present constraints on the model parameters
along with prospects of future experiments in testing their predictions can be
found in e.g. recent reviews [7, 8, 9]. Here we identify the dominant
mechanisms of production of these hypothetical particles at NICA, their
promising signatures, check them against the relevant background and finally
estimate the NICA sensitivity to the model parameters.

2. Both hidden photon and ALPs can travel macroscopic distances before decaying into visible particles. Given this fact we propose to search for the corresponding displaced vertex signature. The noticeable displacement reduces the otherwise too high background down to a negligible level. In recent MPD TDR an upgrade of Inner Tracking System (ITS) was proposed [10]. This upgrade will allow one to determine the displaced vertex position with resolution up to $\sim 10$ $\mu$m. The position of the ion collision (the actual point of each collision) can be fixed within a region of about 100 $\mu$m. To compare different possible outcomes we perform our calculations for three different minimal travel distances of new physics (NP) particles: $L_{min}=100$ $\mu$m, $L_{min}=500$ $\mu$m and $L_{min}=1000$ $\mu$m. The probability of a particle to travel a distance larger than $L_{min}$ and nevertheless decay inside the detector is given by

$P=\exp\left(-\frac{L_{min}}{d}\right)-\exp\left(-\frac{L_{max}}{d}\right),$
(1)

where $L_{max}\sim 1$ m is the detector size, and $d=\tau\gamma\beta$ is the
mean travel distance of NP particle. In our estimations we inferred
$d_{max}\sim 1$ mm that yields $L_{max}\gg d$,
$\exp\left(-\frac{L_{max}}{d}\right)\approx 0$, hence the probability (1)
approaches

$P=\exp\left(-\frac{L_{min}}{d}\right)\,.$ (2)

In our work for the signal of $A^{\prime}$ we consider only its electronic
decay (i.e. $A^{\prime}\to e^{+}e^{-}$), because in the present configuration
the MPD is not equipped with muon detector, while the hadronic decay modes of
$A^{\prime}$ are undistinguished given the huge pion background. In the model
with axion-like particle only the radiative decay (i.e.
$a^{\prime}\to\gamma\gamma$) is accounted as the potential signal source.
However, there are other decays to SM particles. In each model we sum up all
of them to the total decay width to SM particles denoted as $\Gamma_{SM}$.
Moreover, in a particular model of the hypothetical particle there can be
decay modes to particles from the hidden sector. Such unexplored decays can
give sizeable contribution to the total decay width of the hypothetical
particle $1/\tau\equiv\Gamma_{tot}$ and consequently $d$ and relevant
branchings. To take into account these possible decays we additionally discuss
the Half Hidden case (HH) with total width $\Gamma_{tot}=2\Gamma_{SM}$ and the
Half Hidden/5 case (HH/5) with $\Gamma_{tot}=10\Gamma_{SM}$. The first case
corresponds to models where the couplings to hidden sector are of the same
order as the couplings to SM. The second case corresponds to models where the
hidden sector decays dominate. The numbers of signal events then read

$\displaystyle N_{S}$ $\displaystyle=N_{A^{\prime}}\times
P\times\frac{\Gamma(A^{\prime}\rightarrow e^{+}e^{-})}{\Gamma_{tot}},$ (3)
$\displaystyle N_{S}$ $\displaystyle=N_{a}\times
P\times\frac{\Gamma(a\rightarrow\gamma\gamma)}{\Gamma_{tot}},$ (4)

where $N_{A^{\prime}}$ and $N_{a}$ are the numbers of produced hidden vectors
$A^{\prime}$ and ALPs $a$.

Light long-lived mesons like K-mesons are the main source of possible
background, because these mesons also can travel macroscopic distances in the
detector before their decay into visible particles. However, the maximum reach
for NP mass at NICA appears to be less than kaon mass $m_{K}=498$ MeV even in
the background-free case. Still, pions from kaon semileptonic decays may be
misidentified with electrons, which interferes with the suggested signature of
$A^{\prime}$. To avoid this type of background we follow the special procedure
which singles out only pure (almost 100%) electrons at the cost of
60%-reduction of the expected electron statistics [1]. Consequently, the
background-free identification of the signal $e^{+}e^{-}$ pair will be allowed
only for $0.4\times 0.4=0.16$ of the total signal statistics. In what follows
we adopt this procedure and to estimate the 95% CL sensitivity of NICA to the
model parameters we ask for the NICA operation time large enough to collect
not 3 (as typically required by the Poisson statistics in the background free
case) but 3/0.16=18 signal events.

3. First, we investigate models with light vector hypothetical particle $A^{\prime}$ coupled to the SM fields through the vector portal [11]

${\cal
L}_{int}=-\frac{\epsilon}{2}\left(\partial_{\mu}A_{\nu}-\partial_{\nu}A_{\mu}\right)\left(\partial_{\mu}A_{\nu}^{\prime}-\partial_{\nu}A_{\mu}^{\prime}\right),$
(5)

where $A_{\mu}$ stands for the SM photon field. This mixing with photon (5)
yields $A^{\prime}$ direct production in heavy ion collisions, where the big
electric charge highly amplifies the production cross section with respect to
$A^{\prime}$ production in $e^{+}e^{-}$ collisions at similar energies, e.g.
at future $c$-$\tau$ factories [12, 13, 14, 15].

Likewise, one can take advantage of the multiple production inherent in
hadronic scattering: the hidden photon can also emerge in photonic decays of
mesons produced in heavy ion collisions. The most promising decays for the
interesting previously unexplored range of $A^{\prime}$ masses and mixing
$\epsilon<10^{-3}$ are $\pi^{0}\to\gamma A^{\prime}$, $\eta\to\gamma
A^{\prime}$ and $\omega\to\pi^{0}A^{\prime}$. The corresponding branchings are
[16]

$\displaystyle\text{Br}\left(P\to\gamma A^{\prime}\right)$
$\displaystyle=2\epsilon^{2}\,\text{Br}\left(P\rightarrow\gamma\gamma\right)\times\left(1-\frac{m^{2}_{A^{\prime}}}{m^{2}_{P}}\right)^{3},$
(6) $\displaystyle\text{Br}\left(\omega\to\pi^{0}A^{\prime}\right)$
$\displaystyle=\epsilon^{2}\,\text{Br}\left(\omega\rightarrow\pi^{0}\gamma\right)\times\frac{\left[\left(m_{\omega}^{2}-(m_{A^{\prime}}+m_{\pi})^{2}\right)\left(m_{\omega}^{2}-(m_{A^{\prime}}-m_{\pi})^{2}\right)\right]^{3/2}}{\left(m_{\omega}^{2}-m_{\pi}^{2}\right)^{3}}.$
(7)

Since the parent mesons above are short-lived, all the hidden particles appear
in the small vicinity of the ion collision point. The momentum distribution of
the produced in this way $A^{\prime}$ is obtained by boosting the isotropic
distribution over 3-momenta in the meson decay frame to the laboratory frame.
The boost parameters are determined by the transverse momentum $p_{T}$ and
rapidity $y$ of the parent mesons, which we obtain by making use of the
simulations of $10^{5}$ Bi Bi collisions at central mass energy
$\sqrt{s_{\text{NN}}}=9.2$ GeV per nucleon. The simulations are performed with
generator PHSD for pseudoscalar mesons [17] and with generator UrQMD for
vector mesons [18].

In 1 year (50 weeks) of the MPD data taking at the differential luminosity of
$L=10^{27}\,\text{ cm}^{-2}\,\text{s}^{-1}$ we get $N_{\pi}\sim 10^{13}$
neutral pions, $N_{\eta}\sim 10^{12}$ $\eta$-mesons and $N_{\omega}\sim
10^{11}$ $\omega$-mesons [19]. Each channel contributes to the number of
produced hidden photons $A^{\prime}$ as ($X=\pi,\eta,\omega$)

$N_{A^{\prime}}=N_{X}\times\text{Br}\left(X\to A^{\prime}\right)\,.$

The produced hidden vector can potentially decay into the SM particles among
which we recognize lepton and meson pairs with decay rates [20]

$\displaystyle\Gamma\left(A^{\prime}\to l^{+}l^{-}\right)$
$\displaystyle=\frac{\epsilon^{2}e^{2}}{12\pi}m_{A^{\prime}}\left(1+\frac{2m_{l}^{2}}{m_{A^{\prime}}^{2}}\right)\sqrt{1-\frac{4m_{l}^{2}}{m_{A^{\prime}}^{2}}},$
(8) $\displaystyle\Gamma\left(A^{\prime}\to hadrons\right)$
$\displaystyle=\Gamma\left(A^{\prime}\to\mu^{+}\mu^{-}\right)\times
R(m_{A^{\prime}}),$ (9)

where $R(\sqrt{s})=\sigma(e^{+}e^{-}\rightarrow
hadrons)/\sigma(e^{+}e^{-}\rightarrow\mu^{+}\mu^{-})$ is the energy dependent
R-ratio [21].

Then we must account for the fact that the initial meson 3-momentum affects
the decay length of $A^{\prime}$ via non-unity boost factor. We integrate
$(p_{T},y)$ distributions obtained by simulations to get the normalized to
unity $dn_{X}/dp_{X}$ distributions over meson 3-momentum $p_{X}$. Then we
transform Eq.(3) accordingly and get for the number of signal events, these
are electron-positron pairs coming from the vertex displaced from the ion
collision region,

$N_{S}=\int dp_{X}\,N_{X}\,\frac{dn_{X}}{dp_{X}}\times\text{Br}\left(X\to
A^{\prime}\right)\times\text{Br}\left(A^{\prime}\rightarrow
e^{+}e^{-}\right)\times\exp\left(-\frac{L_{min}}{d}\right).$ (10)

Here $d\equiv 1/\Gamma_{tot}\times p_{A^{\prime}}/m_{A^{\prime}}$ and
$p_{A^{\prime}}$ is the $A^{\prime}$ 3-momentum in the laboratory frame. Since
MPD can only detect photons with energies exceeding $50$ MeV, we accordingly
constrain the momenta in the integral (10). Within this approach we arrive at
the results presented in Figs.1, 2, 3,

Figure 1: The regions to be probed at NICA after 1 year of operation at 95% CL
with $A^{\prime}$ produced in $\eta$ meson decays. Left plot shows results for
different minimal recognizable travel distance of $A^{\prime}$, parameterized
by $L_{min}$ in eq. (2). Right plot shows results for different values of
$\Gamma_{tot}$. The existing limits (colored and outlined) are taken from
BaBar at 90% CL [22], KLOE at 90% CL [23], accelerator experiments (NA64 at
90% CL [24], E141 at 95% CL [25], NuCal at 95% CL [26]) and expected reaches
of the ongoing experiments (colored) are given for FASER at 95% CL [27],
Belle-II at 90% CL [28], LHCb D∗ at 95% CL [29], LHCB$\mu$ at 95% CL [30].

where black lines correspond to 18 signal events (lepton pairs) consistent
with limits at 95% CL in the background free case according to our procedure
explained above.

Figure 2: The regions to be probed at NICA after 1 year of operation at 95% CL
with $A^{\prime}$ produced in $\pi^{0}$ meson decays. Left plot shows results
for different minimal recognizable travel distance of $A^{\prime}$,
parameterized by $L_{min}$ in eq. (2). Right plot shows results for different
values of $\Gamma_{tot}$. The existing limits (colored and outlined) are taken
from BaBar at 90% CL [22], KLOE at 90% CL [23], accelerator experiments (NA64
at 90% CL [24], E141 at 95% CL [25], NuCal at 95% CL [26]) and expected
reaches of the ongoing experiments (colored) are given for FASER at 95% CL
[27], Belle-II at 90% CL [28], LHCb D∗ at 95% CL [29], LHCB$\mu$ at 95% CL
[30].

Figure 3: The regions to be probed at NICA after 1 year of operation at 95% CL
with $A^{\prime}$ produced in $\omega$ meson decays. Left plot shows results
for different minimal recognizable travel distance of $A^{\prime}$,
parameterized by $L_{min}$ in eq. (2). Right plot shows results for different
values of $\Gamma_{tot}$. The existing limits (colored and outlined) are taken
from BaBar at 90% CL [22], KLOE at 90% CL [23], accelerator experiments (NA64
at 90% CL [24], E141 at 95% CL [25], NuCal at 95% CL [26]) and expected
reaches of the ongoing experiments (colored) are given for FASER at 95% CL
[27], Belle-II at 90% CL [28], LHCb D∗ at 95% CL [29], LHCB$\mu$ at 95% CL
[30].

On this plots we illustrate the NICA sensitivity to model parameters
$\epsilon$, $m_{A}$ considering separately the three sources of $A^{\prime}$
production. We also investigate the impact of the total decay width
$\Gamma_{tot}$ of $A^{\prime}$ on the NICA sensitivity. To this end for the
plots on left panels we assume $\Gamma_{tot}$ to be a free parameter, but
constrained in such a way, that $\Gamma_{tot}\gtrsim\Gamma_{SM}$ and
corresponding particle decay length defined below Eq. (10) is large enough to
avoid the suppression (2) due to minimal recognizable decay length
$L_{min}=100,\,500,\,1000$ $\mu$m. The latter suppression guarantees, that the
decay vertex is displaced from the ion collision point at the distance
sufficient to be recognizable, and no any background is expected at such
distances. For the plots on right panels we assume a particular relations
between the total width $\Gamma_{tot}$ and the width into SM modes
$\Gamma_{SM}$ and constrain the decay length $d$ from below by choosing the
minimal displacement as $L_{min}=100\,\mu$m.

One concludes, that new regions of the model parameter space can certainly be
explored at NICA after 1 year of operation. The production of $A^{\prime}$ is
dominated by $\pi^{0}$ and $\eta^{0}$ decays.

To estimate the contribution of the direct production of $A^{\prime}$ in heavy
ion collisions we consider its production in ultraperipheral collisions via
$A^{\prime}$-strahlung, assuming colliding ions remain intact. To calculate
the cross section we make use of the CalcHEP package [31] and multiply each
electromagnetic vertex with fermions by the monopole form factor [32]. The
obtained results show that cross section of such processes is too small to
produce interesting amount of $A^{\prime}$.

4. The second model we investigate is Axion Like Particle (ALP) with coupling to photons

$\mathcal{L}=\frac{1}{8}g_{a\gamma\gamma}\;a\,F_{\mu\nu}F_{\lambda\rho}\epsilon^{\mu\nu\lambda\rho}.$
(11)

Along with effective coupling of neutral pseudoscalar mesons
$P=\pi^{0},\,\eta,\,\eta^{\prime}$ to photons [33],

$\mathcal{L}=\frac{\alpha}{4\pi
f}c_{P}\;P\,F_{\mu\nu}F_{\lambda\rho}\epsilon^{\mu\nu\lambda\rho},$ (12)

where $f=92.4$ MeV, $c_{\pi}=1,\;c_{\eta}=1.10,\;c_{\eta^{\prime}}=1.34$, eq.
(11) yields decays of mesons to axions $P\rightarrow\gamma\gamma a$ through
the diagram depicted in Fig.4.

Figure 4: The Feynman diagram for the production of axion in pseudoscalar
radiative decays.

The width of ALP decay to photons is

$\Gamma(a\rightarrow\gamma\gamma)=\frac{g_{a\gamma\gamma}^{2}m_{a}^{3}}{64\pi}.$
(13)

In our analysis, calculating ALP production and ALP decays we account for only
ALP coupling to photons. Generically, there also could be ALP interactions
with leptons and quarks, as we have in QCD axion models. Couplings to fermions
open new decays to pairs of electrons, muons and mesons (if kinematically
allowed). Typically, ALP decay rates to pair of leptons are suppressed by
$m_{l}^{2}/m_{a}^{2}$ [34]. Nevertheless one may say we somehow account for
them introducing HH and HH/5 cases with an additional to photon contribution
to the ALP total width. Coupling to fermions could also provide with another
sources of ALPs like weak decays of $K$-mesons [35, 36]. In our case, where
the photon coupling dominates, we neglect all other possible additional
sources of ALP production, and consider only two-photon displaced vertex as
the signature of ALP decay inside the NICA detector. It implies, that together
with HH and HH/5 cases we obtain conservative estimates of the NICA reach.

For ALPs we use the same simulations of ion collisions as we exploited above
for the model with $A^{\prime}$. The squared amplitude of process depicted in
Fig.4 is calculated using CalcHEP package [31] and then integrated over the
interesting region of the phase space as explained in the case of
$A^{\prime}$. The achieved results are depicted in Fig.5 and Fig. 6,

Figure 5: The regions to be probed at NICA after 1 year of operation at 95% CL
with ALPs produced in $\eta$ meson decays. Left plot shows results for
different minimal recognizable travel distance of ALP, parameterized by
$L_{min}$ in eq. (2). Right plot shows results for different values of
$\Gamma_{tot}$. The existing limits (colored and outlined) are taken from
Belle at 95% CL [37], LEP at 95% CL [38], accelerator experiments (NA64 at 90%
CL [39], E137 at 95% CL [40], NuCal at 90% CL [41]) and expected reaches of
the ongoing experiments (colored) are given for FASER at 95% CL [42], Belle-II
at 90% CL [43].

where the black line refers to 3 signal events required within the Poisson
statistics to exclude the corresponding outlined regions at 95% CL (there is
no dangerous background for the displaced vertex of two photons from the ALP
decay).

Figure 6: The regions to be probed at NICA after 1 year of operation at 95% CL
with ALPs produced in $\eta^{\prime}$ meson decays. Left plot shows results
for different minimal recognizable travel distance of ALP, parameterized by
$L_{min}$ in eq. (2). Right plot shows results for different values of
$\Gamma_{tot}$. The existing limits (colored and outlined) are taken from
Belle at 95% CL [37], LEP at 95% CL [38], accelerator experiments (NA64 at 90%
CL [39], E137 at 95% CL [40], NuCal at 90% CL [41]) and expected reaches of
the ongoing experiments (colored) are given for FASER at 95% CL [42], Belle-II
at 90% CL [43].

We find that the pion contribution to the ALP production is negligible for the
model parameters in the previously unexplored regions.

There is also a direct contribution to the ALP production in heavy ion
collisions due to rescatterings of the secondary photons abundantly produced
in the collisions and subsequent relaxation processes. To estimate the number
of ALPs coming from that photon-photon scattering we make use of the method
presented in [32] and perform calculations for Bi Bi collisions at the same
luminosity of $L=5\cdot 10^{27}\,\text{ cm}^{-2}\,\text{s}^{-1}$ and center-
of-mass energy, $\sqrt{s_{\text{NN}}}=9.2$ GeV, as we adopted for simulation
of the light meson production described above. In our calculations we use the
monopole approximation for equivalent photon spectrum:

$n(\omega)=\frac{Z^{2}\alpha}{\pi}\left[\left(2\frac{\omega^{2}}{(\Lambda\gamma)^{2}}+1\right)\ln\left(1+\frac{(\Lambda\gamma)^{2}}{\omega^{2}}\right)-2\right]\frac{1}{\omega},$
(14)

where $\omega$ is the photon energy, $\gamma$ is the ion gamma-factor, and we
set $\Lambda=50$ MeV. Then we obtain for the cross section of $NN\rightarrow
NNa$:

$\sigma=\sigma(\gamma\gamma\rightarrow
a)\int_{m_{a}^{2}/\omega_{max}^{2}}^{\omega_{max}^{2}/m_{a}^{2}}\frac{dx}{8}n\left(\sqrt{\frac{m_{a}^{2}x}{4}}\right)n\left(\sqrt{\frac{m_{a}^{2}}{4x}}\right),$
(15)

with photon energy ratio $x\equiv\omega_{1}/\omega_{2}$ and
$\omega_{max}\gg\Lambda\gamma$ solving the equation $n(\omega_{max})=0$. Here
again we require that energies of the photons from ALP decays exceed $50$ MeV.
The corresponding to 3 signal events contours are presented in Fig. 7.

Figure 7: The regions to be probed at NICA after 1 year of operation at 95% CL
with ALPs produced in ultraperipheral collisions. The existing limits (colored
and outlined) are taken from Belle at 95% CL [37], LEP at 95% CL [38],
accelerator experiments (NA64 at 90% CL [39], E137 at 95% CL [40], NuCal at
90% CL [41]) and expected reaches of the ongoing experiments (colored) are
given for FASER at 95% CL [42], Belle-II at 90% CL [43].

One observes from Figs. 5-7, that the direct production exhibits similar to
$\eta$-meson channel potential in testing the models with light ALPs.

5. To summarise, in this letter, we start the investigation of the NICA perspectives in searches for hypothetical light particles. We study models with light vectors and model with light axion-like particles. After an upgrade of MPD with ITS it becomes possible to use the displaced vertex as a signature of the light particle decays. It allows to cover yet unexplored regions of new physics model parameter space and cross check results of other ongoing experiments. Implementing HH case in our analysis we further widen the spectrum of models which NICA can actually explore. One may anticipate good prospects for NICA in testing models with light scalars and axial vectors as well.

Our results for ALPs may be improved by taking into account fermionic
couplings and non radiative decays of mesons to ALP inherent in particular
models. However we don’t expect a significant improvement in the NICA
sensitivity. Then, while the direct production is a promising source of ALPs
but there are known uncertainties in calculation of the ALP production in such
processes, e.g. how to determine the number of ultra-peripherial collisions
and the spectrum of viable photons. Still it seems to be the most powerful
source of ALPs at high collision energies with higher $\gamma$-factor for
ions. In the case of $A^{\prime}$ it may be worth to conduct more detailed
research of ultraperipheral collisions. As soon as the details (type of
colliding ions, their energies, luminosity, ITS resolution and other) of MPD
update are finally fixed one will refine the present analysis.

We thank S. Demidov for stimulating ideas and S. Godunov for interesting
discussions. We especially appreciate V. Riabov for valuable comments on the
manuscript, for the information on the NICA collider and detector systems and
for sharing files with kinematics of mesons simulated for NICA beam
scatterings. The work on the expected signal from decaying light exotic
particles is supported by the Russian Science Foundation RSF grant
21-12-00379. The work of D. K. on the expected background is supported by the
Foundation for the Advancement of Theoretical Physics and Mathematics “BASIS”.

## References

  * [1] NICA Collaboration, V. Abgaryan et al., “Status and initial physics performance studies of the MPD experiment at NICA,” The European Physical Journal A 58 no. 7, (Jul, 2022) . https://doi.org/10.1140%2Fepja%2Fs10050-022-00750-6.
  * [2] V. V. Abramov et al., “Possible studies at the first stage of the NICA collider operation with polarized and unpolarized proton and deuteron beams,” Physics of Particles and Nuclei 52 no. 6, (Nov, 2021) 1044–1119. https://doi.org/10.1134%2Fs1063779621060022.
  * [3] T. Asaka, S. Blanchet, and M. Shaposhnikov, “The nuMSM, dark matter and neutrino masses,” Phys. Lett. B 631 (2005) 151–156, arXiv:hep-ph/0503065.
  * [4] M. Pospelov, A. Ritz, and M. B. Voloshin, “Secluded WIMP Dark Matter,” Phys. Lett. B 662 (2008) 53–61, arXiv:0711.4866 [hep-ph].
  * [5] E. K. Akhmedov, V. A. Rubakov, and A. Y. Smirnov, “Baryogenesis via neutrino oscillations,” Phys. Rev. Lett. 81 (1998) 1359–1362, arXiv:hep-ph/9803255.
  * [6] F. Bezrukov and D. Gorbunov, “Light inflaton Hunter’s Guide,” JHEP 05 (2010) 010, arXiv:0912.0390 [hep-ph].
  * [7] G. Lanfranchi, M. Pospelov, and P. Schuster, “The search for feebly interacting particles,” Annual Review of Nuclear and Particle Science 71 no. 1, (2021) 279–313, https://doi.org/10.1146/annurev-nucl-102419-055056. https://doi.org/10.1146/annurev-nucl-102419-055056.
  * [8] J. L. Feng et al., “The forward physics facility at the high-luminosity LHC,” Journal of Physics G: Nuclear and Particle Physics 50 no. 3, (Jan, 2023) 030501. https://doi.org/10.1088%2F1361-6471%2Fac865e.
  * [9] A. Berlin, G. Krnjaic, and E. Pinetti, “Reviving mev-gev indirect detection with inelastic dark matter,” 2023.
  * [10] NICA Collaboration, “MPD-ITS TDR,” 2022.  http://mpd.jinr.ru/doc/mpd-tdr/.
  * [11] B. Holdom, “Two U(1)’s and Epsilon Charge Shifts,” Phys. Lett. B 166 (1986) 196–198.
  * [12] D. Gorbunov and D. Kalashnikov, “Probing light exotics from a hidden sector at $c\text{$-$}\tau$ factories with polarized electron beams,” Phys. Rev. D 107 (Jan, 2023) 015014. https://link.aps.org/doi/10.1103/PhysRevD.107.015014.
  * [13] D. Gorbunov, D. Kalashnikov, P. Pakhlov, and T. Uglov, “On direct observation of millicharged particles at $c\text{$-$}\tau$ factories and other $e^{+}e^{-}$ -colliders,” Physics Letters B 843 (2023) 138033. https://www.sciencedirect.com/science/article/pii/S0370269323003672.
  * [14] Y. Zhang, W.-T. Zhang, M. Song, X.-A. Pan, Z.-M. Niu, and G. Li, “Probing invisible decay of a dark photon at besiii and a future super tau charm factory via monophoton searches,” Phys. Rev. D 100 (Dec, 2019) 115016. https://link.aps.org/doi/10.1103/PhysRevD.100.115016.
  * [15] Z. Liu and Y. Zhang, “Probing millicharge at besiii via monophoton searches,” Phys. Rev. D 99 (Jan, 2019) 015004. https://link.aps.org/doi/10.1103/PhysRevD.99.015004.
  * [16] C. Ahdida and Others, “Sensitivity of the SHiP experiment to dark photons decaying to a pair of charged particles,” The European Physical Journal C 81 no. 5, (May, 2021) . https://doi.org/10.1140%2Fepjc%2Fs10052-021-09224-3.
  * [17] W. Cassing and E. L. Bratkovskaya, “Parton-Hadron-String Dynamics: an off-shell transport approach for relativistic energies,” Nucl. Phys. A 831 (2009) 215–242, arXiv:0907.5331 [nucl-th].
  * [18] S. Bass, “Microscopic models for ultrarelativistic heavy ion collisions,” Progress in Particle and Nuclear Physics 41 (1998) 255–369. https://doi.org/10.1016%2Fs0146-6410%2898%2900058-1.
  * [19] NICA Collaboration, D. Blaschke and Others, “NICA White Paper,” 2014\.  https://mpdroot.jinr.ru.
  * [20] T. Araki, K. Asai, T. Iizawa, H. Otono, T. Shimomura, and Y. Takubo, “New constraint on dark photon at t2k off-axis near detector,” 2023.
  * [21] Particle Data Group Collaboration, R. L. Workman and Others, “Review of Particle Physics,” PTEP 2022 (2022) 083C01.
  * [22] BaBar Collaboration, J. P. Lees et al., “Search for a dark photon in ${e}^{+}{e}^{-}$ collisions at babar,” Phys. Rev. Lett. 113 (Nov, 2014) 201801. https://link.aps.org/doi/10.1103/PhysRevLett.113.201801.
  * [23] A. Anastasi et al., “Limit on the production of a low-mass vector boson in $e^{+}e^{-}\to$ u$\gamma$, u$\to e^{+}e^{-}$ with the kloe experiment,” Physics Letters B 750 (2015) 633–637. https://www.sciencedirect.com/science/article/pii/S0370269315007546.
  * [24] The NA64 Collaboration Collaboration, D. Banerjee et al., “Improved limits on a hypothetical $x(16.7)$ boson and a dark photon decaying into ${e}^{+}{e}^{-}$ pairs,” Phys. Rev. D 101 (Apr, 2020) 071101. https://link.aps.org/doi/10.1103/PhysRevD.101.071101.
  * [25] S. Andreas, C. Niebuhr, and A. Ringwald, “New limits on hidden photons from past electron beam dumps,” Phys. Rev. D 86 (Nov, 2012) 095019. https://link.aps.org/doi/10.1103/PhysRevD.86.095019.
  * [26] J. Blümlein and J. Brunner, “New exclusion limits on dark gauge forces from proton bremsstrahlung in beam-dump data,” Physics Letters B 731 (2014) 320–326. https://www.sciencedirect.com/science/article/pii/S0370269314001208.
  * [27] F. Kling and S. Trojanowski, “Forward experiment sensitivity estimator for the lhc and future hadron colliders,” Phys. Rev. D 104 (Aug, 2021) 035012. https://link.aps.org/doi/10.1103/PhysRevD.104.035012.
  * [28] E. Kou et al., “The Belle II Physics Book,” Progress of Theoretical and Experimental Physics 2019 no. 12, (12, 2019) 123C01, https://academic.oup.com/ptep/article-pdf/2019/12/123C01/32693980/ptz106.pdf. https://doi.org/10.1093/ptep/ptz106.
  * [29] P. Ilten, J. Thaler, M. Williams, and W. Xue, “Dark photons from charm mesons at lhcb,” Phys. Rev. D 92 (Dec, 2015) 115017. https://link.aps.org/doi/10.1103/PhysRevD.92.115017.
  * [30] P. Ilten, Y. Soreq, J. Thaler, M. Williams, and W. Xue, “Proposed inclusive dark photon search at lhcb,” Phys. Rev. Lett. 116 (Jun, 2016) 251803. https://link.aps.org/doi/10.1103/PhysRevLett.116.251803.
  * [31] A. Belyaev, N. D. Christensen, and A. Pukhov, “CalcHEP 3.4 for collider physics within and beyond the standard model,” Computer Physics Communications 184 no. 7, (Jul, 2013) 1729–1769. https://doi.org/10.1016%2Fj.cpc.2013.01.014.
  * [32] M. I. Vysotsky and E. V. Zhemchugov, “Equivalent photons in proton and ion–ion collisions at the LHC,” Usp. Fiz. Nauk 189 no. 9, (2019) 975–984.
  * [33] A. Pich, “Effective field theory,” 1998.
  * [34] J. Liu, Y. Luo, and M. Song, “Investigation of the concurrent effects of ALP-photon and ALP-electron couplings in collider and beam dump searches,” Journal of High Energy Physics 2023 no. 9, (Sep, 2023) . https://doi.org/10.1007%2Fjhep09%282023%29104.
  * [35] NA62 Collaboration, E. C. Gil et al., “Search for $\pi^{0}$ decays to invisible particles,” Journal of High Energy Physics 2021 no. 2, (Feb, 2021) . https://doi.org/10.1007%2Fjhep02%282021%29201.
  * [36] A. W. M. Guerrera and S. Rigolin, “Revisiting $k\rightarrow\pi a$ decays,” 2021\.
  * [37] Belle II Collaboration, F. Abudinén et al., “Search for axionlike particles produced in ${e}^{+}{e}^{-}$ collisions at belle ii,” Phys. Rev. Lett. 125 (Oct, 2020) 161806. https://link.aps.org/doi/10.1103/PhysRevLett.125.161806.
  * [38] The OPAL Collaboration, G. Abbiendi et al., “Multi-photon production in ee collisions at $\sqrt{s}=$181-209 gev,” The European Physical Journal C - Particles and Fields 26 (March, 2003) . https://doi.org/10.1140/epjc/s2002-01074-5.
  * [39] NA64 Collaboration Collaboration, D. Banerjee et al., “Search for axionlike and scalar particles with the na64 experiment,” Phys. Rev. Lett. 125 (Aug, 2020) 081801. https://link.aps.org/doi/10.1103/PhysRevLett.125.081801.
  * [40] J. D. Bjorken, S. Ecklund, W. R. Nelson, A. Abashian, C. Church, B. Lu, L. W. Mo, T. A. Nunamaker, and P. Rassmann, “Search for neutral metastable penetrating particles produced in the slac beam dump,” Phys. Rev. D 38 (Dec, 1988) 3375–3386. https://link.aps.org/doi/10.1103/PhysRevD.38.3375.
  * [41] B. Döbrich, J. Jaeckel, and T. Spadaro, “Erratum to: Light in the beam dump. axion-like particle production from decay photons in proton beam-dumps,” author = Döbrich, B. and Jaeckel, J. and Spadaro, T, 2020 (Oct, 2020) . https://doi.org/10.1007/JHEP10(2020)046.
  * [42] J. L. Feng, I. Galon, F. Kling, and S. Trojanowski, “Axionlike particles at faser: The lhc as a photon beam dump,” Phys. Rev. D 98 (Sep, 2018) 055021. https://link.aps.org/doi/10.1103/PhysRevD.98.055021.
  * [43] M. Dolan, T. Ferber, and C. e. a. Hearty, “Revised constraints and belle ii sensitivity for visible and invisible axion-like particles,” Journal of High Energy Physics 2017 (Dec, 2017) . https://doi.org/10.1007/JHEP12(2017)094.


11institutetext: Veer Surendra Sai University of Technology, Burla, Odisha
768018, INDIA 11email: (debasis.dwibedy<EMAIL_ADDRESS>
# New Competitive Semi-online Scheduling Algorithms for Small Number of
Identical Machines††thanks: Supported by Veer Surendra Sai University of
Technology, Burla, Odisha, 768018 INDIA.

Debasis Dwibedy  Rakesh Mohanty

###### Abstract

Design and analysis of constant competitive deterministic semi-online
algorithms for the multi-processor scheduling problem with small number of
identical machines have gained significant research interest in the last two
decades. In the semi-online scheduling problem for makespan minimization, we
are given a sequence of independent jobs one by one in order and upon arrival,
each job must be allocated to a machine with prior knowledge of some Extra
Piece of Information (EPI) about the future jobs. Researchers have designed
multiple variants of semi-online scheduling algorithms with constant
competitive ratios by considering one or more EPI. In this paper, we propose
four new variants of competitive deterministic semi-online algorithms for
smaller number of identical machines by considering two EPI such as $Decr$ and
$Sum$. We obtain improved upper bound and lower bound results on the
competitive ratio for our proposed algorithms, which are comparable to the
best known results in the literature. In two identical machines setting with
known $Sum$, we show a tight bound of $1.33$ on the competitive ratio by
considering a sequence of equal size jobs. In the same setting we achieve a
lower bound of $1.04$ and an upper bound of $1.16$ by considering $Sum$ and a
sequence of jobs arriving in order of decreasing sizes. For three identical
machines setting with known $Decr$ and $Sum$, we show a lower bound of $1.11$
on the competitive ratio. In this setting, we obtain an upper bound of $1.5$
for scheduling a sequence of equal size jobs and achieves an upper bound of
$1.2$ by considering a sequence of decreasing size jobs. Further we develop an
improved competitive algorithm with an upper bound of $1.11$ on the
competitive ratio.

###### Keywords:

Competitive Analysis Deterministic Semi-online Algorithms Identical Machines
Makespan Non-preemptive Semi-online Scheduling.

##  1 Introduction

The classical scheduling problem requires irrevocable scheduling of a list of
$n$ jobs on a set of $m(\geq 2)$ identical parallel machines with an objective
to minimize the completion time of all jobs i.e., makespan. This problem with
$m=2$ was proved to be NP-complete in [1] by a polynomial time reduction from
the well-known partition problem. The above hardness result was achieved by
using the concept of splitting a weighted set of items into two subsets of
equal weights.

Offline Scheduling. When the list of jobs to be scheduled is given at the
outset, the problem is called offline. The algorithm designed for the offline
$m$ machines scheduling problem is known as an offline algorithm. Out of all
offline algorithms, the one that achieves the smallest makespan is called the
optimal offline algorithm $OPT$. Longest Processing Time (LPT) [2] is one of
the primitive offline algorithms for the $m$ machine offline scheduling
problem. Algorithm LPT first sorts a given list of jobs in order of non-
increasing sizes, then follows the order to schedule the jobs one by one on
the machine that has the current minimum load. In worst case, algorithm LPT
achieves a makespan which is $1.16$ times of the optimum makespan.

Online and Semi-online Scheduling. In practice jobs are not known at the
outset, rather they are revealed one by one in order. A job $J_{i}$ must be
scheduled on a machine $M_{j}$ as soon as it is received with no clue on the
successive jobs $J_{i+1}$, where $1\leq i<n$. Such a scheduling problem is
known as online scheduling. A recent survey on the variants of the online
scheduling problem can be found in [3]. In online scheduling, when some Extra
Piece of Information (EPI) about future jobs is given a priori, the problem
becomes semi-online [4-5].
In this article, we are interested in semi-online scheduling of a sequence of
$n$ independent jobs on $m$ identical parallel machines settings, where we
know jobs arrive in order of non-increasing sizes and the value of the total
sum of their sizes. We are constrained to schedule each job irrevocably and
non-preemptively. Our objective is to minimize the makespan.

Practical Significance. Semi-online scheduling problem often arises in many
practical applications such as resource management in production systems,
interactive parallel computations, robot navigation, distributed data
processing and clients requests management by the network servers. In a
client-server model, let us consider a video download application, which
allows a client to download videos from the internet. When a client places a
request to download a particular video file, the application knows a priori
the total size of the requested file, associated data packets and their order
of delivery. These information, if given to the network routers, would
certainly help to optimize the congestion in the networks and to minimize the
delivery time at the destination. Efficient semi-online scheduling algorithms
can be extremely useful in minimizing the bandwidth consumption at any link of
a network, while routing the data packets across several networks. In certain
applications, where a limited number of resources are used, the design and
analysis of efficient semi-online algorithms are of great theoretical and
research significance.

Performance Measure. The efficiency of a semi-online algorithm $ALG$ is
evaluated by competitive analysis method [6]. In this method a competitive
ratio is computed based on the cost obtained by the semi-online algorithm
$ALG$ and the cost obtained by its optimal offline counterpart. Let us
consider an input instance $\sigma=\langle J_{1},J_{2},\ldots,J_{n}\rangle$,
consisting of $n$ items of a cost minimization problem $X$. Let $C_{ALG}$ and
$C_{OPT}$ be the costs incurred by $ALG$ and $OPT$ respectively. The
competitive ratio can be defined as the smallest $b(\geq 1)$ for which
$\frac{C_{ALG}}{C_{OPT}}\leq b$ for any permutations in the arrival order of
the items in $\sigma$.

Research Motivation. The ongoing research in semi-online scheduling has been
predominantly influenced by two factors. The first one accounts for the
improvement in the best known competitive bounds and the second one inclines
towards the exploration of practically significant new EPI. The EPI is
completely application dependent. The EPI that helps in achieving the current
best bound for a particular setting might not be available in all real world
online scheduling applications. Therefore analysis of semi-online algorithms
based on unexplored EPI or using a combination of multiple EPI to achieve
better competitive analysis results is a major research challenge. According
to our knowledge, a maiden work [7] has been reported till date in the
literature on semi-online scheduling with known $Decr$ and $Sum$. The existing
literature lacks an extensive study on semi-online scheduling of equal size
jobs on two and three identical machines settings. In our study we propose
four new variants of constant competitive deterministic semi-online scheduling
algorithms for smaller number of machines with two EPI.

Our Contribution. We investigate the semi-online scheduling problem with known
$Decr$ and $Sum$. We study the non-preemptive variants for makespan
minimization in two and three identical parallel machines settings. Two
natural input job sequence patterns are explored based on the information on
$Decr$. The first pattern is equivalent to a sequence of equal size jobs and
the second one resembles to a sequence of decreasing size jobs. We prove the
lower bound results for the studied settings by characterizing the input job
sequences. For two identical machines setting, a lower bound of $1.33$ on the
competitive ratio is shown by considering both input patterns, and a lower
bound $1.04$ is proved by considering only the second input pattern. We
propose a deterministic semi-online algorithm named 2DS, which achieves an
upper bound of $1.33$ on the competitive ratio for both input patterns by
maintaining a near equal load on each machine. We improve the upper bound to
$1.16$ by considering only the second input pattern and proposing a
deterministic semi-online algorithm named, Improved 2DS (I2DS). Algorithm I2DS
always keeps a machine with heavy load as compare to the other one. The
imbalance in loads between the machines leads to an improved competitive
bound. However, algorithm 2DS remains best possible for the first input
pattern as the load imbalance principle does not help to improve the upper
bound. For three identical machines setting with known $Decr$ and $Sum$, we
show a lower bound of $1.11$ on the competitive ratio, which holds for both
input patterns. In this setting, we propose a semi-online algorithm named 3DS,
which achieves an upper bound $1.5$ in scheduling equal size jobs.
Furthermore, we prove that algorithm 3DS is $1.2$ competitive with known $Sum$
and $Decr$, where jobs arrive in order of decreasing sizes. Finally we improve
the upper bound $1.2$ on the competitive ratio to $1.11$ by considering only
the second input pattern and proposing the algorithm Improved 3DS (I3DS). Our
proposed algorithms are efficient as they hold the defined bounds for all
input instances of the studied settings.

Organization. The remaining sections of this paper is organized as follows.
Section 2 discusses some basic terminologies and seminal contributions related
to our study. Section 3 presents our proposed algorithms and associated
competitive analysis results for non-preemptive semi-online scheduling for
makespan minimization in two and three identical parallel machines settings
with EPI $Decr$ and $Sum$. Finally section 4 provides the concluding remarks
and highlights the future scope of our work.

##  2 Preliminaries and State-of-the-art Results

We present the basic terminologies, notations and definitions related to our
work in Table 1.

Table 1: Basic Terminologies Notations and Definitions Terminology | Notations |  Definitions
---|---|---
Job | $J_{i}$ |  An executable unit, where $1\leq i\leq n$.
Machine | $M_{j}$ |  A processing unit, where $1\leq j\leq m$.
Processing Time or Size | $p_{i}$ |  Time taken by a job $J_{i}$ to execute on a machine $M_{j}$.
Completion Time | $c_{i}$ |  The time at which a job $J_{i}$ finishes its execution
Load | $l_{j}$ |  Sum of sizes of the jobs that have been assigned to a machine $M_{j}$.
Makespan | $C_{max}$ |  $\max\\{l_{j}|1\leq j\leq m\\}$.
Total sum of sizes of all jobs | Sum |  $\sum_{i=1}^{n}{p_{i}}$.
Largest size | Max or $p_{max}$ |  $\max\\{p_{i}|1\leq i\leq n\\}$.
Non-increasing job sizes | Decr |  $p_{i+1}\leq p_{i}$, for $i\geq 1$.
Tightly grouped processing time | TGRP |  $p_{i}\in[a,b]$, where $a,b>0$.
Optimum Makespan | $C_{OPT}$ |  $\max\\{\frac{1}{m}\cdot\sum_{i=1}^{n}{p_{i}},\hskip 5.69046ptp_{max}\\}$.

###  2.1 State-of-the-art Results

In a semi-online variant of the online scheduling problem, besides the current
job some EPI on the future jobs is also given. The consideration of different
EPI leads to different semi-online variants. The ongoing research in semi-
online scheduling focuses on the improvement in the existing best competitive
bounds for each of the variants. We particularly concentrate on makespan
minimization in two and three identical parallel machines settings. We present
an overview of the important competitive analysis results as follows.
Two Identical Machines. Kellerer et al. [4] studied a semi-online version of
the well-known partition problem, which is equivalent to semi-online
scheduling on two identical machines with known $Sum$. By considering $Sum=2$,
they proposed a $1.33$ competitive semi-online algorithm. The algorithm
schedules a sequence of jobs in such a manner that the maximum load incurred
on a machine is at most $\frac{2}{3}\cdot Sum$. Seiden et al. [5] claimed that
algorithm LPT with an upper bound of $1.16$ on the competitive ratio is best
possible for semi-online scheduling with known $Decr$.
Many researchers investigated the semi-online scheduling problem by
considering multiple EPI and significantly improved the existing best
competitive bounds. Angelelli [8] introduced a pair-wise combination of two
EPI such as $Sum$ and lower bound on job’s processing time. A tight bound of
$1.33$ on the competitive ratio was achieved. Tan and He [7] considered $Sum$
and $Max$ as the known EPI and obtained a tight bound of $1.2$ on the
competitive ratio.
They also considered $Sum$ and $Decr$ as the known EPI to achieve a lower
bound of $1.11$ on the competitive ratio. To prove their claim they considered
two specific instances $\sigma_{1}$, $\sigma_{2}$ with six jobs in each
instance and $Sum=18$, where $\sigma_{1}$ considers $p_{1}=p_{2}=4$,
$p_{3}=p_{4}=p_{5}=p_{6}=2.5$ and $\sigma_{2}$ considers $p_{1}=p_{2}=4$,
$p_{3}=p_{4}=p_{5}=3$ and $p_{6}=1$. Although the achieved bound holds for the
considered instances, it does not help to trace out all instances those
account for the lower bound result. A generalized lower bound of the problem
as a factor of the known $Sum$ is required to capture all such instances. They
proposed the algorithm SD and achieved a matching upper bound on the
competitive ratio by considering $Sum=18$. Algorithm SD schedules the first
job $J_{1}$ on machine $M_{1}$. The second job $J_{2}$ is assigned to $M_{1}$
and the remaining jobs are scheduled on $M_{2}$ if
$l_{1}+p_{2}\leq\frac{5}{9}\cdot Sum$. If $\frac{7}{18}\cdot Sum\leq
l_{1}+p_{2}<\frac{4}{9}\cdot Sum$ or $l_{1}+p_{2}>\frac{5}{9}\cdot Sum$, then
$J_{2}$ is scheduled on $M_{2}$ and the remaining jobs $J_{i}$, where $i\geq
3$ are scheduled based on the following two stopping criteria. Criterion 1: If
$l_{j}+p_{i}\leq\frac{5}{9}\cdot Sum$, then $J_{i}$ is assigned to such a
$M_{j}$ and the remaining jobs are scheduled on the other machine, where
$j\in\\{1,2\\}$. Criterion 2: If $l_{j}+p_{i}>\frac{5}{9}\cdot Sum$, $\forall
j$, then $J_{i}$ is scheduled on the $M_{j}$ for which the current load
$l_{j}=\min\\{l_{1},l_{2}\\}$ and the remaining jobs are assigned to the other
machine. At any moment if the loads $l_{1}=l_{2}$, then $J_{i}$ is assigned to
$M_{2}$. Although algorithm SD improves the existing competitive bound, it is
does not cover all instances of the problem. For example, let us consider a
sequence of three equal size jobs with $p_{1}=p_{2}=p_{3}=1$ and another
sequence of three decreasing size jobs with $p_{1}=5$, $p_{2}=4$ and
$p_{3}=3$. For the first and the second sequence any deterministic semi-online
algorithm has a competitive ratio of at least $1.33$ and $1.16$ respectively.
Therefore the semi-online scheduling problem on two identical machines with
known $Decr$ and $Sum$ requires further investigations in the design of
optimal semi-online algorithms for $n\geq 3$.
Angelelli [9] improved the $1.33$ tight bound to $1.2$ by considering $Sum$
and upper bound ($ub$) on job’s processing time, where $ub\in(0.5,0.6)$. For
$ub\in(0.75,1)$, Angelelli achieved a tight bound of $1+\frac{ub}{3}$ on the
competitive ratio. In [10], Angelelli considered $Sum$ and various intervals
of the upper bound on job’s processing time as the known EPI. For
$ub\in[\frac{1}{b},\frac{2(b+1)}{b(2b+1)}]$ a tight bound $1+\frac{1}{2b+1}$
and for $ub\in(\frac{2b-1}{2b(b-1)},\frac{1}{b-1}]$ a tight bound
$(\frac{b-1}{3})ub+0.66(\frac{b+1}{b})$ were achieved on the competitive
ratio, where $b\geq 2$. Cao et al. [11] obtained a tight bound of $1.2$ by
considering $Max$ and the value of the optimum makespan as the known EPI. Cao
and Wan [12] considered the known information on $Decr$ and $TGRP(1,r)$ and
proved a tight bound of $1.16$ on the competitive ratio. We now present a
summary of the best known competitive bounds in Table 2.

Table 2: Best Known Competitive Bounds for Two Identical Machines EPI | Lower Bound | Upper Bound
---|---|---
$Sum$ | $1.33$ | $1.33$
$Decr$ | $1.16$ | $1.16$
$Sum,TGRP(lb)$ | $1.33$ | $1.33$
$Sum,Max$ | $1.2$ | $1.2$
$Sum,Decr$ | $1.11$ | $1.11$
$Sum,TGRP(ub)$ | $1.2$ | $1.2$
$Max,Opt$ | $1.2$ | $1.2$
$Decr,TGRP(1,r)$ | $1.16$ | $1.16$

Three Identical Machines. He and Dosa [13] initiated a study on semi-online
scheduling in three identical machines settings. They considered $TGRP(r)$ as
the known EPI and achieved an upper bound $1.5$ on the competitive ratio for
$r\in(2,2.5)$. Furthermore, they obtained an upper bound $\frac{4r+2}{2r+3}$
for $r\in(2.5,3)$. Angelelli [14] achieved a lower bound $1.392$ and an upper
bound $1.421$ on the competitive ratio by considering known $Sum$.
Hua et al. [15] introduced multiple EPI in semi-online scheduling on three
identical machines settings. They considered $Sum$ and $Max$ as the known EPI
and obtained a lower bound $1.33$ and an upper bound $1.4$ on the competitive
ratio. For this setting, Wu et al. [16] improved the lower bound of Hua e al.
[15] to achieve a tight bound $1.33$ on the competitive ratio.
By considering only known $Decr$, Cheng et al. [17] achieved a tight bound
$1.18$, which is the best competitive bound known till date in semi-online
scheduling on three identical machines settings. We present a summary of the
best known competitive bounds in Table 3.

Table 3: Best Known Competitive Bounds for Three Identical Machines EPI | Lower Bound | Upper Bound
---|---|---
$TGRP(r)$ | — | $1.5$
$Sum$ | $1.392$ | $1.421$
$Sum,Max$ | $1.33$ | $1.33$
$Decr$ | $1.18$ | $1.18$

The current state-of-the-art results on the competitive ratio for other
variants of the semi-online scheduling problem can be found in a recent survey
of Epstein [18].

##  3 Our Results on Semi-online Scheduling with Known Decr and Sum

In the semi-online scheduling problem with $Decr$ and $Sum$, we know that
$p_{i}\geq p_{i+1}$ for $1\leq i<n$ and we are given the value of
$\sum_{i=1}^{n}{p_{i}}$ at the outset. For this problem, we analyze the
competitiveness of any deterministic semi-online algorithm ALG by considering
two practically significant input job sequence patterns, i.e., $I_{1}$ and
$I_{2}$ based on the known $Decr$. As we know $Decr$ means, $n$ jobs arriving
such that $p_{1}\geq p_{2}\geq p_{3}\geq\ldots\geq p_{n}$. We now can
distinguish the input patterns $I_{1}$ and $I_{2}$ as follows.

$I_{1}$ : $p_{1}=p_{2}=p_{3}=\ldots=p_{n}$, i.e., $p_{i+1}=p_{i}$, $\forall
i$.
$I_{2}$ : $p_{1}>p_{2}>p_{3}>\ldots>p_{n}$, i.e., $p_{i+1}<p_{i}$, $\forall
i$.

The input pattern $I_{1}$ often arises in a client server environment, where
for an instance a client requests only for the static web pages or several
clients request for the home page of a website on the fly. The web server
processes such requests by taking almost equal time for each of them. The
input pattern $I_{2}$ is natural in the context of product manufacturing and
parallel computations, where a larger size task is splitted into several
smaller size jobs and the jobs are given one by one in order of decreasing
sizes to a central scheduler for the assignment of scarce resources. The
objective is to yield a product or a result within a minimum time. Any of the
other possibilities on the $Decr$ must be a subset of the union of $I_{1}$ and
$I_{2}$. In fact, in $I_{1}$, the information on $Decr$ is meaningless. The
problem can also be interpreted as semi-online scheduling of a sequence of
equal size jobs with known $Sum$. While the problem with $I_{2}$ can be
considered as semi-online scheduling of a sequence of decreasing size jobs
with known $Sum$. We study the problem with respect to $I_{1}$ and $I_{2}$ in
two and three identical parallel machines settings as follows.

###  3.1 Two Identical Parallel Machines ($P_{2}$)

When the objective is to minimize the makespan $C_{max}$, we denote the
problem as $P_{2}|Decr,Sum|C_{max}$. Let $C_{ALG}$ and $C_{OPT}$ be the
makespans incurred by any deterministic semi-online algorithm $ALG$ and the
optimal offline algorithm $OPT$ respectively. The lower bound on the
competitive ratio of the problem $P_{2}|Decr,Sum|C_{max}$ represents the
smallest $b(\geq 1)$ such that $\frac{C_{ALG}}{C_{OPT}}\geq b$ for all
instances of the problem. We show the lower bound results of the problem as
follows.

####  3.1.1 Lower Bound Results

###### Theorem 3.1

Any deterministic semi-online algorithm $ALG$ for the problem
$P_{2}|Decr,Sum|C_{max}$ has a competitive ratio of at least $1.33$.

###### Proof

We prove the theorem by adversary method. Let $Sum=k(>6)$ is known and we are
given a sequence of three jobs $J_{1}$, $J_{2}$ and $J_{3}$, where
$p_{1}=\frac{k+3}{3}$ and $p_{2}+p_{3}=\frac{2k-3}{3}$. We consider the
following two cases based on the assignment of initial two jobs.

Case 1. $J_{1}$ and $J_{2}$ are assigned to the same machine.
Let us consider $p_{2}=p_{3}=\frac{2k-3}{6}$. By assigning $J_{3}$ on the
other machine, we have $C_{ALG}\geq\frac{4k+3}{6}$, while
$C_{OPT}=\frac{k}{2}$. Therefore,
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{4}{3}+\frac{1}{k}=1.33+\frac{1}{k}$ (1)

Case 2. $J_{1}$ and $J_{2}$ are assigned to two different machines.
Let us consider $p_{2}=\frac{k}{3}$ and $p_{3}=\frac{k-3}{3}$.
Sub-case 2.1. $J_{3}$ is assigned to the machine, where job $J_{1}$ has been
assigned. We now have $C_{ALG}\geq\frac{2k}{3}$, while $C_{OPT}=\frac{k}{2}$.
This implies
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{4}{3}=1.33$ (2)

Sub-case 2.2. $J_{3}$ is assigned to the machine, where job $J_{2}$ has been
assigned. We now have $C_{ALG}\geq\frac{2k-3}{3}$, while
$C_{OPT}=\frac{k}{2}$. This implies
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{4}{3}-\frac{2}{k}\rightarrow 1.33$ as
$k\rightarrow\infty$ (3)

By Eqs. (1), (2) and (3), we can conclude that there exists an instance of the
problem $P_{2}|Decr,Sum|C_{max}$ such that $\frac{C_{ALG}}{C_{OPT}}\geq 1.33$.
$\Box$

It can be observed that in the proof of Theorem 1, we have considered the
critical instances based on the input patterns $I_{1}$ and $I_{2}$ with
minimum number of jobs to show all possible assignments. We have obtained the
lower bound of the problem by considering the minimal makespan, which was
incurred by the best assignment policy. The result reflects that the largest
value of $k$ leads to a generalized lower bound of the problem on the
competitive ratio. However, we can further minimize the lower bound by
considering only $I_{2}$ and the least value of $k$ i.e., $k=7$. We now
present the lower bound of the problem by considering only $I_{2}$ as follows.

###### Theorem 3.2

Any deterministic semi-online algorithm $ALG$ for the problem
$P_{2}|Decr,Sum|C_{max}$ with $I_{2}$ has a competitive ratio of at least
$1.04$.

###### Proof

To prove our claim let us consider $Sum=k(\geq 7)$ and a sequence of three
jobs $J_{1}$, $J_{2}$ and $J_{3}$, where $p_{1}=\frac{12k}{25}$ and
$p_{2}+p_{3}=\frac{13k}{25}$. Let us consider the best assignment policy and
the critical instance as follows. The jobs $J_{1}$ and $J_{2}$ are scheduled
on two different machines and the job $J_{3}$ is assigned to the machine where
$J_{2}$ has already been assigned. For $p_{2}=\frac{7k}{25}$ and
$p_{3}=\frac{6k}{25}$, we have $C_{ALG}\geq\frac{13k}{25}$, while
$C_{OPT}=\frac{k}{2}$. This implies,
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{26}{25}=1.04$. $\Box$

####  3.1.2 Algorithm 2DS

In the problem $P_{2}|Decr,Sum|C_{max}$, we know larger size jobs arrive
upfront in the sequence and the total sum of sizes of all jobs beforehand. We
aim to schedule the jobs in such a manner that the load of one of the machines
is always at most $\frac{1}{2}\cdot Sum$. We propose a deterministic semi-
online algorithm named 2DS for the problem by considering the input patterns
$I_{1}$ and $I_{2}$. Let $C_{2DS}$ be the makespan incurred by algorithm 2DS.
The algorithm works as follows.

Algorithm 1 2DS

Initially, $l_{1}=l_{2}=0$, $Sum=\sum_{i=1}^{n}{p_{i}}$, and $p_{i+1}\leq
p_{i}$ for $1\leq i<n$

WHILE a new job $J_{i}$ is given with known $Decr$ and $Sum$ DO

BEGIN

IF $l_{1}+p_{i}\leq\frac{1}{2}\cdot Sum$

THEN assign job $J_{i}$ to machine $M_{1}$

UPDATE $l_{1}=l_{1}+p_{i}$

ELSE

assign job $J_{i}$ to machine $M_{2}$

UPDATE $l_{2}=l_{2}+p_{i}$

$i=i+1$

END

Return $C_{2DS}=\max\\{l_{1},l_{2}\\}$

The upper bound on the competitive ratio of our proposed algorithm $2DS$ for
the problem $P_{2}|Decr,Sum|C_{max}$ represents the smallest $b(\geq 1)$ such
that $\frac{C_{2DS}}{C_{OPT}}\leq b$ for all job sequences of the problem. We
now show the upper bound results of algorithm 2DS with respect to $I_{1}$ and
$I_{2}$ by Theorem 3 and Theorem 4 respectively as follows.

####  3.1.3 Upper Bound Result

###### Theorem 3.3

For all job sequences of the problem $P_{2}|Sum|C_{max}$ with $I_{1}$, where
$p_{i}=x$, $x\geq 1$, $n\geq 3$ and $1\leq i\leq n$, we have
$\frac{C_{2DS}}{C_{OPT}}\leq 1.33$.

###### Proof

We consider the following two cases based on the number of jobs $n$.
Case 1. If $n$ is even.
Let us consider $n=2a$ for any $a\geq 2$. As we know that $p_{i}=x$ for $1\leq
i\leq n$, we have $Sum=2ax$, implies, $C_{OPT}=ax$. As $n$ is even, algorithm
2DS assigns the initial $\frac{n}{2}=a$ jobs to machine $M_{1}$ and incurs
$l_{1}=ax$. The remaining $a$ jobs are scheduled on machine $M_{2}$ to obtain
$l_{2}=ax$. We now have $C_{2DS}=ax$, this implies,
$\frac{C_{2DS}}{C_{OPT}}=1$.
Case 2. If $n$ is odd.
Let us consider $n=2a+1$ for any $a\geq 1$. We have $Sum=(2a+1)x$, implies,
$C_{OPT}=\frac{(2a+1)x}{2}$. Algorithm 2DS assigns the initial $a$ jobs to
machine $M_{1}$ and incurs load $l_{1}=ax<\frac{(2a+1)x}{2}$. The remaining
$a+1$ jobs are scheduled on machine $M_{2}$ to obtain a load $l_{2}=(a+1)x$.
As $l_{2}>l_{1}$, we now have $C_{2DS}\leq(a+1)x$. Therefore, we have
$\frac{C_{2DS}}{C_{OPT}}\leq\frac{2x(a+1)}{x(2a+1)}\leq\frac{2a+2}{2a+1}\leq\frac{4}{3}=1.33$,
for $n\geq 3$ and $a\geq 1$. $\Box$

###### Theorem 3.4

For all job sequences of the problem $P_{2}|Decr,Sum|C_{max}$ with $I_{2}$, we
have $\frac{C_{2DS}}{C_{OPT}}\leq 1.33$.

###### Proof

We prove the theorem by critical case analysis method. Let $p_{max}$ be the
largest job, we have $p_{max}=p_{1}$. Let us consider the following two cases
based on the size of the first job.
Case 1. If $p_{1}>\frac{1}{2}\cdot Sum$.
Then $\sum_{i=2}^{n}{p_{i}}<\frac{1}{2}\cdot Sum$, implies $C_{OPT}=p_{1}$.
Algorithm 2DS assigns $J_{1}$ to machine $M_{2}$ and incurs a load
$l_{2}=p_{1}$. The remaining jobs are assigned to machine $M_{1}$, which
incurs a load $l_{1}<\frac{1}{2}\cdot Sum<p_{1}$. Implies,
$C_{2DS}=l_{2}=p_{1}$. Therefore, $\frac{C_{2DS}}{C_{OPT}}=1$.
Case 2. If $p_{1}\leq\frac{1}{2}\cdot Sum$.
Sub-case 2.1. If $p_{1}=\frac{1}{2}\cdot Sum$.
Then, $\sum_{i=2}^{n}{p_{i}}=\frac{1}{2}\cdot Sum$. Algorithm 2DS assigns
$J_{1}$ to machine $M_{1}$ and incurs a load $l_{1}=\frac{1}{2}\cdot Sum$. The
remaining jobs are scheduled on machine $M_{2}$, which incurs a load
$l_{2}=\frac{1}{2}\cdot Sum$. Thus, $C_{2DS}=l_{1}=l_{2}=\frac{1}{2}\cdot
Sum$, while $C_{OPT}=\frac{1}{2}\cdot Sum$. Therefore,
$\frac{C_{2DS}}{C_{OPT}}=1$.

Sub-case 2.2. If $p_{1}<\frac{1}{2}\cdot Sum$.
Then algorithm 2DS schedules $J_{1}$ on machine $M_{1}$. Here, the following
two cases arise.
Sub-sub-case 2.2.1. No other job is assigned to machine $M_{1}$.
Remaining jobs are scheduled on machine $M_{2}$. We now have two
possibilities.
Possibility 1. If $\sum_{i=2}^{n-1}{p_{i}}>\frac{1}{2}\cdot Sum$.
Then $p_{1}+p_{n}<\frac{1}{2}\cdot Sum$, implies there exists a job $J_{n}$
which can be assigned to machine $M_{1}$, which is a contradiction to the Sub-
sub-case 2.2.1. Hence, Possibility 1 does not occur.
Possibility 2. If $\sum_{i=2}^{n-1}{p_{i}}\leq\frac{1}{2}\cdot Sum$.
Then before the scheduling of $J_{n}$, load $l_{2}\leq\frac{1}{2}\cdot Sum$.
However, after scheduling of $j_{n}$, we have the updated load
$l_{2}=l_{2}+p_{n}>\frac{1}{2}\cdot Sum$ as $l_{1}<\frac{1}{2}\cdot Sum$. As
$l_{1}+p_{n}>\frac{1}{2}\cdot Sum$, without loss of generality, we can bound
the value of $p_{n}$ as $2\leq p_{n}\leq p_{max}-2$ for $n\geq 3$. We consider
the following critical instance of the problem to show the largest competitive
ratio. Let us consider an instance with three jobs $J_{1}$, $J_{2}$ and
$J_{3}$, where $p_{1}=p_{max}$, $p_{2}=p_{max}-1$ and $p_{3}=p_{max}-2$.
Algorithm 2DS now schedules job $J_{1}$ on machine $M_{1}$ and assigns
remaining jobs to machine $M_{2}$ to incur $l_{1}=p_{max}$ and
$l_{2}=2p_{max}-3$. As $l_{2}>l_{1}$, we now have $C_{2DS}\leq 2p_{max}-3$,
while $C_{OPT}\geq\frac{3}{2}(p_{max}-1)$. Therefore, we have

$\frac{C_{2DS}}{C_{OPT}}\leq\frac{2(2p_{max}-3)}{3p_{max}-3}\leq\frac{4p_{max}-6}{3p_{max}-3}\leq\frac{4}{3}$,
for $p_{max}\geq 3$ (4)

Sub-sub-case 2.2.2. At least one job other than $J_{1}$ is assigned to machine
$M_{1}$.
Let $J_{k}$ be the latest job, which has been assigned to machine $M_{1}$ and
let $l^{{}^{\prime}}_{1}$ be the load of $M_{1}$ just before the scheduling of
$J_{k}$. We now have

$l^{{}^{\prime}}_{1}+p_{k}\leq\frac{1}{2}\cdot Sum>l_{1}$ (5)

If $J_{k}=J_{n}$, then $l^{{}^{\prime}}_{1}+p_{k}=\frac{1}{2}\cdot Sum$ or
$l^{{}^{\prime}}_{1}+p_{k}<\frac{1}{2}\cdot Sum$. If
$l^{{}^{\prime}}_{1}+p_{k}=\frac{1}{2}\cdot Sum$, then
$C_{2DS}=\frac{1}{2}\cdot Sum$, while $C_{OPT}=\frac{1}{2}\cdot Sum$, implies,
$\frac{C_{2DS}}{C_{OPT}}=1$.

If $l^{{}^{\prime}}_{1}+p_{k}<\frac{1}{2}\cdot Sum$, then let
$l^{{}^{\prime}}_{2}$ be the load of machine $M_{2}$ at this point of time. By
Eq. (5), it is clear that $l^{{}^{\prime}}_{2}<l_{2}$. Therefore, Eq. (4)
holds for this case as well. We now can conclude that
$\frac{C_{2DS}}{C_{OPT}}\leq\frac{4}{3}=1.33$. $\Box$

For the problem $P_{2}|Decr,Sum|C_{max}$ with $I_{1}$, the algorithm 2DS is
best possible in the sense that no semi-online algorithm can overcome the
critical instance with three jobs, where $p_{1}=p_{2}=p_{3}=1$ to obtain a
better competitive ratio than $1.33$. However, we improve the upper bound
$1.33$ on the competitive ratio to $1.16$ for the problem with $I_{2}$, i.e.,
$p_{i+1}<p_{i}$, $\forall i$ by proposing a deterministic semi-online
algorithm named Improved 2DS.

####  3.1.4 Algorithm Improved 2DS (I2DS)

schedules an incoming job $J_{i}$ on machine $M_{1}$ as long as the load
$l_{1}+p_{i}\leq\frac{7}{12}\cdot Sum$. A job $J_{x}$, which incurs a load
$p_{x}$ on machine $M_{1}$ such that $l_{1}+p_{x}>\frac{7}{12}\cdot Sum$ is
assigned to machine $M_{2}$. All such $J_{x}$ are scheduled on machine
$M_{2}$. The idea is to maintain loads on the machines $M_{1}$ and $M_{2}$
such that $l_{1}\leq\frac{7}{12}\cdot Sum$ and $\frac{5}{12}\leq
l_{2}<\frac{7}{12}\cdot Sum$. For a better understanding of the competitive
analysis of algorithm I2DS, let us normalize the processing times of the jobs
in such a manner that $Sum=12$.

Algorithm 2 I2DS

Initially, $l_{1}=l_{2}=0$, $Sum=\sum_{i=1}^{n}{p_{i}}$, and $p_{i+1}<p_{i}$
for $1\leq i<n$

WHILE a new job $J_{i}$ is given with known $Decr$ and $Sum$ DO

BEGIN

IF $l_{1}+p_{i}\leq\frac{7}{12}\cdot Sum$

THEN assign job $J_{i}$ to machine $M_{1}$

UPDATE $l_{1}=l_{1}+p_{i}$

ELSE

assign job $J_{i}$ to machine $M_{2}$

UPDATE $l_{2}=l_{2}+p_{i}$

$i=i+1$

END

Return $C_{I2DS}=\max\\{l_{1},l_{2}\\}$

####  3.1.5 Upper Bound Result

###### Theorem 3.5

For all job sequences of the problem $P_{2}|Decr,Sum|C_{max}$ with $I_{2}$,
where $n\geq 3$ and $p_{n}\geq 3$, we have $\frac{C_{I2DS}}{C_{OPT}}\leq
1.16$.

###### Proof

When no job is assigned to any of the machines, we have loads $l_{1}=l_{2}=0$.
It is given that $Sum=12$. This implies,
$C_{OPT}\geq 6$ (6) We consider the following two critical cases based on the
size of the first job $J_{1}$.
Case 1. If $p_{1}>\frac{7}{12}\cdot Sum$.
Let us consider $A=\sum_{i=2}^{n}{p_{i}}$. It is clear that
$A<\frac{5}{12}\cdot Sum$. Algorithm I2DS now schedules job $J_{1}$ on machine
$M_{2}$ and assigns the remaining jobs $J_{i}$ to machine $M_{1}$, where
$2\leq i\leq n$. This implies, $l_{2}=p_{1}>\frac{7}{12}\cdot Sum$ and
$l_{1}=A<\frac{5}{12}\cdot Sum$. As $l_{2}>l_{1}$, we now have
$C_{I2DS}=p_{1}$, while $C_{OPT}=p_{1}$.
Case 2. If $\frac{5}{12}\cdot Sum<p_{1}\leq\frac{7}{12}\cdot Sum$.
Then $l_{1}+p_{1}>\frac{5}{12}\cdot Sum$. Clearly, $l_{1}<\frac{5}{12}\cdot
Sum$ as $l_{1}=0$ initially. Algorithm I2DS schedules job $J_{1}$ on machine
$M_{1}$ and the updated load $l_{1}\leq\frac{7}{12}\cdot Sum$. We now have
$l_{2}\leq\frac{7}{12}\cdot Sum$ as $l_{1}>\frac{5}{12}\cdot Sum$. This
implies, $C_{I2DS}\leq\frac{7}{12}\cdot Sum$. Thus, we obtain from Eq. (6),
$\frac{C_{I2DS}}{C_{OPT}}\leq\frac{7}{6}=1.16$. The bound holds for any other
cases as well. $\Box$

###  3.2 Three Identical Parallel Machines ($P_{3}$)

When three identical parallel machines are given in the semi-online scheduling
problem with known $Decr$ and $Sum$ to minimize the makespan ($C_{max}$), we
denote the problem as $P_{3}|Decr,Sum|C_{max}$. Let $C_{ALG}$ and $C_{OPT}$ be
the makespans obtained by any semi-online algorithm $ALG$ and the optimal
offline algorithm $OPT$ respectively. We present the lower bound of the
problem $P_{3}|Decr,Sum|C_{max}$ as follows.

####  3.2.1 Lower Bound Result

###### Theorem 3.6

Any deterministic semi-online algorithm $ALG$ for the problem
$P_{3}|Decr,Sum|C_{max}$ has a competitive ratio of at least $1.11$.

###### Proof

We follow the adversary method to prove our claim. Let $Sum=27$ is known in
advance and we are given a sequence of four jobs $J_{1}$, $J_{2}$, $J_{3}$,
$J_{4}$, where $p_{1}=9$ and $p_{2}+p_{3}+p_{4}=18$. We assume that at least
one job must be scheduled on each machine by the end of the job sequence. We
now can consider the following three cases based on the assignment of initial
two jobs.
Case 1. $J_{1}$ and $J_{2}$ are assigned to the same machine $M_{j}$.
Let us consider $M_{j}=M_{1}$ and $p_{2}=6$, implies, $l_{1}=15$. We are now
left with jobs $J_{3}$ and $J_{4}$ such that $p_{3}+p_{4}=12$. Jobs $J_{3}$
and $J_{4}$ must be scheduled on two different machines other than $M_{1}$. By
considering $p_{3}=p_{4}=6$, we obtain the updated loads $l_{2}=l_{3}=6$.
Thus, $C_{ALG}\geq 15$, while $C_{OPT}=9$. Therefore, we have
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{15}{9}=1.66$ (7)
Case 2. $J_{1}$ and $J_{2}$ are scheduled on different machines.
Sub-case 2.1. $J_{3}$ is assigned to the machine, where $J_{1}$ has already
been assigned.
Let us consider $J_{1}$ has been assigned to machine $M_{1}$. We have jobs
$J_{2}$ and $J_{3}$ such that $p_{2}+p_{3}\leq 17$. We now have ten
possibilities for $(p_{2},p_{3})$ i.e., $(9,8)$, $(9,7)$, $(9,6)$, $(9,5)$,
$(8,8)$, $(8,7)$, $(8,6)$, $(8,5)$, $(7,7)$ and $(7,6)$. To minimize the load
on machine $M_{1}$, let us consider $p_{2}=9$ and $p_{3}=5$. Thus, we have the
updated loads $l_{1}=14$, $l_{2}=9$ and $l_{3}=0$. Now job $J_{4}$ with
$p_{4}=4$ must be scheduled on machine $M_{3}$ to update $l_{3}=4$. Thus, we
have $C_{ALG}\geq 14$, while $C_{OPT}=9$. Therefore, we have
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{14}{9}=1.55$ (8)
Sub-case 2.2. $J_{3}$ is assigned to the machine, where $J_{2}$ has already
been assigned.
Let us consider job $J_{2}$ has been assigned to machine $M_{2}$. Now we have
jobs $J_{2}$ and $J_{3}$ such that $p_{2}+p_{3}\leq 17$. Thus, we have three
possibilities for $(p_{2},p_{3})$ i.e., $(8,5)$, $(7,6)$ and $(6,6)$. Let us
consider $p_{2}=p_{3}=6$. We now have the updated loads $l_{1}=9$, $l_{2}=12$
and $l_{3}=0$. Again $J_{4}$ with $p_{4}=6$ must be scheduled on the machine
$M_{3}$ and incurs a load $l_{3}=6$. Thus, we have $C_{ALG}\geq 12$, while
$C_{OPT}=9$. Therefore, we have
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{12}{9}=1.33$ (9)

Sub-case 2.3. $J_{3}$ is scheduled on a different machine.
Let us consider the following four instances, where $J_{i}/p_{i}$ denote a job
and its processing time.

$\sigma_{1}=\langle J_{1}/9,J_{2}/8,J_{3}/8,J_{4}/2\rangle$
$\sigma_{2}=\langle J_{1}/9,J_{2}/8,J_{3}/7,J_{4}/3\rangle$
$\sigma_{3}=\langle J_{1}/9,J_{2}/8,J_{3}/6,J_{4}/4\rangle$
$\sigma_{4}=\langle J_{1}/9,J_{2}/8,J_{3}/5,J_{4}/5\rangle$

It can be easily shown with each of the above instances that any deterministic
semi-online algorithm $ALG$ achieves a competitive ratio such that
$\frac{C_{ALG}}{C_{OPT}}\geq\frac{10}{9}=1.11$ (10)

Therefore, by Eqs. (7), (8), (9) and (10), we conclude that Theorem 6 holds
true. $\Box$

Algorithm 3DS

We now propose a deterministic semi-online algorithm named 3DS for the problem
$P_{3}|Decr,Sum|C_{max}$ by considering both $I_{1}$ and $I_{2}$. Let
$C_{3DS}$ be the makespan obtained by algorithm 3DS. The algorithm works as
follows.

Algorithm 3 3DS

Initially, $l_{1}=l_{2}=l_{3}=0$, $Sum=\sum_{i=1}^{n}{p_{i}}$, and
$p_{i+1}\leq p_{i}$ for $1\leq i<n$

WHILE a new job $J_{i}$ arrives with known $Decr$ and $Sum$ DO

BEGIN

IF $l_{1}+p_{i}\leq\frac{1}{3}\cdot Sum$

THEN assign job $J_{i}$ to machine $M_{1}$

UPDATE $l_{1}=l_{1}+p_{i}$

ELSE

Select a machine $M_{j}$, where $j\in\\{2,3\\}$ for which the current load
$l_{j}=\min\\{l_{2},l_{3}\\}$

Assign job $J_{i}$ to the machine $M_{j}$

UPDATE $l_{j}=l_{j}+p_{i}$

$i=i+1$

END

Return $C_{3DS}=\max\\{l_{1},l_{2},l_{3}\\}$

Algorithm 3DS is an improved variant of Graham’s list scheduling algorithm
[19]. The objective of algorithm 3DS is to always keep the load of machine
$M_{1}$ such that $l_{1}\leq\frac{1}{3}\cdot Sum$ and to maintain loads on
machines $M_{2}$ and $M_{3}$ such that the loads $l_{2}$ and $l_{3}$ are at
most $1.5(C_{OPT})$.

Upper Bound Results

We analyze and present the performance of algorithm 3DS with respect to
$I_{1}$ and $I_{2}$ as follows.

###### Theorem 3.7

For all job sequences of the problem $P_{3}|Decr,Sum|C_{max}$ with $I_{1}$,
where $p_{i}=x$, $x\geq 1$, $n\geq 4$ and $1\leq i\leq n$, we have
$\frac{C_{3DS}}{C_{OPT}}\leq 1.5$.

###### Proof

We consider the following three critical cases based on the number of jobs
$n$.
Case 1. If $n=3a$, for any $a\geq 2$.
Then the initial $a$ jobs are assigned to machine $M_{1}$ and update the load
$l_{1}=ax$. Algorithm 3DS assigns the remaining $2a$ jobs with load $2ax$ to
machines $M_{2}$ and $M_{3}$ such that exactly $a$ jobs are scheduled on each
of the machines and incurs loads $l_{2}=l_{3}=ax$. Thus, we have $C_{3DS}=ax$,
while $C_{OPT}=ax$. Therefore, we have
$\frac{C_{3DS}}{C_{OPT}}=1$ (11)

Case 2. If $n=3a+1$ for $a\geq 1$.
The initial $a$ jobs are scheduled on machine $M_{1}$ to incur a load
$l_{1}=ax$. Out of the remaining $2a+1$ jobs, algorithm 3DS assigns the first
$2a$ jobs on machines $M_{1}$ and $M_{2}$ such that $l_{2}=l_{3}=ax$. Now the
last job $J_{n}$ can either be scheduled on machine $M_{2}$ or on machine
$M_{3}$ to incur a load either $l_{2}=(a+1)x$ or $l_{3}=(a+1)x$. Thus, we have
$C_{3DS}\leq(a+1)x$, while $C_{OPT}=\frac{(3a+1)x}{3}$. Therefore, we have
$\frac{C_{3DS}}{C_{OPT}}\leq\frac{3(a+1)}{3a+1}\leq\frac{3}{2}=1.5$ (12)

Case 3. If $n=3a+2$ for $a\geq 1$.
Then again the initial $a$ jobs are scheduled on machine $M_{1}$ to update the
load $l_{1}=ax$. Algorithm 3DS schedules the next $2a$ jobs on machines
$M_{1}$ and $M_{2}$ to update the loads $l_{2}=l_{3}=ax$ (i.e., exactly $a$
jobs are assigned to each of the machines). Out of the remaining two jobs,
exactly one job is assigned to $M_{2}$ and $M_{3}$ respectively to update the
loads $l_{2}=l_{3}=(a+1)x$. Thus, we have $C_{3DS}\leq(a+1)x$, while
$C_{OPT}=\frac{(3k+2)x}{3}$. Therefore, we have
$\frac{C_{3DS}}{C_{OPT}}\leq\frac{3(a+1)}{3a+2}\leq\frac{6}{5}=1.2$ (13)

By Eqs. (11), (12) and (13), we can conclude that Theorem 7 holds true. $\Box$

###### Theorem 3.8

For all job sequences of the problem $P_{3}|Decr,Sum|C_{max}$ with $I_{2}$,
where $n\geq 4$ and $1\leq i\leq n$, we have $\frac{C_{3DS}}{C_{OPT}}\leq
1.2$.

###### Proof

We prove the theorem by method of contradiction. Let us assume that the input
job sequence $\sigma=\langle J_{1},J_{2},\ldots,J_{t}\rangle$ is the smallest
instance of the problem with respect to number of jobs that contradicts
Theorem 8. Thus $t$ is minimal. Let $C_{3DS}(\sigma)$ and $C_{OPT}(\sigma)$ be
the makespans incurred by algorithm 3DS and $OPT$ respectively for the
sequence $\sigma$. Suppose $J_{r}$ is a job in $\sigma$ that finishes last in
the schedule, generated by algorithm 3DS and $r<t$. We now have an instance
$\sigma_{1}=\langle J_{1},J_{2},\ldots,J_{r}\rangle$ such that
$C_{3DS}(\sigma_{1})=C_{3DS}(\sigma)$, while $C_{OPT}(\sigma_{1})\leq
C_{OPT}(\sigma)$.

This implies,
$\frac{C_{3DS}\sigma_{1}}{C_{OPT}\sigma_{1}}\geq\frac{C_{3DS}(\sigma)}{C_{OPT}(\sigma)}>1.2$.

Thus the instance $\sigma_{1}$ constitutes the smallest counterexample to
Theorem 8, which contradicts our assumption on the minimality of $t$.
Therefore the instance $\sigma$ with $t$ jobs forms the smallest
counterexample such that $\frac{C_{3DS}(\sigma)}{C_{OPT}(\sigma)}>1.2$.
Implies, for any other instance $\sigma_{2}$ with $t-1$ jobs, we have
$\frac{C_{3DS}(\sigma_{2})}{C_{OPT}(\sigma_{2})}\leq 1.2$, where $t-1\geq 4$.
Algorithm 3DS always maintains the loads on the machines $M_{1}$, $M_{2}$ and
$M_{3}$ such that $l_{1}\leq l_{2}$ and $l_{3}\leq l_{2}$.
Let us consider the instance $\sigma_{2}=\langle
J_{1},J_{2},\ldots,J_{t-1}\rangle$. After scheduling all jobs of $\sigma_{2}$,
algorithm 3DS updates the loads of $M_{1}$, $M_{2}$ and $M_{3}$ such that
$l_{1}\leq\frac{1}{3}\cdot Sum$, $l_{2}\leq\frac{2}{5}\cdot Sum$ and
$\frac{4}{15}\cdot Sum\leq l_{3}<\frac{2}{5}\cdot Sum$. It is clear that
assignment of the job $J_{t}$ makes
$\frac{C_{3DS}(\sigma)}{C_{OPT}(\sigma)}>1.2$. We know that before scheduling
of job $J_{t}$, we have $l_{3}<l_{2}$ and $l_{3}\leq\frac{2}{5}\cdot Sum-1$.
Hence job $J_{t}$ is scheduled on machine $M_{3}$ and the updated load
$l_{3}>\frac{2}{5}\cdot Sum$. Without loss of generality, we can bound the
processing time of job $J_{t}$ as $2\leq p_{t}\leq p_{max}-4$. This implies,

$C_{3DS}(\sigma)=l_{3}+p_{max}-4>\frac{2}{5}\cdot Sum$.
$\frac{2}{5}\cdot Sum+p_{max}-5>\frac{2}{5}\cdot Sum$

implies, $p_{max}>5$.

To show the correctness of our assumptions, let us consider the smallest
instance $\sigma_{3}=\langle J_{1}/6,J_{2}/5,J_{3}/4,J_{4}/3,J_{5}/2\rangle$
based on our assumptions on $p_{max}$, $p_{t}$ and $\sigma$. After scheduling
all jobs of $\sigma_{3}$, algorithm $3DS$ updates the loads such that
$l_{1}=6$, $l_{2}=l_{3}=7$. Hence $C_{3DS}(\sigma_{3})\leq 7$, while
$C_{OPT}(\sigma_{3})=\frac{20}{3}$. Therefore
$\frac{C_{3DS}(\sigma_{3})}{C_{OPT}(\sigma_{3})}\leq\frac{21}{20}<1.2$. The
instance $\sigma_{3}$ is a counterexample to our assumptions on $p_{max}$,
$p_{t}$ and $\sigma$. Hence there does not exist any counterexample to Theorem
8. Therefore the Theorem holds true. $\Box$

Algorithm Improved 3DS

For the problem $P_{3}|Decr,Sum|C_{max}$ with $I_{1}$, the algorithm 3DS is
best possible in the sense that no semi-online algorithm can overcome the
instance $\sigma=\langle J_{1}/1,J_{2}/1,J_{3}/1,J_{4}/1\rangle$ to obtain a
better competitive ratio than $1.5$. However, the upper bound $1.2$ for the
problem $P_{3}|Decr,Sum|C_{max}$ with $I_{2}$ can be improved to $1.11$. We
now propose a more sophisticated, yet improved deterministic semi-online
algorithm than 3DS for the problem $P_{3}|Decr,Sum|C_{max}$ with $I_{2}$. We
name the algorithm as Improved 3DS (I3DS) and it works as follows.

Algorithm 4 I3DS

Initially, $l_{1}=l_{2}=l_{3}=0$, $Sum=\sum_{i=1}^{n}{p_{i}}=27$, and
$p_{i+1}<p_{i}$ for $1\leq i<n$

WHILE a new job $J_{i}$ is given with known $Decr$ and $Sum$ DO

BEGIN

IF $l_{1}+p_{i}\leq\frac{1}{3}\cdot Sum$

THEN assign job $J_{i}$ to machine $M_{1}$

UPDATE $l_{1}=l_{1}+p_{i}$

ELSE IF $l_{1}+p_{i}\leq\frac{10}{27}\cdot Sum$

THEN assign job $J_{i}$ to machine $M_{2}$

UPDATE $l_{2}=l_{2}+p_{i}$

ELSE

assign job $J_{i}$ to machine $M_{3}$

UPDATE $l_{3}=l_{3}+p_{i}$

$i=i+1$

END

Return $C_{I3DS}=\max\\{l_{1},l_{2},l_{3}\\}$

The aim of algorithm I3DS is to always maintain loads on machines $M_{1}$,
$M_{2}$ and $M_{3}$ such that $l_{1}\leq\frac{9}{27}\cdot Sum$,
$l_{2}\leq\frac{10}{27}\cdot Sum$ and $\frac{8}{27}\cdot Sum\leq
l_{3}\leq\frac{10}{27}\cdot Sum$. For a better understanding of the
competitive analysis of algorithm I3DS, let us normalize the processing times
of the jobs in such a manner that $Sum=27$.

####  3.2.2 Upper Bound Result

###### Theorem 3.9

For all job sequences of the problem $P_{3}|Decr,Sum|C_{max}$ with $I_{2}$,
where $n\geq 4$ and $p_{n}\geq 3$, we have $\frac{C_{I3DS}}{C_{OPT}}\leq
1.11$.

###### Proof

We know that $Sum=27$ and initially $l_{1}=l_{2}=l_{3}=0$. We now have
$C_{OPT}\geq 9$. We can consider the following critical cases based on the
size of job $J_{1}$
Case 1. If $p_{1}>\frac{10}{27}\cdot Sum$.
We know that $p_{max}=p_{1}$. Clearly, $l_{1}+p_{1}>\frac{10}{27}\cdot Sum$
and $l_{2}+p_{1}>\frac{10}{27}\cdot Sum$. Let us consider
$X=\sum_{i=2}^{n}{p_{i}}$. Clearly, $X<\frac{17}{27}\cdot Sum$. Algorithm I3DS
now assigns $J_{1}$ to machine $M_{3}$ and schedules the remaining jobs to
machines $M_{1}$ and $M_{2}$ such that the updated loads
$l_{1}\leq\frac{7}{27}\cdot Sum$ and $l_{2}\leq\frac{10}{27}\cdot Sum$, while
$l_{3}=p_{max}>\frac{10}{27}\cdot Sum$. Hence, $C_{I3DS}=p_{max}$, while
$C_{OPT}=p_{max}$.

Case 2. If $\frac{1}{3}\cdot Sum<p_{1}\leq\frac{10}{27}\cdot Sum$.
Then $l_{1}+p_{1}>\frac{1}{3}\cdot Sum$ and $l_{2}+p_{1}\leq\frac{10}{27}\cdot
Sum$. This implies, job $J_{1}$ is assigned to machine $M_{2}$ and the updated
load $l_{2}\leq\frac{10}{27}\cdot Sum$. Now
$\sum_{i=2}^{n}{p_{i}}\leq\frac{17}{27}\cdot Sum$.
Case 2(a). No other job than $J_{1}$ is assigned to machine $M_{2}$.
We now can consider the following critical cases based on the size of the
second job $J_{2}$
Sub-case 2.1. If $p_{2}=\frac{1}{3}\cdot Sum$.
Then the updated load $l_{1}=\frac{1}{3}\cdot Sum$ and the remaining jobs are
scheduled on machine $M_{3}$ such that the updated load $\frac{8}{27}\leq
l_{3}<\frac{10}{27}\cdot Sum$. Hence $C_{I3DS}\leq\frac{10}{27}\cdot Sum$,
while $C_{opt}\geq\frac{1}{3}\cdot Sum$. Therefore
$\frac{C_{I3DS}}{C_{OPT}}\leq\frac{10}{9}=1.11$ (14)
Sub-case 2.2. If $p_{1}<\frac{1}{3}\cdot Sum$.
Then job $J_{2}$ is assigned to machine $M_{1}$. Now the updated load
$l_{1}<\frac{1}{3}\cdot Sum$. We now can consider the following cases based on
the assignment of jobs on machine $M_{1}$ as follows.
Sub-sub-case 2.2.1. No other job then $J_{2}$ is scheduled on machine $M_{1}$.
Clearly, $l_{1}\leq\frac{1}{3}\cdot Sum-1$. (15)
Even the assignment of the last job $J_{n}$ to machine $M_{1}$ makes the
updated load $l_{1}>\frac{1}{3}\cdot Sum$.
Before the assignment of job $J_{n}$ to machine $M_{3}$, we have
$l_{3}\leq\frac{8}{27}\cdot Sum-1$. After the scheduling of job $J_{n}$ on
$M_{3}$, we have the updated load $l_{3}>\frac{8}{27}\cdot Sum$ as
$l_{2}\leq\frac{10}{27}\cdot Sum$ and $l_{1}<\frac{1}{3}\cdot Sum$. W.l.o.g,
we can bound the processing time of the last job $J_{n}$ such that $2\leq
p_{n}\leq p_{max}-6$. We now have $l_{3}\leq\frac{8}{27}\cdot
Sum-1+p_{max}-6\leq\frac{8}{27}\cdot Sum+C_{OPT}-7\leq\frac{8}{27}\cdot
Sum+\frac{1}{3}\cdot Sum-7\leq\frac{17}{27}\cdot Sum-7$, implies
$l_{3}\leq 10$ (16)
Hence $C_{I3DS}\leq 10$, while $C_{OPT}\geq 9$. Therefore
$\frac{C_{I3DS}}{C_{OPT}}\leq\frac{10}{9}=1.11$ (17)

Sub-sub-case 2.2.2. At least one job other than $J_{2}$ is assigned to machine
$M_{1}$.
Let $J_{k}$ be the latest job, which has been assigned to $M_{1}$. Let
$l^{\prime}_{1}$ be the load of $M_{1}$ just before the assignment of $J_{k}$.
By Eq. (15), we have
$l^{\prime}_{1}+p_{n}\leq\frac{1}{3}\cdot Sum>l_{1}$ (18)
If $J_{n}=J_{k}$, then by Eq. (18), we have
$l^{\prime}_{1}+p_{n}<\frac{1}{3}\cdot Sum$ or
$l^{\prime}_{1}+p_{n}=\frac{1}{3}\cdot Sum$. If
$l^{\prime}_{1}+p_{n}=\frac{1}{3}\cdot Sum$, then the updated load $l_{3}$ is
such that $\frac{8}{27}\leq l_{3}<\frac{10}{27}\cdot Sum$, while
$l_{2}\leq\frac{10}{27}\cdot Sum$. Hence $C_{I3DS}\leq\frac{10}{27}\cdot Sum$,
while $C_{OPT}\geq\frac{1}{3}\cdot Sum$. Therefore
$\frac{C_{I3DS}}{C_{OPT}}\leq\frac{10}{9}=1.11$.
If $l^{\prime}_{1}+p_{n}<\frac{1}{3}\cdot Sum$. Let $l^{\prime}_{3}$ be the
load of machine $M_{3}$ after the scheduling of $J_{n}$ to machine $M_{1}$. By
Eq. (16), we have $l^{\prime}_{3}<l_{3}$ and
$l^{\prime}_{3}<\frac{10}{27}\cdot Sum$. Hence
$C_{I3DS}=l_{2}\leq\frac{10}{27}\cdot Sum$, while $C_{OPT}\geq\frac{1}{3}\cdot
Sum$. Therefore $\frac{C_{I3DS}}{C_{OPT}}\leq\frac{10}{9}=1.11$. $\Box$

##  4 Conclusion and Future Work

In this paper we investigated the non-preemptive semi-online scheduling
problem in two and three identical parallel machines settings with makespan
minimization objective. We studied the problem by considering a pair-wise
combination of two types of EPI on the future jobs, where we know jobs arrive
in order of non-increasing sizes ($Decr$) and the total sum of sizes of the
jobs ($Sum$) beforehand. In particular we studied the problem with respect to
two practically significant input job sequence patterns, i.e., $I_{1}$ and
$I_{2}$ based on $Decr$. The pattern $I_{1}$ represents a job sequence, where
all jobs are of equal size and $I_{2}$ represents a job sequence, where jobs
arrive in order of decreasing sizes. We showed that prior knowledge of
multiple EPI is extremely helpful in designing improved competitive semi-
online scheduling algorithms. We proved the lower bounds $1.33$ and $1.11$ on
the competitive ratio for the problem in two and three identical machines
settings respectively by the adversary method. We proved a lower bound $1.04$
for the problem by considering only $I_{2}$ in two identical machines setting.
Our method can further be extended to achieve a lower bound of
$\frac{2m}{m+1}$ on the competitive ratio for the problem in $m$ identical
machines settings, where $m\geq 2$. We proposed four new variants of the
deterministic semi-online scheduling algorithms and achieved improved
competitive ratios. The summary of the upper bound results on the competitive
ratio for our proposed semi-online algorithms is presented in Table 4.

Table 4: Summary of Our Upper Bound Results for the problem $P|Decr,Sum|C_{max}$ Machines |  $I_{1}$ |  $I_{2}$ |  $I_{2}$
---|---|---|---
Two |  1.33 |  1.33 |  1.16
Three |  1.5 |  1.2 |  1.11

Future Work. It is non-trivial and interesting to address the following
research challenges as a part of future work.

  * •

Improvement of the upper bound $1.16$ for the problem $P_{2}|Decr,Sum|C_{max}$
with $I_{2}$ for $n\geq 3$ and $p_{i}\geq 1$, $\forall i$.

  * •

Minimization of the upper bound $1.11$ for the problem
$P_{3}|Decr,Sum|C_{max}$ with $I_{2}$ for $n\geq 4$ and $p_{i}\geq 1$,
$\forall i$.

  * •

Study of the problem $P_{m}|Decr,Sum|C_{max}$ with respect to input patterns
$I_{1}$ and $I_{2}$ for $m\geq 4$.

  * •

Exploration of practically significant new input patterns based on the
information on $Decr$ or job’s release time.

  * •

As we know that EPI is an application dependent parameter and it also affects
the performance of a semi-online scheduling algorithm, it is interesting and
challenging to explore practically and theoretically significant new EPI.

## References

  * [1] Lenstra J K, Rinnooy Kan A H G, Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1:343-362.
  * [2] Graham R L. Bounds on multiprocessor timing anomalies. SIAM Journal on Applied Mathematics, 1969, 17(2):416-429.
  * [3] Beaumont O, Canon L C, Eyraud-Dubois L, Lucarelli G, Marchal L, Mommessin C, Simon B, Trystram D. Scheduling on two types of resources: A Survey. ACM Computing Surveys (CSUR), 2020, 53(3):1-36.
  * [4] Kellerer H, Kotov V, Speranza M G, Tuza T. Semi-online algorithms for the partition problem. Operations Research Letters, 1997, 21:235-242.
  * [5] Seiden S, Sgall J, Woeginger G. Semi-online scheduling with decreasing job sizes. Operations Research Letters, 2000, 27:215-221.
  * [6] Tarjan R E, Sleator D D. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 1985, 6(2):306-318.
  * [7] Tan Z, He Y. Semi-online problems on two identical machines with combined partial information. Operations Research Letters, 2002, 30:408-414.
  * [8] Angelelli E. Semi-online scheduling on two parallel processors with known sum and lower bound on the size of the tasks. Central European Journal of Operations Research, 2000, 8:285-295.
  * [9] Angelelli E, Speranza M G, Tuza Zs. Semi-online scheduling on two parallel processors with an upper bound on items. Algorithmica, 2003, 37:243-262.
  * [10] Angelelli E, Speranza M G, Tuza T. New bounds and algorithms for online scheduling: two identical processors, known sum and upper bound on the task. Discrete Mathematics and Theoretical Computer Science, 2006, 8(1):1-16.
  * [11] Cao Q, Cheng T C E, Wan G, Li Y. Several semi-online scheduling problems on two identical machines with combined information. Theoretical Computer Science, 2012, 457(26):35-44.
  * [12] Cao Q, Wan G. Semi-online scheduling with combined information on two identical machines in parallel. Journal of Combinatorial Optimization, 2016, 31(2):686-695.
  * [13] He Y, Dosa G. Semi-online scheduling jobs with tightly grouped processing times on three identical machines. Discrete Applied Mathematics, 2005, 150:140-159.
  * [14] Angelelli E, Speranza M G, Tuza Zs. Semi- online scheduling on three processors with known sum of the tasks. Journal of Scheduling, 2007, 10:263-269.
  * [15] Hua R, Hu J, Lu L. A semi-online algorithm for parallel machine scheduling on three machines. Journal of Industrial Engineering and, Engineering Management, 2006, 20.
  * [16] Wu Y, Tan Z, Yang Q. Optimal semi-online scheduling algorithms on a small number of machines. Lecture Notes in Computer Science (LNCS), Springer, 2007, 4614:504-515.
  * [17] Cheng T C E, Kellerer H, Kotov V. Algorithms better than LPT for semi-online scheduling with decreasing processing times. Operations Research Letters, 2012, 40:349-352.
  * [18] Epstein L. A Survey on makespan minimization in semi-online environments. Journal of Scheduling, 2018, 21(3):269-284.
  * [19] Graham R L. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 1966, 45(1):1563–1581.