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.
翻译:Makepan 排程问题是一个经过广泛研究的NP-硬问题,其最简单版本寻求将一系列具有确定性处理时间的工作分配到两个相同的机器,这样可以将Makepan最小化。然而,在现实生活中,在外部因素的影响下,每项工作的实际处理时间可能围绕预期值和差异进行抽查,而这些工作的实际处理时间可能与共变情况相关。因此,在本文中,我们提出了一个机会限制版的Makepan 排程问题,并调查经典随机本地搜索的理论性能和经典本地搜索的理论性能(1+1)EA。更具体地说,我们首先研究两个受机会限制的Makepan 排程问题及其计算复杂性的变式,然后分别分析两种算法的预期运行时间,以找到两个变式的最佳解决方案或几乎最佳的解决方案。此外,我们还要调查两种变式的两种算法的实验性能。