Self-Evaluation for Job-Shop Scheduling

• URL: http://arxiv.org/abs/2502.08684v1
• Date: Wed, 12 Feb 2025 11:22:33 GMT
• Title: Self-Evaluation for Job-Shop Scheduling
• Authors: Imanol Echeverria, Maialen Murua, Roberto Santana,
• Abstract summary: Combinatorial optimization problems, such as scheduling and route planning, are crucial in various industries but are computationally intractable due to their NP-hard nature. We propose a novel framework that generates and evaluates subsets of assignments, moving beyond traditional stepwise approaches.
• Score: 1.3927943269211593
• License:
• Abstract: Combinatorial optimization problems, such as scheduling and route planning, are crucial in various industries but are computationally intractable due to their NP-hard nature. Neural Combinatorial Optimization methods leverage machine learning to address these challenges but often depend on sequential decision-making, which is prone to error accumulation as small mistakes propagate throughout the process. Inspired by self-evaluation techniques in Large Language Models, we propose a novel framework that generates and evaluates subsets of assignments, moving beyond traditional stepwise approaches. Applied to the Job-Shop Scheduling Problem, our method integrates a heterogeneous graph neural network with a Transformer to build a policy model and a self-evaluation function. Experimental validation on challenging, well-known benchmarks demonstrates the effectiveness of our approach, surpassing state-of-the-art methods.

Related papers

• Learning Task Representations from In-Context Learning [73.72066284711462]
  Large language models (LLMs) have demonstrated remarkable proficiency in in-context learning. We introduce an automated formulation for encoding task information in ICL prompts as a function of attention heads. We show that our method's effectiveness stems from aligning the distribution of the last hidden state with that of an optimally performing in-context-learned model.
  arXiv  Detail & Related papers  (2025-02-08T00:16:44Z)
• Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
  We present a simple and problem-independent sequence decoding method for self-improved learning. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives. Our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.
  arXiv  Detail & Related papers  (2024-07-24T12:06:09Z)
• Multi-objective Binary Differential Approach with Parameter Tuning for Discovering Business Process Models: MoD-ProM [2.3423913554158653]
  We consider the Binary Differential Evolution approach in a multi-objective framework for the task of process discovery. It is shown that the process models generated by the proposed approach are superior to or at least as good as those generated by the state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2024-06-25T16:53:55Z)
• Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
  We propose a switchable decision to accelerate inference by dynamically assigning resources for each data instance. Our method benefits from less cost during inference while keeping the same accuracy.
  arXiv  Detail & Related papers  (2024-05-07T17:44:54Z)
• Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement [1.1510009152620668]
  Current methods for constructive neural optimization usually train a policy using behavior cloning from expert solutions or policy gradient methods from reinforcement learning. We bridge the two by sampling multiple solutions for random instances using the current model in each epoch and then selecting the best solution as an expert trajectory for supervised imitation learning. We evaluate our approach on the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The models trained with our method achieve comparable performance and generalization to those trained with expert data.
  arXiv  Detail & Related papers  (2024-03-22T13:09:10Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling [6.4778725014634615]
  In CP solvers, the variable ordering strategy used to select which variable to explore first has a significant impact on solver effectiveness. We propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers.
  arXiv  Detail & Related papers  (2022-11-26T06:30:28Z)
• Task-Feature Collaborative Learning with Application to Personalized Attribute Prediction [166.87111665908333]
  We propose a novel multi-task learning method called Task-Feature Collaborative Learning (TFCL) Specifically, we first propose a base model with a heterogeneous block-diagonal structure regularizer to leverage the collaborative grouping of features and tasks. As a practical extension, we extend the base model by allowing overlapping features and differentiating the hard tasks.
  arXiv  Detail & Related papers  (2020-04-29T02:32:04Z)
• Continual Learning using a Bayesian Nonparametric Dictionary of Weight Factors [75.58555462743585]
  Naively trained neural networks tend to experience catastrophic forgetting in sequential task settings. We propose a principled nonparametric approach based on the Indian Buffet Process (IBP) prior, letting the data determine how much to expand the model complexity. We demonstrate the effectiveness of our method on a number of continual learning benchmarks and analyze how weight factors are allocated and reused throughout the training.
  arXiv  Detail & Related papers  (2020-04-21T15:20:19Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)
• Model-based Multi-Agent Reinforcement Learning with Cooperative Prioritized Sweeping [4.5497948012757865]
  We present a new model-based reinforcement learning algorithm, Cooperative Prioritized Sweeping. The algorithm allows for sample-efficient learning on large problems by exploiting a factorization to approximate the value function. Our method outperforms the state-of-the-art algorithm sparse cooperative Q-learning algorithm, both on the well-known SysAdmin benchmark and randomized environments.
  arXiv  Detail & Related papers  (2020-01-15T19:13:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.