no. 6
Polynomial algorithms for some scheduling problems with one nonrenewable resource
RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3493-3511

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.

DOI : 10.1051/ro/2021164
Classification : 90B35, 05C85
Keywords: Scheduling problems, nonrenewable resource, decomposition method, series-parallel graph, interval order graph 
@article{RO_2021__55_6_3493_0,
     author = {Sahli, Abderrahim and Carlier, Jacques and Moukrim, Aziz},
     title = {Polynomial algorithms for some scheduling problems with one nonrenewable resource},
     journal = {RAIRO. Operations Research},
     pages = {3493--3511},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {6},
     doi = {10.1051/ro/2021164},
     mrnumber = {4344865},
     zbl = {1483.90058},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021164/}
}
TY  - JOUR
AU  - Sahli, Abderrahim
AU  - Carlier, Jacques
AU  - Moukrim, Aziz
TI  - Polynomial algorithms for some scheduling problems with one nonrenewable resource
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 3493
EP  - 3511
VL  - 55
IS  - 6
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021164/
DO  - 10.1051/ro/2021164
LA  - en
ID  - RO_2021__55_6_3493_0
ER  - 
%0 Journal Article
%A Sahli, Abderrahim
%A Carlier, Jacques
%A Moukrim, Aziz
%T Polynomial algorithms for some scheduling problems with one nonrenewable resource
%J RAIRO. Operations Research
%D 2021
%P 3493-3511
%V 55
%N 6
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021164/
%R 10.1051/ro/2021164
%G en
%F RO_2021__55_6_3493_0
Sahli, Abderrahim; Carlier, Jacques; Moukrim, Aziz. Polynomial algorithms for some scheduling problems with one nonrenewable resource. RAIRO. Operations Research, Tome 55 (2021) no. 6, pp. 3493-3511. doi: 10.1051/ro/2021164

[1] H. Abdel-Wahab and T. Kameda, Scheduling to minimize maximum cumulative cost subject to series-parallel precedence constraints. Oper. Res. 26 (1978) 141–158. | MR | Zbl | DOI

[2] M. Bartusch, R. Möhring and F. Radermacher, Scheduling project network with resource constraints and time windows. Ann. Oper. Res. 16 (1988) 201–240. | MR | Zbl | DOI

[3] J. Carlier and A. H. G. Rinnooy Kan, Scheduling subject to nonrenewable-resource constraints. Oper. Res. Lett. 1 (1982) 52–55. | Zbl | DOI

[4] J. Carlier, A. Moukrim and H. Xu, The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm. Discrete Appl. Math. 157 (2009) 3631–3642. | MR | Zbl | DOI

[5] J. Carlier, A. Moukrim and A. Sahli, Lower bounds for the event scheduling problem with consumption and production of resources. Discrete Appl. Math. 234 (2016) 178–194. | MR | Zbl | DOI

[6] J. Carlier, E. Pinson, A. Sahli and A. Jouglet, An O ( n 2 ) algorithm for time-bound adjustments for the cumulative scheduling problem. Eur. J. Oper. Res. 286 (2020) 468–476. | MR | Zbl | DOI

[7] J. Carlier, A. Sahli, A. Jouglet and E. Pinson, A faster checker of the energetic reasoning for the cumulative scheduling problem. Int. J. Prod. Res. (2021) 1–16. DOI: . | DOI

[8] A. Cesta, A. Oddi and S. Smith, A constraint-based method for project scheduling with time windows. J. Heuristics 8 (2002) 109–136. | Zbl | DOI

[9] S. J. Edwards, D. Baatar, K. Smith-Miles and A. T. Ernst, Symmetry breaking of identical projects in the high-multiplicity rcpsp/max. J. Oper. Res. Soc. 72 (2021) 1822–1843. | DOI

[10] S. Hartmann and D. Briskorn, An updated survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 297 (2021) 1–14. | MR | Zbl | DOI

[11] S. Johnson, Optimal two and three-stage production schedules with setup times included. Nav. Res. Logistics Q. 1 (1954) 61–68. | Zbl | DOI

[12] E. Kaplan and A. Amir, A fast feasibility test for relocation problems. Eur. J. Oper. Res. 35 (1988) 201–205. | Zbl | DOI

[13] I. Krimi, R. Benmansour, S. Hanafi and N. Elhachemi, Two-machine flow shop with synchronized periodic maintenance. RAIRO-Oper. Res. 53 (2019) 351–365. | MR | Zbl | Numdam | DOI

[14] P. Laborie, Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artif. Intell. 143 (2002) 151–188. | MR | Zbl | DOI

[15] L. V. D. Melo and T. A. D. Queiroz, Integer linear programming formulations for the RCPSP considering multi-skill, multi-mode, and minimum and maximum time lags. IEEE Lat. Am. Trans. 19 (2021) 5–16. | DOI

[16] C. L. Monma, The two-machine maximum flow time problem with series-parallel precedence constraints: an algorithm and extensions. Oper. Res. 27 (1979) 792–798. | Zbl | DOI

[17] C. L. Monma and J. B. Sidney, Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4 (1979) 215–224. | MR | Zbl | DOI

[18] K. Neumann and C. Schwindt, Project scheduling with inventory constraints. Math. Methods Oper. Res. 56 (2002) 513–533. | MR | Zbl | DOI

[19] K. Neumann and J. Zhan, Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints. J. Intell. Manuf. 19 (1997) 205–217.

[20] K. Neumann, C. Schwindt and J. Zimmermann, Resource-constrained project scheduling with time windows: recent developments and new applications. In: Perspectives in Modern Project Scheduling, edited by J. Jozefowska and J. Weglarz. Kluwer, Boston (2006) 375–407. | MR | Zbl | DOI

[21] K. V. Palem and B. B. Simons, Scheduling time-critical instructions on risc machines. ACM Trans. Program. Lang. Syst. 15 (1993) 632–658. | DOI

[22] C. H. Papadimitriou and M. Yannakakis, Scheduling interval-ordered tasks. SIAM J. Comput. 8 (1979) 405–409. | MR | Zbl | DOI

[23] Y. Sekiguchi, A decomposition theory based on a dominance relation and composite jobs. Discrete Appl. Math. 17 (1987) 187–211. | MR | Zbl | DOI

[24] R. Sethi, Complete register allocation problems. SIAM J. Comput. 4 (1975) 226–248. | MR | Zbl | DOI

[25] H. Singh, J. S. Oberoi and D. Singh, Multi-objective permutation and non-permutation flow shop scheduling problems with no-wait: a systematic literature review. RAIRO-Oper. Res. 55 (2021) 27–50. | MR | Numdam | DOI

[26] F. Sourd and J. Rogerie, Continuous filling and emptying of storage systems in constraint-based scheduling. Eur. J. Oper. Res. 165 (2005) 510–524. | Zbl | DOI

[27] J. Valdes, R. Tarjan and E. Lawler, The recognition of series-parallel digraphs. SIAM J. Comput. 11 (1982) 298–313. | MR | Zbl | DOI

Cité par Sources :