Cover Image

Updating Lower and Upper Bounds for the Job-Shop Scheduling Problem Test Instances

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Graviers, Marc-Emmanuel Coupvent des, Kobrosly, Lotfi, Guettier, Christophe, Cazenave, Tristan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics I.2.8
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem
by: Kobrosly, Lotfi, et al.
Published: (2025)

Flow Shop Scheduling with Stochastic Reentry
by: von Aspern, Maximilian, et al.
Published: (2026)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

The Days On Days Off Scheduling Problem
by: Nießen, Fabien, et al.
Published: (2024)

Fairness in Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2021)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Pinwheel Scheduling with Real Periods
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
by: Schade, Jamico, et al.
Published: (2023)

Circle graphs can be recognized in linear time
by: Paul, Christophe, et al.
Published: (2025)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Temporal Graph Realization With Bounded Stretch
by: Mertzios, George B., et al.
Published: (2025)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Testing Quasiperiodicity
by: Awofeso, Christine, et al.
Published: (2025)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
by: Swamy, Chaitanya, et al.
Published: (2025)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
by: Chen, Yu, et al.
Published: (2024)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

The Role of Dimension in the Online Chasing Problem
by: Papazov, Hristo
Published: (2023)

Solving the Multiobjective Quasi-Clique Problem
by: Santos, Daniela Scherer dos, et al.
Published: (2024)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
by: Bentert, Matthias, et al.
Published: (2026)

Lower Bounds for Leaf Rank of Leaf Powers
by: Høgemo, Svein
Published: (2024)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

Learning to Prune Instances of Steiner Tree Problem in Graphs
by: Zhang, Jiwei, et al.
Published: (2022)