Scheduling of jobs in a hypercube processing system

Inder Khosla, Sourav Bhattacharya, Wei Tek Tsai

Research output: Contribution to journalArticlepeer-review


When a job is processed in a hypercube multi-processor, it is allocated a cube of processing elements of the requisite size. There are three distinct costs involved in the hypercube scheduling problem: the cost of detecting a free cube (allocation), the cost of migrating jobs and merging the free spaces to accommodate a larger cube request (relocation) and the cost of not meeting the due date (tardiness). Traditionally, research in this area has focused on finding efficient algorithms for allocating a free cube (if any) in the hypercube system. The relocation cost has been treated as an independent cost metric. The role of scheduling has not received much attention and present subcube allocation methods assume a first-come-first- serve (FCFS) approach over the input job set. This paper considers the underlying scheduling issues in a hypercube processing system and shows how techniques other than FCFS scheduling of the incoming jobs can help in reducing the relocation cost and hence the overall subcube resource assignment cost. We discuss five simple and easily implementable dispatching heuristics, and compare their relative performance with the FCFS scheduling rule to demonstrate the advantages of scheduling in subcube allocation.

Original languageEnglish (US)
Pages (from-to)626-639
Number of pages14
JournalJournal of the Operational Research Society
Issue number5
StatePublished - May 1996


  • Computers
  • Scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing


Dive into the research topics of 'Scheduling of jobs in a hypercube processing system'. Together they form a unique fingerprint.

Cite this