Preemptive scheduling of independent jobs on a hypercube

DOI10.1016/0020-0190(88)90209-8MaRDI QIDQ1111373zbMATH OpenOpenAlexFDO

Authors Guan-Ing Chen, Ten H. Lai

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90209-8

zbMATH Keywords

hypercubepreemptive scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Review text

We consider the problem of scheduling n independent jobs on an m- dimensional hypercube system to minimize the finishing time, where each job \(J_ i\) is associated with a dimension \(d_ i\) and a processing time \(t_ i\), meaning that \(J_ i\) requires a \(d_ i\)-dimensional subcube for \(t_ i\) units of time. An \(O(n^ 2)\) algorithm is presented that decides if all n jobs can be finished by a given deadline T. Using this algorithm, one may obtain a minimum-finishing-time schedule in polynomial time.

Recommendations

• Preemptive scheduling of independent jobs with release times and deadlines on a hypercube
• scientific article; zbMATH DE number 4050979
• Scheduling independent jobs on partitionable hypercubes
• An \(O(n \log n)\) feasibility algorithm for preemptive scheduling of n independent jobs on a hypercube
• Preemptive Scheduling of Parallel Jobs on Multiprocessors
• scientific article; zbMATH DE number 871911
• scientific article; zbMATH DE number 2247728
• Scheduling of Jobs in a Hypercube Processing System
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems

Cited in

(13)

• Scheduling independent jobs on partitionable hypercubes
• Scheduling on a hypercube
• Scheduling multiprocessor tasks -- An overview
• An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
• Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
• The master-slave paradigm in parallel computer and industrial settings
• scientific article; zbMATH DE number 4050979 (Why is no real title available?)
• Scheduling of Jobs in a Hypercube Processing System
• scientific article; zbMATH DE number 2247728 (Why is no real title available?)
• Walk on the hypercube with minimum similarities
• Preemptive scheduling of independent jobs with release times and deadlines on a hypercube
• An \(O(n \log n)\) feasibility algorithm for preemptive scheduling of n independent jobs on a hypercube

This page was built for publication: Preemptive scheduling of independent jobs on a hypercube

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