Computational complexity of some scheduling problems with multiprocessor tasks

DOI10.1016/J.DISOPT.2005.08.001zbMATH Open1166.90344OpenAlexW2014334704MaRDI QIDQ1019301FDOQ1019301

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Title not available (Why is that?)
• Scheduling multiprocessor tasks -- An overview
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hybrid flow-shop scheduling problems with multiprocessor task systems.
• Scheduling UET task systems with concurrency on two parallel identical processors
• Title not available (Why is that?)
• Scheduling multiprocessor tasks for mean flow time criterion

Cited In (14)

• Complexity results for scheduling tasks with discrete starting times
• On the worst-case ratio of a compound multiprocessor scheduling algorithm
• A composite algorithm for multiprocessor scheduling
• The complexity of multidimensional periodic scheduling
• Complexity of the Project Sequencing Problem
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• 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
• Counting and enumeration complexity with application to multicriteria scheduling

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)