Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem

• URL: http://arxiv.org/abs/2212.11478v2
• Date: Mon, 3 Jul 2023 03:07:59 GMT
• Title: Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem
• Authors: Feng Shi, Xiankun Yan, and Frank Neumann
• Abstract summary: We propose a chance-constrained version of the Makespan Scheduling problem. We investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities.
• Score: 12.791789710379057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influence of external factors, and the actual processing times of these jobs may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities, then separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the two variants. In addition, we investigate the experimental performance of the two algorithms for the two variants.

Related papers

• Genetic-based Constraint Programming for Resource Constrained Job Scheduling [5.068093754585243]
  Resource constrained job scheduling is a hard computation optimisation problem that originates in the mining industry. Off-the-shelf solutions cannot solve this problem satisfactorily in reasonable timeframes. This paper proposes a genetic programming algorithm to discover efficient search strategies of constraint programming.
  arXiv  Detail & Related papers  (2024-02-01T09:57:38Z)
• Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
  Many real-world design problems evaluate multiple experimental conditions in parallel and replicate each condition multiple times due to large and heteroscedastic observation noise. We propose the Batch Thompson Sampling for Replicable Experimental Design framework, which encompasses three algorithms. We show the effectiveness of our algorithms in two practical real-world applications: precision agriculture and AutoML.
  arXiv  Detail & Related papers  (2023-11-02T12:46:03Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  We explore the use of Doubly Matrices (DSM) for matching and assignment nature permutation problems. Specifically, we adopt the framework of estimation of distribution algorithms and compare DSMs to some existing proposals for permutation problems. Preliminary experiments on instances of the quadratic assignment problem validate this line of research and show that DSMs may obtain very competitive results.
  arXiv  Detail & Related papers  (2023-04-05T14:36:48Z)
• A Sequential Deep Learning Algorithm for Sampled Mixed-integer Optimisation Problems [0.3867363075280544]
  We introduce and analyse two efficient algorithms for mixed-integer optimisation problems. We show that both algorithms exhibit finite-time convergence towards the optimal solution. We establish quantitatively the efficacy of these algorithms by means of three numerical tests.
  arXiv  Detail & Related papers  (2023-01-25T17:10:52Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  Job-shop Scheduling Problem (JSP) is a well-known and challenging optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. In this paper, we investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving.
  arXiv  Detail & Related papers  (2022-05-16T09:33:00Z)
• Data-driven Prediction of Relevant Scenarios for Robust Optimization [0.0]
  We study robust one- and two-stage problems with discrete uncertainty sets. We propose a data-driven computation to seed the iterative solution method with a set of starting scenarios. Our experiments show that predicting even a small number of good start scenarios by our method can considerably reduce the time of the iterative methods.
  arXiv  Detail & Related papers  (2022-03-30T19:52:29Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• 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)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• 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.