Breaking jobs into parts may allow for improving the overall performance, for example, decreasing the makespan.
In both variants, the goal is to find a schedule that minimizes the makespan subject to the preemption constraints.
total preemptions, the problem is NP-hard, whereas McNaughton[1] shows a linear-time algorithm with
Shachnai, Tamir, and Woeginger[5] proved NP-hardness for the case where the number of preemption is strictly less than
For example, Liu and Cheng[7] consider single-machine scheduling with job release and delivery dates, where there is no firm bound on the number of preemptions, but each preemption requires spending time on "job setup".
Xing and Zhang[2] allow unbounded splittings, and give polynomial algorithms for many optimality criteria (such as makespan, lateness, tardiness, and more), with identical, uniform, and unrelated machines.
Son et al.[11] study makespan minimization on a single machine with a machine-availability constraint with a lower bound on the length of each part of a job that is split.
For identical machines, Shim and Kim[12] suggest a branch and bound algorithm with the objective to minimize total tardiness with independent job setup time.
Yalaoui and Chu[13] propose a heuristic to the same problem, with the objective to minimize the makespan.
Kim et al.[14] suggest a two-phase heuristic algorithm with the objective of minimizing total tardiness.
They show that allowing a bounded number of splittings reduces the complexity of scheduling.