Scholarlink

<p>Efficient scheduling of patient examinations is vital to reduce waiting time, balance resource utilization, and enhance patient and provider satisfaction. This paper addresses a patient examination scheduling problem by incorporating realistic operational features, including heterogeneous patient arrival times, precedence relations among examinations, and flexible allocation of rooms. The objective is to jointly minimize the maximum patient completion time and the total waiting time. A mixed-integer programming model and a column generation-based heuristic approach, denoted as CG-VND-E, are developed based on a set partitioning reformulation. Within the proposed algorithm, initial columns are generated via a greedy heuristic, while a variable neighborhood descent algorithm explores examination plans for each patient, encompassing room assignments and examination scheduling. An enumeration algorithm with two acceleration mechanisms, dominance rule and lower bound-based pruning, is employed in the decoding part of the variable neighborhood descent algorithm. Extensive computational experiments show that the proposed CG-VND-E algorithm outperforms the original model solved via the Gurobi solver. Furthermore, CG-VND-E consistently yields higher-quality solutions, with average objective values improved by 0.31%, 1.58%, and 6.35% over the original model across the small-, medium-, and large-scale instances. The effectiveness of the greedy heuristic and acceleration strategies is also verified, and sensitivity analysis is conducted to provide managerial insights for practical implementation.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Integrated optimization of patient examination scheduling with room flexibility and precedence constraints: a column generation-based heuristic approach

  • 期刊论文

  • 发表日期：

    2026年7月11日

查看全文
  • Shaowen Lan,
  • Hangzhen Yang,
  • Kaining Shao,
  • Jianfu Chen,
  • Yongliang Lu

摘要

Efficient scheduling of patient examinations is vital to reduce waiting time, balance resource utilization, and enhance patient and provider satisfaction. This paper addresses a patient examination scheduling problem by incorporating realistic operational features, including heterogeneous patient arrival times, precedence relations among examinations, and flexible allocation of rooms. The objective is to jointly minimize the maximum patient completion time and the total waiting time. A mixed-integer programming model and a column generation-based heuristic approach, denoted as CG-VND-E, are developed based on a set partitioning reformulation. Within the proposed algorithm, initial columns are generated via a greedy heuristic, while a variable neighborhood descent algorithm explores examination plans for each patient, encompassing room assignments and examination scheduling. An enumeration algorithm with two acceleration mechanisms, dominance rule and lower bound-based pruning, is employed in the decoding part of the variable neighborhood descent algorithm. Extensive computational experiments show that the proposed CG-VND-E algorithm outperforms the original model solved via the Gurobi solver. Furthermore, CG-VND-E consistently yields higher-quality solutions, with average objective values improved by 0.31%, 1.58%, and 6.35% over the original model across the small-, medium-, and large-scale instances. The effectiveness of the greedy heuristic and acceleration strategies is also verified, and sensitivity analysis is conducted to provide managerial insights for practical implementation.