Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan

• URL: http://arxiv.org/abs/2512.23150v1
• Date: Mon, 29 Dec 2025 02:27:45 GMT
• Title: Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan
• Authors: Vítor A. Barbosa, Rafael A. Melo,
• Abstract summary: We consider the strongly NP-hard single-machine coupled task scheduling problem with exact delays to minimize the makespan.<n>We model the problem using constraint programming (CP) and propose a biased random-key genetic algorithm (BRKGA)<n>Our BRKGA combines some successful components in the literature: an initial solution generator, periodical restarts and shakes, and a local search algorithm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the strongly NP-hard single-machine coupled task scheduling problem with exact delays to minimize the makespan. In this problem, a set of jobs has to be scheduled, each composed of two tasks interspersed by an exact delay. Given that no preemption is allowed, the goal consists of minimizing the completion time of the last scheduled task. We model the problem using constraint programming (CP) and propose a biased random-key genetic algorithm (BRKGA). Our CP model applies well-established global constraints. Our BRKGA combines some successful components in the literature: an initial solution generator, periodical restarts and shakes, and a local search algorithm. Furthermore, the BRKGA's decoder is focused on efficiency rather than optimality, which accelerates the solution space exploration. Computational experiments on a benchmark set containing instances with up to 100 jobs (200 tasks) indicate that the proposed BRKGA can efficiently explore the problem solution space, providing high-quality approximate solutions within low computational times. It can also provide better solutions than the CP model under the same computational settings, i.e., three minutes of time limit and a single thread. The CP model, when offered a longer running time of 3600 seconds and multiple threads, significantly improved the results, reaching the current best-known solution for 90.56% of these instances. Finally, our experiments highlight the importance of the shake and local search components in the BRKGA, whose combination significantly improves the results of a standard BRKGA.

Related papers

• Edge Collaborative Gaussian Splatting with Integrated Rendering and Communication [69.23838350582764]
  We present edge collaborative (ECO-GS) where each user can switch between a small GS model to guarantee fidelity and a remote large GS model to guarantee fidelity.<n>We propose integrated and communication (IRAC) which jointly optimize low-cost rendering status and edge power allocation.
  arXiv  Detail & Related papers  (2025-10-26T15:33:29Z)
• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• The Iterative Chainlet Partitioning Algorithm for the Traveling Salesman Problem with Drone and Neural Acceleration [27.475353583459263]
  We introduce the Iterative Chainlet Partitioning (ICP) algorithm and its neural acceleration for solving the Traveling Salesman Problem with Drone (TSP-D)<n>ICP yields an average improvement of 2.6% in solution quality over the previous state-of-the-art algorithm while reducing computational time by 91.3%.<n>Compared to ICP, NICP reduces the total computational time by 28.6%, while the objective function value increase is limited to 0.14%.
  arXiv  Detail & Related papers  (2025-04-21T14:51:15Z)
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  We propose digitized counterdiabatic quantum optimization (DCQO)algorithms for two scheduling problems.<n>For the job-shop scheduling problem, we aim at finding the optimal schedule for a robot executing a number of tasks under specific constraints.<n>For the traveling salesperson problem, the goal is to find the path that covers all cities and is associated with the shortest traveling distance.
  arXiv  Detail & Related papers  (2024-05-24T16:53:30Z)
• Selective Task offloading for Maximum Inference Accuracy and Energy efficient Real-Time IoT Sensing Systems [3.0748861313823]
  We propose a lightweight hybrid genetic algorithm (LGSTO) to solve the multidimensional knapsack problem. Experiment results show that LGSTO performed 3 times faster than the fastest comparable schemes.
  arXiv  Detail & Related papers  (2024-02-24T18:46:06Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Optimization of Robot Trajectory Planning with Nature-Inspired and Hybrid Quantum Algorithms [0.0]
  We solve robot trajectory planning problems at industry-relevant scales. Our end-to-end solution integrates highly versatile random-key algorithms with model stacking and ensemble techniques. We show how the latter can be integrated into our larger pipeline, providing a quantum-ready hybrid solution to the problem.
  arXiv  Detail & Related papers  (2022-06-08T02:38:32Z)
• Exact methods and lower bounds for the Oven Scheduling Problem [5.7485371212305685]
  The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding models.
  arXiv  Detail & Related papers  (2022-03-23T16:28:05Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.