Parallel task scheduling information

Parallel task scheduling (also called parallel job scheduling^[1]^[2] or parallel processing scheduling^[3]) 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 J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter p_j and a size parameter q_j, and it must run for exactly p_j time-steps on exactly q_j machines in parallel.

Veltman et al.^[4] and Drozdowski^[3] denote this problem by $P|size_{j}|C_{\max }$ in the three-field notation introduced by Graham et al.^[5] P means that there are several identical machines running in parallel; size_j means that each job has a size parameter; C_max means that the goal is to minimize the maximum completion time. Some authors use $P|m_{j}|C_{\max }$ instead.^[1] Note that the problem of parallel-machines scheduling is a special case of parallel-task scheduling where $size_{j}=1$ for all j, that is, each job should run on a single machine.

The origins of this problem formulation can be traced back to 1960.^[6] For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than $3/2$ unless $P=NP$ .^{[citation needed]}

^ ^a ^b Cite error: The named reference Johannes was invoked but never defined (see the help page).
^ Cite error: The named reference PPTAS was invoked but never defined (see the help page).
^ ^a ^b Drozdowski, Maciej (2009). "Scheduling for Parallel Processing". Computer Communications and Networks. doi:10.1007/978-1-84882-310-5. ISBN 978-1-84882-309-9. ISSN 1617-7975.
^ Veltman, B; Lageweg, B. J; Lenstra, J. K (1990-12-01). "Multiprocessor scheduling with communication delays". Parallel Computing. 16 (2): 173–182. doi:10.1016/0167-8191(90)90056-F. ISSN 0167-8191.
^ Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey" (PDF). Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326.
^ Codd, E. F. (1960-06-01). "Multiprogram scheduling". Communications of the ACM. 3 (6): 347–350. doi:10.1145/367297.367317. S2CID 14701351.

[Johannes-1] Cite error: The named reference Johannes was invoked but never defined (see the help page).

[PPTAS-2] Cite error: The named reference PPTAS was invoked but never defined (see the help page).

[:0-3] Drozdowski, Maciej (2009). "Scheduling for Parallel Processing". Computer Communications and Networks. doi:10.1007/978-1-84882-310-5. ISBN 978-1-84882-309-9. ISSN 1617-7975.

[4] Veltman, B; Lageweg, B. J; Lenstra, J. K (1990-12-01). "Multiprocessor scheduling with communication delays". Parallel Computing. 16 (2): 173–182. doi:10.1016/0167-8191(90)90056-F. ISSN 0167-8191.

[initial_specification-5] Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey" (PDF). Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326.

[6] Codd, E. F. (1960-06-01). "Multiprogram scheduling". Communications of the ACM. 3 (6): 347–350. doi:10.1145/367297.367317. S2CID 14701351.

Parallel task scheduling information

and 24 Related for: Parallel task scheduling information

Parallel task scheduling

Optimal job scheduling

Data parallelism

Interval scheduling

Hilbert curve scheduling

Critical path method

Parallel computing

Parallel Extensions

Work stealing

Strip packing problem

Slurm Workload Manager

Cron

Gang scheduling

Threading Building Blocks

Topological sorting

Heterogeneous earliest finish time

Fractional job scheduling

OpenMP

Apache Hadoop

Instruction scheduling

Computer cluster

Supercomputer operating system

MultiLisp

Automatic parallelization