@inproceedings{fce6b3ff9d504af5be0ab7dd5bff3d35,
title = "Scheduling Stochastic Jobs - Complexity and Approximation Algorithms",
abstract = "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.",
author = "Liangde Tao and Lin Chen and Guochuan Zhang",
note = "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 {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; null ; Conference date: 02-08-2021 Through 13-08-2021",
year = "2021",
language = "English",
series = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",
publisher = "Association for the Advancement of Artificial Intelligence",
pages = "367--375",
editor = "Susanne Biundo and Minh Do and Robert Goldman and Michael Katz and Qiang Yang and Zhuo, {Hankz Hankui}",
booktitle = "31st International Conference on Automated Planning and Scheduling, ICAPS 2021",
}