Abstract
The Flexible Job-shop Scheduling Problem (FJSP) is an important combinatorial optimization problem that arises in manufacturing and service settings. FJSP is composed of two subproblems, an assignment problem that assigns tasks to machines, and a scheduling problem that determines the starting times of tasks on their chosen machines. Solving FJSP instances of realistic size and composition is an ongoing challenge even under simplified, deterministic assumptions. Motivated by the inevitable randomness and uncertainties in supply chains, manufacturing, and service operations, this paper investigates the potential of using a deep learning framework to generate fast and accurate approximations for FJSP. In particular, this paper proposes a two-stage learning framework 2SLFJSP that explicitly models the hierarchical nature of FJSP decisions, uses a confidence-aware branching scheme to generate appropriate instances for the scheduling stage from the assignment predictions and leverages a novel symmetry-breaking formulation to improve learnability. 2SL-FJSP is evaluated on instances from the FJSP benchmark library. Results show that 2SL-FJSP can generate high-quality solutions in milliseconds, outperforming a state-of-the-art reinforcement learning approach recently proposed in the literature, and other heuristics commonly used in practice.
Abstract (translated)
灵活的制造和服务调度问题(FJSP)是一个在制造和服务水平设置中产生的重要组合优化问题。FJSP由两个子问题组成,即任务分配问题,该问题将任务分配给机器,以及任务调度问题,该问题确定任务在其选定机器上的开始时间。即使在简单、确定性假设下,解决FJSP的实际规模和组成问题仍然是一个持续的挑战。受供应链、制造和服务水平操作不可避免的随机和不确定性的启发,本文研究了使用深度学习框架生成FJSP快速而准确的近似的可能性。特别,本文提出了一个两阶段的学习框架2SLFJSP,该框架 explicitly models FJSP决策的Hierarchical nature,使用具有自我意识分支结构的自信分支计划,从任务分配预测中生成调度阶段适当的实例,并利用一种新的破坏对称的配方来提高学习性。2SL-FJSP在FJSP基准库中实例的评估中得到了评价。结果显示,2SL-FJSP可以在毫秒级内生成高质量的解决方案,比最近在文献中提出的先进的奖励学习方法以及通常在实践中使用的其他启发式方法表现更好。
URL
https://arxiv.org/abs/2301.09703