论文标题
偶然受限的制造计划问题的进化算法的运行时性能
Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem
论文作者
论文摘要
MakePAN调度问题是一个广泛研究的NP硬性问题，其最简单的版本为一组具有确定性处理时间的作业提供了分配方法，可以将MakePan最小化。但是，在现实生活中，在外部因素的影响下，每个作业的实际处理时间可能会随着预期价值的变化而随机，并且这些工作的实际处理时间可能与协方差相关。因此，在本文中，我们提出了一个偶然的限制版本的MakePAN调度问题，并研究了经典随机局部搜索的理论性能和（1+1）EA。更具体地说，我们首先研究了偶然受限的MakePAN调度问题的两个变体及其计算复杂性，然后分别分析两种算法的预期运行时，以获得最佳解决方案或几乎最佳解决方案，以使两个变体的实例获得最佳解决方案。此外，我们研究了两种变体的两种算法的实验性能。
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.
