# Curvature Inheritance Symmetry on M-Projectively Flat Spacetimes

Absos Ali Shaikh1, Musavvir Ali2, Mohammad Salman3 and Füsun Özen Zengin4
1 Department of Mathematics,
University of Burdwan,
Golapbag, Burdwan-713104,
West Bengal, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
2,3 Department of Mathematics,
Aligarh Muslim University,
Aligarh-202002, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
4 Department of Mathematics,
Istanbul Technical University,
34469-Istanbul, Turkey<EMAIL_ADDRESS>
###### Abstract.

The paper aims to investigate curvature inheritance symmetry in M-projectively
flat spacetimes. It is shown that the curvature inheritance symmetry in
M-projectively flat spacetime is a conformal motion. We have proved that M-
projective curvature tensor follows the symmetry inheritance property along a
vector field $\xi$, when spacetime admits the conditions of both curvature
inheritance symmetry and conformal motion or motion along the vector field
$\xi$. Also, we have derived some results for M-projectively flat spacetime
with perfect fluid following the Einstein field equations with a cosmological
term and admitting the curvature inheritance symmetry along the vector field
$\xi$. We have shown that an M-projectively flat perfect fluid spacetime
obeying the Einstein field equations with a cosmological term and admitting
the curvature inheritance symmetry along a vector field $\xi$ is either a
vacuum or satisfies the vacuum-like equation of state. We have also shown that
such spacetimes with the energy momentum tensor of an electromagnetic field
distribution do not admit any curvature symmetry of general relativity.
Finally, an example of M-projectively flat spacetime has been exhibited.

###### Key words and phrases:

M-projective curvature tensor, flat spacetime, curvature inheritance,
conformal motion, Einstein field equations, perfect fluid spacetime.

###### 2020 Mathematics Subject Classification:

83C20; 83C05; 53B20

##  1\. Introduction

A pseudo-Riemannian manifold with a non-zero $(0,2)$ type Ricci tensor
$R_{ij}$ is known as Einstein manifold if $R_{ij}$ is proportional to the
metric tensor $g_{ij}$. In other words, we can simply say that Einstein
manifolds form a natural subclass of the manifold of constant curvature [9].
In the field of general relativity [16] and Riemannian geometry, Einstein
manifolds play a significant role. A spacetime is considered as a four
dimensional connected semi-Riemannian manifold $(V_{4},g)$ with Lorentzian
metric $g$ of signature $(-,+,+,+)$. Due to the casual character of vectors,
the Lorentzian manifolds [9] are the practical option for the studying general
theory of relativity.

With metric tensor $g_{ij}$ and Riemannian connection $\nabla$, let
$(V_{4},g)$ be a 4-dimensional differentiable manifold of class $C^{\infty}$.
M-projective curvature tensor of the manifold $V_{4}$ was defined by
Pokhariyal and Mishra [24] in 1971 which can be written in the following form

$\bar{W}^{h}_{ijk}=R^{h}_{ijk}+\frac{1}{6}(\delta^{h}_{j}R_{ik}-\delta^{h}_{k}R_{ij}+R^{h}_{j}g_{ik}-R^{h}_{k}g_{ij}),$
(1.1)

where $R^{h}_{ijk}$ is the Riemannian curvature, $g_{ij}$ is the metric and
$R_{ij}$ is Ricci tensor in $V_{4}$, the tensor field $\bar{W}^{h}_{ijk}$ is
the M-projective curvature tensor. We note that the M-projective curvature
tensor is a generalized curvature tensor, i.e., it satisfies the symmetry and
skew-symmetry properties like Riemann curvature and satisfies Bianchi
identity. If $\bar{W}^{h}_{ijk}=0$ on $V_{4}$ identically, then that manifold
is known as M-projectively flat manifold. We mention that any M-projectively
flat semi-Riemannian manifold is an Einstein manifold and a space of constant
curvature. Many authors have studied about spacetimes and their geometries and
physics such as: Abdussattar and Dwivedi [1] studied conharmonic symmetries in
fluid spacetimes, Zengin [30] studied M-Projectively flat spacetimes, pseudo
Z-symmetric spacetimes by Mantica and Suh [21], concircular curvature tensor
and fluid spacetimes by Ahsan et al. [2, 3, 4, 5, 6, 7] and many more. The
properties of M-projective curvature tensor were studied by Ojha [22, 23] and
M-projective curvature tensor on various structures has been studied by
several authors (see, [11, 20, 25, 26, 28, 31]).

The present paper is dedicated to certain investigations in general theory of
relativity for M-projectively flat case. We have explored the condition when
energy momentum tensor follow symmetry inheritance property and its Lie
derivative vanishes in M-projectively flat spacetimes.

The Bianchi identities describe the interaction between the matter and free
gravitational parts of the gravitational field, which is characterized by the
curvature tensor in general theory of relativity. In gravitational physics,
the main objective of all investigations is the construction of the
gravitational potential, which satisfies the Einstein field equations (EFEs)
with a cosmological constant. Consider the EFEs with cosmological term as

$R_{ij}-\frac{R}{2}g_{ij}+\wedge g_{ij}=k~{}T_{ij},$ (1.2)

where $g_{ij}$, $R_{ij}$, $T_{ij}$, $\wedge$ and $k$ are respectively denote
the metric, Ricci tensor, energy-momentum tensor, cosmological term and the
gravitational constant. The energy-momentum tensor for a perfect fluid is
defined by the following

$T_{ij}=(\mu+p)u_{i}u_{j}+pg_{ij},$ (1.3)

here $\mu$, the energy density, $p$ the isotropic pressure and $u^{i}$ is the
velocity vector field of the flow satisfying $g_{ij}u^{j}=u_{i}$ for all $i$,
also $u_{i}u^{i}=-1$.

Geometrical symmetries of the spacetime are represented by the following
equation [29]

$\pounds_{\xi}A=2\varOmega A$ (1.4)

where $\pounds_{\xi}$ stands for the Lie derivative along the vector field
$\xi^{i}$. The vector field $\xi^{i}$ may be timelike ($\xi^{i}\xi_{i}<0$),
spacelike ($\xi^{i}\xi_{i}>0$) or null ($\xi^{i}\xi_{i}=0$), ‘A’ denotes a
geometrical/physical quantity and $\varOmega$ is a scalar function.

A simple example can be provided as the metric inheritance symmetry in
particular for $g_{ij}$, it is conformal motion (Conf M) [19] along a vector
field $\xi^{i}$, so

$\pounds_{\xi}g_{ij}=2\psi g_{ij},$ (1.5)

where $\psi$ is a conformal function, equation (1.5) implies motion/isometry
for $\psi=0$. In this case $\xi$ is called a Killing vector [29]. More than 30
geometric symmetries have been found in literature till date. For detailed
study of symmetry inheritance, see [2, 13, 14, 15, 18].

In 1992, Duggal [14] introduced the concept of curvature inheritance (CI)
symmetry. Curvature inheritance is the generalization of curvature
collineation (CC), which was defined by Katzin in 1969 [19].

######  Definition 1.1.

[14] A spacetime $(V_{4},~{}g)$ admits curvature inheritance symmetry along a
smooth vector field $\xi^{i}$, if it satisfies

$\pounds_{\xi}R^{h}_{ijk}=2\varOmega R^{h}_{ijk},$ (1.6)

where $\varOmega=\varOmega(x^{i})$ is known as inheriting factor or
inheritance function.

If $\varOmega=0$, then $\pounds_{\xi}R^{h}_{ijk}=0$ and $\xi^{i}$ is said to
follow a curvature symmetry on $V_{4}$ or simply to write it generate a
curvature collineation. The CI equation (1.6) can be written in component form
as

$R^{h}_{ijk;l}\xi^{l}-R^{l}_{ijk}\xi^{h}_{;l}+R^{h}_{ljk}\xi^{l}_{;i}+R^{h}_{ilk}\xi^{l}_{;j}+R^{h}_{ijl}\xi^{l}_{;k}=2\varOmega
R^{h}_{ijk}.$ (1.7)

######  Definition 1.2.

[14] A spacetime $(V_{4},~{}g)$ admits Ricci inheritance (RI) symmetry along a
smooth vector field $\xi^{i}$, if it satisfies the following equation

$\pounds_{\xi}R_{ij}=2\varOmega R_{ij}.$ (1.8)

Contraction of (1.6) gives (1.8). Thus, in general, every curvature
inheritance is Ricci inheritance symmetry (i.e., CI $\Rightarrow$ RI), but the
converse may not hold. Also, RI reduces to RC when $\varOmega=0$ and for
$\varOmega\neq 0$, it is called as proper RI.

The literature on study of spacetimes exhibits, a deep interest towards the
research of different symmetries (in particular, curvature, Ricci, projective,
matter, semi-conformal symmetry, conharmonic curvature inheritance). These
geometrical symmetries are much helpful for obtaining exact solutions of
Einstein field equations (1.2). Such work of researches [13, 27] motivates us
to inquire the curvature inheritance symmetry in the spacetime, admitting
M-projective curvature tensor. The plan of this paper is as follows:

After Section 1, the introduction and preliminaries, we study curvature
inheritance in an M-projectively flat spacetime. Section 3 deals with
M-projectively flat perfect fluid spacetime admitting curvature inheritance
symmetry and examination of some properties of such a spacetime. Equation of
state is derived in Section 4 which is physically significant in cosmology.
Finally, we obtained some interesting results considering a purely
electromagnetic distribution. In the last section, we provide an example in
the form of a metric which is M-projectively flat.

##  2\. Curvature Inheritance in M- Projectively Flat Spacetimes

Consider an M-projectively flat Lorentzian manifold $(V_{4},g)$, therefore
(1.1) under condition $\bar{W}^{h}_{ijk}$ = 0, implies

$R^{h}_{ijk}=\frac{1}{6}(\delta^{h}_{k}R_{ij}-\delta^{h}_{j}R_{ik}+R^{h}_{k}g_{ij}-R^{h}_{j}g_{ik}).$
(2.1)

Contracting with respect to $h$ and $k$, we get

$R_{ij}=\frac{R}{4}g_{ij},$ (2.2)

here $R$ is scalar curvature. Thus, we can state that “An M-projectively flat
spacetime is an Einstein manifold.” From equations (2.1) and (2.2), we have

$R^{h}_{ijk}=\frac{R}{12}(g^{h}_{k}g_{ij}-g^{h}_{j}g_{ik}).$ (2.3)

Thus, a result by Zengin [30] is mentioned as “An M-projectively flat
spacetime is of constant curvature”. Also, M-projectively flat Lorentzian
manifold is Ricci symmetric, i.e. $\nabla_{k}R_{ij}=0$.

For $(V_{4},g)$ admitting Ricci inheritance, (1.8) and (2.2) lead to
$\pounds_{\xi}g_{ij}=2\varOmega g_{ij}.$ Thus, we have the following:

######  Theorem 2.1.

Every Ricci inheritance in an M-projectively flat spacetime is a conformal
motion.

Since, every M-projectively flat spacetime is Einstein [3], thus from Theorem
2.1, we can state the following:

######  Corollary 2.1.

Every Ricci inheritance in an Einstein manifold is a conformal motion.

We know that a space with non-zero constant curvature or every harmonic space
is Einstein. Then it yields the following:

######  Corollary 2.2.

Every Ricci inheritance in a space of constant curvature is a conformal
motion.

######  Corollary 2.3.

Every Ricci inheritance in a harmonic space is a conformal motion.

We know that in a semi-Riemannian space, every curvature inheritance is a
Ricci inheritance [14]. Hence, we have

######  Corollary 2.4.

Every curvature inheritance in an M-projectively flat spacetime is a conformal
motion with the conformal function $\varOmega$.

On similar lines of Corollaries ((2.1) - (2.3)), we simply write the
following:

######  Corollary 2.5.

Every curvature inheritance in an Einstein spacetime is a conformal motion.

######  Corollary 2.6.

Every curvature inheritance in a space of constant curvature is a conformal
motion.

######  Corollary 2.7.

Every curvature inheritance in a harmonic space is a conformal motion.

Now, we consider the Lorentzian space of two dimensional. Since, every $V_{2}$
is an Einstein space, where scalar curvature $R$ is a non-zero function of
coordinates, (1.8) and (2.2) lead to (assuming that $V_{2}$ admits a Ricci
inheritance)

$4(2\varOmega R_{ij})=R(\pounds_{\xi}g_{ij})+(\pounds_{\xi}R)g_{ij}.$ (2.4)

Or

$\pounds_{\xi}g_{ij}=\left[2\varOmega-\frac{\pounds_{\xi}R}{R}\right]g_{ij},\
$ (2.5)
$\implies\pounds_{\xi}g_{ij}=\left[2\varOmega-g\left(\frac{gradR}{R},\xi\right)\right]g_{ij}$

In particular if $\varOmega=\frac{1}{2}\ g\left(\frac{gradR}{R},\xi\right)$,
then $\xi$ is a Killing vector.
Hence, we have the following result

######  Theorem 2.2.

Every Ricci inheritance in a 2-dimensional Riemannian space is a conformal
motion.

######  Corollary 2.8.

If in a $2$-dimensional Lorentzian space admitting Ricci inheritance,
$grad(R)$ (i.e. the scalar potential) is orthogonal to $\xi$, then $\xi$ is a
Killing vector.

Since, CI $\Rightarrow$ RI, Theorem 2.2 gives the following result.

######  Corollary 2.9.

Every curvature inheritance in a 2-dimensional Lorentzian space is a conformal
motion.

If the scalar curvature $R$ holds the inheritance symmetry property in a
2-dimensional Lorentzian space, i.e., $\pounds_{\xi}R=2\varOmega R$ or
$\pounds_{\xi}R-2\varOmega R=0$, then equation (2.5) implies
$\pounds_{\xi}g_{ij}=0$. Thus, we have the following:

######  Corollary 2.10.

If the scalar curvature of $V_{2}$ holds inheritance symmetry, then every
curvature inheritance in $V_{2}$ is a motion.

Combining the equations (2.2) and EFEs (1.2), we get

$T_{ij}=\frac{1}{\kappa}(\wedge-\frac{R}{4})g_{ij},\ \ \kappa\neq 0.$ (2.6)

Thus, we have the following:

######  Proposition 2.1.

An M- projectively flat spacetime, the energy-momentum tensor holds EFEs with
a cosmological term is in the form of equation (2.6).

######  Theorem 2.3.

If an M- projective curvature tensor in $(V_{4},g)$ admits curvature
inheritance along a Killing vector field $\xi$, then M- projective curvature
tensor follows the symmetry inheritance property along $\xi$.

###### Proof.

The Lie differentiation of equation (1.1) along to Killing vector field $\xi$
leads to

$\pounds_{\xi}\bar{W}^{h}_{ijk}=\pounds_{\xi}R^{h}_{ijk}+\frac{1}{6}[\delta^{h}_{j}\pounds_{\xi}R_{ik}-\delta^{h}_{k}\pounds_{\xi}R_{ij}+\pounds_{\xi}(R^{h}_{j})g_{ik}-\pounds_{\xi}(R^{h}_{k})g_{ij}].$
(2.7)

If we consider a spacetime $(V_{4},g)$ admits curvature inheritance symmetry
then from (2.7), we obtain

$\pounds_{\xi}\bar{W}^{h}_{ijk}=2\varOmega[~{}R^{h}_{ijk}+\frac{1}{6}(\delta^{h}_{j}R_{ik}-\delta^{h}_{k}R_{ij}+R^{h}_{j}g_{ik}-R^{h}_{k}g_{ij})],$
In view of (1.1), the above equation entails

$\pounds_{\xi}\bar{W}^{h}_{ijk}=2\varOmega\bar{W}^{h}_{ijk}.$ (2.8)

This leads the proof. ∎

######  Theorem 2.4.

If an M- projective curvature tensor on a $(V_{4},g)$ with a CKV $\xi$
satisfies the curvature inheritance property, then M- projective curvature
tensor follows the symmetry inheritance property along $\xi$.

###### Proof.

The Lie differentiation of equation (1.1) along to Killing vector field $\xi$
leads to

$\pounds_{\xi}\bar{W}^{h}_{ijk}=\pounds_{\xi}R^{h}_{ijk}+\frac{1}{6}[\delta^{h}_{j}\pounds_{\xi}R_{ik}-\delta^{h}_{k}\pounds_{\xi}R_{ij}+\pounds_{\xi}(R^{h}_{j})g_{ik}-\pounds_{\xi}(R^{h}_{k})g_{ij}+2\varOmega(R^{h}_{j}g_{ik}-R^{h}_{k}g_{ij})].$
(2.9)

If a spacetime $(V_{4},g)$ admits curvature inheritance symmetry then from
(2.9), we obtain

$\pounds_{\xi}\bar{W}^{h}_{ijk}=2\varOmega[~{}R^{h}_{ijk}+\frac{1}{6}(\delta^{h}_{j}R_{ik}-\delta^{h}_{k}R_{ij}+R^{h}_{j}g_{ik}-R^{h}_{k}g_{ij})].$
By virtue of the above equation, we obtain

$\pounds_{\xi}\bar{W}^{h}_{ijk}=2\varOmega\bar{W}^{h}_{ijk}.$ (2.10)

This gives the proof. ∎

For M-projectively flat spacetimes we can simply obtain some results on
curvature inheritance symmetry. Also, there are some results already in
literature which can be proved for the M-projectively flat spacetime. For
example, “every proper CI in an Einstein space $(R\neq 0)$ is a proper conf M
with a conformal function $\varOmega$”given by Duggal [14] is obvious in the
M-projectively flat spacetime.

##  3\. Curvature Inheritance in M- Projectively flat perfect fluid spacetimes

In a perfect fluid spacetime,

$T_{ij}=(\mu+p)u_{i}u_{j}+pg_{ij},$ (3.1)

where the symbols are explained after equation (1.3). On contraction of (2.6),
we obtain

$T=\frac{1}{\kappa}(4\wedge-R)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}or~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}R=(4\wedge-\kappa
T),$ (3.2)

and contraction of equation (3.1), leads to

$T=(3p-\mu).$ (3.3)

Use of equations (3.2) and (3.3), yields

$R=[4\wedge+(\mu-3p)\kappa].$ (3.4)

Next, we use a dynamic result for a perfect fluid spacetime along a conformal
Killing vector field $\xi^{i}$, consider the equation [14]

$\pounds_{\xi}\mu=-2\square\varOmega-2\varOmega\mu-2\varOmega_{;ij}u^{i}u^{j},$
(3.5)

where $\square\varOmega=-\frac{1}{3}\varOmega R$ and
$\varOmega_{;ij}=-\frac{1}{3}\varOmega R_{ij}$. In a perfect fluid spacetime,
comparing with EFEs (1.2) and equation (3.1) with the condition
$u_{i}u^{i}=-1$, we get

$R_{ij}u^{i}u^{j}=(\kappa\mu-\frac{R}{2}+\wedge)=[\kappa(\frac{3p+\mu}{2})-\wedge].$
(3.6)

If we set

$\varOmega_{;ij}=\frac{\varOmega}{2}[\frac{R}{3}g_{ij}-2R_{ij}],$ (3.7)

then from [14], every CIV is also a CKV in an M- projectively flat spacetime.
If we multiply both sides by $u^{i}u^{j}$ in (3.7), using equation (3.6) and
$u^{i}$ to be timelike then we obtain

$\varOmega_{;ij}u^{i}u^{j}=\varOmega(\frac{R}{3}-\kappa\mu-\wedge)=-\frac{\varOmega}{3}[(2\mu+3p)\kappa-\wedge].$
(3.8)

Now using $\square\varOmega=-\frac{1}{3}\varOmega R$ and (3.8) in (3.5), we
get

$\pounds_{\xi}\mu=2\varOmega[(\kappa-1)\mu+\wedge].$ (3.9)

Next, we find $\pounds_{\xi}p$ in M- projectively flat spacetime as follows:

$\pounds_{\xi}p=\frac{4}{3}\square~{}\varOmega-2\varOmega
p-\frac{2}{3}\varOmega_{;ij}u^{i}u^{j}.$ (3.10)

By using $\square\varOmega=-\frac{1}{3}\varOmega R$ and (3.8) in (3.10), we
get

$\pounds_{\xi}p=2\varOmega[(\kappa-1)p-\wedge].$ (3.11)

Thus, we have the following result

######  Theorem 3.1.

If an M-projectively flat spacetime $(V_{4},g)$ with perfect fluid holds EFEs
with a cosmological constant admits the curvature inheritance symmetry along a
vector field $\xi$, then we have the following

$(a)~{}~{}~{}\pounds_{\xi}\mu=2\varOmega[(\kappa-1)\mu+\wedge]$
$(b)~{}~{}~{}\pounds_{\xi}p=2\varOmega[(\kappa-1)p-\wedge].$

Consider the following special cases:

$\mathbf{Case~{}1:}$ Under the hypothesis of Theorem 3.1, if $(V_{4},g)$ is a
perfect fluid hold the EFEs without a cosmological term (i.e. $\wedge$ = 0),
then we have the following inheritance equations

$(a)~{}~{}~{}\pounds_{\xi}\mu=2\varOmega(\kappa-1)\mu,$ (3.12)
$(b)~{}~{}~{}\pounds_{\xi}p=2\varOmega(\kappa-1)p.$ (3.13)

$\mathbf{Case~{}2:}$ Under the hypothesis of Theorem 3.1, if $(V_{4},g)$ is a
perfect fluid spacetime satisfying the EFEs without a cosmological term (i.e.
$\wedge$ = 0 and $\kappa=1$ ), then we have the following equations

$(a)~{}~{}~{}\pounds_{\xi}\mu=0,$ (3.14) $(b)~{}~{}~{}\pounds_{\xi}p=0.$
(3.15)

A spacetime $(V_{4},g)$ inherits symmetry along a homothetic vector field
$\xi$, if the following equations hold for a perfect fluid:

$(a)~{}~{}~{}\pounds_{\xi}\mu=2\varOmega\mu$
$(b)~{}~{}~{}\pounds_{\xi}p=2\varOmega p$
$(c)~{}~{}~{}\pounds_{\xi}u^{i}=2\varOmega u^{i}$.

Recently, the interest of many researcher has increased towards the study of
the spacetime symmetry inheritance along a conformal Killing vector field
$\xi$. Coley and Tupper [12] have worked on special CKV. Now, it will be
demonstrated that how the Theorem 3.1 is used to change the symmetry equations
(3.12) and (3.13) for a curvature inheritance vector field in an
M-projectively flat spacetime. Therefore, consider a conformal Killing vector
field $\xi$, such that from [13]

$\pounds_{\xi}u^{i}=2\varOmega u^{i}+v^{i}$ (3.16)

where $v^{i}$ is a spacelike vector orthogonal to $u^{i}$. Einstein field
equations (1.2) for a perfect fluid, with (3.1), imply that $u^{i}$
eigenvector of $R_{ij}$, and $u^{i}u_{i}=-1$

$R_{ij}u^{j}=[-\kappa(\frac{3p+\mu}{2})+\wedge]u_{i}.$ (3.17)

If $\xi$ is the curvature inheritance vector or Ricci inheritance vector, then
using (3.17) in (3.7), we get

$\varOmega_{;ij}u^{i}u^{j}=-\frac{\varOmega}{3}[(2\mu+3p)\kappa-\wedge].$
(3.18)

Using the above equation in $(\mu+p)v_{i}$ =
$2[\varOmega_{;ij}u^{j}+(\varOmega_{;kl}u^{k}u^{l})u_{i}]$, we find that
$v_{i}$ = 0 for $(\mu+p)$ $\neq$ 0\. Then, equation (3.16) reduces to

$\pounds_{\xi}u^{i}=2\varOmega u^{i}.$ (3.19)

The calculation of equations (3.12), (3.13) and (3.19) can be summarized in
the following theorems.

######  Theorem 3.2.

If an M-projectively flat spacetime with a perfect fluid obeying the Einstein
field equations without a cosmological term admits a curvature inheritance
symmetry along the vector field $\xi$, then symmetry with respect to $\xi$ is
inherited by the spacetime.

######  Theorem 3.3.

Let $(V_{4},g)$ be an M-projectively flat spacetime with a perfect fluid
obeying the Einstein field equation and admitting curvature inheritance
symmetry along vector field $\xi$. If the perfect fluid denotes radiation era
or stiff matter then this spacetime does not contain the cosmological
constant.

###### Proof.

Let us assume that the perfect fluid denotes the radiation era, i.e.,
$\mu=3p$. By taking the Lie derivative of this equation and using (3.9) and
(3.11), we can see that $\wedge$ = 0. Similarly, if the perfect fluid denotes
stiff matter, i.e., $\mu=p$, then we also get $\wedge=0$. This completes the
proof. ∎

######  Theorem 3.4.

Let $(V_{4},g)$ be an M-projectively flat spacetime with a perfect fluid
obeying the Einstein field equations and admitting curvature inheritance
symmetry along vector field $\xi$. If the Lie derivative of $(\mu+p)$ is zero,
then either the matter content of the spacetime satisfying the vacuum-like
equation of state or $(\mu+p)$ is constant.

###### Proof.

By using (3.9) and (3.11), we get

$\pounds_{\xi}(\mu+p)=\pounds_{\xi}\mu+\pounds_{\xi}p=0.$ (3.20)

Finally, we can say that either the matter content of the spacetime satisfy
the vacuum like equation of state or $(\mu+p)$ is constant. Thus, the proof is
completed. ∎

##  4\. Equation of State

Let $(V_{4},g)$ be an M-projectively flat spacetime admitting curvature
inheritance along a vector field $\xi$. From Corollary 2.4, $\xi$ is a CKV,
satisfying the following equation

$(\xi^{j}R_{ij})_{;i}=-3\square\psi.$ (4.1)

Using Einstein field equations, (4.1) leads to

$([kT^{ij}-(\wedge-\frac{R}{2})g^{ij}]\xi_{j})_{;i}=-3\square\psi.$ (4.2)

As $-3\square\psi=\alpha R$, therefore

$([kT^{ij}-(\wedge-\frac{R}{2})g^{ij}]\xi_{j})_{;i}=\alpha R.$ (4.3)

Further, for the perfect fluid spacetime with (3.1), we have

$[kp-\wedge+\frac{R}{2}]\xi^{i}_{;i}=\alpha R.$ (4.4)

Equation (4.4), on substitution $\xi^{i}_{;i}$ = $4\alpha$ reduces to

$4(kp-\wedge)=-R.$ (4.5)

Here $\xi$ is CKV. For an M-projectively flat spacetime, the scalar curvature
$R=4\wedge-k(3p-\mu)$. Now comparing with (4.5), we have

$\mu+p=0,~{}~{}~{}~{}(k\neq 0)$ (4.6)

which may describe two cases (i) empty spacetime $\mu$ = $p$ =0 and (ii)
perfect fluid spacetime holding vacuum like equation of state.

Thus, we state the result as follows

######  Theorem 4.1.

Let an M-projectively flat spacetime with perfect fluid obeying the EFEs with
cosmological constant be admit curvature inheritance symmetry along a vector
field $\xi$. Then $(V_{4},g)$ is either a vacuum or satisfies the vacuum-like
equation of state.

From [27], we note that $\mu+p=0$ implies that scalar curvature is equal to
cosmological constant and Ojha [23] termed this as Phantom Barrier. Alan Guth
in 1981 proposed the idea of cosmic inflation [17], and explained the similar
conditions for the same in the universe. Amendola and Tsujikawa [8] explained
the term inflation in their paper as rapid expansion of the spacetime that
might occurred just after the Big Bang. In the light of above discussion, we
have

######  Theorem 4.2.

Let a perfect fluid M-projectively flat spacetime $(V_{4},g)$ obeying the EFEs
with cosmological constant, admits curvature inheritance symmetry along a
vector field $\xi$. Then $(V_{4},g)$ represents inflation.

From equations (3.1) and (4.6), we obtain

$T_{ij}=pg_{ij}.$ (4.7)

Since, an M-projectively flat spacetime is Einstein, thus it is of constant
scalar curvature. Further as $\wedge$ and $k$ are constants, therefore
equation (4.5) confirms that $p$ is constant. Hence $\mu=-p$ is also constant.
This condition has a special significance in the physics of spacetime. With
this condition, the fluid starts behaving like a cosmological constant [27],
which is also called Phantom Barrier [10]. This causes inflation of the
universe [8].

Thus, we obtain the following theorem:

######  Theorem 4.3.

The isotropic pressure and energy density of an M-projectively flat perfect
fluid spacetime satisfying EFEs with cosmological constant admitting the
curvature inheritance symmetry along a vector field $\xi$ are constants.

##  5\. A Purely Electromagnetic Distribution Admitting Curvature Inheritance
Symmetry

Section $5$ is devoted to the study of few results for purely electromagnetic
distribution. Contraction of (4.7), provides

$T=4p.$ (5.1)

Using the equations (5.1) and (3.3), we get $p$ = $-\mu$ = $\frac{T}{4}.$ Now
since for a purely electromagnetic distribution, $T=0$. We have $p$ = $\mu$ =
0, in other words “In a purely electromagnetic distribution, the isotropic
pressure and the energy density of a perfect fluid spacetime satisfying
Einstein field equations with cosmological constant vanish.”

Putting $\mu$ = $p$ = 0 in (3.1), we get $T_{ij}$ = 0. This implies that the
spacetime is vacuum. Taking contraction of (1.2), we get

$R=4\wedge-kT,$ (5.2)

substituting (5.2) in EFEs (1.2) and for purely electromagnetic distribution,
we get

$R_{ij}=\wedge~{}g_{ij}.$ (5.3)

If M-projectively flat perfect fluid spacetime $(V_{4},g)$ admits curvature
inheritance symmetry along $\xi$. Then Lie derivative of equation (5.3) leads
to a conformal motion. Thus, we may state the following result:

######  Theorem 5.1.

Th curvature inheritance symmetry in an M-projectively flat perfect fluid
spacetime for a purely electromagnetic distribution, which satisfies EFEs with
a cosmological term is conformal motion.

In this case, we choose Einstein field equations without cosmological constant
takes the form

$R_{ij}-\frac{R}{2}g_{ij}=k~{}T_{ij}.$ (5.4)

Contracting (5.4) we get

$R=-kT.$ (5.5)

For purely electromagnetic distribution $T$ = 0, (5.5) reduces to $R$ = 0.
Therefore, from (2.3), we obtain

$R^{h}_{ijk}=0.$ (5.6)

This implies that $(V_{4},g)$ is an Euclidean space. Thus, we have the
following result:

######  Corollary 5.1.

In a purely electromagnetic distribution, an M-projectively flat perfect fluid
spacetime $(V_{4},g)$ satisfying EFEs without a cosmological constant does not
admit any curvature symmetry.

##  6\. Example of an M-Projectively Flat Spacetime

Let $\mathbb{R}^{4}$ be equipped with the following metrics in terms of
coordinates $x^{1}$, $x^{2}$, $x^{3}$ and $x^{4}$ given as follows:

$ds^{2}=-(dx^{1})^{2}+e^{x^{1}}[(dx^{2})^{2}+(dx^{3})^{2}+(dx^{4})^{2}],$
(6.1) $ds^{2}=(dx^{1})^{2}+e^{x^{1}}[(dx^{2})^{2}+(dx^{3})^{2}+(dx^{4})^{2}].$
(6.2)

We note that the metric in (6.1) (resp. (6.2)) is a Lorentzian (resp.
Riemannian) metric.
$)ofthemetric\eqref{6.1}aregivenby$$\begin{array}[]{c}\Gamma^{2}_{12}=\Gamma^{3}_{13}=\Gamma^{4}_{14}=\frac{1}{2},\
\Gamma^{1}_{22}=\Gamma^{1}_{33}=\Gamma^{1}_{44}=\frac{e^{x^{1}}}{2}.\end{array}$$\par\indent
Thenon-vanishingcomponentsoftheRiccitensor$R_ij$andRiemann-
Christoffelcurvaturetensor$R_hijk$ofthemetric\eqref{6.1}aregivenby\par$$\begin{array}[]{c}R_{1212}=R_{1313}=R_{1414}=-\frac{e^{x^{1}}}{4},\
R_{2323}=R_{2424}=R_{3434}=\frac{e^{2x^{1}}}{4},\end{array}$$\begin{array}[]{c}R_{11}=\frac{3}{4},\
\par R_{22}=R_{33}=R_{44}=-\frac{3e^{x^{1}}}{4}.\\\ \end{array}$$\par
Also,forthemetric\eqref{6.1},thescalarcurvatureis$R=-3$.ItiseasytocomputethatallthecomponentsoftheM-
projectivecurvaturetensorarezero.Thuswehavethefollowingresult:\par\par\begin{theorem}Let$\mathbb{R}^{4}$beequippedwiththeLorentzianmetricgivenin\eqref{6.1},then$(\mathbb{R}^{4},g)$isanM-
projectivelyflatspacetime.\end{theorem}\par\begin{remark}Wenotethat$(\mathbb{R}^{4},g)$endowedwiththeRiemannianmetric\eqref{6.2}isalsoM-
projectivelyflat.\end{remark}\par\begin{remark}Wementionthatthemetrics\eqref{6.1}and\eqref{6.2}arewarpedproduct$M_{1}\times_{f}M_{2}$,wherethewarpingfunction$f=e^{x^{1}}$with$1$-dimensionalbase$M_{1}$and$3$-dimensionalfibre$M_{2}$.\end{remark}\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\thebibliography\lx@bibitem{Abdussattar
and B Dwivedi}Abdussattar,D.andDwivedi,B.,{\it
Fluidspacetimesandconharmonicsymmetries},J.Math.Phys.\textbf{39(6)}(1998),3280
--3295.\par\lx@bibitem{Ahsan}Ahsan,Z.,{\it
Onageometricalsymmetryofthespacetimeofgeneralrelativity},Bull.Cal.Math.Soc.\textbf{97(3)}(2005),191
--200.\par\lx@bibitem{ZAhsan1}Ahsan,Z.andAli,M.,{\it
Curvaturetensorforthespacetimeofgeneralrelativity},Int.J.ofGeom.MethodsMod.Phys.\textbf{14(5)}(2017),1750078-1(13pages).\par\lx@bibitem{ZAhsan2}Ahsan,Z.andAli,M.,{\it
Quasi-
conformalcurvaturetensorforthespacetimeofgeneralrelativity},PalestineJ.Math.\textbf{4(1)}(2015),233
--240.\par\lx@bibitem{ZAhsan3}Ahsan,Z.andSiddiqui,S.A.,{\it
Concircularcurvaturetensorandfluidspacetimes},Int.J.Theoret.Phys.\textbf{48}(2009),3202
--3212.\par\par\lx@bibitem{AliM}Ali,M.,Salman,M.andBilal,M.,{\it
Conharmoniccurvatureinheritanceinspacetimeofgeneralrelativity},Universe\textbf{7}(505)(2021),1
--
21(21pages).\par\lx@bibitem{Zahsan12}Ali,M.,Pundeer,N.A.,Ahmad,N.andAhsan,Z.,{\it
Semiconformalsymmetr:Anewsymmetryonthespacetimemanifoldofgeneralrelativity},J.Math.Comp.Sci.\textbf{20(3)}(2020),214
--254.\par\lx@bibitem{LS}Amendola,L.andTsujikawa,S.,{\it
DarkEnergy:Theoryandobservations},Cambridgeuniv.press,Cambridge,\textbf{2010}.\par\par\par\lx@bibitem{Besse}Besse,A.L.,{\it
Einsteinmanifolds},Ergeb.Math.Grenzgeb.,3.Folge,Bd.10.Berlin,Heidelberg,NewYorkSpringer-
Verlag,\textbf{1987}.\par\lx@bibitem{SNR}Chakraborty,S.,Mazumder,N.andBiswas,R.,{\it
Cosmologicalevolutionacrossphantomcrossingandthenatureofthehorizon},Astrophys.SpaceSci.Libr.{\bf
334}(2011),183--186.\par\par\lx@bibitem{SKRH}Chaubey,S.K.andOjha,R.H.,{\it
OntheM-
projectivecurvaturetensorofaKenmotsumanifold},Differ.Geom.Dyn.Syst.\textbf{12}(2010),52
--60.\par\lx@bibitem{AA Coley}Coley,A.A.andTupper,B.O.J.,{\it
SpecialconformalKillingvectorspacetimesandsymmetryinheritance},J.Math.Phys.\textbf{30}(1989),2615
--2619.\par\lx@bibitem{klduggal2}Duggal,K.L.,{\it
Relativisticfluidswithshearandtimelikeconformalcollineations},J.Math.Phys.\textbf{28(11)}(1987),2700
--2704.\par\lx@bibitem{Duggal}Duggal,K.L.,{\it
CurvatureinheritancesymmetryinRiemannianspaceswithapplicationstofluidspacetimes},J.Math.Phys.\textbf{33(9)}(1992),2989
--2997.\par\lx@bibitem{K.L.DuggalandR.Sharma}Duggal,K.L.andSharma,R.,{\it
SymmetriesofspacetimesandRiemannianmanifolds},KluwerAcademicPress,TheNetherlands,\textbf{1999}.\par\par\par\lx@bibitem{Eishart}Eisenhart,L.P.,{\it
RiemannianGeometry},PrincetonUniversityPress,Princeton,N.J.,\textbf{1926}.\par\par\lx@bibitem{Guth}Guth,A.H.,{\it
Inflationaryuniverse:Apossiblesolutiontothehorizonandflatnessproblems},CarnegieObservatoriesAstrophysicsSeries,Vol.2,MeasuringandModelingtheUniverse,CambridgeUniv.Press,Cambridge,\textbf{1981}.\par\lx@bibitem{hall}Hall,G.S.,{\it
Symmetriesandcurvaturestructureingeneralrelativity},WorldScientificPublishingCo.Ltd.,Singapore,\textbf{2004}.\par\par\lx@bibitem{Katzin}Katzin,G.H.,Levine,J.andDavis,W.R.,{\it
Curvaturecollineation:AfundamentalsymmetrypropertyofthespacetimeofgeneralrelativitydefinedbythevanishingLiederivativeoftheRiemanniancurvaturetensor},J.Math.Phys.\textbf{10(4)}(1969),617
--629.\par\par\lx@bibitem{Shyam}Kishor,S.andVerma,P.,{\it CertainresultsonM-
projectivecurvaturetensoron$(k,\mu)$-contactspaceforms},PalestineJ.Math.\textbf{11(1)}(2022),531
--540.\par\par\lx@bibitem{Mantica1}Mantica,C.A.andSuh,Y.J.,{\it Pseudo-
Zsymmetricspace-
times},J.Math.Phys.\textbf{55(4)}(2014),042502-1(12pages).\par\lx@bibitem{RH2}Ojha,R.H.,{\it
M-projectivelyflatSasakianmanifolds},IndianJ.PureAppl.Math.\textbf{17(4)}(1986),481
--484.\par\lx@bibitem{RH1}Ojha,R.H.,{\it AnoteontheM-
projectivecurvaturetensor},IndianJ.PureAppl.Math.\textbf{ 8(12)}(1975),1531--
1534.\par\lx@bibitem{GPPokh}Pokhariyal,G.P.andMishra,R.S.,{\it
Curvaturetensorsandtheirrelativisticsignificance},YokohamaMath.J.\textbf{19(2)}(1971),97
--103.\par\par\par\lx@bibitem{Shaikh2003}Shaikh,A.A.andBiswas,S.,{\it OnM-
projectivelyrecurrentSasakianmanifolds},SouthEastAsianJ.ofMath.andMath.Sci.\textbf{2(1)}(2003),61
--
65.\par\par\par\par\par\lx@bibitem{Shanmukha}Shanmukha,B.andVenkatesha,V.,{\it
M-projectivecurvaturetensoronan$(LCS)_{2n+1}$manifold},J.Appl.Anal.\textbf{27(2)}(2021),283
--
288.\par\par\lx@bibitem{KarmerD}Stephani,H.,Kramer,D.,McCallum,M.andHerlt,E.,{\it
ExactsolutionsofEinstein’sfieldequations},CambridgeUniv.Press,2ndedn.,\textbf{2003}.\par\lx@bibitem{Venkatesha}Venkatesha,V.andSumangala,B.,{\it
OnM-
projectivecurvaturetensorofageneralizedSasakianspaceform},ActaMath.Univ.Comenian.\textbf{82(2)}(2013),209
--217.\par\lx@bibitem{yanoK}Yano,K.,{\it ThetheoryofLie-
derivativesanditsapplications},North-
HollandPubl.Co.,Amsterdam,\textbf{1957}.\par\lx@bibitem{Zengin1}Zengin,F.\"{O}.,{\it
M-projectivelyflatspacetimes},Math.Rep.\textbf{4}(2012),363--
370.\par\lx@bibitem{Zengin2}Zengin,F.\"{O}.,{\it OnM-projectivelyflatLP-
Sasakianmanifolds},UkrainianMath.J.\textbf{65}(2014),1725--
1732.\par\par\par\par\par\par\par\par\endthebibliography\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par$


# On Preemptive Scheduling of Unrelated Machines Using Linear Programming

Nodari Vakhania

###### Abstract

We consider a basic problem of preemptive scheduling of $n$ non-simultaneously
released jobs on a group of $m$ unrelated parallel machines so as to minimize
maximum job completion time, the makespan. In the scheduling literature, the
problem is commonly considered to be solvable in polynomial time by linear
programming (LP) techniques proposed in Lawler and Labetoulle [4]. The authors
in [4] give a LP formulation of the version with simultaneously released jobs
and show how an optimal solution to this LP can be used to construct an
optimal schedule to the latter problem. They also give a linear programming
formulation of a related problem for non-simultaneously released jobs with the
objective to minimize the maximum job lateness, and show how an optimal
solution to this LP problem can be used to construct an optimal solution for
non-simultaneously released jobs to minimize the maximum job lateness. As the
current study shows, for non-simultaneously released jobs, unlikely, there
exist a linear program such that a schedule with the minimum makespan can be
constructed based on an optimal LP solution. We also prove that, in case no
splitting of the same job on a machine is allowed (i.e., job part assigned to
a machine is to be processed without an interruption on that machine), the
problem is NP-hard. As a side result, we obtain that, whenever job splitting
is not allowed, given an optimal LP solution, it is NP-hard to find an optimal
schedule with the minimum makespan that agrees with that LP solution. As
another side result, we obtain that it is NP-hard to find an optimal schedule
with at most $m-1$ preemptions if jobs are released non-simultaneously. We
also present two positive results. First, we construct an optimal schedule in
a low degree polynomial time in case an optimal solution to a modified LP
formulation that we propose already possesses “enough” amount of integer
components so that it yields no more than $m$ preempted jobs parts. We also
propose a stronger mixed integer linear program formulation. Finally, we
extend the schedule construction procedure based on an optimal LP solution
from Lawler and Labetoulle [4] for non-simultaneously released jobs. The
extended procedure, among all feasible schedules that agree with any feasible
(not necessarily optimal) LP solution, generates one with the minimum
makespan. Such procedure is helpful, in particular, because, as we show, there
may exist no optimal schedule that agrees with an optimal LP solution if jobs
are non-simultaneously released.

Keywords: Scheduling, unrelated machines, release time, linear programming,
time complexity

##  1 Introduction

Scheduling unrelated machines to minimize the maximum job completion time is a
well-known optimization problem. In a group of unrelated machines, a machine
$i$ has no universal speed characteristic (machine speed is job dependent), in
contrast to a group of uniform machines, where each machine is characterized
by a universal speed that extends to a whole set of jobs. A group of machines
with the same speed is commonly referred to as a group of identical machines
(the speed of every machine is the same for every job). In the scheduling
problem that we consider here, commonly abbreviated as
$R|r_{j};pmtn|C_{\max}$, there are $n$ jobs to be performed by $m$ parallel
unrelated machines. Job $j$ becomes available at its (integer) release time
$r_{j}$ and it requires an (integer) processing time $p_{ij}$ on machine $i$,
$i=1,\dots,m$ (for the sake of simplicity, we will refer to jobs and machines
by their corresponding indexes). A job, being processed by a machine, can be
interrupted and resumed later on the same or on any other machine. In a
feasible schedule a machine can process at most one job at a time and a job
can be processed by at most one machine at a time, every job $j$ is assigned
to a machine no earlier than at time $r_{j}$ and it is completely processed,
i.e., $\sum_{i=1}^{m}t_{ij}/p_{ij}=1$, where $t_{ij}$ is the total amount of
time that machine $i$ spends on job $j$ in that schedule. The objective is to
find an optimal schedule, a feasible one in which the maximum job (machine)
completion time $C_{\max}$ is the minimum possible.

In the scheduling literature, this classical scheduling problem is commonly
considered to be solvable in polynomial time by linear programming technique
from Lawler and Labetoulle [4] (we refer the reader to publicly accessible
sources [9] and [10]). Lawler and Labetoulle [4] proposed a linear programming
formulation for the version of the above described problem without job release
times, and have adopted an open shop scheduling method of Gonzalez and Sahni
[2] for the construction of an optimal schedule for that version of the
problem based on an optimal LP solution. A feasible LP solution determines
which part of each job is to be processed by each machine, i.e., it
distributes job parts to machines without specifying particular starting time
of job part(s) on the corresponding machine(s). Hence, a scheduling stage
identifying start time of every job part on the corresponding machine is
required to transform such distribution to a feasible schedule.

It is commonly accepted that scheduling problems with non-simultaneously
released jobs are considerably more difficult to solve than the corresponding
versions with simultaneously released jobs (it is a typical scenario that a
polynomially solvable scheduling problem with simultaneously released jobs
becomes NP-hard if jobs are released non-simultaneously at arbitrary times). A
distribution to linear program considered in Lawler and Labetoulle [4]
“implicitly assumes” that job parts can be assigned to the machines at any
time moment. This does not apply in case the jobs are non-simultaneously
released. Such a “lack of information” essentially complicates the use an
optimal fractional LP solution for the construction of an optimal preemptive
schedule for non-simultaneously released jobs. We suggest two alternative
linear programs for problem $R|r_{j};pmtn|C_{\max}$ that are more “flexible”
since they take somehow into account job release times. The second LP, is
however, a mixed integer linear program. Even the latter LP is not strong
enough in the sense that an optimal schedule not necessarily agrees with an
optimal distribution generated for that LP. In fact, there may exist no
optimal schedule that agrees with any optimal distribution to any of the
linear programs that we consider here. Moreover, as we argue, unlikely, there
exists a “strong enough” linear program such that an optimal solution to that
linear program can be used for the construction of an optimal schedule to
problem $R|r_{j};pmtn|C_{\max}$ with non-simultaneously released jobs. If
however, an optimal solution to a modified LP formulation that we propose,
possesses “enough” amount of integer components (so that it yields no more
than $m$ preempted jobs parts), then an optimal schedule can be constructed in
a low degree polynomial time based on this optimal LP solution, as we show in
Section 4. We also extend the schedule construction procedure based on an
optimal LP solution of Lawler and Labetoulle [4] for non-simultaneously
released jobs. The extended procedure, among all feasible schedules that agree
with any feasible (not necessarily optimal) LP solution, generates one with
the minimum makespan. The extended procedure is helpful, in particular,
because any optimal schedule may only agree with a non-optimal LP solution if
jobs are non-simultaneously released. As this study shows, for non-
simultaneously released jobs, unlikely, there exist a linear program such that
a schedule with the minimum makespan can be constructed based on an optimal
solution to that linear program.

We also give NP-hardness results. In particular, if no splitting of the same
job on a machine is allowed (i.e., job part assigned to a machine is to be
processed without an interruption on that machine), then we show that the
problem with non-simultaneously released jobs is NP-hard. As a side result, we
obtain that, whenever job splitting is not allowed, given an optimal LP
solution, it is NP-hard to find an optimal schedule with the minimum makespan
that agrees with that LP solution. As another side result, we obtain that it
is NP-hard to find an optimal preemptive schedule with at most $m-1$
preemptions. This result somehow extends an earlier known fact that scheduling
identical machines with at most $m-2$ preemptions, even for simultaneously
released jobs, is NP-hard [8].

We complete this section by a very brief look at a few earlier known related
results. Non-preemptive scheduling on identical machines of simultaneously
released jobs $P||C_{\max}$ is already NP-hard. This is in contrast to the
preemptive case, even on a group of uniform machines $Q|pmtn|C_{\max}$, for
which a low-degree polynomial time algorithm is known Gonzalez and Sahni [1].
The setting with non-simultaneously released jobs $Q|r_{j},pmtn|C_{\max}$
remains polynomially solvable Labetoulle et al. [3], as well as the version
with unrelated machines but simultaneously released jobs $R|pmtn|C_{\max}$
Lawler and Labetoulle [4]. As already noted, the authors in [4] give a linear
programming formulation of the problem and show how an optimal solution to
this LP can be used to construct an optimal solution to the latter problem.
Lawler and Labetoulle [4] also give a linear programming formulation of a
related problem $R|pmtn|L_{\max}$ where the objective is to minimize the
maximum job lateness $L_{\max}$ (the lateness $L_{j}$ of job $j$ in schedule
$S$ is the difference between the completion time of that job in that schedule
and its due-date $d_{j}$, a “desirable” completion time for that job, and
$L_{\max}$ is the maximum job lateness). This formulation allows to use their
schedule construction procedure to generate an optimal schedule to that
problem.

##  2 Alternative linear programs

In this section we present linear programs that have been used for scheduling
unrelated machines. The following linear program LP1$(C_{\max})$ was
successfully used for an approximate solution of the non-preemptive version of
the problem $R||C_{\max}$ with simultaneously released jobs first by Potts [6]
and later in [7]:

Minimize $C_{\max}$
Subject to
$\sum\limits_{j=1}^{n}x_{ij}p_{ij}\leq C_{\max},\ \ i=1,\dots,m$
$\sum\limits_{i=1}^{m}{x_{ij}}=1,\ \ j=1,...,n$
$x_{ij}\geq 0,\ \ \ i=1,...,m,\ \ j=1,\dots,n.$

In this linear program entry $x_{ij}=t_{ij}/p_{ij}$ represents the part of job
$j$ to be processed by machine $i$, for $j=1,\dots,n$ and $i=1,\dots,m$. These
entries define the corresponding distribution of job parts on machines. Unlike
a schedule which is a mapping that assigns to each job specific time
interval(s) on one or more machines, a distribution, instead of these time
intervals, defines only their lengths on the corresponding machines. Because
of real assignment variables, a distribution may split a job in different
parts and assign these parts to different machines. Note that a distribution
involves no start times and only assigns job parts to machines (hence, there
is an infinite number of feasible schedules respecting a given distribution).
In particular, a solution to a linear program is a distribution that
explicitly indicates which fraction of each job is assigned to each machine.
We refer the reader to [7] for related formal definitions, concepts and
properties.

A distribution to linear program $LP1(C_{\max})$ has a nice property that it
possesses a large amount of integer (zero) entries so that it yields at most
$m-1$ preempted jobs. Then such distribution can be rounded to (an integer)
feasible approximate non-preemptive solution to problem $R||C_{\max}$, as
suggested by Potts [6], where a complete enumeration of at most $m-1$
preempted jobs on $m$ machines is carried out. This results in a
2-approximation solution in time, polynomial in $n$ and exponential in $m$.
Using a modified linear program combined with a binary search, a rounding that
guarantees a 2-approximation solution in polynomial (in both $n$ and $m$) time
was achieved in Lenstra et al. [5]. A new method of rounding an optimal
distributionmto linear program $LP1(C_{\max})$ proposed in [7] yielded an
improvement of the bound 2 to $2-1/m$. This latter bound is the best possible
that can be obtained by rounding a distribution to a feasible non-preemptive
schedule.

In an optimal distribution to linear program LP1$(C_{\max})$, the total length
of the parts of a job assigned to the machines can be longer than the
minimized magnitude $C_{\max}$. Hence, such distribution is inappropriate for
the preemptive case $R|pmtn|C_{\max}$. Linear program LP2$(C_{\max})$ which
bounds the length of the assigned parts of each job was studied in Lawler and
Labetoulle [4]. This linear program requires an additional set of $n$
restrictions (2) (one additional restriction for each job):

Minimize $C_{\max}$
Subject to

$\sum\limits_{j=1}^{n}x_{ij}p_{ij}\leq C_{\max},\ \ i=1,\dots,m$ (1)
$\sum\limits_{i=1}^{m}x_{ij}p_{ij}\leq C_{\max},\ \ j=1,\dots,n$ (2)

$\sum\limits_{i=1}^{m}{x_{ij}}=1,\ \ j=1,...,n$
$x_{ij}\geq 0,\ \ \ i=1,...,m,\ \ j=1,\dots,n.$

Because of these additional $n$ restrictions (2), the total number of basic
(non-zero) variables is no more bounded by $m-1$ (in case an optimal
distribution to linear program LP2$(C_{\max})$ still yields no more than $m-1$
preemptions, it can easily be transformed to an optimal preemptive schedule
with at most $m-1$ preemptions, see Section 4). If an optimal distribution to
linear program $LP2(C_{\max})$ yields more than $m$ preempted job parts, an
optimal schedule to problem $R|pmtn|C_{\max}$ can still be constructed in
polynomial time. Lawler and Labetoulle [4] adopted open shop scheduling
technique from Gonzalez and Sahni [2] for constructing an optimal feasible
schedule from an optimal distribution to linear program LP2$(C_{\max})$ (note
that an open shop instance can be already seen as a distribution). We describe
this method in more detail in Section 4.

Suppose we have a feasible schedule for an instance of problem
$R|pmtn|C_{\max}$ respecting an optimal distribution $\\{x_{ij}\\}$ to linear
program LP2$(C_{\max})$ with the makespan

$C_{\max}=\max\\{\max_{i}\sum\limits_{j=1}^{n}x_{ij}p_{ij},\max_{j}\sum\limits_{i=1}^{m}x_{ij}p_{ij}.\\}$
(3)

Then this schedule is clearly optimal. Such an optimal schedule is constructed
in Lawler and Labetoulle [4].

During the construction of the schedule in [4], job parts can be assigned to
machines at any time moment. Such an approach is not particularly useful if
the jobs are not simultaneously released. Such “lack of required restrictions”
questions the usefulness of an optimal fractional solution (an optimal
distribution) to a linear program for the construction of an optimal
preemptive schedule for problem $R|r_{j};pmtn|C_{\max}$. In particular, bound
(3) is no more attainable, i.e., for a given instance of problem
$R|r_{j},pmtn|C_{\max}$, there may exist no feasible schedule with makespan
$C_{\max}$ respecting a given optimal distribution to linear program
LP2$(C_{\max})$ (e.g., consider an optimal distribution in which the sum of
the job parts assigned to some machine is $C_{\max}$ but no job assigned to
that machine is released at time 0). Furthermore, no feasible schedule
respecting that optimal distribution might be optimal. This assertion is true
for linear program LP2$(C_{\max})$, and is also true for more enhanced linear
programs that we give later on.

##  3 NP-hardness results

Let $R|r_{j},pmtn\ -\ nosplit|C_{\max}$ denote the version of problem
$R|r_{j},pmtn|C_{\max}$ in which no job part assigned to a machine can be
split on that machine (it is to be processed continuously on that machine). No
splitting is a reasonable assumption in a number of applications where it is
undesirable to interrupt a currently running job on a machine in favor of
another job (such split would cause unreasonable amount of machine reset and
setup times).

###### Theorem 1

$R|r_{j},pmtn\ -\ nosplit|C_{\max}$ is NP-hard.

Proof. We show that the decision version of $R|r_{j},pmtn\ -\
nosplit|C_{\max}$ is NP-complete using the reduction from an NP-complete
PARTITION problem. Consider an arbitrary instance of this problem with $k$
items $\\{z_{1},\dots,z_{k}\\}$ and with $M=\sum_{i=1}^{k}z_{i}$. Let $P_{1}$
and $P_{2}$ be a partition of the $k$ items with $\sum_{l\in
P_{1}}z_{l}=\sum_{l\in P_{2}}z_{l}=M/2$, a solution to PARTITION ($P_{1}\cup
P_{2}=\\{z_{1},\dots,z_{k}\\}$, $P_{1}\cap P_{2}=\emptyset$).

Our scheduling instance consists of $4+k$ jobs on three machines, where
$Z_{1},\dots,Z_{k}$ are partition jobs. All partition jobs are released at
time 3. The processing times of these jobs are such that $p_{2Z_{j}}=2z_{j}/M$
and $p_{iZ_{j}}=\infty$, for $j=1,\dots,k$ and $i=1,3$ (note that the total
length of the partition jobs is $2$). The processing times of the remaining
four jobs are defined as follows. $p_{11}=p_{21}=p_{31}=6$, $p_{13}=2$,
$p_{24}=3$ and $p_{32}=5$. All the unspecified processing times are infinity
(large enough numbers). Job 3 is released at time 4 and the remaining jobs are
released at time 0 (except the partition ones which are released at time 3).

As it is easy to see, the processing time 6 of job 1 is a lower bound on the
optimal schedule makespan. In a schedule with this makespan (see Fig. 1):
On machine 1, job $J^{3}$ cannot be started earlier than at its release time 4
and can be completed at time 6, hence job 1 starts at its release time 0 and
competes at time 4. On machine 3, job $J^{2}$ is to occupy 5 time units.
Hence, only one time unit is left where job $J^{1}$ can be processed on that
machine. Therefore, one unit of time of job $J^{1}$ is to be processed on
machine 2. All partition jobs are to be processed also on machine 2. None of
the partition jobs can start earlier than at time 3 whereas job $J^{4}$ is to
occupy 3 time units on machine 2. Since machine 1 is running job $J^{1}$ in
interval $[0,4)$, job $J^{4}$ is needs to occupy the first 3 time units on
machine 2 and is to be followed by the partition jobs. Since the assigned to
machine 3 part of job $J^{2}$ cannot be interrupted on that machine, the
remaining unprocessed unit time of job $J^{1}$ can only be executed within the
interval $[4,5)$ on machine 2. Hence, exactly the intervals $[3,4)$ and
$[5,6)$ are left for the partition jobs.

Figure 1: An optimal schedule with makespan 6. Dark regions represent
partition jobs.

It should now be apparent that there exist a schedule of length 6 if and only
if the partition instance has a “yes” answer, i.e., there exists a partition
of set $\\{z_{1},\dots,z_{k}\\}$ into sets $P_{1}$ and $P_{2}$ with equal
length 1. In other words, an optimal schedule with makespan 6 provides a
solution to PARTITION, and vice-versa, if PARTITION has a solution then the
above optimal schedule can be constructed in polynomial time.

###### Corollary 1

Given an instance of problem $R|r_{j},pmtn|C_{\max}$, it is NP-hard to find an
optimal solution with at most $m-1$ preemptions.

Proof. By Theorem 1, $R|r_{j},pmtn\ -\ nosplit|C_{\max}$ is NP-hard. No split
on any machine yields at most $m$ preempted job parts (one job part on every
machine), hence at most $m-1$ preemptions.

###### Corollary 2

Given an optimal distribution, it is NP-hard to find a schedule for problem
$R|r_{j},pmtn\ -\ nosplit|C_{\max}$ with the minimum makespan respecting that
distribution.

Proof. From the proof of Theorem 1, the PARTITION instance is to be solved if
job $J^{2}$ is not allowed to be split on machine 3. The corollary follows as
the distribution respected by the schedule of Fig. 1 is optimal.

##  4 Scheduling little-preemptive distributions

In this section we show how an optimal schedule can be constructed in case an
optimal distribution to linear program LP2$(C_{\max})$ yields at most $m$
preempted job parts. We first consider the case of simultaneously released
jobs. Then we introduce a new liner program and consider the case when jobs
are not simultaneously released.

###  4.1 Simultaneously released jobs

Suppose an optimal distribution to linear program LP2$(C_{\max})$ yields no
more than $m-1$ preemptions, i.e., there are at most $m$ (preempted) job
parts, hence at most one such part on any machine. We can convert such
distribution to an optimal preemptive schedule for problem $R|pmtn|C_{\max}$
with at most $2m-4$ preemptions as follows. Sort the preempted jobs in non-
increasing order of their total processing times (the total processing time of
job $j$ in distribution $\\{x_{ij}\\}$ is
$\sum\limits_{i=1}^{m}x_{ij}p_{ij}$). Take the first job $j$ in the list and
consider its parts in the ascending order of the machine indexes to which
these parts are assigned. Let $i_{1}<\dots<i_{k}$ be these indexes (ones of
the corresponding machines). Schedule the first part of job $j$ at time 0 on
machine $i_{1}$, schedule the second part at the completion time of the first
part on machine $i_{2}$, and so on, schedule the last $k$th part at the
completion time of the preceding $(k-1)$th part on machine $i_{k}$. Due to
inequalities (2), the completion time of the last scheduled part of job $j$
cannot be larger than $C_{\max}$. Now take the second job in the list and
schedule its parts similarly, and so on. Since there is at most one preempted
job part on any machine, no conflicts between preempted parts of different
jobs will occur. The remaining entire job parts are scheduled in the remained
idle time slots from time 0 in any order without creating an idle time in
between the jobs. In case an overlapping of an entire part with an earlier
included preempted job part occurs, the entire job part is preempted and
resumed at the completion time of the latter preempted job part. Due to
inequalities (1), the makespan of the resultant feasible schedule will not
surpass $C_{\max}$. Note that no additional preemption will occur on any
machine on which a preempted job part is scheduled the first or the last on
that machine. In the worst case, there is only one preempted job distributed
among all the machines. Then $m-3$ additional preemptions will occur, hence
the $2m-4$ is an upper bound on the number of preemptions.

###  4.2 Non-simultaneously released jobs

First, let us modify linear program LP2$(C_{\max})$ by replacing inequalities
(2) with the following set of inequalities that take into account the release
time of each job:

$r_{j}+\sum\limits_{i=1}^{m}x_{ij}p_{ij}\leq C_{\max},\ \ j=1,\dots,n.$ (4)

The resultant new linear program LP3$(C_{\max})$ properly reflects the desired
restriction for each job.

Suppose now an optimal distribution to linear program LP3$(C_{\max})$ yields
no more than $m-1$ preemptions. The above described schedule construction
procedure for simultaneously released jobs can easily be extended for non-
simultaneously released jobs for problem $R|r_{j};pmtn|C_{\max}$. We again
consider job parts in ascending order of the corresponding machine indexes.
Now, instead of starting each first (according to this order) part of the next
job from the list at time 0, it is scheduled at the release time of that job.
The entire (non-preempted) jobs are scheduled in non-decreasing order of the
their release times on each machine. Due to the modified inequalities (4) (and
the fact that there is at most one preempted job part on any machine), again,
any of the preempted jobs will complete no later than at time $C_{\max}$.

##  5 “Weaknesses” of linear programs

For a given feasible schedule to an instance of the scheduling problem
$R|r_{j};pmtn|C_{\max}$ with makespan $C_{\max}$, let $\\{x_{ij}\\}$ be the
distribution that respects this schedule. The values $C_{\max}$ and
$\\{x_{ij}\\}$ form a feasible solution to linear programs LP3$(C_{\max})$ and
LP2$(C_{\max})$. A less obvious question is, given a distribution to linear
program LP3$(C_{\max})$, whether there is an optimal schedule respecting that
distribution with the makespan $C_{\max}$. If this assertion is true, then a
feasible schedule respecting an optimal distribution will be optimal.

Thus a feasible schedule respecting an optimal distribution is trivially
optimal if its makespan is $C_{\max}$. Lawler and Labetoulle [4] constructed
schedules respecting optimal distributions to linear program LP2$(C_{\max})$
with makespan is $C_{\max}$ for simultaneously released jobs. In contrary to
the case with simultaneously released jobs, an optimal schedule respecting an
optimal distribution to linear program LP3$(C_{\max})$ (and linear program
LP2$(C_{\max})$) not necessarily attains makespan $C_{\max}$ if jobs are non-
simultaneously released. In particular, inequalities (1) no more reflect
actual restrictions imposed by job release times on the completion time of
each machine, since it may not be possible to schedule a job assigned to a
machine at the earliest idle-time moment on that machine. In particular,
restrictions (1) are no more necessarily satisfied in an optimal schedule
where the completion time of a machine may be larger than $C_{\max}$ (recall
an earlier mentioned simple scenario where no job assigned to a machine is
released at time 0). Even restrictions (4) may not be satisfied in an optimal
schedule.

We illustrate these points on small problem instances in the following
examples. For none of these instances the procedure from Section 4.2 can
guarantee the construction of an optimal schedule with makespan $C_{\max}$.
Our examples illustrate that in an optimal schedule constructed from an
optimal distribution to linear program LP3$(C_{\max})$, neither restrictions
(1) nor restrictions (4) might be satisfied (the completion time of at least
one job in that schedule can be larger than $C_{\max}$). More importantly, a
bit later we will see that an optimal schedule not necessarily respects an
optimal distribution.

Example 1. Let us consider a problem instance where an optimal distribution
assigns just two different job parts to the same machine (hence the schedule
construction procedure from Section 4.2 already cannot be applied). We have
five jobs $2,\dots,6$ on four machines $1,\dots,4$ such that:
$r_{3}=3,\ r_{2}=2,\ r_{4}=8,\ r_{5}=0,\ r_{6}=5$.
$p_{13}=p_{33}=15$, $p_{22}=p_{32}=p_{42}=16$, and $p_{14}=p_{26}=p_{45}=13$.
The processing times of these jobs on the remaining machines are infinities
(large enough numbers). Note that in any feasible schedule, jobs 4, 6 and 5
can only be processed by machines 1,2 and 4, respectively. Job 2 is to be
distributed among machines 2,3 and 4, and job 3 is to be distributed on
machines 1 and 3.

(a) A non-feasible schedule respecting distribution 1

(b) A feasible schedule respecting distribution 1

(c) A non-feasible schedule respecting distribution 2

(d) A feasible schedule respecting distribution 2

(e) A globally optimal schedule that respects a non-optimal distribution 3

(f) A globally optimal schedule that respects a non-optimal distribution 4

Figure 2:

There are a few optimal distributions to linear program LP2$(C_{\max})$ with
$C_{\max}=18$. We consider two of them which assign (preempted) parts of jobs
3 and 2 to machine 3. In distribution 1, the processing times are as follows:
$t_{13}=5,\ t_{14}=13$, $t_{22}=4,\ t_{26}=13$, $t_{32}=8,\ t_{33}=10$ and
$t_{45}=13,\ t_{42}=4$.
Note that this is not an optimal distribution to linear program
LP3$(C_{\max})$ due to inequalities (4) where $C_{\max}=r_{4}+p_{14}=8+13=21$
is attained for job $4$. A non-feasible schedule respecting distribution 1 is
depicted in Fig. 2a, and an optimal schedule respecting the same distribution
with makespan 24 is depicted in Figure 2b.

An optimal distribution 2 is identical to distribution 1 except that
$t_{22}=5,\ \ t_{32}=6$ and $t_{42}=5$ (see Fig. 2c). An optimal schedule
respecting this distribution has the makespan 23, see Fig. 2d.

As can see, distribution 2 possesses better properties, so that an optimal
schedule respecting that distribution has a smaller makespan than an optimal
schedule respecting distribution 1. At the same time, none of these schedules
is (globally) optimal (see below). Moreover, one can easily verify that there
exists no optimal schedule respecting any optimal distribution to linear
program LP2$(C_{\max})$. (From here on we refer to a schedule with minimum
makespan respecting a given optimal distribution as an optimal schedule
respecting that distribution; such schedule, may not be (globally) optimal,
i.e., there may exist no optimal schedule respecting this distribution.
Moreover, there may exist no optimal schedule respecting any optimal
distribution.)

Now we consider a modification of the above considered distributions, a non-
optimal distribution 3 with $C_{\max}=20$, in which $t_{22}=5$, $t_{32}=4$,
$t_{42}=7$. A schedule with the makespan 21 respecting this distribution is
depicted in Fig. 2e. Distribution 3 is not optimal for linear program
LP2$(C_{\max})$ and it is not feasible to linear program LP3$(C_{\max})$
(e.g., $r_{4}+t_{14}=21>20$, see inequalities 4). It is easy to see that the
schedule of Fig. 2e is (globally) optimal.

In Fig. 2f another optimal schedule with the makespan 21 is depicted. This
schedule respects distribution 4 with $C_{\max}=21$, which is not optimal for
linear program LP2$(C_{\max})$ but it is (feasible and) optimal for linear
program LP3$(C_{\max})$ (due to inequalities (4), $C_{\max}=8+13=21$ is
attained for job $4$, and 21 is also the load of machine 4). However, this
schedule is not feasible for an instance of $R|r_{j},pmtn\ -\
nosplit|L_{\max}$. Distribution 4 differs from the above optimal distributions
on machines 3 and 4. Job processing times are distributed as follows:
$t_{13}=5,\ t_{14}=13$, $t_{22}=5,\ t_{26}=13$, $t_{32}=3,\ t_{33}=10$ and
$t_{45}=13,\ t_{42}=8$.

As we saw from the above example, optimal schedules respecting different
optimal distributions may have different makespan. “Guessing” an optimal
distribution and also a “suitable” linear program is an important and also
difficult task. Furthermore, as we argue in the next section, unlikely, there
exists a universal “suitable” linear program for the studied scheduling
problem, such that an optimal schedule respecting an optimal distribution to
that linear program can be guaranteed to be (globally) optimal. Below we give
a smaller problem instance illustrating similar points.

(a)

(b)

Figure 3: A non-feasible schedule respecting an optimal distribution (a) and
an optimal schedule (b)

Example 2. As another example, consider a smaller problem instance with four
jobs on two machines. Jobs 1 and 4 are released at times 3 and 1,
respectively, and jobs 2 and 3 are released behind these jobs at time, say 5,
i.e.,
$r_{1}=3,\ r_{2}=1$ and $r_{3}=r_{4}=5$.
Job processing times are as follows:
$p_{11}=9,\ p_{12}=\infty$, $p_{14}=\infty,\ p_{24}=10$, $p_{13}=p_{23}=3$ and
$p_{12}=p_{22}=2$.
An optimal distribution with $C_{\max}=12$ defines the processing times
$t_{11}=9,\ t_{13}=3$ and $t_{24}=10,\ t_{22}=2$. This distribution is optimal
for both linear programs LP2$(C_{\max})$ and LP3$(C_{\max})$. A non-feasible
schedule with makespan 12 respecting this distribution is depicted in Figure
3a, whereas an optimal feasible schedule with makespan 14 is depicted in
Figure 3b. The latter schedule respects another distribution with processing
times $t_{11}=9,\ t_{12}=2$ and $t_{24}=10,\ t_{23}=3$ (in which the roles of
jobs 2 and 3 are interchanged) and it is not optimal for linear programs
LP2$(C_{\max})$ and LP3$(C_{\max})$. The latter distribution is however
optimal for linear program MILP$(C_{\max})$ that we introduce in the next
section.

##  6 Another linear program

Linear program LP3$(C_{\max})$, although it properly reflects the desired
restriction for each job, it does not reflect actual restrictions imposed by
job release times on machine start times due to the nature of inequalities (1)
dealing with a mere sum of processing times of jobs assigned to each machine.
This causes potential conflicts while scheduling machines. In particular,
there may exist no optimal schedule to problem $R|r_{j};pmtn|C_{\max}$
respecting an optimal distribution to linear program LP3$(C_{\max})$. An
appropriate modification of restrictions (1) would require a kind of
“prediction” of an actual completion time of each machine given the job parts
assigned to this and other machines possessing parts of the same jobs. Such a
prediction however seems to be unrealistic since it would actually require the
outcome of scheduling process on each machine. Nevertheless, we may stall make
some assumptions on the scheduling strategy on each machine. In particular, we
easily observe that no avoidable gap is created on any machine in an optimal
schedule. It is easy to see that, among the job parts assigned to a machine,
the first included one corresponds to an earliest released job in an optimal
schedule. In general, whenever an idle time is unavoidable on a machine, an
earliest released job is scheduled immediately after that idle time on that
machine. However, in a liner program with these kind of restrictions the use
of Boolean variables seems to be unavoidable.

Define $nm$ 0-1 variables, $z_{ij}$ being 1 if a (non-empty) part of job $j$
is assigned to machine $i$, and 0 otherwise. Let, further, $J(>r)$ denote the
set of jobs having the release time no smaller than $r$. Then we can rewrite
$m$ constraints (1) into $nm$ constraints as follows.

$z_{ij}r_{j}+\sum\limits_{l\in J(>r)}x_{il}p_{il}\leq C_{\max},\ \ \
j=1,\dots,n,\ \ \ i=1,\dots,m$ (5)

By incorporating these restrictions instead of constraints (1) and introducing
additional $nm$ 0-1 constraints

$z_{ij}\in\\{0,1\\}$

into linear program LP3$(C_{\max})$, we obtain a mixed 0-1 integer linear
program MILP$(C_{\max})$.

(a) A non-feasible schedule respecting the first optimal distribution

(b) A feasible schedule respecting the first distribution

(c) A globally optimal schedule respecting the second optimal distribution

(d) A globally optimal schedule respecting the third optimal distribution

Figure 4: Schedules constructed based on distributions to linear program
MILP$(C_{\max})$.

Example 1 (continuation). Returning to the problem instance of Example 1, we
can easily observe that, for an optimal distribution to the new linear program
MILP$(C_{\max})$, $C_{\max}=21$. In particular, distribution 4 from the
previous section (Fig. 2f) is optimal also for linear program
MILP$(C_{\max})$. There exist other optimal distributions to linear program
MILP$(C_{\max})$. In one of them,
$t_{13}=3,\ t_{14}=13$, $t_{22}=4,\ t_{26}=13$, $t_{32}=5,\ t_{33}=12$ and
$t_{45}=13,\ t_{42}=7$,
see Fig. 4a representing a non-feasible schedule that respects this
distribution. A feasible schedule with makespan 23 respecting the same
distribution is depicted in Fig. 4b. In a slight modification of the latter
optimal distribution, job 3 is redistributed on machines 1 and 3 so that its
processing time on machine 1 is increased by 2 and its processing time on
machine 3 is decreased by the same amount. This results in a globally optimal
schedule with makespan 21 depicted in Fig. 4c. In another optimal distribution
$t_{22}$ is reduced to $3$ and $t_{42}$ is increased to $8$. Another globally
optimal schedule with makespan 21 respecting the latter optimal distribution
is depicted in Fig 4d.

As we can see, even for a very small sized problem instance, a number of
different optimal distributions to the new linear program MILP$(C_{\max})$
exist, some of them leading to an optimal schedule and some not. We again need
to “guess” a “correct” optimal distribution among all possible optimal ones.
Moreover, as we show below, not necessarily there exists a globally optimal
schedule that respects an optimal distribution to the new linear program
MILP$(C_{\max})$, as it was the case for liner programs LP2$(C_{\max})$ and
LP3$(C_{\max})$.

Example 1a. Consider a slight modification of the problem instance of Example
1 in which all job parameters remain the same except that $r_{4}=0$. This
reduces the makespan of an optimal distribution to linear program
MILP$(C_{\max})$ from $C_{\max}=21$ to $C_{\max}=20$. Now job 4 can be
partitioned on machine 1 in two parts, hence $t_{13}$ can be increased to 7.
An optimal schedule with makespan 20 respecting this optimal distribution is
depicted in Fig. 5a.

Example 1b. For the second modification of Example 1, let $r_{4}=6$. For an
optimal distribution to this modified instance $C_{\max}=20$, which is the
completion time of machine 4 (note that the completion time on machine 1,
compared to that in the schedule of Fig. 4b, is reduced by the length of the
gap $[6,8)$). A non-feasible schedule respecting an optimal distribution is
depicted in Fig. 5b. An optimal feasible schedule with makespan 23 respecting
the same distribution is depicted in Fig. 5c. The latter schedule is not
globally optimal. An optimal schedule with makespan 21 is illustrated in Fig
5d; this schedule respects a distribution with the same makespan
$C_{\max}=21$. Observe that the latter distribution is not optimal for linear
program MILP$(C_{\max})$.

(a)

(b)

(c)

(d)

Figure 5: (a): An optimal schedule for the first modified instance; (b): a
non-feasible schedule respecting an optimal distribution for the second
modified instance; (c): an optimal schedule respecting the latter
distribution; (d): and an optimal schedule, that respects a non-optimal
distribution

##  7 The scheduling method of Lawler and Labetoulle

In the following section we describe the method of Lawler and Labetoulle [4]
for the construction of an optimal schedule from an optimal distribution to
linear program LP2$(C_{\max})$ for problem $R|pmtn|C_{\max}$, and then we show
how it can be extended to construct an optimal schedule respecting any
distribution to problem $R|r_{j};pmtn|C_{\max}$.

Lawler and Labetoulle [4] adopted open shop scheduling technique of Gonzalez
and Sahni [2] for the construction of an optimal feasible schedule with
makespan $C_{\max}$ respecting an optimal distribution to program
LP2$(C_{\max})$ for simultaneously released jobs (note that an open shop
instance can already be seen as a distribution). Recall that an optimal
distribution $\\{x_{ij}\\}$ defines an $m$ x $n$ non-negative processing time
matrix $T=\\{t_{ij}\\}=x_{ij}p_{ij}$. The so-called decrementing sets are
iteratively formed from iteration 1 by selecting one entry in each tight row
and in each tight column: a row/column is tight iff the sum of the entries in
that row/column is exactly $C_{\max}$. The initial processing time matrix
$T=T^{1}$, defined by an optimal distribution, is iteratively transformed into
the $m$ x $n$ 0-matrix. At each iteration $h>0$, the matrix $T^{h-1}$ of the
previous iteration is updated according to the formed decrementing set $D^{h}$
at iteration $h$; in particular, each entry in matrix $T^{h-1}$ corresponding
to an element of set $D^{h}$ is decreased by a suitably chosen (small enough)
number $\delta^{h}$ resulting in the updated matrix $T^{h}$ of iteration $h$.
$\delta^{h}$ is chosen in such a way that the new matrix $T^{h}$ possesses
similar properties as its predecessor matrix $T^{h-1}$: The sum of the
elements in each row and column of the updated matrix is no larger than
$C_{\max}-\sum_{i=1}^{h}\delta^{i}$. The elements in decrementing set $D^{h}$
define a partial schedule of iteration $h$ of length $\delta^{h}$ according to
the selected portions of processing times. $\sigma^{h}$ is the partial
schedule generated by iteration $h$, which is obtained by a mere merging of
the partial schedules of each of the iterations $1,\dots,h$, so that the
makespan of partial schedule $\sigma^{h}$ is
$\tau^{h+1}=\sum_{i=1}^{h}\delta^{i}$. We will refer to $\tau^{h+1}$ as the
scheduling time of iteration $h+1$, which is the time moment at which the
partial schedule of iteration $h+1$ starts. The whole procedure halts at
iteration $h$ such that matrix $T^{h}$ is a 0-matrix. At that iteration,
$\sigma^{h}$ is a complete feasible schedule. The optimality of this complete
schedule immediately follows from the fact that its makespan is $C_{\max}$ (a
lower bound on the optimum schedule makespan).

In the initial matrix $T$ and in each following matrix $T^{h}$ there exists a
decrementing set. This follows from a known Birkhoff and von-Neumann theorem
stating that every doubly stochastic matrix is a linear combination of
permutation matrices. Indeed, by completing matrix $T$ with additional slack
rows and columns, an $m+n$ x $m+n$ matrix with the entries of each its row and
column summing up to $(C_{\max})$ can be obtained. Dividing all the entries of
this matrix by $(C_{\max})$, a doubly stochastic matrix is obtained. Then a
permutation matrix from the theorem defines a decrementing set.

(a)

(b)

(c)

(d)

Figure 6: A non-feasible schedule respecting an optimal distribution (a), a
feasible non-optimal schedule (b) and two optimal schedules (c) and (d)
respecting the same distribution.

Example 4. Let us illustrate the scheduling method of Lawler and Labetoulle on
a small instance of problem $R|pmtn|C_{\max}$. It is basically the instance of
Example 1 adopted for the case when all jobs are simultaneously released. To
maintain $C_{\max}=18$, we increase the processing time of jobs 2 and 3 to 18
and decrease the processing time of job 5 to 10. It can be easily verified
that in an optimal distribution to linear program LP2$(C_{\max})$ with
$C_{\max}=18$, we have $t_{13}=5,\ t_{14}=13$, $t_{22}=5,\ t_{26}=13$,
$t_{32}=5,\ t_{33}=13$, and $t_{42}=8,\ t_{45}=10$. A non-feasible schedule
respecting this distribution is depicted in Fig. 6a. This schedule can
straightforwardly be converted to a feasible schedule of Fig. 6b with makespan
23 by imposing a gap $[0,5)$ on machine 3. This schedule is not optimal. An
optimal one respecting the above optimal distribution is depicted in Fig. 6c.

Table 1: Flowchart of the procedure with processing time matrices and the
corresponding decrementing sets (marked with circles)

| 1
---
2
3
4
| 2 | 3 | 4 | 5 | 6
---|---|---|---|---
0 | ⑤ | 13 | 0 | 0
5 | 0 | 0 | 0 | ⑬
⑤ | 13 | 0 | 0 | 0
8 | 0 | 0 | ⑩ | 0
| 2 | 3 | 4 | 5 | 6
---|---|---|---|---
0 | 0 | ⑬ | 0 | 0
5 | 0 | 0 | 0 | ⑧
0 | ⑬ | 0 | 0 | 0
⑧ | 0 | 0 | 5 | 0
| 2 | 3 | 4 | 5 | 6
---|---|---|---|---
0 | 0 | ⑤ | 0 | 0
⑤ | 0 | 0 | 0 | 0
0 | ⑤ | 0 | 0 | 0
0 | 0 | 0 | ⑤ | 0
| 2 | 3 | 4 | 5 | 6
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0

The scheduling method of Lawler and Labetoulle [4] will generate an optimal
schedule as follows. The initial matrix $T=T^{1}$ of job processing times
defined by the optimal distribution is represented in the first quarter of
Table 1, where the entries corresponding to the elements of the decrementing
set $D^{1}$ and the following decrementing sets are circled. $\delta^{1}$ can
be chosen to be equal to 5. The updated matrix $T^{2}$ and the entries
corresponding to the elements of the decrementing set $D^{2}$ are shown in the
second quarter of Table 1. The first partial schedule with length 5 can be
seen as the initial (first) part of the schedule of Fig. 6d corresponding to
interval $[0,5)$. The computations in the following iterations $h=2,3$ with
$\delta^{2}=8$, $\delta^{3}=5$ are reflected in the next quarters of Table 1
and in the upper parts in the schedule of Fig. 6d. Although schedule
$\delta^{3}$ of Fig. 6d with makespan $C_{\max}=5+8+5=18$ is somewhat similar
to that of Fig. 6c, it splits job 5 on machine 4 (hence it is not a feasible
solution to problem $R|r_{j},pmtn\ -\ nosplit|L_{\max}$).

###  7.1 Scheduling non-simultaneously released jobs

One naturally wishes to extend the schedule construction technique of Lawler
and Labetoulle [4] for non-simultaneously released jobs. As we saw, an optimal
schedule respecting an optimal distribution to any of linear programs that we
considered is not necessarily optimal. Without giving a formal proof that
there may exist no other “proper” linear program for the problem, we argued in
Section 6.1 that it is unlikely that such linear program exists. As we also
observed, there may exist no globally optimal schedule respecting an optimal
distribution, i.e., any such schedule may respect a non-optimal distribution.

Due to these observations, now we would like to find a schedule with the
minimum makespan among all schedules respecting a given (not necessarily
optimal) distribution, i.e., find an optimal schedule respecting that
distribution. The schedule construction technique of Lawler and Labetoulle [4]
can be generalized by maintaining an extra information on which job parts can
be scheduled at every scheduling time $\tau^{h}$. Note that such care is to be
taken only on the first scheduled part of each job. For that, we introduce an
additional row 0 in processing time matrices.

Initially, in the extended matrix $T^{1}$, the entry $t^{1}_{0j}$ in column
$j$ of row 0 is $r_{j}$; iteratively,
$t^{h}_{0j}:=\max\\{0,r_{j}-\tau^{h}\\}$. During the scheduling process, we
impose an additional restriction that forbids scheduling of job $j$ at time
$\tau^{h}$ if $t^{h}_{0j}>0$ (independently of whether the corresponding
entries are from a tight row or tight column).

As a result, not necessarily a decrementing set will contain one entry from a
tight row or a tight column. In particular, set $D^{h}$ will contain no entry
from a (tight) row $i$ if among yet unscheduled job parts assigned to machine
$i$ no job is yet released by time $\tau^{h+1}$ (i.e., for any positive entry
in row $i$, the corresponding entry in row 0 is positive); likewise, the
decrementing set of iteration $h$ will contain no entry from a (tight) column
$j$ if job $j$ is not yet released by time $\tau^{h+1}$.

We will refer to a row $i$ from matrix $T^{h}$ as ready at iteration $h$ if it
contains a positive entry $t_{ij}^{h}>0$ such that $t^{h}_{0j}=0$; we will
refer to such an entry as valid for row $i$ at iteration $h$.

Let $t^{h}_{0j}=0$, and let $M_{h}(j)$ be the set of machines such that the
entry $t_{ij}^{h}$ is valid for $i\in M_{h}(j)$. Then the ready rows from set
$M_{h}(j)$ are said to be conflicting by job $j$ at iteration $h$. Note that
two or more rows may be conflicting by two or more different jobs.

A decrementing set $D^{h}$ of iteration $h$ contains one entry from a ready
row such that no two entries from the same column are included into that set
(since the same job cannot be scheduled on different machines at a time);
whenever a ready row $i$ contains an element from a tight column $j$, the
corresponding part of job $j$ can be selected if entry $t_{ij}$ is valid at
iteration $h$.

It might not be possible to select an entry from every ready row at a given
iteration $h$ since two or more rows may be conflicting by the same jobs in
such a way that all entries cannot be selected. For example, if we have two
ready rows with valid entries only in, say, column $j$, then only one of these
entries can be selected; likewise, if there are three ready rows with valid
entries only in, say, columns $j$ and $j^{\prime}$, then only two of these
entries, one from column $j$ and the other from column $j^{\prime}$, can be
selected in decrementing set $D^{h}$. We break ties by selecting the
corresponding entry from row $i$ with the maximum current load, i.e., with the
maximum $\sum_{l=1}^{n}t_{il}^{h}$. If such a row contains several valid
entries, then the entry from a column $j$ with the maximum remaining
processing time, i.e., with the maximum $\sum_{l=1}^{m}t_{lj}^{h}$ is
selected. Further ties are broken by selecting an entry from column $l$ such
that $t^{h-1}_{il}\in D^{h-1}$ (i.e., part of job $l$ was included in the
decrementing set of the previous iteration). The latter tie breaking rule
avoids unnecessary preemption of an already running job. (At every iteration
$h$, the rows can be considered in non-increasing order of their loads and the
corresponding valid entries can be selected from a column $j$ with the maximum
remaining processing time.)

Let $r$ be the minimum positive element in row $0$ at iteration $h$ in matrix
$T^{h}$, i.e., $r=\min_{j}t^{h}_{0j}$. The jump $\delta^{h}$ at iteration $h$
is now defined as the minimum between $\delta^{h}$ as defined in Lawler and
Labetoulle [4] and $r$.

Since there may exist no more than $n$ district job release times, the
extended method yields an additional term $n$ bounding the number of
iterations and hence has the same polynomial time complexity as the method of
Lawler and Labetoulle [4]. It is not difficult to see that $\tau^{h^{*}}$ is
an optimal schedule makespan, where $h^{*}$ is the last iteration in the
procedure. First note that the extended procedure will work as the basic one
from the earliest scheduling time $\tau^{h^{\prime}}$ such that
$t_{0j}^{h^{\prime}}=0$, for all $j=1,\dots,n$, since the corresponding
decrementing sets will contains $m$ elements with exactly one element from
each tight column (by the construction, all entries in column $j$ will be
valid at any iteration $h$ with $\tau^{h}\geq r_{j}$). In general, the
extended procedure will work as the basic one if at every iteration there are
$m$ non-conflicting ready rows with an entry in a tight column so that the
entries from each tight column are included into the corresponding
decrementing sets. Otherwise, in case there is an entry in a tight column that
was not selected at an iteration $h$, the corresponding entry in row 0 should
have been positive, i.e., the corresponding job is not released by the current
scheduling time $\tau^{h-1}$. In other words, if an entry from a tight column
$j$ was not included in decrementing set $D^{h}$ then there is no valid entry
from that column at iteration $h$, equivalently, $r_{j}>\tau^{h-1}$. No
feasible schedule may include such a job at time $\tau^{h-1}$. Likewise, if
there are only $l<m$ non-conflicting ready rows at iteration $h$, then there
are only $l$ jobs that can feasibly be scheduled at time $\tau^{h-1}$. Our tie
breaking rule will include an entry corresponding to each of these $l$ jobs in
decrementing set $D^{h}$, in total $l$ entries from $l$ rows corresponding to
$l$ most loaded machines will be included. Finally, note that among
conflicting rows, ties can easily be broken by selecting valid entries from
the rows corresponding to most loaded machines.

Example 3. Let us first illustrate the extended scheduling method for the
scheduling instance from Theorem 1. Recall an optimal distribution respected
by the schedule of Fig. 1. Let us first assume that we have a solution to the
corresponding partition instance, i.e., we have sets $P_{1}$ and $P_{2}$.
Then, for the sake of simplicity, we can represent all partition jobs in one
column marked as $P$, see Table 2 below. We update the entries in this column
according to the made selections. All partition jobs from sets $P_{1}$ and
$P_{2}$ are scheduled consequently without creating any machine idle time in
two different (aggregated) iterations 2 and 4. In the first quarter of Table 2
an initial extended processing time matrix $T^{0}$ is presented. For this
instance, all three rows are ready from the beginning of iteration 1. The
valid entries corresponding to the elements in the decrementing set $D_{1}$
are circled (note that the corresponding entries in row 0 are 0). Row 1 and
column 1 are tight, hence element $t_{11}$ is circled. From rows 2 and 3
elements $t_{24}$ and $t_{32}$ are similarly selected. We have $\delta^{1}=3$
and $\tau^{1}=3$. The part of the schedule of Fig. 1 corresponding to the
interval $[0,3)$ is the partial schedule $\sigma^{1}$ of iteration 1. Matrix
$T^{1}$ is similarly represented in the second quarter of Table 2 (note that
the entries in row 0 are updated correspondingly). Now, $\delta^{2}=1$ and
hence $\tau^{2}=4$. The part of the schedule of Fig. 1 corresponding to the
interval $[0,4)$ is partial schedule $\sigma^{2}$. Similarly, in the following
iterations 3 and 4, $\delta^{3}=1$, $\tau^{3}=5$, and $\delta^{4}=1$ and
$\tau^{4}=6$.

Schedule $\sigma^{4}$ is the resultant complete schedule of Fig. 1 which
extends through the interval $[0,6)$. Since column 1 is tight, the
corresponding parts of job $J^{1}$ are included in the decrementing sets in
iterations 1,2, 3 and 4 (until this job is completely scheduled). Note that
$C_{\max}=6$ is attained by both, job $J^{1}$ and machine 2 in the optimal
distribution of Fig. 1 (i.e., the total length of job $J^{1}$ and the load of
machine 2, see inequalities 4 and 5). Hence, schedule $\sigma^{4}$ is optimal.

Given an optimal distribution of Fig. 1, the extended scheduling procedure
will create an optimal schedule without the knowledge of a solution to the
PARTITION instance. Then the jumps $\delta^{i}$ will be determined by the
lengths of the selected partition jobs (without our aggregated presentation,
the number of iterations would depend on $k$, in our case, it would be $k+2$).
Note that the procedure may split a partition job or/and job $J^{2}$, which is
not allowed for setting $R|r_{j},pmtn\ -\ nosplit|L_{\max}$. For instance, in
this example, job $J^{2}$ was not split on machine 3 the corresponding parts
of that job being selected in consecutive iterations 1,2 and 3 (in fact, we
solved an instance of problem $R|r_{j},pmtn\ -\ nosplit|L_{\max}$ given a
solution to the PARTITION instance, see Corollary 2). Finally, note that,
depending on the made selections of the decrementing sets, the procedure may
create different optimal schedules respecting the same distribution.

Table 2: Flowchart of the extended procedure with processing time matrices and
the corresponding decrementing sets

| 0
---
1
2
3
| 1 | 2 | 3 | 4 | P
---|---|---|---|---
0 | 0 | 4 | 0 | 3
④ | 0 | 2 | 0 | 0
1 | 0 | 0 | ③ | 2
1 | ⑤ | 0 | 0 | 0
| 1 | 2 | 3 | 4 | P
---|---|---|---|---
0 | 0 | 1 | 0 | 0
① | 0 | 2 | 0 | 0
1 | 0 | 0 | 0 | ②
1 | ② | 0 | 0 | 0
| 1 | 2 | 3 | 4 | P
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | ② | 0 | 0
① | 0 | 0 | 0 | 1
1 | ① | 0 | 0 | 0
| 1 | 2 | 3 | 4 | P
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | ① | 0 | 0
0 | 0 | 0 | 0 | ③
① | 0 | 0 | 0 | 0
| 1 | 2 | 3 | 4 | P
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0

Example 1 (continuation 2). Next, we illustrate the extended schedule
construction procedure on the problem instance of our basic Example 1. We
first construct an optimal schedule of Fig. 2d respecting optimal distribution
2 (recall that this schedule is not globally optimal). Table 3 represents the
flowchart of the procedure in its 10 iterations (we omit the table with all 0
entries of the last iteration 11). Initially in matrix $T^{1}$ all entries in
row 0 are positive except that of column (job) 5. In particular, only row 4 is
ready. Since 2 is the minimum entry in row 0, $\delta^{1}=2$, hence
$\tau^{1}=2$. The partial schedule of iteration 1 corresponds to the segment
$[0,2)$ of the schedule in Fig. 7. In the next matrix $T^{2}$ there arises one
additional ready row 2 with the entry 5 in column 2 (recall that the minimum
entry in column 0 of matrix $T^{1}$ was precisely in column 2). Now the
minimum entry in row 0 is 3, hence $\delta^{2}=\min\\{5,1\\}=1$ and
$\tau^{1}=2+1=3$, see again Fig 2d. The entries in the decrementing set
$D^{2}$ correspond to columns 2 and 5 (both, jobs 2 and 5 are released by time
2). Again, in the processing time matrix $T^{3}$ there arises one additional
ready row 1 corresponding to job 3. The decrementing set $D^{3}$ contains now
3 jobs so that already 3 machines, 1,2 and 4 become busy. At the next
iteration 4 job 6 becomes available on machine 2, but the last unscheduled
part of job 2 is scheduled on that machine by our tie breaking rule. The
decrementing set of iteration 5 already contains 4 elements, hence all four
machines become busy; $\delta^{5}=1$ and $\tau^{5}=2+1+2+2+1=8$, see Fig. 7.
At iteration 6 all entries in row 0 in matrix $T^{6}$ are already 0, hence all
job parts become released. The procedure continues in the same fashion until
it constructs a complete feasible schedule of Fig. 2d respecting an optimal
distribution 2 to linear program MILP$(C_{\max})$.

Table 3: caption of table 3.

|  |  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
| 0
---
1
2
3
4
|  2 |  3 |  8 |  0 |  5
---|---|---|---|---
0 | 5 | 13 | 0 | 0
5 | 0 | 0 | 0 | 13
6 | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize13}⃝ | 0
|  0 |  1 |  6 |  0 |  3
---|---|---|---|---
0 | 5 | 13 | 0 | 0
{\footnotesize5}⃝ | 0 | 0 | 0 | 13
6 | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize11}⃝ | 0
|  0 |  0 |  5 |  0 |  2
---|---|---|---|---
0 | {\footnotesize5}⃝ | 13 | 0 | 0
{\footnotesize4}⃝ | 0 | 0 | 0 | 13
6 | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize10}⃝ | 0
|  0 |  0 |  3 |  0 |  0
---|---|---|---|---
0 | {\footnotesize3}⃝ | 13 | 0 | 0
{\footnotesize2}⃝ | 0 | 0 | 0 | 13
6 | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize8}⃝ | 0
|  0 |  0 |  1 |  0 |  0
---|---|---|---|---
0 | {\footnotesize1}⃝ | 13 | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize13}⃝
{\footnotesize6}⃝ | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize6}⃝ | 0
| 0
---
1
2
3
4
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize13}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize12}⃝
{\footnotesize5}⃝ | 10 | 0 | 0 | 0
5 | 0 | 0 | {\footnotesize5}⃝ | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize8}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize7}⃝
0 | {\footnotesize10}⃝ | 0 | 0 | 0
{\footnotesize5}⃝ | 0 | 0 | 0 | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize3}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize2}⃝
0 | {\footnotesize5}⃝ | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize1}⃝ | 0 | 0
0 | 0 | 0 | 0 | 0
0 | {\footnotesize3}⃝ | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 0 | 0
0 | {\footnotesize2}⃝ | 0 | 0 | 0
0 | 0 | 0 | 0 | 0

Table 4: caption of table 4.

|  |  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
|  2 |  3 |  4 |  5 |  6
---|---|---|---|---
| 0
---
1
2
3
4
|  2 |  3 |  8 |  0 |  5
---|---|---|---|---
0 | 5 | 13 | 0 | 0
5 | 0 | 0 | 0 | 13
4 | 10 | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize13}⃝ | 0
|  0 |  1 |  6 |  0 |  3
---|---|---|---|---
0 | 5 | 13 | 0 | 0
{\footnotesize5}⃝ | 0 | 0 | 0 | 13
4 | 10 | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize11}⃝ | 0
|  0 |  0 |  5 |  0 |  2
---|---|---|---|---
0 | {\footnotesize5}⃝ | 13 | 0 | 0
{\footnotesize4}⃝ | 0 | 0 | 0 | 13
4 | 10 | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize10}⃝ | 0
|  0 |  0 |  1 |  0 |  0
---|---|---|---|---
0 | {\footnotesize1}⃝ | 13 | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize13}⃝
{\footnotesize4}⃝ | 10 | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize6}⃝ | 0
| 0
---
1
2
3
4
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize13}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize12}⃝
{\footnotesize3}⃝ | 10 | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize5}⃝ | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize9}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize8}⃝
0 | {\footnotesize10}⃝ | 0 | 0 | 0
7 | 0 | 0 | {\footnotesize1}⃝ | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize8}⃝ | 0 | 0
0 | 0 | 0 | 0 | {\footnotesize7}⃝
0 | {\footnotesize8}⃝ | 0 | 0 | 0
{\footnotesize7}⃝ | 0 | 0 | 0 | 0
|  0 |  0 |  0 |  0 |  0
---|---|---|---|---
0 | 0 | {\footnotesize1}⃝ | 0 | 0
0 | 0 | 0 | 0 | 0
0 | {\footnotesize1}⃝ | 0 | 0 | 0
0 | 0 | 0 | 0 | 0

Now we apply our schedule construction procedure to a non-optimal distribution
to obtain a globally optimal schedule respecting that distribution. We
illustrate this using a non-optimal distribution 3 from Example 1 (see Fig.
2e). We represent the flowchart of the procedure in Table 4. Initially at
iteration 1 we have one ready row 4 with a single valid entry 13
(corresponding to job 2) which is included into the decrementing set $D^{1}$;
$\delta_{1}=t^{1}_{02}=2$ and $\tau^{1}=2$. At iteration 2 row 2 also gets
ready with a single valid entry 5 corresponding to job 2;
$D^{2}=\\{t^{2}_{22},t^{2}_{45}\\}=\\{5,11\\}$, $\delta_{2}=t^{2}_{03}=1$ and
$\tau^{2}=2+1=3$. At iteration 3 one additional row 1 with a single valid
entry 5 corresponding to job 2 gets ready;
$D^{3}=\\{t^{3}_{13},t^{3}_{22},t^{3}_{45}\\}=\\{5,4,10\\}$; now
$\delta_{3}=t^{3}_{06}=2$, but since the remaining processing time of job 2 is
13, the same as that of job 6, by our tie breaking rule we include
$t^{3}_{22}$ (and not $t^{3}_{26}$) in set $D^{3}$ (without creating
unnecessary preemption of job 2). We respectively skip one iteration by
setting $\delta_{3}=4$ and hence letting $\tau^{3}=2+1+4=7$. At iteration 4
all 4 rows are ready and the corresponding four entries marked in the fourth
quarter of Table 4 are included in set $D^{4}$. The next four iterations are
similarly reflected in Table 4 (we omitted gain the 0-matrix of iteration 9).
The resultant complete optimal schedule with makespan
$\tau^{8}=2+1+4+1+3+2+7+1=21$ coincides with that of Fig. 2e.

##  8 Concluding remarks

Optimal distributions to linear programs that we considered here, including
linear program MILP$(C_{\max})$, do not “completely capture” all required
features for the construction of an optimal schedule to problem
$R|r_{j};pmtn|C_{\max}$. Some optimal distributions may posses better features
than others for the creation of an optimal schedule, but it is difficult to
predict what kind of an optimal distribution an LP solver will deliver and
what kind of an optimal distribution is preferable, in general. Moreover, a
non-optimal distribution may suit better a given problem instance than any
optimal one so that an optimal schedule respecting that non-optimal
distribution may be globally optimal, whereas no globally optimal schedule
respecting an optimal distribution may exist (Section 6).

The extended schedule construction procedure from Section 7.1 may be applied
to any (not necessarily optimal) distribution to obtain an optimal schedule
respecting that distribution. Such a schedule may also be globally optimal
(e.g., the schedule of Fig. 4d). The method of Lawler and Labetoulle [4] for
the construction of an optimal schedule relies on the fact that the makespan
of a (globally) optimal schedule to linear program LP2$(C_{\max})$ equals to
the corresponding $C_{\max}$ for problem $R|pmtn|C_{\max}$. As we saw, similar
property does not hold for problem $R|r_{j};pmtn|C_{\max}$, as the makespan of
a globally optimal schedule may be larger than the corresponding $C_{\max}$.

A linear program, “more intelligent” than the linear programs studied here,
would “correctly” estimate the starting time of the first scheduled job on
each machine. However, this kind of estimation looks unrealistic without
actually carrying out the scheduling of assigned job parts. Hence unlikely,
there exists a liner programming such that an optimal schedule respecting an
optimal distribution to that linear program can be guaranteed to be optimal.
Because of this, we suggested an alternative schedule construction procedure
that delivers an optimal schedule to problem $R|r_{j},pmtn|L_{\max}$
respecting any distribution. Such distribution can of course be obtained by a
linear program, but it might be possible to create it using some alternative
way. In contrast with the studied here scheduling problem
$R|r_{j},pmtn|L_{\max}$, for the setting $R|pmtn|L_{\max}$ without job release
times, an optimal schedule respecting an optimal distribution to linear
program LP2$(C_{\max})$ is guaranteed to be optimal. In this sense, the latter
problem possesses more accessible structural properties than the former one.

##  9 Acknowledgment

The author is grateful to Victor Pacheco for his very kind help in creating
figures and tables using the tools of a graphical interface Xfig and Latex,
respectively.

## References

  * [1] Gonzalez T. and S. Sahni, “Preemptive scheduling of uniform processor systems”, Journal of the ACM 25, 92-101, 1978.
  * [2] Gonzalez T. and S. Sahni, “Open Shop Scheduling to Minimize Finish time”, Journal of the ACM 23, 665-679 (1976)
  * [3] Labetoulle, J.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. “Preemptive scheduling of uniform machines subject to release dates”, in Pulleyblank, H.R. (ed.) Progress in Combinatorial Optimization, New York, Academic Press, 245–261, 1984.
  * [4] Lawler, E.L.; Labetoulle, J.: On preemptive scheduling of unrelated parallel processors by linear programming, Journal of the Association of Computing Machinery 1978, 25 (4), 612–619.
  * [5] J.K. Lenstra, D.B. Shmoys and E. Tardos. ”Approximation algorithms for scheduling unrelated parallel machines” Math. Programming, 46, 259-271, 1990
  * [6] C.N. Potts. “Analysis of a linear programming heuristic for scheduling unrelated parallel machines” Discrete Appl. Math., 10, 155-164, 1985
  * [7] Shchepin E. and N. Vakhania. “An optimal rounding gives a better approximation for scheduling unrelated machines”, Operations Research Letters 33, p.127-133 (2005)
  * [8] E. Shchepin and N. Vakhania. “On the geometry, preemptions and complexity of multiprocessor and open shop scheduling”. Annals of Operations Research 159, p.183-213, 2008.
  * [9] http://www2.informatik.uni-osnabrueck.de/knust/class/ (Complexity results for scheduling problems by Peter Brucker and Sigrid Knust: a classification of optimal scheduling problems by what is known on their runtime complexity.)
  * [10] http://schedulingzoo.lip6.fr/ (Scheduling Zoo by Christoph Durr, Sigrid Knust, Damien Prot, Oscar C. Vasquez: an online tool for searching an optimal scheduling problem using the notation.)