Scheduling independent 2-processor tasks to minimize schedule length

DOI10.1016/0020-0190(84)90006-1MaRDI QIDQ796987zbMATH OpenOpenAlexDBLPWikidataFDO

Authors M. Drabowski, Jacek Blazewicz, Jan Węglarz

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0020-0190(84)90006-1

zbMATH Keywords

deterministic schedulingidentical processorsmultiprocessor taskspolynomial-time algorithm

Mathematics Subject Classification ID

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

Review text

The problem considered in this paper is the deterministic scheduling of tasks on a set of identical processors. However, the model presented differs from the classical one by the requirement that certain tasks need more than one processor at a time for their processing. In the paper an O(n log n) algorithm is given for scheduling n preemtable tasks on m processors to minimize schedule length, when tasks are divided into two subsets. Each task from the first subset requires one processor at a time, and each task from the second subset requires two processors at a time for its processing.

Recommendations

• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Scheduling independent multiprocessor tasks
• Scheduling independent multiprocessor tasks
• Scheduling independent two processor tasks on a uniform duo-processor system
• scientific article; zbMATH DE number 1234084

Cites work

• Characterization of Connection Assignment of Diagnosable Systems
• scientific article; zbMATH DE number 3744543 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Optimization of Reduced Dependencies for Synchronous Sequential Machines

Cited in

(14)

• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling multiprocessor tasks -- An overview
• Scheduling multiprocessor tasks with chain constraints
• Two-way dominant sequence clustering for processor scheduling
• Linear and quadratic algorithms for scheduling chains and opposite chains
• Scheduling chained multiprocessor tasks onto large multiprocessor system
• Scheduling of resource tasks
• scientific article; zbMATH DE number 3883925 (Why is no real title available?)
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Two processor scheduling with limited preemption
• Scheduling Independent Tasks with Deadlines on Semi-identical Processors
• scientific article; zbMATH DE number 4089308 (Why is no real title available?)
• Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length
• Scheduling independent two processor tasks on a uniform duo-processor system

This page was built for publication: Scheduling independent 2-processor tasks to minimize schedule length

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