Fractional job scheduling explained

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.^[1]
• 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.^[2]

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^[3] 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^[4] yields at most

2 n -2 preemptions. Shachnai, Tamir, and Woeginger^[5] proved NP-hardness for the case where the number of preemption is strictly less than 2 n -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 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.^[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

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

1. McNaughton . Robert . October 1959 . Scheduling with Deadlines and Loss Functions . Management Science . en . 6 . 1 . 1–12 . 10.1287/mnsc.6.1.1 . 0025-1909.
2. Xing . Wenxun . Zhang . Jiawei . 2000-07-15 . Parallel machine scheduling with splitting jobs . Discrete Applied Mathematics . en . 103 . 1 . 259–269 . 10.1016/S0166-218X(00)00176-1 . 0166-218X.
3. Shchepin, Evgeny, and Nodari Vakhania. "New tight NP-hardness of preemptive multiprocessor and open-shop scheduling." Proceedings of 2nd multidisciplinary international conference on scheduling: Theory and applications MISTA 2005. 2005.
4. Gonzalez . Teofilo . Sahni . Sartaj . 1978-01-01 . Preemptive Scheduling of Uniform Processor Systems . Journal of the ACM . 25 . 1 . 92–101 . 10.1145/322047.322055 . 0004-5411. free .
5. Shachnai . Hadas . Tamir . Tami . Woeginger . Gerhard J. . 2005-07-01 . Minimizing Makespan and Preemption Costs on a System of Uniform Machines . Algorithmica . en . 42 . 3 . 309–334 . 10.1007/s00453-005-1171-0 . 14256666 . 1432-0541.
6. Soper . Alan J. . Strusevich . Vitaly A. . 2019-05-31 . Schedules with a single preemption on uniform parallel machines . Discrete Applied Mathematics . GO X Meeting, Rigi Kaltbad (CH), July 10--14, 2016 . en . 261 . 332–343 . 10.1016/j.dam.2018.03.007 . 126307013 . 0166-218X. free .
7. Liu . Zhaohui . Cheng . T. C. Edwin . 2002-04-30 . Scheduling with job release dates, delivery times and preemption penalties . Information Processing Letters . en . 82 . 2 . 107–111 . 10.1016/S0020-0190(01)00251-4 . 0020-0190. 10397/32337 . free .
8. Blazewicz . Drabowski . Weglarz . May 1986 . Scheduling Multiprocessor Tasks to Minimize Schedule Length . IEEE Transactions on Computers . C-35 . 5 . 389–393 . 10.1109/TC.1986.1676781 . 18188390 . 1557-9956.
9. Deng . Xiaotie . Gu . Nian . Brecht . Tim . Lu . Kaicheng . 2000 . Preemptive Scheduling of Parallel Jobs on Multiprocessors . SIAM Journal on Computing . en . 30 . 1 . 145–160 . 10.1137/S0097539797315598 . 1717179 . 0097-5397.
10. Serafini . Paolo . 1996 . Scheduling Jobs on Several Machines with the Job Splitting Property . Operations Research . 44 . 4 . 617–628 . 10.1287/opre.44.4.617 . 172004 . 0030-364X.
11. Son . Trang Hong . Van Lang . Tran . Huynh-Tuong . Nguyen . Soukhal . Ameur . 2021-01-01 . Resolution for bounded-splitting jobs scheduling problem on a single machine in available time-windows . Journal of Ambient Intelligence and Humanized Computing . en . 12 . 1 . 1179–1196 . 10.1007/s12652-020-02162-0 . 255752164 . 1868-5145.
12. Shim . Sang-Oh . Kim . Yeong-Dae . 2008-03-01 . A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property . Computers & Operations Research . Part Special Issue: New Trends in Locational Analysis . en . 35 . 3 . 863–875 . 10.1016/j.cor.2006.04.006 . 0305-0548.
13. YALAOUI . FAROUK . CHU . CHENGBIN . 2003-02-01 . An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times . IIE Transactions . 35 . 2 . 183–190 . 10.1080/07408170304382 . 62630299 . 0740-817X.
14. Kim * . Y.-D. . Shim . S.-O. . Kim . S.-B. . Choi . Y.-C. . Yoon . H. M. . 2004-11-01 . Parallel machine scheduling considering a job-splitting property . International Journal of Production Research . 42 . 21 . 4531–4546 . 10.1080/00207540410001720745 . 60729549 . 0020-7543.
15. Kim . Hyun-Jung . 2018-02-01 . Bounds for parallel machine scheduling with predefined parts of jobs and setup time . Annals of Operations Research . en . 261 . 1 . 401–412 . 10.1007/s10479-017-2615-z . 254228092 . 1572-9338.
16. Wang . Chenjie . Liu . Changchun . Zhang . Zhi-hai . Zheng . Li . 2016-07-01 . Minimizing the total completion time for parallel machine scheduling with job splitting and learning . Computers & Industrial Engineering . en . 97 . 170–182 . 10.1016/j.cie.2016.05.001 . 0360-8352.
17. Kim . Hyun-Jung . Lee . Jun-Ho . 2021-02-01 . Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers . Computers & Operations Research . en . 126 . 105115 . 10.1016/j.cor.2020.105115 . 225115689 . 0305-0548.
18. Book: Krysta . Piotr . Sanders . Peter . Vöcking . Berthold . Mathematical Foundations of Computer Science 2003 . Scheduling and Traffic Allocation for Tasks with Bounded Splittability . Lecture Notes in Computer Science . 2003 . 2747 . Rovan . Branislav . Vojtáš . Peter . https://link.springer.com/chapter/10.1007/978-3-540-45138-9_44 . en . Berlin, Heidelberg . Springer . 500–510 . 10.1007/978-3-540-45138-9_44 . 978-3-540-45138-9. 11858/00-001M-0000-0014-6BD1-8 . free .