TY - JOUR AU - Tao, Liangde AU - Chen, Lin AU - Zhang, Guochuan PY - 2021/05/17 Y2 - 2024/03/28 TI - Scheduling Stochastic Jobs - Complexity and Approximation Algorithms JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 31 IS - 1 SE - Main Track DO - 10.1609/icaps.v31i1.15982 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/15982 SP - 367-375 AB - Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the beta-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution. ER -