  Parallel machine scheduling has been extensively studied in the past decades,
with applications ranging from production planning to job processing in large
computing clusters. In this work we study some of these fundamental
optimization problems, as well as their parameterized and reoptimization
variants.
  We first present improved bounds for job scheduling on unrelated parallel
machines, with the objective of minimizing the latest completion time
(makespan) of the schedule. We consider the subclass of fully-feasible
instances, in which the processing time of each job, on any machine, does not
exceed the minimum makespan. The problem is known to be hard to approximate
within factor 4/3 already in this subclass. Although fully-feasible instances
are hard to identify, we give a polynomial time algorithm that yields for such
instances a schedule whose makespan is better than twice the optimal, the best
known ratio for general instances. Moreover, we show that our result is robust
under small violations of feasibility constraints.
  We further study the power of parameterization. We show that makespan
minimization on unrelated machines admits a parameterized approximation scheme,
where the parameter used is the number of processing times that are large
relative to the latest completion time of the schedule. We also present an FPT
algorithm for the graph-balancing problem, which corresponds to the instances
of the restricted assignment problem where each job can be processed on at most
2 machines.
  Finally, motivated by practical scenarios, we initiate the study of
reoptimization in job scheduling on identical and uniform machines, with the
objective of minimizing the makespan. We develop reapproximation algorithms
that yield in both models the best possible approximation ratio of
$(1+\epsilon)$, for any $\epsilon >0$, with respect to the minimum makespan.
