This paper addresses the complex issue of resource-constrained scheduling, an
NP-hard problem that spans critical areas including chip design and
high-performance computing. Traditional scheduling methods often stumble over
scalability and applicability challenges. We propose a novel approach using a
differentiable combinatorial scheduling framework, utilizing Gumbel-Softmax
differentiable sampling technique. This new technical allows for a fully
differentiable formulation of linear programming (LP) based scheduling,
extending its application to a broader range of LP formulations. To encode
inequality constraints for scheduling tasks, we introduce \textit{constrained
Gumbel Trick}, which adeptly encodes arbitrary inequality constraints.
Consequently, our method facilitates an efficient and scalable scheduling via
gradient descent without the need for training data. Comparative evaluations on
both synthetic and real-world benchmarks highlight our capability to
significantly improve the optimization efficiency of scheduling, surpassing
state-of-the-art solutions offered by commercial and open-source solvers such
as CPLEX, Gurobi, and CP-SAT in the majority of the designs.

通过使用一个可微分的组合调度框架和 Gumbel-Softmax 可微分取样技术，本文提出了一种解决资源受限调度问题的新方法，扩展了线性规划的应用范围，并通过对比评估结果表明，在优化效率方面，超过了 CPLEX、Gurobi 和 CP-SAT 等现有解决方案的能力。

规模可区分的组合调度算法

Differentiable Combinatorial Scheduling at Scale

Our focus is on projects, i.e., business processes, which are emerging as the
economic drivers of our times. Differently from day-to-day operational
processes that do not require detailed planning, a project requires planning
and resource-constrained scheduling for coordinating resources across sub- or
related projects and organizations. A planner in charge of project planning has
to select a set of activities to perform, determine their precedence
constraints, and schedule them according to temporal project constraints. We
suggest a data-driven project planning approach for classes of projects such as
infrastructure building and information systems development projects. A project
network is first learned from historical records. The discovered network
relaxes temporal constraints embedded in individual projects, thus uncovering
where planning and scheduling flexibility can be exploited for greater benefit.
Then, the network, which contains multiple project plan variations, from which
one has to be selected, is enriched by identifying decision rules and frequent
paths. The planner can rely on the project network for: 1) decoding a project
variation such that it forms a new project plan, and 2) applying
resource-constrained project scheduling procedures to determine the project's
schedule and resource allocation. Using two real-world project datasets, we
show that the suggested approach may provide the planner with significant
flexibility (up to a 26% reduction of the critical path of a real project) to
adjust the project plan and schedule. We believe that the proposed approach can
play an important part in supporting decision making towards automated
data-driven project planning.

对于基础设施建设和信息系统开发等类别的项目，我们提出了一种数据驱动的项目规划方法，该方法通过学习历史记录构建项目网络，从而为规划人员提供灵活性，将对项目计划和时间表进行调整的决策支持。