Scheduling Stochastic Jobs - Complexity and Approximation Algorithms

Liangde Tao, Lin Chen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication31st International Conference on Automated Planning and Scheduling, ICAPS 2021
EditorsSusanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo
PublisherAssociation for the Advancement of Artificial Intelligence
Pages367-375
Number of pages9
ISBN (Electronic)9781713832317
StatePublished - 2021
Event31st International Conference on Automated Planning and Scheduling, ICAPS 2021 - Guangzhou, Virtual, China
Duration: Aug 2 2021Aug 13 2021

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume2021-August
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

Conference31st International Conference on Automated Planning and Scheduling, ICAPS 2021
Country/TerritoryChina
CityGuangzhou, Virtual
Period08/2/2108/13/21

Fingerprint

Dive into the research topics of 'Scheduling Stochastic Jobs - Complexity and Approximation Algorithms'. Together they form a unique fingerprint.

Cite this