Parallel task scheduling

Article summary

Parallel task scheduling (also called parallel job scheduling or parallel processing 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 J 1 , J 2 , ..., 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. and Drozdowski denote this problem by P|size_j|C_{\max} in the three-field notation introduced by Graham et al. 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. 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.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.