Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)

Andrew Murray; Michael Cashmore; Ashwin Arulselvan

Abstract

Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is strongly controllable (SC) there exists a concrete schedule that is robust to any uncertainty. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole’s inequality.

Original language	English
Number of pages	2
Publication status	E-pub ahead of print - 23 Jun 2022
Event	19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research - https://sites.google.com/usc.edu/cpaior-2022, Los Angeles, United States Duration: 20 Jun 2022 → 23 Jun 2022

Conference

Conference	19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research
Abbreviated title	CPAIOR 2022
Country/Territory	United States
City	Los Angeles
Period	20/06/22 → 23/06/22

Keywords

probabilistic simple temporal networks (PSTN)
chance constrained optimisation
automated planning and scheduling

Cite this

@conference{a2425f57f83848d5b326cc45409d9c96,

title = "Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)",

abstract = "Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is strongly controllable (SC) there exists a concrete schedule that is robust to any uncertainty. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole{\textquoteright}s inequality.",

keywords = "probabilistic simple temporal networks (PSTN), chance constrained optimisation, automated planning and scheduling",

author = "Andrew Murray and Michael Cashmore and Ashwin Arulselvan",

year = "2022",

month = jun,

day = "23",

language = "English",

note = "19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research, CPAIOR 2022 ; Conference date: 20-06-2022 Through 23-06-2022",

}

Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract). / Murray, Andrew ; Cashmore, Michael ; Arulselvan, Ashwin.

2022. Abstract from 19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research, Los Angeles, California, United States.

Research output: Contribution to conference › Abstract › peer-review

TY - CONF

T1 - Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)

AU - Murray, Andrew

AU - Cashmore, Michael

AU - Arulselvan, Ashwin

PY - 2022/6/23

Y1 - 2022/6/23

N2 - Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is strongly controllable (SC) there exists a concrete schedule that is robust to any uncertainty. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole’s inequality.

AB - Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is strongly controllable (SC) there exists a concrete schedule that is robust to any uncertainty. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole’s inequality.

KW - probabilistic simple temporal networks (PSTN)

KW - chance constrained optimisation

KW - automated planning and scheduling

UR - https://doi.org/10.1007/978-3-031-08011-1

M3 - Abstract

T2 - 19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research

Y2 - 20 June 2022 through 23 June 2022

ER -

Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)

Abstract

Conference

Keywords

Other files and links

Embargoed Document

Fingerprint

Cite this