This paper addresses the problem of maximizing the utilization of operating rooms, which is translated to jobs scheduling in an identical parallel machine environment with sequence-dependent setup times and an objective of minimizing the makespan. The jobs’ processing times and setup times are stochastic for better depiction of the real world. This is a non-deterministic polynomial time (NP)-hard problem, and in this paper a new heuristic is developed and compared to existing ones using simulation and optimization. The results and analysis obtained from the computational experiments proved the superiority of the proposed algorithm Longest Expected Processing with Setup Time (LEPST) over the other algorithms presented.
Tsoy, G., J.-P. Arnaout, T. Smith and G. Rabadi.2004. A genetic algorithm approach for surgery operating rooms scheduling problem. In Proceedings of the 25th National Conference of the American Society for Engineering Management, Alexandria, Virginia.
2.
Dexter, F. , A. Macario, R. Traub, M. Hopwood and D. Lubarsky.1999. An operating room scheduling strategy to maximize the use of operating room block time: computer simulation of patient scheduling and survey of patients’ preferences for surgical waiting time. Anesthesia & Analgesia, 89: 7-20.
3.
Garey, M.R. and D.S. Johnson.1979. Computer and intractability: a guide to the theory of NP-completeness, W H Freeman, San Francisco.
4.
Bruno, J.L. , P.J. Downey and G.N. Frederickson.1981. Sequencing tasks with exponential service times to minimize the expected flow time or makespan . Journal of the ACM, 28: 100-113.
5.
Arnaout, J-P. and Kulbashian, S.2008. Maximizing the utilization of operating rooms with stochastic times using simulation. Proceedings of the 2008 Winter Simulation Conference, pp. 1617-1623, Miami, FL.
6.
Shmitz, H. and N. Kwak.1972. Monte Carlo simulation of operating-room and recovery-room usage. Operations Research , 20: 1171- 1180.
7.
Dexter, F.2000. A strategy to decide whether to move the last case of the day in an operating room to another empty operating room to decrease overtime labor costs. Anesthesia & Analgesia , 91: 925- 928.
8.
Jebali, A. , A. Alouane and P. Ladet.2006. Operating rooms scheduling . International Journal of Production Economics, 99: 52-62.
9.
Guinet, A. and S. Chaabane.2003. Operating theatre planning. International Journal of Production Economics, 85: 69-81.
10.
Kharraja, S., S. Chaabane and E. Marcon.2002. Evaluation de performances pour deux stratégies de programmation opératoire de bloc. In Actes de la 2eme Conf Int Francophone d’Automatique, Nantes, France.
11.
Sethi, R.1977. On the complexity of mean flow time scheduling. Mathematics of Operations Research, 2: 320-330.
12.
Graham, R.L.1969. Boundaries on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17: 416-429.
13.
Pinedo, M.1995. Scheduling: Theory, Algorithms, and Systems, Prentice Hall, NJ.
14.
Lee, Y. and M. Pinedo.1997. Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research, 100: 464-474.
15.
Monma, C.L. and C.N. Potts.1989. On the complexity of scheduling with batch setups. Operations Research, 37: 798-804.
16.
Min, L. and W. Cheng.1999. A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines. Artificial Intelligence in Engineering, 13: 399-403.
17.
Rabadi, G., Moraga, R. and Al-Salem, A. ( 2006), Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent Manufacturing , 17: 85-97.
18.
Glazebrook, K.D.1979. Scheduling tasks with exponential service times on parallel machines. Journal of Applied Probability , 16: 685-689.
19.
Weiss, G. and M. Pinedo.1980. Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. Journal of Applied Probability, 17: 187-202.
20.
Weber, R.R. , P. Varaiya and J. Walrand.1986. Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Journal of Applied Probability, 23: 841-847.
21.
Weiss, G.1992. Turnpike optimality of Smith’s rule in parallel machines stochastic scheduling. Mathematics of Operations Research, 17: 255-270.
22.
Mohring, R., A. Shulz and M. Uetz.1999. Approximation in stochastic scheduling: the power of LP-based priority policies. Journal of the ACM (JACM), 46: 924-942.
23.
Javidi, T. , N-O. Song and D. Teneketzis.2001. Expected makespan minimization on identical machines in two interconnected queues. Probability in the Engineering and Informational Sciences, 15: 409-443.
24.
Arnaout, J-P., G. Rabadi and J.H. Mun .2006. A dynamic heuristic for the stochastic unrelated parallel machine scheduling problem. International Journal of Operations Research, 3: 136- 143.
25.
Fisher, R.A.1960. The Design of Experiments, Hafner Pub. Co., NY.
26.
Taguchi, G.1993. Taguchi Methods: Design of Experiments, American Supplier Institute, Inc., MI.
27.
NIST/SEMATECH e-Handbook of Statistical Methods, http://www.itl.nist.gov/div898/handbook/.
28.
Ross, P.1996. Taguchi techniques for quality engineering, McGraw Hill, New York.
29.
Kelton, D., R. Sadowski and D. Sturrock.2004. Simulation with Arena, 3rd edn, McGraw-Hill Companies, New York.
30.
Weng, M., J. Lu and H. Ren.2001. Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70: 215-226.
