Job scheduling with preemption

Various problems have been studied in job scheduling with preemption. One of them is generalized multiprocessor scheduling (GMS). It has two variants.

• In the first variant, the total number of preemptions is bounded by some fixed integer.
• In the second variant, each job ${\displaystyle j}$ has an associated parameter that bounds the number of times ${\displaystyle j}$ can be preempted throughout a feasible schedule.

In both variants, the goal is to find a schedule that minimizes the makespan subject to the preemption constraints.

For identical machines, Shchepin and Vakhania^[3] prove that with at most ${\displaystyle n-2}$ total preemptions, the problem is NP-hard, whereas McNaughton^[1] shows a linear-time algorithm with ${\displaystyle n-1}$ preemptions.

For uniform machines, a polynomial algorithm by Gonzalez and Sahni^[4] yields at most ${\displaystyle 2n-2}$ preemptions. Shachnai, Tamir, and Woeginger^[5] proved NP-hardness for the case where the number of preemption is strictly less than ${\displaystyle 2n-2}$. They also presented a PTAS for GMS with a global preemption bound, and another PTAS for GMS with job-wise preemption bound when the number of machines is a fixed constant.

Soper and Strusevitch^[6] study the special case in which at most one preemption is allowed. They show that makespan minimization is polynomial for two machines.

Many papers study other variants of preemptive scheduling. 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".

Some works like Blazewicz et al.^[8] or Deng et al.^[9] study preemptive scheduling for jobs with parallelism where jobs must be processed simultaneously on several processors.

Job scheduling with splitting

Various objectives have been studied. There are many variants including different setup times. In machine scheduling, the "setup time" refers to the time required to prepare a machine for a specific job or task. Sequence-dependent setup time is a situation where the setup time required for a job depends on the job that came before it, rather than being constant for all jobs (independent job setup time).

Serafini^[10] assumes unbounded splittings and preemptions and gives polynomial-time algorithms that minimize the maximum tardiness and the maximum weighted tardiness, for uniform and unrelated machines.

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. For the case with independent job setup time, they give a ${\displaystyle 7/4}$ approximation algorithm.

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. With the objective to minimize the makespan, Kim^[15] studies another variant with family setup time in which no setup is required when parts from the same job are produced consecutively. And, Wang et al.^[16] include a learning property that improves the processing time of a job according to the learning effect. The learning has to be restarted if one job is split and processed by a different machine.

For uniform machines, Kim and Lee^[17] study a variant with dedicated machines (there are some dedicated machines for each job), sequence-dependent setup times, and limited set-up resources (jobs require setup operators that are limited) with the objective to minimize the makespan. Krysta, Sanders, and Vöcking^[18] study makespan minimization using the k-splittable variant, a variant where each job is allowed to be split into most ${\displaystyle k}$ different machines. They show that this variant and another more general variant where each job has its own splitability parameter, are NP-hard. They give some approximation algorithms, but their main result is a polynomial-time algorithm for both problems, for a fixed number of machines. They show that allowing a bounded number of splittings reduces the complexity of scheduling.

In all these works, there is no global bound on the number of splitting jobs.