Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.01356 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- This paper introduces bucket calculus, a novel mathematical framework that fundamentally transforms the computational complexity landscape of parallel machine scheduling optimization. We address the strongly NP-hard problem $P2|r_j|C_{\max}$ through an innovative adaptive temporal discretization methodology that achieves exponential complexity reduction from $O(T^n)$ to $O(B^n)$ where $B \ll T$, while maintaining near-optimal solution quality. Our bucket-indexed mixed-integer linear programming (MILP) formulation exploits dimensional complexity heterogeneity through precision-aware discretization, reducing decision variables by 94.4\% and achieving a theoretical speedup factor $2.75 \times 10^{37}$ for 20-job instances. Theoretical contributions include partial discretization theory, fractional bucket calculus operators, and quantum-inspired mechanisms for temporal constraint modeling. Empirical validation on instances with 20--400 jobs demonstrates 97.6\% resource utilization, near-perfect load balancing ($σ/μ= 0.006$), and sustained performance across problem scales with optimality gaps below 5.1\%. This work represents a paradigm shift from fine-grained temporal discretization to multi-resolution precision allocation, bridging the fundamental gap between exact optimization and computational tractability for industrial-scale NP-hard scheduling problems.