Fractional Job Scheduling

Fractional job scheduling is a variant of optimal job scheduling in which it is allowed to break jobs into parts and process each part separately on the same or a different machine. Breaking jobs into parts may allow for improving the overall performance, for example, decreasing the makespan. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the optimization variables become continuous. On the other hand, breaking jobs apart might be costly.

Variants

There are several variants of job scheduling problems in which it is allowed to break jobs apart. They can be broadly classified into preemption and splitting.

* In the preemption variants, different parts of a job must be processed at different times. In the three-field notation, they are denoted by pmtn. They were first studied by McNaughton.
* In the splitting variants, different parts of a job may be processed simultaneously on different machines. They are denoted by split and were introduced by Xing and Zhang.

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 $j$ has an associated parameter that bounds the number of times $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 prove that with at most $n-2$ total preemptions, the problem is NP-hard, whereas McNaughton shows a linear-time algorithm with $n-1$ preemptions.

For uniform machines, a polynomial algorithm by Gonzalez and Sahni yields at most $2n-2$ preemptions. Shachnai, Tamir, and Woeginger proved NP-hardness for the case where the number of preemption is strictly less than $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 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 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.'' or Deng ''et al.'' 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 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 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 $7/4$ approximation algorithm.

Son et al. 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 suggest a branch and bound algorithm with the objective to minimize total tardiness with independent job setup time. Yalaoui and Chu propose a heuristic to the same problem, with the objective to minimize the makespan. Kim et al. suggest a two-phase heuristic algorithm with the objective of minimizing total tardiness. With the objective to minimize the makespan, Kim 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. 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 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{{Cite book , last1=Krysta , first1=Piotr , last2=Sanders , first2=Peter , last3=Vöcking , first3=Berthold , title=Mathematical Foundations of Computer Science 2003 , chapter=Scheduling and Traffic Allocation for Tasks with Bounded Splittability , series=Lecture Notes in Computer Science , date=2003 , volume=2747 , editor-last=Rovan , editor-first=Branislav , editor2-last=Vojtáš , editor2-first=Peter , chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-45138-9_44 , language=en , location=Berlin, Heidelberg , publisher=Springer , pages=500–510 , doi=10.1007/978-3-540-45138-9_44 , isbn=978-3-540-45138-9, hdl=11858/00-001M-0000-0014-6BD1-8 , hdl-access=free study makespan minimization using the k-splittable variant, a variant where each job is allowed to be split into most $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.

References

Job scheduling