EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3362. Resource constrained project scheduling with durational uncertainties and maximum time lags

Invited abstract in session WA-26: Optimization problems in scheduling, stream Combinatorial Optimization.

Wednesday, 8:30-10:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Evelin Szögi
Institute for Computer Science and Control
2. Péter Györgyi
Institute for Computer Science and Control
3. Tamas Kis
Institute for Computer Science and Control

Abstract

We study a resource constrained project scheduling problem. A set of jobs arrive in real-time and each of them is a sequence of tasks that require several resources for execution. There are minimum and maximum time lag constraints among the consecutive tasks, which may have uncertain durations. The objective is to minimize the total waiting time so that we guarantee the feasibility of the resulting schedule.
The problem has a great practical interest in small-scale biomanufacturing systems, such as laboratory for drug design, where there can be large uncertainties in the duration of the tasks. For instance, the production of CAR T cells for personalized gene therapies of patients with a serious disease. The production process requires several steps including cell expansion where millions of CAR T cells are grown in a cell culture. The variance of cell expansion time may be several days, while the other production steps are deterministic and take a couple of days.
We have the following results:
1) We provide theoretical bounds about the quality of solutions we may expect.
2) We propose a polynomial time reactive scheduling policy for inserting tasks into a schedule. This method (i) can handle large instances, (ii) outperforms a simple heuristic with the feasibility guarantee, and (iii) starts each job as early as possible relative to the previously scheduled jobs.

Ack.: This work has been supported by the H2020 project AIDPATH, grant agreement number 101016909.

Keywords

Status: accepted

Back to the list of papers