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

DOI10.1007/S00453-003-1078-6MaRDI QIDQ1879360zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Klaus Jansen

Publication date 22 September 2004

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-003-1078-6

zbMATH Keywords

non-preemptive schedule

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1947422
• scientific article; zbMATH DE number 1241387
• scientific article; zbMATH DE number 1305441
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

Cited in

(22)

• Scheduling trees of malleable tasks for sparse linear algebra
• Online malleable job scheduling for m 3
• Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves models
• A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds
• Multi-core real-time scheduling for generalized parallel task models
• Preemptive scheduling for approximate computing on heterogeneous machines: tradeoff between weighted accuracy and makespan
• Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
• Competitive online scheduling of perfectly malleable jobs with setup times
• An approximation algorithm for the general max-min resource sharing problem
• An approximation algorithm for scheduling malleable tasks under general precedence constraints
• Resource loading with time windows
• Improved algorithms for online scheduling of malleable parallel jobs on two identical machines
• Scheduling malleable tasks with precedence constraints
• An effective approximation algorithm for the malleable parallel task scheduling problem
• scientific article; zbMATH DE number 1003247 (Why is no real title available?)
• scientific article; zbMATH DE number 1947422 (Why is no real title available?)
• Asymptotically optimal scheduling of random malleable demands in smart grid
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Approximation algorithms for scheduling parallel jobs
• Algorithms and Computation
• Peak demand minimization via sliced strip packing
• Machine scheduling with resource dependent processing times

This page was built for publication: Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879360)