Approximation algorithms for scheduling unrelated parallel machines

Numerical mathematical programming methods (65K05) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Vertex cover meets scheduling, Dynamic scheduling on parallel machines, Parallel machine scheduling under a grade of service provision, Group activity selection problem with approval preferences, Online makespan minimization with budgeted uncertainty, Truthful mechanism design for multidimensional scheduling via cycle monotonicity, No-wait scheduling in single-hop multi-channel lans, Unrelated parallel machine scheduling using local search, On the optimality of exact and approximation algorithms for scheduling problems, An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, Scheduling of conditional executed jobs on unrelated processors, Setting lower bounds on truthfulness, A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search, Exact and approximation algorithms for makespan minimization on unrelated parallel machines, Tight approximations for resource constrained scheduling and bin packing, On the existence of schedules that are near-optimal for both makespan and total weighted completion time, Machine scheduling with resource dependent processing times, Approximation algorithms for multiprocessor scheduling under uncertainty, Moderately exponential approximation for makespan minimization on related machines, Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems, Minimizing average flow-time under knapsack constraint, Strong LP formulations for scheduling splittable jobs on unrelated machines, Scheduling and fixed-parameter tractability, On the configuration LP for maximum budgeted allocation, Coupled and \(k\)-sided placements: generalizing generalized assignment, Fast approximation algorithms for job scheduling with processing set restrictions, The price of envy-freeness in machine scheduling, Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, Improved lower bounds for non-utilitarian truthfulness, Scheduling jobs with equal processing times subject to machine eligibility constraints, A lower bound of \(1+\varphi \) for truthful scheduling mechanisms, Restricted assignment scheduling with resource constraints, Assigning papers to referees, On-line load balancing made simple: greedy strikes back, On-line algorithms for the channel assignment problem in cellular networks., Approximation algorithms for general packing problems and their application to the multicast congestion problem, Scheduling unit length jobs on parallel machines with lookahead information, Robust algorithms for preemptive scheduling, Grouping techniques for scheduling problems: simpler and faster, Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, On the approximation of the single source \(k\)-splittable flow problem, Dynamic scheduling for heterogeneous desktop grids, On the configuration-LP for scheduling on unrelated machines, A 3/2-approximation algorithm for the graph balancing problem with two weights, A comment on scheduling on uniform machines under chain-type precedence constraints, On the geometry, preemptions and complexity of multiprocessor and shop scheduling, Online scheduling on parallel machines with two goS levels, Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem, Performance guarantees for scheduling algorithms under perturbed machine speeds, Unrelated parallel machine scheduling -- perspectives and progress, Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming, Estimating the makespan of the two-valued restricted assignment problem, Min-max cover of a graph with a small number of parts, Approximation algorithms for scheduling on multi-core processor with shared speedup resources, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, A note on the prize collecting traveling salesman problem, Parallel machine scheduling with speed-up resources, Truthful mechanism design via correlated tree rounding, The efficiency of fair division, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, A hierarchical solution approach for a multicommodity distribution problem under a special cost structure, Online scheduling of two job types on a set of multipurpose machines with unit processing times, Maximum bipartite flow in networks with adaptive channel width, Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree, Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach, Multipurpose machine scheduling with rejection and identical job processing times, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, Minimizing flow time on a constant number of machines with preemption, A note on ``An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, A note on graph balancing problems with restrictions, An improved lower bound for rank four scheduling, Iterated greedy local search methods for unrelated parallel machine scheduling, On \((1, \epsilon )\)-restricted max-min fair allocation problem, Optimal matroid partitioning problems, Scheduling jobs with release and delivery times subject to nested eligibility constraints, Algorithms for hierarchical and semi-partitioned parallel scheduling, 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines, Approximation algorithms for the load-balanced capacitated vehicle routing problem, Approximation algorithms for the multiprocessor scheduling with submodular penalties, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Coordination mechanisms for selfish scheduling, Approximate algorithms for unrelated machine scheduling to minimize makespan, Geometric quadrisection in linear time, with application to VLSI placement, Truthful mechanisms for two-range-values variant of unrelated scheduling, Optimal location with equitable loads, A lower bound for scheduling mechanisms, The Pareto frontier of inefficiency in mechanism design, Approximability of flow shop scheduling, Heuristics for unrelated machine scheduling with precedence constraints, Scheduling parallel machines with inclusive processing set restrictions and job release times, A lexicographic approach to bi-objective loading of a flexible assembly system, A cutting plane algorithm for the unrelated parallel machine scheduling problem, Priority algorithms for makespan minimization in the subset model., Off-line temporary tasks assignment., Cellular control of manufacturing systems, Approximation algorithms for general parallel task scheduling, An approximation algorithm for the generalized assignment problem, Max-min fair rate allocation and routing in energy harvesting networks: algorithmic analysis, Balancing perfectly periodic service schedules: An application from recycling and waste management, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Optimal Coordination Mechanisms for Unrelated Machine Scheduling, On some special cases of the restricted assignment problem, Efficient coordination mechanisms for unrelated machine scheduling, Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems, Task scheduling in networks, Energy-Efficient Algorithms for Non-preemptive Speed-Scaling, APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS, Online load balancing of temporary tasks, Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints, Restricted max-min allocation: integrality gap and approximation algorithm, An \(R||C_{\max}\) quantum scheduling algorithm, The VCG Mechanism for Bayesian Scheduling, Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms, Scheduling on unrelated machines under tree-like precedence constraints, A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds, Exact makespan minimization of unrelated parallel machines, Parallel machine scheduling with nested processing set restrictions, Approximating Scheduling Machines with Capacity Constraints, Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times, On the extension complexity of scheduling polytopes, Makespan minimization on unrelated parallel machines with a few bags, A comparative study of solution representations for the unrelated machines environment, ONLINE SCHEDULING OF MIXED CPU-GPU JOBS, Wave order picking under the mixed-shelves storage strategy: a solution method and advantages, Robust scheduling with budgeted uncertainty, On-line scheduling of parallel jobs, Approximation algorithms for the graph balancing problem with two speeds and two job lengths, Strategic Scheduling Games: Equilibria and Efficiency, Unnamed Item, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Unnamed Item, A complete 4-parametric complexity classification of short shop scheduling problems, Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling, Structural parameters for scheduling with assignment restrictions, Structured Instances of Restricted Assignment with Two Processing Times, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Graph balancing: a special case of scheduling unrelated parallel machines, Compact LP Relaxations for Allocation Problems, Matching with sizes (or scheduling with processing set restrictions), Matching with sizes (or scheduling with processing set restrictions), Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints, Santa Claus Meets Hypergraph Matchings, A Quasi-Polynomial Approximation for the Restricted Assignment Problem, Scheduling of Jobs on Dissimilar Parallel Machine Using Computational Intelligence Algorithms, Makespan minimization in online scheduling with machine eligibility, Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget, A Family of Scheduling Algorithms for Hybrid Parallel Platforms, Capacitated Vehicle Routing with Non-uniform Speeds, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, 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, Task assignment algorithms for two-type heterogeneous multiprocessors, Real-time scheduling with resource sharing on heterogeneous multiprocessors, Online Scheduling on a CPU-GPU Cluster, Online scheduling with equal processing times and machine eligibility constraints, On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems, An optimal rounding gives a better approximation for scheduling unrelated machines, Unnamed Item, Worst-case analysis for on-line service policies, Sublogarithmic approximation for telephone multicast, Parallel machine scheduling with nested job assignment restrictions, Heuristics for scheduling unrelated parallel machines, Unnamed Item, Approximation schemes for scheduling and covering on unrelated machines, Improved Lower Bounds for Non-utilitarian Truthfulness, ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors, Optimal online algorithms for scheduling on two identical machines under a grade of service, Capacitated Vehicle Routing with Nonuniform Speeds, Coordinating oligopolistic players in unrelated machine scheduling, Computing Nash equilibria for scheduling on restricted parallel links, A PTAS for Scheduling Unrelated Machines of Few Different Types, The Influence of Link Restrictions on (Random) Selfish Routing, Simpler and Better Algorithms for Minimum-Norm Load Balancing, New bounds for truthful scheduling on two unrelated selfish machines, Better Bin Packing Approximations via Discrepancy Theory, Latency Constrained Aggregation in Chain Networks Admits a PTAS, Complete Complexity Classification of Short Shop Scheduling, Upper and lower degree-constrained graph orientation with minimum penalty, POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION, A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates, Unnamed Item, Lazy Local Search Meets Machine Scheduling, Stochastic Load Balancing on Unrelated Machines, PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION, On minimizing the makespan when some jobs cannot be assigned on the same machine, Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, Multicriteria scheduling, EPTAS for load balancing problem on parallel machines with a non-renewable resource, Preemptive and non-preemptive scheduling on two unrelated parallel machines, Unnamed Item, Unnamed Item, GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE, Fair by design: multidimensional envy-free mechanisms, THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING, Task swapping networks in distributed systems, Performance guarantees of local search for minsum scheduling problems, Parallel Machines Scheduling with Deteriorating Maintenance Activities and Job Rejection, EPTAS for the dual of splittable bin packing with cardinality constraint, On competitive analysis for polling systems, Configuration balancing for stochastic requests, Time-flexible min completion time variance in a single machine by quadratic programming, Malleable scheduling beyond identical machines, Online max-min fair allocation, Resource time-sharing for IoT applications with deadlines, Competitive algorithms for demand response management in a smart grid, Fair division of indivisible goods: recent progress and open questions, On the complexity of scheduling unrelated parallel machines with limited preemptions, On best-of-both-worlds fair-share allocations, Polynomial-time combinatorial algorithm for general max-min fair allocation, Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs, Makespan minimization in online scheduling with machine eligibility, EPTAS for load balancing problem on parallel machines with a non-renewable resource, Scheduling experiments on a nulear reactor using mixed integer programming, Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility, A new lower bound for deterministic truthful scheduling, Related machine scheduling with machine speeds satisfying linear constraints, Approximation results for makespan minimization with budgeted uncertainty, Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, An EPTAS for scheduling on unrelated machines of few different types

Cites Work