  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
\cite{ll78}. The authors in \cite{ll78} 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. 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. We also
extend the schedule construction procedure based on an optimal LP solution from
Lawler and Labetoulle \cite{ll78} 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.
