Convex quadratic and semidefinite programming relaxations in scheduling
From MaRDI portal
Publication:3196615
DOI10.1145/375827.375840zbMath1323.90024OpenAlexW2102588682MaRDI QIDQ3196615
Publication date: 30 October 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15671
convex optimizationscheduling theoryapproximation algorithmsrandomized algorithmsworst-case ratiounrelated machinesperformance guarantee
Semidefinite programming (90C22) Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Fast First-Order Algorithms for Packing–Covering Semidefinite Programs, A survey of scheduling with controllable processing times, Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints, Optimal restricted due date assignment in scheduling, Unrelated Machine Scheduling with Stochastic Processing Times, The Boolean quadratic programming problem with generalized upper bound constraints, Scheduling on unrelated machines under tree-like precedence constraints, An exact extended formulation for the unrelated parallel machine total weighted completion time problem, Unrelated parallel machine scheduling with new criteria: complexity and models, Approximation algorithms for multiprocessor scheduling under uncertainty, An exact quadratic programming approach based on convex reformulation for seru scheduling problems, The symmetric quadratic knapsack problem: approximation and scheduling applications, Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, Approximation algorithms for indefinite complex quadratic maximization problems, GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times, An approximation algorithm for scheduling two parallel machines with capacity constraints., Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling, Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines, Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality, Scheduling with earliness-tardiness penalties and parallel machines, Approximation algorithms for scheduling problems with a modified total weighted tardiness objective, Approximability of average completion time scheduling on unrelated machines, MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, Globally solving nonconvex quadratic programming problems via completely positive programming, Designing PTASs for MIN-SUM scheduling problems, A \(\frac 32\)-approximation algorithm for parallel machine scheduling with controllable processing times, An approximate algorithm for a high-multiplicity parallel machine scheduling problem, Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search, Scheduling equal length jobs with eligibility restrictions, A new approximation algorithm for unrelated parallel machine scheduling with release dates, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, Decentralized utilitarian mechanisms for scheduling games, A study of the quadratic semi-assignment polytope, Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems, Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations, Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, Concentration inequalities for nonlinear matroid intersection, Unnamed Item, Multi-wave tabu search for the Boolean quadratic programming problem with generalized upper bound constraints, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product
