Learning to solve the single machine scheduling problem with release times and sum of completion times

• URL: http://arxiv.org/abs/2101.01082v1
• Date: Mon, 4 Jan 2021 16:40:18 GMT
• Title: Learning to solve the single machine scheduling problem with release times and sum of completion times
• Authors: Axel Parmentier and Vincent T'Kindt
• Abstract summary: We focus on the solution of a hard single machine scheduling problem by new algorithms embedding techniques from machine learning field and scheduling theory. Theses transform an instance of the hard problem into an instance of a simpler one solved to optimality.
• Score: 0.76146285961466
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we focus on the solution of a hard single machine scheduling problem by new heuristic algorithms embedding techniques from machine learning field and scheduling theory. These heuristics transform an instance of the hard problem into an instance of a simpler one solved to optimality. The obtained schedule is then transposed to the original problem. Computational experiments show that they are competitive with state-of-the-art heuristics, notably on large instances.

Related papers

• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  We propose a more general dynamic network that can combine both quantization and early exit dynamic network: QuEE. Our algorithm can be seen as a form of soft early exiting or input-dependent compression. The crucial factor of our approach is accurate prediction of the potential accuracy improvement achievable through further computation.
  arXiv  Detail & Related papers  (2024-06-20T15:25:13Z)
• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness [0.0]
  We propose a deep neural network that acts as a decomposition-time estimator of the criterion value used in a single-pass scheduling algorithm. We show that our machine learning-driven approach can efficiently generalize information from the training phase to significantly larger instances.
  arXiv  Detail & Related papers  (2024-02-19T15:34:09Z)
• Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize [0.0]
  The proposed approach can lead to a significant reduction in solution time. Active and supervised learning is used to learn a surrogate model that predicts the computational performance. The results show that the proposed approach can lead to a significant reduction in solution time.
  arXiv  Detail & Related papers  (2023-10-10T23:49:26Z)
• An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
  This paper proposes a novel end-to-end approach to solving scheduling problems by means of CP and Reinforcement Learning (RL) Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets.
  arXiv  Detail & Related papers  (2023-06-09T08:24:56Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
  arXiv  Detail & Related papers  (2021-07-15T04:47:35Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  Real-world applications typically require finding good solutions early in the search to enable fast decision-making. We propose the first data-driven framework for schedulings in an exact MIP solver. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
  arXiv  Detail & Related papers  (2021-03-18T14:49:52Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
  This real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
  arXiv  Detail & Related papers  (2020-06-22T15:38:00Z)

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.