Exact and Approximate Algorithms for Scheduling Nonidentical Processors

DOI10.1145/321941.321951zbMath0329.68041MaRDI QIDQ4095869

Ellis Horowitz, Sartaj K. Sahni

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321941.321951

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

On maximal and minimal triangular planar graphs: an optimization approach, Improved optimal algorithms for scheduling unit-length independent tasks on uniform machines, Task scheduling with precedence constraints to minimize the total completion time, Parallel machine scheduling with job assignment restrictions, Algorithmic mechanism design, Computing Nash equilibria for scheduling on restricted parallel links, Semi-online scheduling with known maximum job size on two uniform machines, Approximation algorithms for scheduling unrelated parallel machines, Mathematical programming formulations for machine scheduling: A survey, Two-dimensional packing with conflicts, Grouping techniques for scheduling problems: simpler and faster, Performance of service policies in a specialized service system with parallel servers, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, A comment on parallel-machine scheduling under a grade of service provision to minimize makespan, Iterated greedy local search methods for unrelated parallel machine scheduling, Planning production using mathematical programming: The case of a woodturning company, Tighter approximation bounds for LPT scheduling in two special cases, Optimal location with equitable loads, Exact and approximate algorithms for high-multiplicity parallel machine scheduling, Scheduling parallel machines with inclusive processing set restrictions and job release times, Worst-case analysis of a scheduling algorithm, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Richard Bellman's contributions to computer science, Parallel approximation schemes for subset sum and knapsack problems, Scheduling on machines with variable service rates, Efficient scheduling of tasks without full use of processor resources, General approximation algorithms for some arithmetical combinatorial problems, A linear compound algorithm for uniform machine scheduling, A note on MULTIFIT scheduling for uniform machines, Unrelated parallel machine scheduling using local search, A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search, Exact and approximation algorithms for makespan minimization on unrelated parallel machines, Parallel machine batching and scheduling with deadlines, Polynomial time approximation algorithms for machine scheduling: Ten open problems, A cutting plane algorithm for the unrelated parallel machine scheduling problem, Off-line temporary tasks assignment., Improving the complexities of approximation algorithms for optimization problems, Worst-case analysis for on-line service policies, Heuristics for scheduling unrelated parallel machines, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Approximation schemes for a class of subset selection problems, Heuristics and augmented neural networks for task scheduling with non-identical machines, An optimal rounding gives a better approximation for scheduling unrelated machines, Approximation schemes for scheduling and covering on unrelated machines, Structure and complexity of extreme Nash equilibria, SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS, GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE, Analysis of the Q.A.D. algorithm for an homogeneous multiprocessor computing model with independent memories, Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems, Unnamed Item, Unnamed Item, NP-Complete operations research problems and approximation algorithms, Approximation scheduling algorithms: a survey