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.
翻译:灵活的工作商店日程安排问题(FJSP)是制造和服务环境中出现的一个重要组合优化问题。FJSP由两个子问题组成,一个是分配给机器的任务问题,另一个是决定其选定机器的任务起始时间的时间安排问题。解决FJSP现实规模和构成情况是一个持续的挑战,即使是在简化的、决定性的假设下也是如此。本文受到供应链、制造业和服务业务不可避免的随机性和不确定性的驱动,研究利用深层次学习框架为FJSP产生快速和准确近似的可能性。特别是,本文件提出一个两阶段学习框架2SLFJSP,明确模拟FJSP决定的等级性质,使用信任分层机制从分配预测中为时间安排阶段创造适当的情况,并利用新的断析公式改进学习能力。本文件对FJSP基准图书馆的一些实例进行了评估,结果显示,2SL-FSP可以在最近使用的高级实践方法中产生高品质解决方案,他使用的普通实践强化方法,他最近使用的普通实践学习方法比过去第二年的另一种状态。