【摘要】在医院的许多科室中，医学检查和医生诊断是两个必要的服务项目。通常，某一工作日内这些科室中同时存在两类患者。一种是新来的患者，他们来寻求医生的初步诊断。另一种是重访该科室来依次进行医学检查和进一步诊断的患者。近年，为了缓解系统拥挤，许多医院开始提供预约服务。如何合理调度上述两阶段服务系统中两类患者的预约成为与患者满意度及系统效率密切相关的关键问题。由此，提出了一种决策两阶段中所有患者预约时间的联合调度策略。考虑到患者的随机服务时间和转移时间，建立了相应的随机规划模型。为了在合理的计算时间内得到高质量调度，设计了一个基于抽样平均近似的混合变邻域搜索-L形算法。而后进行了基于上海同济医院心血管内科的数值实验。提出的联合调度策略被证明可以减少两类病人看诊的等待时间并提高系统效率。一个管理学观点同时被发现，即为准时到达医生处的患者分配更长的诊断时间是有益的。