Shop scheduling problems with multiprocessor tasks on dedicated processors

DOI10.1007/BF02099688zbMath0831.90071OpenAlexW2076508578MaRDI QIDQ1897372

Andreas Krämer, Peter Brucker

Publication date: 27 August 1995

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02099688

zbMATH Keywords

makespan minimizationmultiprocessor tasksNP-hard problemsshop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Feasible insertions in job shop scheduling, short cycles and stable sets, Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Tabu-search for the multi-mode job-shop problem, A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop., Surgical case scheduling as a generalized job shop scheduling problem, Feasible job insertions in the multi-processor-task job shop, Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems, Scheduling multiprocessor tasks -- An overview, Scheduling multiprocessor tasks on two parallel processors

Cites Work

• Unnamed Item
• Multiprocessor scheduling with communication delays
• An efficient algorithm for the job-shop problem with two jobs
• Scheduling multiprocessor tasks on three dedicated processors
• Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• NP-hardness of shop-scheduling problems with three jobs
• An efficient algorithm for a job shop problem
• Optimal two- and three-stage production schedules with setup times included
• Integer Programming with a Fixed Number of Variables
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Open shop problems with unit time operations
• Open Shop Scheduling to Minimize Finish Time
• Flowshop and Jobshop Schedules: Complexity and Approximation
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Nonpreemptive scheduling of independent tasks with prespecified processor allocations