A short note on the approximability of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints

The single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints is considered. There are some fixed jobs which are already fixed in the schedule. The remaining free jobs are to be assigned to the machines in such a way that they do not overlap with the fixed jobs. The order of job processing between the free jobs is restricted by given precedence constraints ≤, and the jobs are processed without preemption. The objective is to minimize the makespan. In the literature this problem has been proved to be strongly NP-hard even without precedence constraints. It is shown that this problem has a linear-time 2-approximation algorithm, but has no pseudopolynomial-time (2-δ)-approximation algorithm, for every δ＞0, if P≠NP.