Volume 55, Number 6, November-December 2021
|Page(s)||3493 - 3511|
|Published online||25 November 2021|
Polynomial algorithms for some scheduling problems with one nonrenewable resource
COSYS/GRETTIA, Univ Gustave Eiffel, CNRS, ESIEE Paris, F-77454 Marne-la-Vallée, France
2 Sorbonne universités, Université de Technologie de Compiègne, CNRS, laboratoire Heudiasyc UMR 7253, CS 60 319, 60 203 Compiègne Cedex, France
* Corresponding author: firstname.lastname@example.org
Accepted: 26 October 2021
This paper deals with the Extended Resource Constrained Project Scheduling Problem (ERCPSP) which is defined by events, nonrenewable resources and precedence constraints between pairs of events. The availability of a resource is depleted and replenished at the occurrence times of a set of events. The decision problem of ERCPSP consists of determining whether an instance has a feasible schedule or not. When there is only one nonrenewable resource, this problem is equivalent to find a feasible schedule that minimizes the number of resource units initially required. It generalizes the maximum cumulative cost problem and the two-machine maximum completion time flow-shop problem. In this paper, we consider this problem with some specific precedence constraints: parallel chains, series-parallel and interval order precedence constraints. For the first two cases, polynomial algorithms based on a linear decomposition of chains are proposed. For the third case, a polynomial algorithm is introduced to solve it. The priority between events is defined using the properties of interval orders.
Mathematics Subject Classification: 90B35 / 05C85
Key words: Scheduling problems / nonrenewable resource / decomposition method / series-parallel graph / interval order graph
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.