Complexity Results for Multiprocessor Scheduling under Resource Constraints
From MaRDI portal
Publication:4140712
DOI10.1137/0204035zbMath0365.90076OpenAlexW2095381673WikidataQ62270107 ScholiaQ62270107MaRDI QIDQ4140712
Michael R. Garey, David S. Johnson
Publication date: 1975
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0204035
Related Items
The complexity of the 0/1 multi-knapsack problem, Small polyomino packing, Complexity of equilibrium in competitive diffusion games on social networks, Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph, Scheduling tasks on two processors with deadlines and additional resources, Minimizing mean flow time with parallel processors and resource constraints, Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity, Scheduling: agreement graph vs resource constraints, Scheduling with conflicts: Online and offline algorithms, Maximizing data locality in distributed systems, TETRIS IS HARD, EVEN TO APPROXIMATE, New trends in machine scheduling, On permutation schedules for two-machine flow shops with buffer constraints and constant processing times on one machine, Do branch lengths help to locate a tree in a phylogenetic network?, Time slot scheduling of compatible jobs, Allocation of partially renewable resources: Concept, capabilities, and applications, On the Scalability of Constraint Solving for Static/Off-Line Real-Time Scheduling, On optimal coverage of a tree with multiple robots, Minimizing the total weighted completion time of fully parallel jobs with integer parallel units, Multitask \(n\)-vehicle exploration problem: complexity and algorithm, Extending partial representations of circular-arc graphs, New results in two identical machines scheduling with agreement graphs, Dissection with the Fewest Pieces is Hard, Even to Approximate, Bounds for the Convergence Time of Local Search in Scheduling Problems, Solving the resource constrained deadline scheduling problem via reduction to the network flow problem, Unnamed Item, Priority-based bin packing with subset constraints, Towards optimal formwork pairing on construction sites, An improved algorithm for parallel machine scheduling under additional resource constraints, Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints., Output Rate Variation Problem: Some Heuristic Paradigms and Dynamic Programming, An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem, On the continuous working problem, Restricted assignment scheduling with resource constraints, An experimental analysis of local minima to improve neighbourhood search., On the calendar planning problem with renewable resource, Single machine group scheduling with family setups to minimize total tardiness, Complexity of Project Scheduling Problem with Nonrenewable Resources, Scheduling on Two Unbounded Resources with Communication Costs, Weighted total acquisition, Upward point set embeddings of paths and trees, On the classes of interval graphs of limited nesting and count of lengths, Some remarks on 3-partitions of multisets, Multi-parallel work centers scheduling optimization with shared or dedicated resources in low-volume low-variety production systems, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, On-line scheduling of parallel jobs in a list, Optimizing version release dates of research and development long-term processes, Extending partial representations of proper and unit interval graphs, Mathematical models and decomposition methods for the multiple knapsack problem, Implementing mixed-criticality synchronous reactive programs upon uniprocessor platforms, Shiftable intervals, A variant of multi-task \(n\)-vehicle exploration problem: maximizing every processor's average profit, Buffer management for colored packets with deadlines, Multi-dimensional bin packing problems with guillotine constraints, NP-complete scheduling problems, Event-based MILP models for resource-constrained project scheduling problems, Enriched metaheuristics for the resource constrained unrelated parallel machine scheduling problem, Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines, Fast parallel heuristics for the job shop scheduling problem, Treemaps for Directed Acyclic Graphs, Resource constrained scheduling as generalized bin packing, On \(k\)-partitions of multisets with equal sums, Comparison of lower bounds to the lengths of deterministic multiprocessor schedules, Algorithms for minimizing maximum lateness with unit length tasks and resource constraints, Approximation algorithms for replenishment problems with fixed turnover times, Realization problems on reachability sequences, Bounds on list scheduling of UET tasks with restricted resource constraints, Two simulated annealing-based heuristics for the job shop scheduling problem, Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times, NP-Complete operations research problems and approximation algorithms, Approximation algorithms for scheduling unrelated parallel machines, Complexity of Lambek calculi with modalities and of total derivability in grammars, The Complexity of Fixed-Height Patterned Tile Self-assembly, On the complexity of coordinated display of multimedia objects, Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application, A linear time algorithm for restricted bin packing and scheduling problems, Bin packing and multiprocessor scheduling problems with side constraint on job types, Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs, Structure and complexity of extreme Nash equilibria, Scheduling Opposing Forests, Scheduling subject to resource constraints: Classification and complexity, Network flows and non-guillotine cutting patterns, Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach, Production, maintenance and resource scheduling: a review, On the Membership Problem of Permutation Grammars — A Direct Proof of NP-Completeness, On the complexity of iterated shuffle, Extending partial representations of subclasses of chordal graphs, Scheduling periodic tasks on uniform multiprocessors, Scheduling with an orthogonal resource constraint, An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems, Tabu search in audit scheduling, Parallel machine scheduling with additional resources: notation, classification, models and solution methods
