Fractional job scheduling

Last updated

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.

Contents

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.

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 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 total preemptions, the problem is NP-hard, whereas McNaughton [1] shows a linear-time algorithm with preemptions.

For uniform machines, a polynomial algorithm by Gonzalez and Sahni [4] yields at most preemptions. Shachnai, Tamir, and Woeginger [5] proved NP-hardness for the case where the number of preemption is strictly less than . 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 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 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.

Related Research Articles

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value.

List scheduling is a greedy algorithm for Identical-machines scheduling. The input to this algorithm is a list of jobs that should be executed on a set of m machines. The list is ordered in a fixed order, which can be determined e.g. by the priority of executing the jobs, or by their order of arrival. The algorithm repeatedly executes the following steps until a valid schedule is obtained:

Uniform machine scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run-time of job j on machine i is pi,j = pj / si.

Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on a single machine, in a way that optimizes a certain objective, such as the throughput.

Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs and a list of machines. The required output is a schedule – an assignment of jobs to machines. The schedule should optimize a certain objective function. In the literature, problems of optimal job scheduling are often called machine scheduling, processor scheduling, multiprocessor scheduling, or just scheduling.

Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO1, O2, ..., On which need to be processed in a specific order. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set.

Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as flow-shop scheduling, each job contains exactly m operations. The i-th operation of the job must be executed on the i-th machine. No machine can perform more than one operation simultaneously. For each operation of each job, execution time is specified.

Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan - the total length of the schedule. In the specific variant known as open-shop scheduling, each job consists of a set of operationsO1, O2, ..., On which need to be processed in an arbitrary order. The problem was first studied by Teofilo F. Gonzalez and Sartaj Sahni in 1976.

The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution.

Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.

Parallel task scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule. In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific processing-time. There is also a number m specifying the number of machines that can process the jobs. The LPT algorithm works as follows:

  1. Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.
  2. Schedule each job in this sequence into a machine in which the current load is smallest.

Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers m, k. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.

Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.

<span class="mw-page-title-main">Philippe Baptiste</span>

Philippe Baptiste is a French engineer, academic and researcher. Baptiste is most well known as the president of the National Centre for Space Studies CNES in addition to his several books and scientific publications and communications in the field of algorithms, combinatorial optimization, operational research and artificial intelligence.

References

  1. 1 2 McNaughton, Robert (October 1959). "Scheduling with Deadlines and Loss Functions". Management Science. 6 (1): 1–12. doi:10.1287/mnsc.6.1.1. ISSN   0025-1909.
  2. 1 2 Xing, Wenxun; Zhang, Jiawei (2000-07-15). "Parallel machine scheduling with splitting jobs". Discrete Applied Mathematics. 103 (1): 259–269. doi:10.1016/S0166-218X(00)00176-1. ISSN   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. doi: 10.1145/322047.322055 . ISSN   0004-5411.
  5. ↑ Shachnai, Hadas; Tamir, Tami; Woeginger, Gerhard J. (2005-07-01). "Minimizing Makespan and Preemption Costs on a System of Uniform Machines". Algorithmica. 42 (3): 309–334. doi:10.1007/s00453-005-1171-0. ISSN   1432-0541. S2CID   14256666.
  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. 261: 332–343. doi: 10.1016/j.dam.2018.03.007 . ISSN   0166-218X. S2CID   126307013.
  7. ↑ Liu, Zhaohui; Cheng, T. C. Edwin (2002-04-30). "Scheduling with job release dates, delivery times and preemption penalties". Information Processing Letters. 82 (2): 107–111. doi:10.1016/S0020-0190(01)00251-4. hdl: 10397/32337 . ISSN   0020-0190.
  8. ↑ Blazewicz; Drabowski; Weglarz (May 1986). "Scheduling Multiprocessor Tasks to Minimize Schedule Length". IEEE Transactions on Computers. C-35 (5): 389–393. doi:10.1109/TC.1986.1676781. ISSN   1557-9956. S2CID   18188390.
  9. ↑ Deng, Xiaotie; Gu, Nian; Brecht, Tim; Lu, Kaicheng (2000). "Preemptive Scheduling of Parallel Jobs on Multiprocessors". SIAM Journal on Computing. 30 (1): 145–160. doi:10.1137/S0097539797315598. ISSN   0097-5397. S2CID   1717179.
  10. ↑ Serafini, Paolo (1996). "Scheduling Jobs on Several Machines with the Job Splitting Property". Operations Research. 44 (4): 617–628. doi:10.1287/opre.44.4.617. ISSN   0030-364X. JSTOR   172004.
  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. 12 (1): 1179–1196. doi:10.1007/s12652-020-02162-0. ISSN   1868-5145. S2CID   255752164.
  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. 35 (3): 863–875. doi:10.1016/j.cor.2006.04.006. ISSN   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. doi:10.1080/07408170304382. ISSN   0740-817X. S2CID   62630299.
  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. doi:10.1080/00207540410001720745. ISSN   0020-7543. S2CID   60729549.
  15. ↑ Kim, Hyun-Jung (2018-02-01). "Bounds for parallel machine scheduling with predefined parts of jobs and setup time". Annals of Operations Research. 261 (1): 401–412. doi:10.1007/s10479-017-2615-z. ISSN   1572-9338. S2CID   254228092.
  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. 97: 170–182. doi:10.1016/j.cie.2016.05.001. ISSN   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. 126: 105115. doi:10.1016/j.cor.2020.105115. ISSN   0305-0548. S2CID   225115689.
  18. ↑ Krysta, Piotr; Sanders, Peter; Vöcking, Berthold (2003). "Scheduling and Traffic Allocation for Tasks with Bounded Splittability". In Rovan, Branislav; Vojtáš, Peter (eds.). Mathematical Foundations of Computer Science 2003. Lecture Notes in Computer Science. Vol. 2747. Berlin, Heidelberg: Springer. pp. 500–510. doi:10.1007/978-3-540-45138-9_44. hdl: 11858/00-001M-0000-0014-6BD1-8 . ISBN   978-3-540-45138-9.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.