Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems

DOI10.1016/0377-2217(95)00350-9zbMath0916.90144OpenAlexW2082853263MaRDI QIDQ1266535

Peter Brucker, Andreas Krämer

Publication date: 7 October 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00350-9

zbMATH Keywords

makespanflow shopjob shoppolynomial time algorithmsmultiprocessor tasksresource-constrained schedulingmean flow timeweighted number of tardy tasks

Mathematics Subject Classification ID

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

Related Items (20)

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ Polynomially solvable cases of the project scheduling problem with changing consumption and supply rates of nonaccumulative resources ⋮ Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective ⋮ Increasing the revenue of self-storage warehouses by optimizing order scheduling ⋮ Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors ⋮ A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks ⋮ Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Multicoloring trees. ⋮ Hybrid flow-shop scheduling problems with multiprocessor task systems. ⋮ A job-shop problem with one additional resource type ⋮ On distance constrained labeling of disk graphs ⋮ A Lagrangian heuristic for satellite range scheduling with resource constraints ⋮ Computational complexity of some scheduling problems with multiprocessor tasks ⋮ Scheduling multiprocessor tasks -- An overview ⋮ Production, maintenance and resource scheduling: a review ⋮ Personnel scheduling and supplies provisioning in emergency relief operations ⋮ Parallel machine scheduling with additional resources: notation, classification, models and solution methods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiprocessor scheduling with communication delays
• Scheduling subject to resource constraints: Classification and complexity
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• A linear time algorithm for restricted bin packing and scheduling problems
• Shop scheduling problems with multiprocessor tasks on dedicated processors
• An efficient algorithm for a job shop problem
• On Scheduling Independent Tasks with Restricted Execution Times
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems