The surgical case scheduling problem with fuzzy duration time: An ant system algorithm

Document Type : Article

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.

2 Department of Industrial Management, Faculty of Management and Accounting, Shahid Beheshti University, G.C., Tehran, Iran.

Abstract

In this paper, we address the surgical case scheduling problem in multi operating theater environment with uncertain service times in order to minimize makespan. In surgical case scheduling, not only the hospital resources are allocated to surgical cases but also the start time of performing surgeries is determined based on sequence of cases in a short-term time horizon. We consider fuzzy numbers for duration times of all stages and hereafter the problem called fuzzy surgical case scheduling. Since the operational environment in the problem is similar to no-wait multi-resource fuzzy flexible job shop problem, we consider constraints of that for formulating and solving problem. This problem is strongly an NP-hard optimization problem, hence we employ ant system algorithm to tackle problem. The proposed approach is illustrated by detailed examples of three test cases, and numerical computational experiments. Therefore, the performance of proposed algorithm is compared with a schedule constructed by first-come-first-service rule on all test instances. Also, a real case is provided from Isfahan’s hospital to evaluate proposed algorithm.  Consequently, computational experiments state that algorithm outperforms results obtained by hospital planning as well as fuzzy rule, and these indicate efficiency and capability of our algorithm for optimizing the makespan.

Keywords

Main Subjects

References

References:
1. Vijayakumar, B., Parikh, P.J., Scott, R., Barnes, A., and Gallimore, J. "A dual binpacking approach to scheduling surgical cases at a publicly-funded hospital", European Journal of Operational Research, 224, pp. 583-591 (2013).
2. Zhao, Z. and Li, X. "Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming", Operations Research for Health Care, 3(3), pp. 160-167 (2014).
3. Denton, B., Viapiano, J., and Vogl, A. "Optimization of surgery sequencing and scheduling decisions under uncertainty", Health Care Management Science, 10(1), pp. 13-24 (2007).
4. Atighehchian, A. "Stochastic operating room scheduling", PhD Thesis, Dep. Indsturial Engineering, Tarbiat Modares University, Iran, Tehran (2011).
5. Guerriero, F. and Guido, R. "Operational research in the management of the operating theatre: a survey", Health Care Manag Sci, 14, pp. 89-144 (2011).
6. Zakaria, Y. Abdelrasol, Z.Y., Harraz, N., and Eltawil, A. "A proposed solution framework for the operating room scheduling problems", Proceedings of the World Congress on Engineering and Computer, 2, pp. 1149- 1157 (2013).
7. Samudra, M., Van Riet, C., Demeulemeester, E., Cardoen, B., Vansteenkiste, N., and Rademakers, F.E. "Scheduling operating rooms: achievements, challenges and pitfalls", J Sched, 19(5), pp. 493-525 (2016).
8. Dellaert, N. and Jeunet, J. "A variable neighborhood search algorithm for the surgery tactical planning problem", Computers and Operation Research, 84, pp. 216-225 (2017).
9. Magerlein, J.M. and Martin, J.B. "Surgical demand scheduling: A review", Health Service Research, 13, pp. 418-433 (1978).
10. Fei, H., Meskens, N., and Chu, C. "A planning and scheduling problem for an operating theatre using an open scheduling strategy", Computers & Industrial Engineering, 58, pp. 221-230 (2010).
11. Adan, I., Bekkers, J., Dellaert, N., Jeunet, J., and Vissers, J. "Improving operational effectiveness of tactical master plans for emergency and elective patients under stochastic demand and capacitated resources", European Journal of Operational Research, 213, pp. 290-308 (2011).
12. Marques, I., Captivo, M.E., and Vaz Pato, M. "Scheduling elective surgeries in a Portuguese hospital using a genetic heuristic", Operations Research for Health Care, 3(2), pp. 59-72 (2014).
13. Marques, I. and Captivo, M.E. "Bicriteria elective surgery scheduling using an evolutionary algorithm", Operations Research for Health Care, 7(24), pp. 14-26 (2015).
14. Aringhieri, R., Landa, P., Soriano, P., Tanfani, E., and Testi, A. "A two level metaheuristic for the operating room scheduling and assignment problem", Computers & Operations Research, 54, pp. 21-34 (2015).
15. Guido, R. and Conforti, D. "A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem", Computers and Operation Research, 87, pp. 270-282 (2017).
16. Pham, D.N. and Klinkert, A. "Surgical case scheduling as a generalized job shop scheduling problem", European Journal of Operational Research, 185, pp. 1011- 1025 (2008).
17. Ghazalbash, S., Sepehri, M.M., Shadpour, P., and Atighehchian, A. "Operating room scheduling in teaching hospitals", Advances in Operations Research, 2012 (2012).
18. Davila, M.P., Centeno, G., Fabri, P., Laurentis, K., Reeves, K., andWeng, M. "A methodology for scheduling operating rooms under uncertainty", PhD Thesis, University of South Florida (2013).
19. Meskens, N., Duvivier, D., and Hanset, A. "Multiobjective operating room scheduling considering desiderata of the surgical team", Decision Support Systems, 55, pp. 650-659 (2013).
20. M'Hallah, R. and Al-Roomi, A.H. "The planning and scheduling of operating rooms: A simulation approach", Computers & Industrial Engineering, 78, pp. 235-248 (2014).
21. Xiang, W., Yin, J., and Lim, G. "An ant colony optimization approach for solving an operating room surgery scheduling problem", Computers & Industrial Engineering, 85, pp. 335-345 (2015).
22. Saadouli, H., Jerbi, B., Dammaka, A., Masmoudi, L., and Bouaziz, A. "A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department", Computers & Industrial Engineering, 80, pp. 72-79 (2015).
23. van Essen, J.T., Hurink, J.L., Hartholt, W., and van den Akker, B.J. "Decision support system for the operating room rescheduling problem", Health Care Manag Sci, 15(4), pp. 355-372 (2012).
24. Erdem, E., Qu, X., and Shi, J. "Rescheduling of elective patients upon the arrival of emergency patients", Decision Support Systems, 54, pp. 551-563 (2012).
25. Fugener, A., Hans, E.W., Kolisch, R., Kortbeek, N., and Vanberkel, P.T. "Master surgery scheduling with consideration of multiple downstream Units", European Journal of Operational Research, 239, pp. 227-236 (2014).
26. Cardoen, B., Demeulemeester, E., and Belien, J. "Operating room planning and scheduling: A literature review", European Journal of Operational Research, 201, pp. 921-932 (2010).
27. Lee, S. and Yih, Y. "Reducing patient-flow delays in surgical suites through determining start-times of surgical cases", European Journal of Operational Research, 238, pp. 620-629 (2014).
28. Marques, I. and Captivo, E.M. "Different stakeholders's perspectives for a surgical case assignment problem: deterministic and robust approaches", European Journal of Operational Research, 261(1) , pp. 260-278 (2017).
29. Van Riet, C. and Demeulemeester, E. "Trade-offs in operating room planning for electives and emergencies: A review", Operations Research for Health Care, 7, pp. 52-69 (2015).
30. Lamiri, M., Xie, X., Dolgui, A., and Grimaud, F. "A stochastic model for operating room planning with elective and emergency demand for surgery", Eur J Oper Res, 185(3), pp. 1026-1037 (2008).
31. Lamiri, M., Grimaud, F., and Xie, X. "Optimization methods for a stochastic surgery planning problem", Int J Prod Econ, 120(2), pp. 400-410 (2009).
32. Saremi, A., Jula, P., ElMekkawy, T., and Wang, G.G. "Appointment scheduling of outpatient surgical services in a multistage operating room department", Int. J. Production Economics, 141, pp. 646-658 (2013).
33. Mateus, C., Marques, I., and Captivo, M.E. "Local search heuristics for a surgical case assignment problem", Operations Research for Health Care, 17, pp. 71-81 (2018).
34. Dubois, D., Fargier, H., and Fortemps, P. "Fuzzy scheduling: Modelling  flexible constraints vs. coping with incomplete knowledge", European Journal of Operational Research, 147, pp. 231-252 (2003).
35. Gonzalez-Rodriguez, I., Vela, C.R., Puente, J., and Hernandez-Arauzo, A. "Improved local search for job shop scheduling with uncertain durations", Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling, pp. 124-131 (2008a).
36. Gonzalez-Rodriguez, I., Puente, J., Vela, C.R., and Varela, R. "Semantics of schedules for the fuzzy jobshop problem", IEEE Transactions on Systems Man and Cybernetics - Part A: Systems and Humans, 38, pp. 655-666 (2008b).
37. Palacios, J.J., Vela, C.R., Puente, J., and Gonzalez-Rodriguez, I. "Hybrid cooperative coevolution for fuzzy flexible job shop scheduling problems", Proceedings of Erofuse, pp. 199-206 (2013).
38. Lei, D.M. "Co-evolutionary genetic algorithm for fuzzy  flexible job shop scheduling", Appl. Soft Comput., 12(8), pp. 2237-2245 (2012).
39. Xu, Y., Wang, L., Wang, S., and Liu, M. "An effective teaching-learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time", Neurocomputing, 148, pp. 26-35 (2015).
40. Liu, B., Fan, Y., and Liu, Y. "A fast estimation of distribution algorithm for dynamic fuzzy  flexible jobshop scheduling problem", Computers & Industrial Engineering, 87, pp. 193-201 (2015).
41. Lin, J. "A hybrid biogeography-based optimization for the fuzzy  flexible job-shop scheduling problem", Knowledge-Based Systems, 78, pp. 59-74 (2015).
42. Guinet, A. and Chaabane, S. "Operating theatre planning", International Journal of Production Economics, 85(1), pp. 69-81 (2003).
43. Augusto, V., Xie, X., and Perdomo, V. "Operating theatre scheduling with patient recovery in both operating rooms and recovery beds", Computers & Industrial Engineering, 58(2), pp. 231-238 (2010).
44. Pinedo, M., Scheduling: Theory, Algorithms and Systems, Prentice-Hall, Ed., 3th Edn., New Jersey, Englewood Cliffs (2008).
45. Sakawa, M. and Kubota, R. "Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms", Eur. J. Oper. Res., 120(2), pp. 393-407 (2000).
46. Demir, Y. and Isleyen, S.K. "Evaluation of mathematical models for  flexible job-shop scheduling problems", Applied Mathematical Modelling, 37, pp. 977- 988 (2013).
47. Ozguven, C., Ozbakir, L., and Yavuz, Y. "Mathematical models for job-shop scheduling problems with routing and process plan flexibility", Applied Mathematical Modelling, 34, pp. 1539-1548 (2010).
48. Noori-Darvish, S., Mahdavi, I., and Mahdavi-Amiri, N. "A bi-objective possibilistic programming model for open shop scheduling problems with sequencedependent setup times, fuzzy processing times, and fuzzy due dates", Applied Soft Computing, 12, pp. 1399-1416 (2012).
49. Dorigo, M., Maniezzo, V., and Colorni, A. "Positive feedback as a search strategy", Technical Report 91- 016, Dip. Elettronica, Politecnico di Milano, Italy (1991).
50. Dorigo, M., Maniesso, V., and Colorni, A. "The ant system: optimization by a colony of cooperating agents", IEEE Trans. Systems Man Cybernet, Part B, 26, pp. 29-42 (1996).
51. Kuo, R.J., Wibowo, B.S., and Zulvia, F.E. "Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time", Applied Mathematical Modelling, 40(23-24), pp. 9990- 10001 (2016).
Scientia Iranica
Volume 26, Issue 3
Transactions on Industrial Engineering (E)
May and June 2019
Pages 1824-1841

Files

History

  • Receive Date: 31 March 2017
  • Revise Date: 06 October 2017
  • Accept Date: 23 June 2018

Share

How to cite

Statistics