Modelisation and resolution of a problem of resource pooling in a hospital context

Page:

677-702

DOI:

https://doi.org/10.3166/JESA.49.677-702

OPEN ACCESS

Abstract:

This article proposes a modelisation and a resolution of a problem of resource pooling in a hospital context. This problem is an extension of the Resource Constrained Project Scheduling Problem: the Multi-Site RCPSP with resource pooling in a multisite environment. This extension considers new constraints for the RCPSP like transportation times and choice of the site where tasks are executed. A linear program of this problem is given. Three resolution methods are described: local search, simulated annealing and Iterated Local Search with two different acceptance criteria: simulated annealing type acceptance criterion and better acceptance criterion. We compare the results obtained with each method. ILS with simulated annealing type acceptance criterion gives the best results.

Keywords:

*RCPSP, multi-Site, scheduling, transportation time, resource pooling, metaheuristic.*

1. Introduction

2. Problématique

3. Les problèmes similaires de la littérature

4. Modélisation mathématique du RCPSP multi-site

5. Proposition de méthodes approchées

6. Expérimentations

7. Conclusion

References

Bilge U., Ulusoy G. (1995). A time window approach to simultaneous scheduling of machines and material handling system in an fms. Operations Research, vol. 43, n" 6, p. $1058-1070$

Blazewicz J., Lenstra J., Kan A. (1983). Scheduling subject to resource constraints:

classification and complexity. Discrete Applied Mathematics, vol. $5, \mathrm{n}^{\circ} 1, \mathrm{p} .11-24$

Carlier J. (1984). Problèmes diordonnancement à contraintes de ressources : algorithmes et complexité. Thèse de doctorat, Université Paris VI, Paris.

Chassiakos A., Sakellaropoulos S. (2005). Time-cost optimization of construction projects with generalized activity constraints. Journal of Construction Engineering and Management, vol. $131, \mathrm{n}^{\circ} 10, \mathrm{p} .1115-1124$

Correia I., Lourenço L. L., Gama F. Saldanha-da. (2012). Project scheduling with flexible resources: formulation and inequalities. OR spectrum, vol. $34, \mathrm{n}^{\circ} 3, \mathrm{p} .635-663$

Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of Np-Completeness. W. H. Freeman \& Co., New York, NY, USA.

Gourgand M., Grangeon N., Klement N. (2014). Activities planning and resource assignment on multi-place hospital system: Exact and approach methods adapted from the bin packing problem. In 7 th international conference on health informatics, p. $117-124$ Angers, France.

Hwang J., Chow Y., Anger F., Lee C. (1989). Scheduling precedence graphs in systems with interprocessor communication times. SLAM Joumal on Computing, vol. $18, \mathrm{n}^{\circ} 2, \mathrm{p} .244-$257

Johnson S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval research logistics quarterly, vol. 1, n " , p. 61-68.

Kan A. R. (2012). Machine scheduling problems: classification, complexity and (2012). Machine schedling computations. Springer Science \& Business Media.

Kirkpatrick S. (1984). Optimization by simulated annealing: Quantitative studies. Joumal of statisticalphysics, vol 34, ne 5-6, p. 975-986.

Kise H. (1991). On an automated two-machine flowshop scheduling problem with infinite buffer. J. Oper. Res. Soc. Japan, vol. 34, p. 354-361.

Klein R (2000). Project scheduling with time-varying resource constraints. Intermational Joumal of Production Research, vol. $38, \mathrm{n}^{\circ} 16, \mathrm{p} .3937-3952$

Klein R. Scholl A. (1999). Computing lower bounds by destnuctive improvement: An application to resource-constrained project scheduling. European Joumal of Operational Research, vol $112, \mathrm{n}^{\circ} 2, \mathrm{p} .322-346$

Klein R. Scholl A (2000). Progress: Optimally solving the generalized resource-constrained project scheduling problem Mathematical Methods of Operations Research, vol. $52, \mathrm{n}^{\circ} 3$ p. $467-488$.

Kolisch R. (1998). Integrated scheduling, assembly area- and part-assignment for large scale, make-to-order assemblies. International Joumal of Production Economics, vol. 64 p. 127-141.

Langston M. A. (1987). Interstage transportation planning in the deterministic flow-shop environment. Operations Research, vol. 35, n"4, p. 556-564.

Lee C.-Y., Chen Z-L. (2001). Machine scheduling with transportation considerations. Joumal of Scheduling, vol. 4, n $^{\circ} 1,$ p. $3-24$

Lombardi M. Milano M. (2009). A precedence constraint posting approach for the rcpsp with time lags and variable durations. In I Gent (Ed), Principles and practice of constratint programmmg - $c p$ 2009, vol $5732,$ p. $569-583$. Springer Berlin Heidellberg

Lourenço H. R, Martin O. C., Stutzle T. (2003). Handbook of metaheruristics. In F. Glover, G. Kochenberger (Eds), p. 321-353. Kluwers Academic Publishers.

Maggu P., Das G. (1980). On 2x n sequencing problem with transportation times of jobs. Pure and Applied Mathematika Sciences, vol. 12, n" 1, p. 219-227.

Maggu P. L., Das G., Kumar R. (1981). On equivalent-job for job-block in 2x n sequencing problem with transportation-times. Joumal of the Operations Research Soctety of Japan, vol. $24, \mathrm{n}^{\circ} 2, \mathrm{p} .136-146$

Maggu P. L., Smghal M. L., Mohammad N., Yadav S. K. (1982, sep). On n-job, 2-machine flow-shop scheduling problem with arbitrary time lags and transportation times of jobs. Joumal of the Operations Research Society of Japan, vol $25, \mathrm{n}^{\circ} 3, \mathrm{p} .219-227$

Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H, Teller E. (1953). Equation of state calculations by fast computing machines. The joumal of chemical physics, vol 21, n^ 6, p. 1087-1092.

Mitten L. (1959). Sequencing n jobs on two machines with arbitrary time lags. Management science, vol. 5, n $^{13},$ p. $293-298$.

Norre S. (1993). Problèmes de placement de táches: méthodes stochastique et evaluation des performances. These de doctorat, Université Blaise Pascal, Clermont-Ferrand.

Ogũz O... Bala H. (1994). A comparative study of computational procedures for the re- source constrained project scheduling problem European Joumal of Operational Research, vol $72, \mathrm{n}^{\circ} 2, \mathrm{p} \cdot 406-416$