Cover Image

Scheduling on Identical Machines with Setup Time and Unknown Execution Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kawase, Yasushi, Makino, Kazuhisa, Phan, Vinh Long, Sumita, Hanna
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
by: Kawase, Yasushi, et al.
Published: (2023)

Perfect Matchings and Popularity in the Many-to-Many Setting
by: Kavitha, Telikepalli, et al.
Published: (2024)

Online Matching with Delays and Size-based Costs
by: Kawase, Yasushi, et al.
Published: (2024)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
by: Deppert, Max A., et al.
Published: (2025)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

Composition Orderings for Linear Functions and Matrix Multiplication Orderings
by: Kubo, Susumu, et al.
Published: (2024)

Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio
by: Yoshinaga, Toru, et al.
Published: (2026)

Characterizing the integer points in 2-decomposable polyhedra by closedness under operations
by: Kimura, Kei, et al.
Published: (2024)

Online Flexible Busy Time Scheduling on Heterogeneous Machines
by: Calinescu, Gruia, et al.
Published: (2024)

A Competitive Algorithm for Throughput Maximization on Identical Machines
by: Moseley, Benjamin, et al.
Published: (2021)

Weighted Chairman Assignment and Flow-Time Scheduling
by: Liu, Siyue, et al.
Published: (2025)

Total Completion Time Scheduling Under Scenarios
by: Bosman, Thomas, et al.
Published: (2024)

A general framework for finding diverse solutions via network flow and its applications
by: Iwamasa, Yuni, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Submodular Max-Min Allocation under Identical Valuations
by: Boehmer, Kimon
Published: (2026)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
by: Chen, Qingyun, et al.
Published: (2024)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
by: Lindermayr, Alexander, et al.
Published: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
by: Brinkop, Hauke, et al.
Published: (2022)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
by: Mieno, Takuya, et al.
Published: (2024)

Shortest cover after edit
by: Mitani, Kazuki, et al.
Published: (2024)

Unbreakable Decomposition in Close-to-Linear Time
by: Anand, Aditya, et al.
Published: (2024)

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
by: Heeger, Klaus, et al.
Published: (2024)

Detection of Common Subtrees with Identical Label Distribution
by: Azaïs, Romain, et al.
Published: (2023)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
by: Chen, Tianqi, et al.
Published: (2025)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
by: Jeang, John, et al.
Published: (2026)

Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
by: Hertrich, Christoph, et al.
Published: (2020)

Adwords with Unknown Budgets and Beyond
by: Udwani, Rajan
Published: (2021)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
by: Li, Shi
Published: (2024)

Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
by: Mendoza-Cadena, Mirabel, et al.
Published: (2026)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
by: Blauth, Jannis, et al.
Published: (2022)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
by: Oka, Keigo, et al.
Published: (2026)