Coupled task scheduling with time-dependent processing times
Tóm tắt
The single machine coupled task scheduling problem includes a set of jobs, each with two separated tasks, and there is an exact delay between the tasks. We investigate the single machine coupled task scheduling problem with the objective of minimizing the makespan under identical processing time for the first task and identical delay period for all jobs, and the time-dependent processing time setting for the second task. Certain healthcare appointment scheduling problems can be modeled as the coupled task scheduling problem. Also, the incorporation of time-dependent processing time for the second task lets the human resource fatigue and the deteriorating health conditions be modeled. We provide optimal solution under certain conditions. In addition, we propose a dynamic program under the condition that the majority of jobs share the same time-dependent characteristic. We develop a heuristic for the general case and show that the heuristic performs well.
Tài liệu tham khảo
Ageev, A. A. (2018). Inapproximately lower bounds for open shop problems with exact delays. Approximation and online algorithms (pp. 45–55). New York: Springer.
Ageev, A. A., & Baburin, A. E. (2007). Approximation algorithms for UET scheduling problems with exact delays. Operations Research Letters, 35(4), 533–540.
Ageev, A. A., & Kononov, A. V. (2007). Approximation algorithms for scheduling problems with exact delays. Approximation and online algorithms. Berlin: Springer.
Ahr, D., Békési, J., Galambos, G., Oswald, M., & Reinelt, G. (2004). An exact algorithm for scheduling identical coupled tasks. Mathematical Methods of Operations Research, 59(2), 193–203.
Azadeh, A., Farahani, M. H., Torabzadeh, S., & Baghersad, M. (2014). Scheduling prioritized patients in emergency department laboratories. Computer Methods and Programs in Biomedicine, 117(2), 61–70.
Baptiste, P. (2010). A note on scheduling identical coupled tasks in logarithmic time. Discrete Applied Mathematics, 158(5), 583–587.
Békési, J., Galambos, G., Jung, M. N., Oswald, M., & Reinelt, G. (2014). A branch-and-bound algorithm for the coupled task problem. Mathematical Methods of Operations Research, 80(1), 47–81.
Bessy, S., & Giroudeau, R. (2019). Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, 22(3), 305–313.
Blazewicz, J., Ecker, K., Kis, T., Potts, C. N., Tanas, M., & Whitehead, J. (2010). Scheduling of coupled tasks with unit processing times. Journal of Scheduling, 13(5), 453–461.
Cheng, T. C. E., Ding, Q., & Lin, B. M. T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13.
Condotta, A., & Shakhlevich, N. (2012). Scheduling coupled-operation jobs with exact time-lags. Discrete Applied Mathematics, 160(16), 2370–2388.
Condotta, A., & Shakhlevich, N. (2014). Scheduling patient appointments via multilevel template: a case study in chemotherapy. Operations Research for Health Care, 3(3), 129–144.
Gawiejnowicz, S. (2008). Time-dependent scheduling. New York: Springer.
Graham, R., Lawler, E., Lenstra, J., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.
Gupta, J. N. D., & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 14(4), 387–393.
Gurobi Optimization, L. (2018). Gurobi Optimizer Reference Manual.
Hwang, F. J., & Lin, B. M. T. (2011). Coupled-task scheduling on a single machine subject to a fixed-job-sequence. Computers and Industrial Engineering, 60(4), 690–698.
Khatami, M. and Salehipour, A. (2020). A binary search algorithm for the general coupled task scheduling problem. 4OR, 1–19.
Khatami, M., Salehipour, A., & Cheng, T. C. E. (2020). Coupled task scheduling with exact delays: literature review and models. European Journal of Operational Research, 282(1), 19–39.
Kunnathur, A. S., & Gupta, S. K. (1990). Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research, 47(1), 56–64.
Legrain, A., Fortin, M.-A., Lahrichi, N., Rousseau, L.-M., & Widmer, M. (2015). Stochastic optimization of the scheduling of a radiotherapy center. Journal of Physics: Conference Series. Vol. 616. 1. IOP Publishing, 012008.
Lehoux-Lebacque, V., Brauner, N., & Finke, G. (2015). Identical coupled task scheduling: polynomial complexity of the cyclic case. Journal of Scheduling, 18(6), 631–644.
Leung, J. Y.-T., Li, H., & Zhao, H. (2007). Scheduling two-machine flow shops with exact delays. International Journal of Foundations of Computer Science, 18(02), 341–359.
Li, H., & Zhao, H. (2007). Scheduling Coupled-Tasks on a Single Machine. IEEE Symposium on Computational Intelligence in Scheduling, 137–142.
Liu, Z., Lu, J., Liu, Z., Liao, G., Zhang, H. H., & Dong, J. (2019). Patient scheduling in hemodialysis service. Journal of Combinatorial Optimization, 37(1), 337–362.
Marinagi, C. C., Spyropoulos, C. D., Papatheodorou, C., & Kokkotos, S. (2000). Continual planning and scheduling for managing patient tests in hospital laboratories. Artificial Intelligence in Medicine, 20(2), 139–154.
Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Re-search, 21(6), 653–659.
Orman, A., & Potts, C. (1997). On the complexity of coupled-task scheduling. Discrete Applied Mathematics, 72(1), 141–154.
Pérez, E., Ntaimo, L., Malavé, C. O., Bailey, C., & McCormack, P. (2013). Stochastic online appointment scheduling of multi-step sequential procedures in nuclear medicine. Health Care Management Science, 16(4), 281–299.
Pérez, E., Ntaimo, L., Wilhelm, W. E., Bailey, C., & McCormack, P. (2011). Patient and resource scheduling of multi-step medical procedures in nuclear medicine. IIE Transactions on Healthcare Systems Engineering, 1(3), 168–184.
Shapiro, R. D. (1980). Scheduling coupled tasks. Naval Research Logistics Quarterly, 27(3), 489–498.
Sherali, H. D., & Smith, J. C. (2005). Interleaving two-phased jobs on a single machine. Discrete Optimization, 2(4), 348–361.
Simonin, G., Darties, B., Giroudeau, R., & König, J.-C. (2011). Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor. Journal of Scheduling, 14(5), 501–509.
Yu, W., Hoogeveen, H., & Lenstra, J. K. (2004). Minimizing make span in a two-machine flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7(5), 333–348.