Exact and Approximate Algorithms for Scheduling Nonidentical Processors

DOI10.1145/321941.321951zbMath0329.68041OpenAlexW1992734168WikidataQ128788428 ScholiaQ128788428MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (only showing first 100 items - show all)

Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ Bin stretching with migration on two hierarchical machines ⋮ Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs ⋮ Algorithmic mechanism design ⋮ Vertex cover meets scheduling ⋮ Richard Bellman's contributions to computer science ⋮ Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems ⋮ A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis ⋮ Parallel approximation schemes for subset sum and knapsack problems ⋮ Unrelated parallel machine scheduling using local search ⋮ Non-preemptive Scheduling on Machines with Setup Times ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Scheduling on machines with variable service rates ⋮ Approximation schemes for a class of subset selection problems ⋮ On maximal and minimal triangular planar graphs: an optimization approach ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Setting lower bounds on truthfulness ⋮ Improving the complexities of approximation algorithms for optimization problems ⋮ A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search ⋮ Exact and approximation algorithms for makespan minimization on unrelated parallel machines ⋮ Improved optimal algorithms for scheduling unit-length independent tasks on uniform machines ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Streaming algorithms for multitasking scheduling with shared processing ⋮ Complete formulations of polytopes related to extensions of assignment matrices ⋮ Approximation schemes for subset-sums ratio problems ⋮ Robust scheduling with budgeted uncertainty ⋮ Moderately exponential approximation for makespan minimization on related machines ⋮ Semi-online scheduling with known maximum job size on two uniform machines ⋮ Implementation of optimal schedules in outsourcing with identical suppliers ⋮ The price of anarchy for utilitarian scheduling games on related machines ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Task scheduling with precedence constraints to minimize the total completion time ⋮ Efficient scheduling of tasks without full use of processor resources ⋮ Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty ⋮ Heuristics and augmented neural networks for task scheduling with non-identical machines ⋮ A lower bound of \(1+\varphi \) for truthful scheduling mechanisms ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ Structural parameters for scheduling with assignment restrictions ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ General approximation algorithms for some arithmetical combinatorial problems ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Restricted assignment scheduling with resource constraints ⋮ Approximate strong equilibria in job scheduling games with two uniformly related machines ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Two-dimensional packing with conflicts ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Performance of service policies in a specialized service system with parallel servers ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems ⋮ TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION ⋮ Min-max cover of a graph with a small number of parts ⋮ SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS ⋮ Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors ⋮ Real-time scheduling with resource sharing on heterogeneous multiprocessors ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ An optimal rounding gives a better approximation for scheduling unrelated machines ⋮ Unnamed Item ⋮ A comment on parallel-machine scheduling under a grade of service provision to minimize makespan ⋮ Optimal collusion-resistant mechanisms with verification ⋮ Worst-case analysis for on-line service policies ⋮ Parallel machine scheduling with job assignment restrictions ⋮ Multipurpose machine scheduling with rejection and identical job processing times ⋮ Heuristics for scheduling unrelated parallel machines ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ Computing Nash equilibria for scheduling on restricted parallel links ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines ⋮ Unnamed Item ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Planning production using mathematical programming: The case of a woodturning company ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ A linear compound algorithm for uniform machine scheduling ⋮ NP-Complete operations research problems and approximation algorithms ⋮ Approximation algorithms for scheduling unrelated parallel machines ⋮ A priority based unbalanced time minimization assignment problem ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ A note on MULTIFIT scheduling for uniform machines ⋮ Improved price of anarchy for machine scheduling games with coordination mechanisms ⋮ Tighter approximation bounds for LPT scheduling in two special cases ⋮ Optimal location with equitable loads ⋮ Parallel machine batching and scheduling with deadlines ⋮ A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix ⋮ Approximation scheduling algorithms: a survey ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times ⋮ Structure and complexity of extreme Nash equilibria ⋮ A cutting plane algorithm for the unrelated parallel machine scheduling problem ⋮ Solving min-max shortest-path problems on a network ⋮ Off-line temporary tasks assignment. ⋮ GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE ⋮ Worst-case analysis of a scheduling algorithm ⋮ Analysis of a linear programming heuristic for scheduling unrelated parallel machines ⋮ Analysis of the Q.A.D. algorithm for an homogeneous multiprocessor computing model with independent memories

This page was built for publication: Exact and Approximate Algorithms for Scheduling Nonidentical Processors