Computational complexity of some scheduling problems with multiprocessor tasks

DOI10.1016/J.DISOPT.2005.08.001MaRDI QIDQ1019301zbMATH OpenOpenAlexFDO

Authors Yakov Zinder, Van Ha Do, Ceyda Oğuz

Publication date 2 June 2009

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2005.08.001

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the complexity of multiprocessor task scheduling
• Complexity of a class of task scheduling problems
• Complexity results for scheduling tasks with discrete starting times
• On the complexity of scheduling tasks with discrete starting times
• scientific article; zbMATH DE number 1157215

Cites work

• scientific article; zbMATH DE number 1634827 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1534501 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• scientific article; zbMATH DE number 2221458 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Hybrid flow-shop scheduling problems with multiprocessor task systems.
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Scheduling UET task systems with concurrency on two parallel identical processors
• Scheduling multiprocessor tasks -- An overview
• Scheduling multiprocessor tasks for mean flow time criterion

Cited in

(14)

• Counting and enumeration complexity with application to multicriteria scheduling
• On the worst-case ratio of a compound multiprocessor scheduling algorithm
• Complexity results for scheduling tasks with discrete starting times
• A composite algorithm for multiprocessor scheduling
• The complexity of multidimensional periodic scheduling
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Complexity of the Project Sequencing Problem
• A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring
• The single-processor scheduling problem with time restrictions: complexity and related problems
• Scheduling in the presence of processor networks : complexity and approximation
• Complexity of a class of task scheduling problems
• Scheduling multiprocessor UET tasks of two sizes
• The counting complexity of a simple scheduling problem
• Complexity of scheduling problems with multi-purpose machines

This page was built for publication: Computational complexity of some scheduling problems with multiprocessor tasks

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