TY - GEN
T1 - Scheduling Stochastic Jobs - Complexity and Approximation Algorithms
AU - Tao, Liangde
AU - Chen, Lin
AU - Zhang, Guochuan
N1 - Funding Information:
Research of Liangde Tao and Guochuan Zhang was partly supported by “New Generation of AI 2030” Major Project (2018AAA0100902). Research of Lin Chen was partly supported by NSF Grant 1756014.
Publisher Copyright:
Copyright © 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2021
Y1 - 2021
N2 - Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the β-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.
AB - Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the β-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.
UR - http://www.scopus.com/inward/record.url?scp=85124652575&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85124652575
T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS
SP - 367
EP - 375
BT - 31st International Conference on Automated Planning and Scheduling, ICAPS 2021
A2 - Biundo, Susanne
A2 - Do, Minh
A2 - Goldman, Robert
A2 - Katz, Michael
A2 - Yang, Qiang
A2 - Zhuo, Hankz Hankui
PB - Association for the Advancement of Artificial Intelligence
T2 - 31st International Conference on Automated Planning and Scheduling, ICAPS 2021
Y2 - 2 August 2021 through 13 August 2021
ER -