Publication Type

Journal Article

Version

publishedVersion

Publication Date

2-2019

Abstract

In real-world project scheduling applications, activity durations are often uncertain. Proactive scheduling can effectively cope with the duration uncertainties, by generating robust baseline solutions according to a priori stochastic knowledge. However, most of the existing proactive approaches assume that the duration uncertainty of an activity is not related to its scheduled start time, which may not hold in many real-world scenarios. In this paper, we relax this assumption by allowing the duration uncertainty to be time-dependent, which is caused by the uncertainty of whether the activity can be executed on each time slot. We propose a stochastic optimization model to find an optimal Partial-order Schedule (POS) that minimizes the expected makespan. This model can cover both the time-dependent uncertainty studied in this paper and the traditional time-independent duration uncertainty. To circumvent the underlying complexity in evaluating a given solution, we approximate the stochastic optimization model based on Sample Average Approximation (SAA). Finally, we design two efficient branch-and-bound algorithms to solve the NP-hard SAA problem. Empirical evaluation confirms that our approach can generate high-quality proactive solutions for a variety of uncertainty distributions.

Keywords

Branch-and-bound algorithms, Empirical evaluations, Partial order schedules, Proactive scheduling, Real-world scenario, Sample average approximation, Stochastic optimization model, Uncertainty distributions

Discipline

Theory and Algorithms

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Publication

Journal of Artificial Intelligence Research

Volume

64

First Page

385

Last Page

427

ISSN

1076-9757

Identifier

10.1613/jair.1.11369

Publisher

AI Access Foundation

Additional URL

https://doi.org/10.1613/jair.1.11369

Download

Share

COinS