Preemptive scheduling of independent jobs on a hypercube
type: Item
instance of: scholarly article
title: Preemptive scheduling of independent jobs on a hypercube
zbMATH Open document ID: 0658.68041
DOI: 10.1016/0020-0190(88)90209-8
author: Guan-Ing Chen
author: Ten H. Lai
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4076609
zbMATH Keywords: preemptive scheduling
zbMATH Keywords: hypercube
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90209-8
OpenAlex ID: W1996376059
cites work: Q3787470
Recommended article: Preemptive scheduling of independent jobs with release times and deadlines on a hypercube
Recommended article: Q3787470
Recommended article: Scheduling independent jobs on partitionable hypercubes
Recommended article: An \(O(n \log n)\) feasibility algorithm for preemptive scheduling of n independent jobs on a hypercube
Recommended article: Preemptive Scheduling of Parallel Jobs on Multiprocessors
Recommended article: Q4875180
Recommended article: Q5718920
Recommended article: Scheduling of Jobs in a Hypercube Processing System
Recommended article: An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
description: scientific article; zbMATH DE number 4076609