The rapid development of online healthcare has posed new challenges for hospitals in allocating physician resources across integrated online and offline service systems. This paper investigates the physician scheduling problem of an online healthcare service system while considering offline services. We model the system as a nonstationary processor-sharing queue using continuous-time Markov chains and the uniformization method. Based on this framework, we derive closed-form analytical expressions to compute patient sojourn times, queue lengths, and physician overtime. Then, we formulate the physician scheduling problem as a non-linear model and further linearize this model into a mixed-integer programming (MIP) model. Based on the linearization technique, the problem can be exactly solved by the MIP solver, such as Gurobi. To cope with real-life large-scale problem data, we also propose a two-phase modeling method and a variable neighborhood search (VNS) algorithm. Using empirical data from a partner hospital, we evaluate the accuracy of our modeling and the performance of our solution methods. Numerical experiments demonstrate that our approaches generate high-quality physician schedules that outperform existing practices currently adopted by the hospital. In the non-epidemic scenario, our approach reduces the average patient sojourn time by 12.7% compared with the hospital’s current practice. In the epidemic scenario, our approach reduces the average patient sojourn time by 14.7%.

This paper addresses a real-life stochastic car batching and sequencing problem in the body shop of a vehicle plant. Unlike previous research on similar problems in the paint shop or assembly shop, our problem primarily focuses on production planning in the body shop, with specific constraints on the production sequence (e.g., the bodies of each model cannot be produced individually but must be produced in batches of a specific size) and considers the impact of sampling inspection. Solving this large-scale car batching and sequencing problem in the body shop within an acceptable computation time is challenging. In this paper, several efficient dynamic programming-based algorithms are designed to solve the problem. First, a dynamic programming model is established for the deterministic version of the problem, and the optimal solution can be obtained by the dynamic programming approach. Furthermore, faced with the uncertainty introduced by sampling inspection, a more difficult and practical stochastic car batching and sequencing problem is modeled as a discrete-time Markov decision process. A rollout method-based approximate dynamic programming algorithm is designed to solve this complex problem. Finally, the proposed algorithms’ effectiveness is examined using real-life production data. Note to Practitioners—This paper is motivated by our collaboration with a vehicle production plant in Shanghai, China. The plant mainly produces$3\sim 4$electrified models, with an annual output of up to 300,000 units/year. The plant consists of three workshops: the body shop, the paint shop, and the assembly shop. A multi-model flexible production line has been set up in the body shop. In practice, as multiple models are produced on the production line simultaneously, the plant adopts a mode of batch production to batch and sequence the bodies to be produced. Due to the specialty of the batch production mode and the uncertainty brought by the sampling inspection, the stochastic car batching and sequencing problem in the body shop presents a challenge to the plant. This paper proposes dynamic programming and approximate dynamic programming algorithms to effectively solve this stochastic optimization problem. The numerical experiments show the proposed algorithms can solve large-scale problems with near-optimal solutions within a reasonable time span. The algorithm can assist decision-makers in determining the batch size and the production sequence in automobile manufacturing enterprises.

This paper presents an approach to solving the physician scheduling problem in fever clinics by combining Benders decomposition and column generation. The Benders decomposition involves iterating between a master problem that computes the physician staffing requirements and a subproblem that allocates physicians’ schedules to meet these requirements. We suggest an approach based on column generation for an effective solution to the subproblem. In addition, several acceleration strategies are provided to enhance the solution’s efficiency. Based on data collected from fever clinics in Shanghai, the numerical study confirms that the proposed method can control patient queue length and physician working hours. It is also demonstrated that the method can effectively optimize physician scheduling under severe epidemics. The models and algorithms developed from this research can assist fever clinics in their operation and management during an epidemic.Note to Practitioners—Our study is motivated by our collaboration with a fever clinic in a large hospital in Shanghai, China. Since 2019, the Covid-19 virus has spread worldwide, burdening the healthcare system immensely. In China, fever clinics are on the front line in the fight against Covid-19, providing services to patients at high risk of infection. Because of several specific constraints, the physician scheduling process in such clinics is different and more complex. It is challenging for medical managers to provide physicians with high-quality schedules. In order to solve this problem, we proposed a series of methods. In particular, an approach combining Benders decomposition and column generation is designed to solve the problem exactly, and several acceleration strategies are proposed to solve the problem more effectively. Based on real-life hospital data, we demonstrate that the methods presented in this article may help hospital managers obtain more reasonable scheduling solutions, thereby improving patient service quality without increasing physician workload.

Emergency departments (EDs) are facing increasing overcrowding and long patient waiting time, which is mainly caused by the time-varying demand of new and returning patients. In this paper, we focus on scheduling ED physicians to reduce the patient waiting time and the physician working hours. We consider the ED network as a time-varying queuing system with returns and provide an analytical methodology to approximate the system state and patient waiting time of this system. The computation of the system state is based on the pointwise stationary fluid flow approximation method, while we compute the patient waiting time by classifying the patients into groups and individually calculating the waiting time of each group. Because of the nonlinearity of the approximation methods, we propose a linearization technique to formulate the physician scheduling problem as a mixed-integer programming (MIP) model. Since the MIP model is hard to be solved by an optimization solver, a tabu search algorithm is designed. Numerical experiments show that our proposed methods can reasonably approximate the system state and patient waiting time of this complex queueing model. The scheduling computed by the heuristic algorithm can improve the physician schedule without increasing the number of physicians. Note to Practitioners—This article is motivated by the emergency department of our collaborative hospital in Wuhan, China. The emergency department wishes to use a “flexible shifts” strategy to obtain a better physician scheduling plan. Different from the traditional “three shifts” strategy, the “flexible shifts” strategy has more available shifts and more flexible physician assignments to accommodate the fluctuation of the patient demands. However, the managers generally have difficulty providing high-quality schedules to physicians, since they usually lack the understanding of the impact of the time-varying patient demands with returns. Thus, we propose a set of approaches to solve this problem. Especially, a computational approach for calculating the patient waiting time that considers the stochastic and time-varying arrivals of patients and their returns is proposed. Experiments with hospital’s real-life data show the methods proposed in this paper are useful for generating reasonable scheduling plans that can reduce the patient waiting time and system state without increasing the physician numbers.

This article addresses a weekly physician scheduling problem in Covid-19. This problem has arisen in fever clinics in two collaborative hospitals located in Shanghai, China. Because of the coronavirus pandemic, the hospitals must consider some specific constraints in the scheduling problem. For example, due to social distance limitation, the patient queue lengths are much longer in the coronavirus pandemic, even with the same waiting patients. Thus, the hospitals must consider the maximum queue length in the physician scheduling problem. Moreover, the fever clinic’s scheduling rules are different from those in the common clinic, and some specific regulatory constraints have to be considered in the epidemic. We first build a mathematical model for this problem, in which a pointwise stationary fluid flow approximation method is used to compute the queue length. Some linearization techniques are designed to make the problem can be solved by commercial solvers, such as Gurobi. We find that solving this model from practical applications of the hospital within an acceptable computation time is challenging. Consequently, we develop an efficient two-phase approach to solve the problem. A staffing model and a branch-and-price algorithm are proposed in this approach. The performances of our models and approaches are discussed. The effectiveness of the proposed algorithms for real-life data from collaborative hospitals is validated.Note to Practitioners—This article is motivated by our collaborations with two hospitals in Shanghai, China. Covid-19 has swept the world since 2019 and is still raging in many regions, posing an unprecedented challenge to healthcare systems in countries worldwide. The hospitals are the frontlines of healthcare service, and the physicians are the most critical resource in the battles to coronavirus pandemic. In China, many large-scale hospitals establish fever clinics to serve fever patients. The physician scheduling for such clinics is different and complicated in the Covid-19 due to many specific constraints. We find that the managers are tough to give high-quality schedules to physicians. Thus, we propose a set of algorithms to solve this problem. Especially, a two-phase approach that consists of a staffing standard and a branch-and-price algorithm is designed. Based on hospitals’ real-life data, we show that the methods presented in this article can be used to help hospital managers obtain more reasonable scheduling solutions that can improve the service quality without increasing the workloads of physicians.

Ambulance offload delays have become a challenging concern for emergency healthcare service providers. These delays often occur when the number of patients in the emergency department (ED) exceed the designed capacity such that ED cannot accept an incoming patient immediately, thereby forcing the ambulance and crew to wait with the patient until a bed becomes available. In this paper, we analyze and optimize the emergency medical services network, including ambulance stations and EDs. The objective is to reduce ambulance offload delays and lessen the congestion of EDs. To this end, we first build a continuous-time Markov chain to characterize this network analytically. Next, from the perspectives of both ambulance stations and EDs, we develop resource configuration and optimization models for this network. We investigate the reasons for ED overcapacity and ambulance offload delays. Finally, we design an effective approach to reconfigure the resources in the emergency medical services network, leading to a new and better equilibrium. Note to Practitioners—This article is motivated by our collaborations with the Emergency Medical Service Center (also called 120 Center) and several hospitals in Shanghai, China. The Emergency Medical Service Center and ED of hospitals are the frontlines of healthcare services in Shanghai. They provide medical treatment services for acutely ill and injured patients, so the operation of this system is critical to the health of such patients. Today, the ambulance offloading delay poses a challenge to the Emergency Medical Service Center, as it reduces the usage of ambulances and crews, as well as putting patients at risk. Meanwhile, the EDs sometimes suffer from bed shortages and overcrowding. Emergency Medical Service Centers and hospitals are both striving to improve the performance of this system. We analyze the network, including both the ambulance station (AS) and ED, and formulate a continuous-time Markov chain model to describe the network states. Then, we propose two optimization models from both AS and ED perspectives with a series of approximation methods to overcome computational difficulties. We obtain the equilibrium through joint optimization of AS and ED and demonstrate some valuable insights for managing ambulances and beds in the ED. Methods presented in this article may help decision-makers in emergency medical services systems.

In the coronavirus epidemic, many Chinese hospitals have established buffer zones to prevent the spread and transmission of the virus. The buffer zone is a monitored and separate area where the patients who need hospitalizations after the quick treatments in the emergency department can temporarily wait for the Covid-19 test and receive some healthcare services to stabilize their conditions. Because the beds in the buffer zones are limited, the managers face the patient admission control problem for the buffer zone. This management and control problem is challenging since the patient arrivals are uncertain, and the patients’ conditions are different. In this paper, we build the infinite- and finite-horizon Markov decision process (MDP) models for this problem. We use the uniformization method to discretize the patient flow. We propose various iteration algorithms to solve the MDP models and obtain the optimal and threshold policies. Numerical experiments validate the advantages of the policies obtained by the algorithms in this paper over the current policies of hospitals.Note to Practitioners—The ongoing COVID-19 pandemic has been causing enormous damage to people’s health, jobs, and well-being. COVID-19 has affected almost all countries globally and has changed the operation mode of the healthcare system, especially the hospitals. The hospitals are the frontlines of healthcare service and the battle with the COVID-19 pandemic. This article is motivated by our collaborations with hospitals in Shanghai, China. In China, many hospitals establish buffer zones: a monitored area where the patients who need hospitalizations after the quick treatments in the emergency department can temporarily wait for the Covid-19 test and receive some healthcare services to stabilize their conditions. Because the zone’s capacity is limited, the managers must make dynamic patient admission control decisions according to multiple factors, such as patients’ health conditions and the usage of beds in the zone. We propose two MDP models to solve this complex problem. Several iteration algorithms are designed to solve the MDP models and obtain the optimal and threshold policies. Based on hospitals’ real-life data, we show the methods presented in this paper can help hospital managers make more reasonable decisions. Although we focus on the hospital’s buffer zone in China, the methodology and approach for this problem can be extended to other practical hospital management scenarios in the coronavirus pandemic. For example, For example, some hospitals have admission control problems for coronavirus patients due to hospital capacity limitations. The hospital has to decide if a patient is accepted as an inpatient or suggested to home quarantine. In such a case, the admission control problem can also be solved by the methodologies in the paper.

Traffic congestion is an inescapable problem that frustrates drivers in megacities. Although there is hardly a way to eliminate the congestion, it is possible to mitigate the impact through predictive methods. This paper develops a data-driven optimization approach for the dynamic shortest path problems (DSPP), considering traffic safety for urban navigations. The dynamic risk scores and travel times at different times and locations are estimated by the Safe Route Mapping (SRM) methodology and Long Short-Term Memory (LSTM) with Autoencoder, respectively, where possible variations in the future are considered. The DSPP is formulated as a mixed-integer linear programming problem under risk constraints to minimize the total travel cost, defined as the weighted sum of distance and travel time. To improve the efficiency of the DSPP, we design an improved tabu search with alternative initial-solution algorithms to accommodate various problem scales. Moreover, subgraph and self-adaptive insertion techniques are adopted as acceleration strategies to enhance computational efficiency further. Numerical experiments investigate the computational performance and the solution quality of our algorithm. The result shows satisfactory solution quality and computational efficiency with the proposed acceleration strategies compared to the CPLEX solver, a label-setting algorithm, and a state-of-the-art algorithm. Our algorithm can also compete with Google Maps regarding the travel cost in a real network in Manhattan, NY, USA, which is promising for Urban Navigations.

This article addresses the periodic home health care (HHC) server assignment problem in HHC companies. This problem is a variant of the periodic vehicle routing problem with specific constraints for customers and servers (e.g., customers' requirements for multiple medical skills and continuous care offered by a given number of servers and servers' requirements for workload balance). Solving large-scale problems from practical applications of HHC companies within an acceptable computation time is challenging. Consequently, we develop an efficient region-partition-based algorithm to solve these large-scale problems. First, the algorithms assign customers and servers to many independent regions. Second, four different tabu search (TS) algorithms are designed to solve the optimization problem of each region. Finally, the algorithms iteratively adjust the assignment of customers and servers to regions and solve the problems of each region. The performances of different TS algorithms are discussed. The effectiveness of the proposed region-partition-based algorithm for large-scale problems is validated.

This paper aims to devise efficient combination chemotherapy schedules that determine the dosages of drugs administered to cancer patients with drug resistance that, as a Gordian knot to cancer chemotherapy, may weaken the efficacy of chemotherapy. To characterize cell growth, we use the existing cell cycle-specific model, in which the mechanism of acquired drug resistance is incorporated. Subsequently, the determination of the optimal chemotherapy schedule for the patients is formulated as a nonlinear optimization problem, with the objective of minimizing not only the quantity of tumor cells but also the posttreatment chemotherapy-induced toxicity. To overcome the difficulty in finding a satisfactory solution to the problem due to its nonlinear nature, we develop a memetic algorithm (MA) with an advanced local search strategy. The efficiency of the proposed MA is validated by comparison with other state-of-the-art methods. In addition, we compare the best found solution to the problem in the presence of drug resistance with that in the absence of drug resistance. The resultant findings reveal that drug resistance is a crucial factor in the determination of chemotherapy schedules.

Fluctuations in emergency department (ED) patient arrivals during the day are one of the main causes of the long waiting times that are frequently encountered, and ED staffing is one of the key drivers of ED service quality improvement. This paper first proposes discrete-time models for approximating the patient waiting times for any given ED staffing. The waiting time approximation is based on three simple ideas: the separation of patients served in a period and patients overflowed, the combination of M/M/c approximation for patients served and waiting time analysis of overflow patients, and the transformation of the performance evaluation into an optimization problem with the number of overflow patients as decision variables. The resulting waiting time approximations are then integrated into ED staffing optimization models, and variable neighborhood search algorithms are developed to solve the ED staffing models. Numerical experiments with real-life data from Chinese hospitals are performed to validate the proposed models and algorithms. The results show that the proposed methodology is able to significantly reduce the total waiting time of patients without increasing staff capacity. The online appendix is available at https://doi.org/10.1287/ijoc.2017.0799 .