Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme (Q1879360)

From MaRDI portal
Revision as of 18:20, 28 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
scientific article

    Statements

    Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme (English)
    0 references
    0 references
    0 references
    22 September 2004
    0 references
    The article treats a scheduling problem with \(n\) jobs on up to \(m\) identical machines, where the processing time of each task is dependend from the number of machines (processors) assigned to the job, whereas the overall sum of machines (processors) assigned at one time is limited by the number of machines \(m\). The dependency is defined very general (i.e., processing time \(pj\) \((k\) processors assigned) \(=fj(j,k)\), where \(fj\) is an arbitrary function for each job \(j)\). The objective is to minimize the makespan. This problem is called ``malleable parallel task scheduling''. As an overall assumption, one want to have a schedule without preemtion. Even the preemtive formulation of the problem is known as NP-hard. Therefore in the paper an algorithm is contructed which provides an approximative solution within a fixed accuracy. The main idea behind the approximation is to use the preemtive problem as a basic to construct non-preemtive solutions and to use data rounding to scale down the problem. As usual for these kind of approximation, the effort increases with the required accuracy of the approximative solution.
    0 references
    non-preemptive schedule
    0 references

    Identifiers