  We study a scheduling problem arising in pandemic times where jobs should
keep sufficient distance during transit times to machines. To model this, each
job has a transit time before and after its processing time, i.e., three
parameters. We seek conflict-free schedules in which the transit times of no
two jobs on machines in close proximity intersect. More formally, for the
problem "Scheduling with Contact Restrictions" (SCR), we are given a set of
jobs, a set of machines, and a conflict graph on the machines. The goal is to
find a conflict-free schedule of minimum makespan.
  We show that, unless P=NP, the problem does not allow for a constant factor
approximation even for identical jobs and every choice of fixed positive
parameters, including the unit case. However, given an oracle for a maximum
collection of disjoint independent sets , we provide a 2-approximation
algorithm for identical jobs. Moreover, we present optimal and near optimal
schedules for unit jobs on several graph classes. For bipartite graphs, we give
a 4/3-approximation and an asymptotic 7/6-approximation. Furthermore, we solve
the problem on complete graphs, complete bipartite graphs, and traceable
bipartite graphs in polynomial time. For trees, we compute schedules with
highest load density yielding near optimal solutions.
