Scheduling meets n-fold integer programming

DOI10.1007/S10951-017-0550-0MaRDI QIDQ2317129zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dušan Knop, Martin Koutecký

Publication date 8 August 2019

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.02611

zbMATH Keywords

fixed parameterized tractabilityscheduling on parallel machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Integer programming (90C10)

Abstract: Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In 2014, Mnich and Wiese initiated a systematic study in this direction. In this paper we continue this study and show that several additional cases of fundamental scheduling problems are fixed parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where p max is the maximum processing time of a job and w max is the maximum weight of a job: - Makespan minimization on uniformly related machines $(Q||C_{max})$ parameterized by $p_{max}$, - Makespan minimization on unrelated machines $(R||C_{max})$ parameterized by $p_{max}$ and the number of kinds of machines, - Sum of weighted completion times minimization on unrelated machines $(R||sum{w}_i{C}_i)$ parameterized by $p_{max}+w_{max}$ and the number of kinds of machines, - The same problem, $(R||sum{w}_i{C}_i),$ parameterized by the number of distinct job times and the number of machines.

Recommendations

• Scheduling and fixed-parameter tractability
• Scheduling and fixed-parameter tractability
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• High-multiplicity \(N\)-fold IP via configuration LP
• \(n\)-fold integer programming in cubic time

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complete 4-parametric complexity classification of short shop scheduling problems
• A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Algebraic and geometric ideas in the theory of discrete optimization
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Bin packing with fixed number of bins revisited
• Completing partial schedules for open shop with unit processing times and routing
• Complexity of preemptive minsum scheduling on unrelated parallel machines
• Convex separable optimization is not much harder than linear optimization
• Fifty years of scheduling: a survey of milestones
• Fundamentals of parameterized complexity
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Huge unimodular \(n\)-fold programs
• Integer Programming with a Fixed Number of Variables
• Integer optimization on convex semialgebraic sets
• Nonlinear discrete optimization. An algorithmic theory
• On the parametric complexity of schedules to minimize tardy tasks.
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Scheduling and fixed-parameter tractability
• Scheduling independent tasks to reduce mean finishing time
• Scheduling two competing agents when one agent has significantly fewer jobs
• Semidefinite Optimization and Convex Algebraic Geometry
• Strip Graphs: Recognition and Scheduling
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• The third comprehensive survey on scheduling problems with setup times/costs
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• Voting and bribing in single-exponential time
• \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
• \(n\)-fold integer programming in cubic time

Cited in

(34)

• Combinatorial \(n\)-fold integer programming and applications
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• On the parameterized tractability of single machine scheduling with rejection
• A multivariate complexity analysis of the material consumption scheduling problem
• On the complexity of scheduling problems with a fixed number of parallel identical machines
• About the complexity of two-stage stochastic IPs
• High-multiplicity \(N\)-fold IP via configuration LP
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Integer programming in parameterized complexity: three miniatures
• A general scheme for solving a large set of scheduling problems with rejection in FPT time
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Improved approximation algorithms for two-stage flowshops scheduling problem
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Parameterized complexity of a coupled-task scheduling problem
• Scheduling and fixed-parameter tractability
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Integer programming in parameterized complexity: five miniatures
• scientific article; zbMATH DE number 7651172 (Why is no real title available?)
• Serial batching to minimize the weighted number of tardy jobs
• Block-structured integer programming: can we parameterize without the largest coefficient?
• Tight complexity lower bounds for integer linear programming with few constraints
• Scheduling personal finances via integer programming
• About the Complexity of Two-Stage Stochastic IPs
• Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
• Fixed-parameter approximation schemes for weighted flowtime
• Empowering the configuration-IP: new PTAS results for scheduling with setup times
• On the NP-hardness of two scheduling problems under linear constraints
• On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)
• Moderate exponential-time algorithms for scheduling problems
• Combinatorial \(n\)-fold integer programming and applications
• Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines

This page was built for publication: Scheduling meets \(n\)-fold integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317129)