Scheduling Stochastic Jobs - Complexity and Approximation Algorithms
Keywords:Uncertainty And Stochasticity In Planning And Scheduling
AbstractUncertainty 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.
How to Cite
Tao, L., Chen, L., & Zhang, G. (2021). Scheduling Stochastic Jobs - Complexity and Approximation Algorithms. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 367-375. https://doi.org/10.1609/icaps.v31i1.15982