Paper Reading AI Learner

Two-Stage Learning For the Flexible Job Shop Scheduling Problem

2023-01-23 20:23:35
Wenbo Chen, Reem Khir, Pascal Van Hentenryck

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

PDF

https://arxiv.org/pdf/2301.09703.pdf


Tags
3D Action Action_Localization Action_Recognition Activity Adversarial Agent Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot