Omar El-Rifai

Thierry Garaix

Vincent Augusto

Xiaolan Xie
email: xie@emse.fr

A Stochastic Optimization Model for Shift Scheduling in Emergency Departments

Excessive waiting time in Emergency Departments (ED) can be both a cause of frustration and more importantly, a health concern for patients. Waiting time arises when the demand for work goes beyond the facility's service capacity. ED service capacity mainly depends on human resources and on beds available for patients. In this paper, we focus on human resources organization in an ED and seek to best balance between service quality and working conditions. More specifically, we address the personnel scheduling problem in order to optimize the shift distribution among employees and minimize the total expected patients' waiting time. The problem is also characterized by a multi-stage re-entrant service process. With an appropriate approximation of patients' waiting times, we first propose a stochastic mixed-integer programming model that is solved by a sample average approximation (SAA) approach. The resulting personnel schedules are then evaluated using a discrete-event simulation model. Numerical experiments are then performed with data from a French hospital to compare different personnel scheduling strategies.

Introduction

Emergency departments are the crux of hospitals as they serve as a center for medical treatment and as a continuously operating portal for inpatient admissions [START_REF] Schuur | The growing role of emergency departments in hospital admissions[END_REF]. It is important when considering the ED, to provide patients with timely health care while maintaining a healthy work environment for the personnel. Further ED are facing the challenge of providing a good quality of service while being cost-effective.

Increasing demand for health services in recent years and a reduction of the number of resources in the health industry due to budget cuts have led to chronic overcrowding in the ED [START_REF] Jones | A multivariate time series approach to modeling and forecasting demand in the emergency department[END_REF]. From the patients' point of view, an overcrowded emergency department leads to excessive waiting times. While from a health specialist point of view, it can be the cause of an unfriendly work environment [START_REF] Rogers | The Working Hours Of Hospital Staff Nurses And Patient Safety[END_REF]. One of the major consequences of overcrowding with regards to the Operations Research community is a growing interest in developing strategies that make the most efficient use of the available resources [START_REF] Ernst | Staff scheduling and rostering: review of applications, methods and models[END_REF]. In France, a recent report of the first national ED conference which gathered health practitioners and government officials decreed the urgency of the problem of long waiting times [START_REF]Réduire les temps de passage aux Urgences[END_REF]. The report describes several strategies to reduce the potential bottlenecks that cause overcrowding which can also be found in the literature [START_REF] Sven | A systematic review of triagerelated interventions to improve patient flow in emergency departments[END_REF][START_REF] Akkerman | Reallocation of beds to reduce waiting time for cardiac surgery[END_REF][START_REF] Bruin | Dimensioning hospital wards using the Erlang loss model[END_REF]. Among the recommendations, the authors mention the need to improve patient flow, the need to organize inpatients bed resources and the need to make a better use of available resources.

As ED work around the clock, a turnover of health care professionals is necessary in order to ensure an appropriate service level at all time. In the context of emergency departments, the work demand across the day is subject to the rate of arrivals of patients. In turn, the arrival rate of patients is subject to stochastic variations. These variations make the problem of organizing the workforce difficult.

1 A look at the number of patients and the staff level in Figure 1 observed at our collaborating hospital clearly shows mismatch of patients flow and personnel schedules. At every time period, the activity is estimated with the average number of patients present in the ED. Figure 1 clearly shows a peak of activity in the evenings. The distribution of staffs on duty does not appropriately match the peaks of activities observed in the ED. These observations prompted us to design a personnel scheduling model to meet the work demand accurately while satisfying the work constraints imposed. In this paper, we present a human resources planning model for ED in order to explore the various human resources planning options and to take into account their robustness to face uncertainties and time-dependent patient arrival rate. The main efficiency criterion considered is the total patient waiting time. While other criteria are possible, total waiting time is a good indicator of patient service quality and ED crowding.

Personnel schedule is determined by a high-level stochastic programming model in which patient waiting times are approximated by a discrete time model and legal constraints for personnel scheduling are taken into account. The stochastic programming model is solved by a deterministic sample average approximation (SAA) [START_REF] Kleywegt | The sample average approximation method for discrete optimization[END_REF] and mixed-integer programming. The resulting personnel schedules are evaluated with a more realistic ED discrete-event simulation model.

Workforce Scheduling in Emergency Departments

With the growing work constraints and the expansion of work facilities, the employee scheduling problem has become, for most industries, manually intractable. As early as 1954, mathematical models have been used in order to computationally assist industries to schedule their employees to work [START_REF] Edie | Traffic delays at toll booths[END_REF]. Employee scheduling is often decomposed into several sub-problems [START_REF] Ernst | Staff scheduling and rostering: review of applications, methods and models[END_REF]. In a dynamic environment where the workload is variable, the first task is to be able to forecast the work demand for any scheduling horizon [START_REF] Mccarthy | The challenge of predicting demand for emergency department services[END_REF][START_REF] Jones | Forecasting daily patient volumes in the emergency department[END_REF][START_REF] Jones | A multivariate time series approach to modeling and forecasting demand in the emergency department[END_REF]. Once a work demand estimate is known, the decision maker has to determine an optimal staffing level for each scheduling period. After that, the staffing level is used as a basis for creating schedules that meet the staffing level appropriately. Finally, an assignment phase matches employees to the schedules created.

One of the peculiarities in scheduling studies conducted for health care systems is the focus on multiskill scheduling. The work demand in health care systems needs to be addressed by appropriately qualified personnel and cannot be distributed arbitrarily between the resources [START_REF] Warner | Scheduling nursing personnel according to nursing preference: A mathematical programming approach[END_REF][START_REF] Jaumard | A generalized linear programming model for nurse scheduling[END_REF]. This multi-skill characteristic adds yet another layer of complexity to the workforce scheduling in ED that is often overlooked. We identify two main types of human resources in this study (physicians and nurses) and schedule them simultaneously. Simultaneous scheduling of different resources means having the work of one type of resource impact the schedules of the other.

With regards to the staffing problem, the work demand in the ED cannot be determined easily and depends on the arrivals of patients in the services and on the interactions between different resources. Literature on staff scheduling in the ED often considers stochastic demand patterns in order to address the uncertainty in the arrival of patients [START_REF] Izady | Setting staffing requirements for time dependent queueing networks: The case of accident and emergency departments[END_REF][START_REF] Sinreich | Reducing emergency department waiting times by adjusting work shifts considering patient visits to multiple care providers[END_REF]. Sinreich and Jabali [START_REF] Sinreich | Staggered work shifts: a way to downsize and restructure an emergency department workforce yet maintain current operational performance[END_REF] propose a simulation model coupled with an linear programming model to downsize emergency departments while keeping the patients' length of stay (LOS) constant. The simulation model dictates the required staffing profile while the linear programming model chooses the schedules that matches this staffing profile best. Zeltyn et al. [START_REF] Zeltyn | Simulation-based models of emergency departments:: Operational, tactical, and strategic staffing[END_REF] propose a unique simulation model to address the human resources allocation problem on multiple decision levels (operation, tactical and strategic). On the tactical level, they use two strategies: the Rough Cut Capacity Planing (RCCP) technique and the Offered Load approach. The later being a refinement of the former that allows to split the workload. The staffing level is computer hourly through the analysis of a simple queuing system. Queuing theory has also been extensively used for determining staffing levels because it allows the evaluation of quality of service criteria such as the waiting time of patients [START_REF] Green | Using queueing theory to increase the effectiveness of emergency department provider staffing[END_REF][START_REF] Jennings | Server staffing to meet time-varying demand[END_REF]. However, analytic formulas for determining optimal staffing levels are often limited with regards to the complexity of the system they can analyze. As such, no analytical formula exists for optimally determining staffing level in systems with time-dependent stochastic arrival rates but instead numerical approximations have been used to alleviate this problem [START_REF] Vile | Time-dependent Stochastic Modelling for Predicting Demand and Scheduling of Emergency Medical Services[END_REF]. For example Ingolfsson et al. [START_REF] Ingolfsson | Accounting for time-varying queueing effects in workforce scheduling[END_REF] use an integrated queuing and optimization model to investigate the effect of time-varying arrival rates in the context of workforce scheduling. The authors present a heuristic to construct potential schedule then use queuing theory to evaluate the resulting service levels. Izady and Worthington [START_REF] Izady | Setting staffing requirements for time dependent queueing networks: The case of accident and emergency departments[END_REF] use queuing theory and simulation in an iterative staffing scheme to determine schedules for an ED modeled as an infinite server network with different tasks and processes. After an appropriate staffing level is determined, an ILP is employed to find shifts that minimize the over-staffing and under-staffing. Cochran and Roche [START_REF] Cochran | A multi-class queuing network analysis methodology for improving hospital emergency department performance[END_REF] suggest a queuing network approach for capacity planning of beds and staff in an ED. Their methodology is based on a multiple-customer class queuing analysis to increase ED access. Seasonal variation is of patient arrival patterns is considered.

In this work, the ED is represented as a multi-server multi-stage time-dependent priority queue system with re-entrance, Poisson distributed arrivals and exponential service times. Physicians and nurses are the servers whose cyclic schedules are to be determined. The planning horizon is discretized into time periods and a different mean arrival rate is given for every period of the day. We choose the expected total patient waiting time as the main criteria to optimize as it is often associated with patients' and staff well-being and is a good indicator of ED crowding. In order to address the complex nature of the problems, many studies addressed each sub-problem in the employee workforce scheduling independently by overlooking the inherent interaction between them [START_REF] Vile | Time-dependent Stochastic Modelling for Predicting Demand and Scheduling of Emergency Medical Services[END_REF]. As such, the optimal staffing level is often considered separately from the scheduling problem. This approach neglects complex waiting queues generated by uncertainties and changing patient arrival rate, which is crucial for ED crowding. In this work, we consider the staffing level as part of the scheduling problem and solve them both simultaneously. Integrating the two sub-problems allows us to schedule employees while reproducing the work dynamics of the system and simulating the patient flow.

The structure of the work is divided into two parts. First, we build an optimization model that finds staff schedules with operational constraints. Then, we evaluate more accurately our solution in a simulation model to measure the value of some of the assumptions in the optimization model. The optimization problem is solved by a Sample Average Approximation (SAA) solution methodology by considering different possible scenarios or realization of patient flows in the ED and optimizing the workforce scheduling problem considering all the different realizations. The remaining of the paper is organized as follows. We first describe the ED model in details in Section 3, then explain the optimization and the simulation models along with the assumptions that we consider in each in Sections 4 and 5 respectively. Then, we present numerical experiments in Section 6 and conclude in Section 7.

of an ED. Patients can follow different trajectories through the ED depending on their pathology and their severity level. A simplified scheme for their trajectory is as follows. Patients are first assessed by a nurse to determine whether they need vital medical care, a step often called triage. If they need vital care, they are taken in priority to a resuscitation room. Otherwise, the patients wait in a waiting room until a physician is available to examine them. After the first assessment, patients are either directly treated by a nurse or are sent for auxiliary exams to confirm the diagnostic. The auxiliary exams range from a simple blood test to time-consuming imaging tests. After the auxiliary exams are performed, the patients are examined again by a physician and finally treated by a nurse before being discharged or admitted into another department in the hospital [START_REF] Izady | Setting staffing requirements for time dependent queueing networks: The case of accident and emergency departments[END_REF]. The second assessment leads to re-entrance of patients to the same resources. Priority is given to patients that are being assessed for the second time by physicians over patients arriving for the first time.

Each process in the ED can be modeled as a queue where jobs to be served are the patients and the hospital staff are the servers that handle these jobs. Figure 2 illustrates a basic queuing system. On the left side, we have patient arrivals into the system which follow an inhomogeneous Poisson distribution of parameter λ t . Once in the system, they wait in a queue before being served by one of the servers of the system. The service time is assumed to be exponentially distributed in this paper. This corresponds to an M t /M/c queue model where M stands for the Markovian assumptions on the arrival and the service rates and c is the number of servers available.

Figure 2: A basic queue model that represents a process in an ED From the above, each ED has three main activities: assessment, treatment and auxiliary exams. The two health care providers that we model in the system are physicians and nurses. Physicians perform health assessments and examine the patients before and after having auxiliary exams. While nurses handle the final treatment administered to patients. As such, physicians are the servers for the two assessment queues of our system and nurses are the servers for the last queue. The overall system is illustrated in Figure 3. We do not schedule the lab technicians as they are often resources not entirely dedicated to the ED but instead delay patients that need to have auxiliary exams done.

Apart from the patients care pathway modeling, the queuing model also accounts for the stochastic nature of the work in the ED. The arrival rate of patients greatly varies during a day with peak arrival during the evenings and low arrival during the night. Service time needed to treat each patient can-not be known in advance. The stochastic service duration used in this paper models the different needs of patients. The number of patients arriving for each period of our planning horizon is parametrized by mean arrival rates that can be estimated from past data. Service distributions are estimated based on mean service times observed and found in the literature.

In Section 4, we present the mathematical formulation that we derived from the system specifications explained in this section. Some simplifying assumptions are made and detailed to solve the problem in reasonable time. Nonetheless, the solutions are evaluated using a more realistic simulation model whose specifications are explained in Section 5.

Mathematical Formulation

In this section, we present a mathematical formulation that is based on the details discussed in section 3. The objective is to optimize a waiting time performance indicator that we approximate with discrete time variables. As patients' waiting time is heavily influenced by the number of personnel present in the ED at any given time, the model finds optimal schedules over the planning horizon. For the time being, we are not interested in assigning the schedules to actual health personnel but only in finding an optimized schedule that meets the objective of minimizing the average total waiting time. In order to keep the model realistic, we allow for a limited number of different hours in which the staff can start working.

The number of patients arriving at each period t for each queue q is denoted A t,q (ω). This symbol is overloaded in our model as it both designates the Poisson distributed arrival to the first two queues and the variable designating the arrival of patients to the nurses' queue. After the patients enter a queue, they are counted as waiting in the variable W t,q (ω). Patients that are served in a queue, are counted in the variables O t,q (ω). Then, parameter L i,n,t (ω) determines the service capacity of the staff at each period. More specifically, the parameter determines the number of patients that n resources of type i can serve during period t. The ω index designates one scenario of patients' arrival and visit to the ED. The decision variables of the model x i,n,t define the number of health care providers working during period t.

To model the operational constraints, we use several parameters. A lower bound LBD and an upper bound U BD specify the possible lengths of the shifts that can be assigned to the personnel. The number of different hours of the day in which personnel of type i can start working is denoted by d i . An upper bound T T i is set on the number of total working hours that can be scheduled for resources of type i. The delay at the auxiliary exams is designated by δ. Finally some variables, p i,t , s i,t , e i,t and z i,t are used to facilitate the expression of shift constraints. Some modeling assumptions are made in order to be able to solve the problem efficiently. A discrete-time approximation of the waiting time is calculated as W t,q minus O t,q . What follows is that patients arriving during one period can only be treated in the next. Also, the waiting time of patients during the period they arrive is not counted. The patients are divided into two classes, those that do not require auxiliary exams and those that do. Each patients' class has a well defined trajectory from the start. This allows us to avoid having to route the patients to their appropriate queue after they have been assessed. This assumption is justifiable inasmuch as we do not care about each patients' trajectory individually. Instead, we keep track of the total number of patients in each queue of the system at each period t. We also assume the system is initially empty. We make this assumption by starting the scheduling horizon at an hour when it is reasonable to say that the system is clear. As of the data available to us, this is most true around 5:30 in the morning. Furthermore, we do not distinguish between the different health care providers with the same skills and consider all physicians to be homogeneous and all nurses to be homogeneous. For the sake of simplicity, we omitted the possible visit of patients to the vital care unit. As of the data available from the UHC of Lille for the year 2011 and 2012, patients that require vital prognosis only constitute 1.79% of the total patients and those in need of resuscitation merely 0.45%. Finally, auxiliary exams are always assumed to last for a fixed duration. Of course, these assumptions are relaxed in the simulation model and evaluated for consistency in the numerical experiments.

Parameter

(W t,q (ω) -O t,q (ω))] (1)
Subject to: O 1,q (ω) = 0 ∀q (4)

W 1,q (ω) = A 1,q (ω) ∀q ∈ {1, 2} (2)
W 1,q (ω) = 0 ∀q / ∈ {1, 2} (3)
W t,1 (ω) = W t-1,1 (ω) + A t,1 (ω) + O max(t-δ,1),2 -O t-1,1 (ω) ∀t ∈ [2..T ] ( 5
)
W t,2 (ω) = W t-1,2 (ω) + A t,2 (ω) -O t-1,2 (ω) ∀t ∈ [2..T ] (6)
W t,3 (ω) = W t-1,3 (ω) + O t-1,1 (ω) -O t-1,3 (ω) ∀t ∈ [2..T ] (7)
O t,q (ω) ≤ W t,q (ω) ∀t ∀q (8) q∈{1,2} O t,q (ω) ≤ N1 n=1 L 1,n,t (ω) * x 1,n,t (ω) ∀t (9)
O t,3 (ω) ≤ N2 n=1 L 2,n,t (ω) * x 2,n,t (ω) ∀t ( 10
) t p i,t ≤ T T i ∀i (11)
t (s i,t -e i,t ) = 0 ∀i (12)

p i,t = t t =2 (s i,t -e i,t ) + p i,1 ∀t ∈ [1..T ] ∀i (13)
p i,1 = p i,T + s i,1 -e i,1 ∀i (14)
mod(t+LBD,T +1)

t =t+1 e i,t ≤ p i,t -s i,t ∀t ∈ [1..T ] ∀i (15)
p i,t ≤ mod(t+U BD+1,T +1) t =t+1 e i,t ∀t ∈ [1..T ] ∀i ( 16
) Ni n=1 n * x i,n,t = p i,t ∀i ∀t (17)
Ni n=1

x i,n,t = 1 ∀i ∀t (18)

z i,t * N i >= s i,t ∀i ∀t (19)
z i,t ≤ d i ∀i ∀t (20)
p i,t ≥ 1 ∀i ∀t (21)
p i,t ≥ s i,t + 1 ∀i ∀t (22)
The objective function of the model ( 1) is a discrete time approximation of the total patients waiting time accumulated over all the scenarios. By summing over all the sample scenarios ω ∈ Ω considered, we seek to obtain a good approximation of the estimated value of the actual waiting time of patients in the system. Constraints (3) and (4) initialize the number of patients in the queues in each scenario. This assumption of empty patient queue at the beginning of a day corresponds to our field observation of several ED in which often no patient remains late in the night such as at 5.30am. This is true whether the ED is busier during the day or not. The next set of equations of the problem are balance equations to track the movement of patients through the ED. As such, (5), ( 6) and ( 7) update the number of patients in each queue at every time period.

Constraints (8) specify a logical bound for the number of patients served during a period. This number can-not be larger than the number of patients already in the queue. Then, constraints [START_REF] Jennings | Server staffing to meet time-varying demand[END_REF] limit the total number of staffing hours available for each type of resource. Constraints ( 12) through ( 14) are logical constraints that define the range of values the variables p, s and e can take. Then, constraints ( 15) and ( 16) define the type of shifts that are allowed by specifying a lower bound and an upper bound on the shift lengths.

Constraints [START_REF] Schuur | The growing role of emergency departments in hospital admissions[END_REF] and ( 18) assign a value to the variables x which is used to limit the number of patients served at every time period in constraints ( 9) and [START_REF] Jaumard | A generalized linear programming model for nurse scheduling[END_REF]. Finally constraints [START_REF] Sinreich | Reducing emergency department waiting times by adjusting work shifts considering patient visits to multiple care providers[END_REF] through [START_REF] Warner | Scheduling nursing personnel according to nursing preference: A mathematical programming approach[END_REF] are operational constraints to make sure that there are at most d i different moments of the day where resources of type i start working and that there is at least one resource of each type in every time period. We need to have an upper bound on the number of periods resources can start working in because physicians and nurses need to transmit patients' information to their colleagues before leaving the service. As such, constraints [START_REF] Warner | Scheduling nursing personnel according to nursing preference: A mathematical programming approach[END_REF] make sure that the shifts of the different resources overlap.

Simulation Model

In order to evaluate the validity of the assumptions and simplifications made in the mathematical formulation, we test the solutions obtained using a simulation model. The simulation model includes several features not considered in the optimization model for a more accurate representation of the ED. The simulation improves over the mathematical formulation on several fronts: system specification, patients specification and resources activities.

As in the optimization model, exponential service time and Poisson arrival rates are used in the simulation model. However, the simulation uses a discrete event paradigm instead of the discrete time model paradigm in the optimization. This is important as one of the key assumptions in the optimization problem is that a discrete time model can serve to calculate patients' waiting time accurately. Second, the vital care pathway is no longer ignored. Patients requiring vital prognosis are attended by a physician and a nurse immediately. Auxiliary exams are divided into two categories: biological exams and diagnostic imaging exams. The biological exams make for 55% of the examinations.

Patients on the other hand are no longer homogeneous but are classified according to their acuity level (from 1 to 5 in increasing order of severity). The classification scheme used is that of the french hospitals known as CCMU (Classification Clinique des Malades des Urgences). This allows for a sickest-first prioritization in the different queues of the ED. Additionally, the patients that are classified as CCMU 4 or CCMU 5 skip the regular route and are treated in priority in the vital care pathway. These patients are served by both a nurse and a physician for a random duration.

Finally, with regards to resources, physicians are no longer solely occupied by patients. Instead, they also have to respond to administrative tasks such as searching patients' historical data or finding downstream beds for inpatients. Beds are not explicitly modeled in the system. instead, patients waiting in queues are considered to be assigned either a room or a hallway bed. Administrative tasks occur at random intervals but follow the same distribution laws as patient arrivals. Having the same distribution makes sense if we think that administrative tasks are more likely to occur when patients enter the system. Nurses no longer solely handle patients' treatments but also take care of the biological exams.

This improved ED model is used to evaluate the solutions obtained with the optimization model. Important system statistics such as the estimated patients' waiting time and the time spent in the system can be extracted and a confidence interval for these data can be calculated.

Numerical Experiments

Numerical experiments have been conducted to show the potential reduction of patients' waiting time in an ED by adjusting the workforces' shift schedules. The parameters settings for the optimization model, the simulation model, and the real-world benchmark are described in Section 6.1. In Section 6.2, we check that the optimization model matches enough key features of the queuing system to provide suitable solutions. In order to do so, the schedules obtained by running the optimization model are evaluated and compared to simulation tests. The performances of different scheduling strategies are also compared. The strategies differ in the constraints on the employees' shifts. In Section 6.3 the robustness of schedules facing significant demand increase is evaluated and in Section 6.4 the transition from week schedules to week-end schedules is investigated. The optimization model is solved using a commercial solver (IBM Ilog Cplex 12.5). All tests were performed on an Intel(R) Xeon(R) 4 cores CPU E5520 @ 2.27GHz with 8 MB of cache memory and 8 GB of RAM. The evaluation is done using AnyLogic 6.9.

Parameters Settings and Real-World Data

The parameters used in the experimental section are based on data for the years 2011-2012 of patients' entries in the pediatrics' ED of the University Hospital Center (UHC) of Lille France. We extracted from these data an average number of patients' arrivals per half-hour of the day and used them as parameters for the Poisson distributions of each period. The length of the period also called time step ∆ = 30 minutes is chosen primarily to coincide with the shifts change marks used in the hospital. Also, the patients' arrival averages are calculated according to length of the time step. Average values would be less significant if they relied on less data. As the data available only contain arrival and departure times, we did not determine the service duration of patients in the same manner as the arrivals. Instead, we relied on average service durations found in the literature and on experts' opinion to calibrate these parameters. However, the patients' lengths of stays obtained with these service durations are of the same order of magnitude than those observed in the real data. Based on these parameters, we generate several possible scenarios for patients arrivals and service time.

In the UHC of Lille, the number of resources working during the week differs drastically from the number of resources working on the weekends. Therefore, two set of optimization tests are run. The first set of tests uses the staff hours available during the week and the arrival distributions extracted for weekdays and the second set of tests relies on data for weekends. The total staff hours available serves as an upper bound on the number of hours scheduled. Each scenario in the optimization model is generated by obtaining a realization ω of the distributions of the arrival and service times. Once the different parameters of the models are set, the scenarios are the only input to the model.

After the schedules are optimized, we evaluate these schedules and the waiting time they produce in the simulation model. As the schedules we obtain are cyclical, the evaluation is done for several consecutive days. We introduce a warm-up period in order to reach stable results. Evaluating the performance of the schedules can be done on a large number of replications which allows the calculation a confidence interval. The parameters used for the experimental runs are summarized in Table 3.

To validate the pertinence of a scenario-based strategy, we ran three different instances of optimization tests. After obtaining the resulting schedules from each test, we evaluated the evolution of the expected waiting time in the simulation model using the resulting schedules. We see the results in Figure 4, where the average waiting time over all three tests are displayed. The average waiting time of the patients decreases with the increase of the number of scenarios used in the optimization. We notice that the expected waiting time stabilizes for about |Ω| = 100 scenarios.

In terms of computational feasibility, our model strongly depends on the number of scenarios used for optimization and on the time step chosen. This is because the number of variables increases linearly with the number of scenarios and the number of periods. Fortunately, we showed that the simulated average waiting time converges with solutions obtained from 100 scenarios. From our tests, all solutions with 100 scenarios were obtained within 4 hours with a 0.11% relative gap in the worst case.

Other variables in the model also influence the running time but to a lesser extent. As such, the number of patients in the queues does not increase the number of variables but only the range the variables can take. On the other hand, the number of variables representing resources: x i,n,t increases as the number of resources increases but is independent of the number of scenarios. For example, in a large ED with about 200 patients daily and 10 to 15 resources of each type, the optimal solution is still obtained within the 4 hours of computation time. Throughout the tests, the schedules obtained are compared against the reference schedule ref that is currently put in place in the ED of Lille. The first alternative we test are schedules obtained with shifts whose length is fixed to 8 hours for both physicians and nurses. The schedules obtained with this strategy give us an idea of how much we can improve by changing the starting times along with more restrictive shift constraints than what is currently practiced. Then, we keep the shifts lengths range from 4 to 12 hours as it is the case in the UHC of Lille but modify the starting times. The third and final alternative is to create shifts with no constraint on their lengths. In this last case, the only constraint is the total number of hours worked. This last strategy is not realistic but merely allows us to compute a lower bound on the total waiting time of the patients in the optimization model. Constraints on every schedule strategies are given in Table 4. The parameters d i and T T i refer to the parameters presented in the optimization model.

Parameter

Shifts

Analysis of optimized schedules

We verify in a first part that the optimized schedules obtained can actually reduce the average waiting time of patients compared to the reference schedule when tested in simulation conditions. In order to do so, we allow for different assumptions on the shifts as explained previously. In all the alternatives tested, we allow the shifts to start on any period of the day but only permit a limited number of shift changes to occur as it is currently the case. Our analysis in this subsection focuses on weekends but results obtained for weekdays are similar and lead to the same conclusions. Table 5 summarizes the results obtained for schedules optimized to weekend conditions. The first column specifies the shifts type used. The number next to the shift type specifies different runs of the optimization problem, each with a different set of scenarios. W -O, is total objective value converted to average hour units per patient. This value gives an approximation on the expected waiting time as computed in the optimization model. The total waiting time associated with each queue, q in the optimization model is given in the columns W q -O q , for q ∈ {1, 2, 3}. Next, the Gap indicates the percentage distance between best lower and upper bounds obtained. An time limit of 240 minutes is used for each run of the optimization problem.

Shifts W-O (h) W 1 -O 1 (h) W 2 -O 2 (h) W 3 -O 3 (h) Gap % Time(mins) ref (
The simulation model of Section 5, is used to evaluate each solution schedule. The results of the evaluation are presented in Table 6. The simulation is run over 100 replications each of 10 successive days. Since we only have a unique reference schedule, only one row keeps track of the expected waiting time using the reference schedule. Table 6 first notes the patients' expected waiting time in W ait. The next columns indicated the expected and max waiting time in the physicians' queue (Q phys ) and nurses' final treatment queue (Q nurs ). The results consistently reduce the expected waiting time of patients in more flexible strategies. This is further confirmed by the similar behavior of the maximum expected waiting time over all replications, in columns Qmax. However, within this trend of reducing the average waiting time, the results are not very stable. Different set of scenarios in the optimization model result in different waiting time in the simulation model. For example with shifts of fixed length the waiting time varies between 79.94 minutes for the first set of scenarios and 87.28 for the second set. This can be explained by the approximations that were made and the fact that we only used a limited number of scenarios (σ= 100) to optimize.

Having schedules with very flexible shifts (in the range 1-24 hours) does not really improve the waiting time of patients compared to schedules with shifts in the range of 4-12 hours. Consequently, we note that modifying the starting times of the shifts is the factor that helps us most improve the expected waiting times, even with a constant total working hours capacity. As explained in Section 3, queues 1 and 2 are served by physicians and queue 3 is served by nurses. In the simulation model, the first two queues are grouped into a physician queue Q phys .

Figures 5, 6 and 7 present example staffing levels obtained by optimizing the schedules following the different shift strategies. The reference schedule clearly misses the evening peak of arrivals while the other strategies closely match the arrival curve. We note that the solution with shifts varying from 4 to 12 hours and those varying from 1 to 24 hours are very close and match the ascending and descending slopes of the arrivals flow. These observations corroborate the results obtained in Tables 5 and6.

Validation of the Robustness of the Schedules

In this set of simulation runs, we increment the number of patients arriving to the system and evaluate the schedules obtained through optimization again. In order to do so, we increment the average Poisson parameter for each period. This increase in the number of arrivals results in about 15% more patients per period. Since the schedules have not been optimized to perform under these conditions, the evaluation allows us to have an idea on the robustness of the schedules during epidemic periods.

The results of this set of tests are summarized in Tables 7 and8. We notice from the results that the expected waiting time increases proportionally to the results of Section 6.2 across the different solution instances. Consequently, the optimized schedules still outperform the reference schedule in unfavorable conditions. This coherence in the waiting times is still true for each queue individually but we see a disproportionate increase in the average maximum waiting times for schedules constructed with (1-24h) constraints. This increase is understandable as the (1-24h) constraints specifically exploit the discrete-time approximation of the optimization model. Schedules with (1-24h) constraints can be expected to perform poorly under different conditions than those they were optimized for.

Shifts

Week to Weekend Transition

One limitation of the previous results is that the cyclical schedules are evaluated independently for weekdays and weekends. In order to have simulation conditions that are closer to reality, the transition from a weekday schedule to a weekend schedule needs to be evaluated. Consequently, weekday and weekend schedules are concatenated and tested under both the average conditions for arrivals and the epidemic conditions. The results in Tables 9 and10 show that the transition from the week schedules to the weekend schedules can be done without real complications. The average waiting times observed when the concatenation of schedules is performed follow the results obtained previously. Indeed, the optimize schedules outperform the reference schedules under normal and epidemic conditions.

The results of the final set of tests are summarized in Figures 8 and9. As we have mentioned, the schedules with shifts varying from 1 to 24 hours do not give a significant advantage over the schedules with shifts varying from 4 to 12 hours. Finally, Figures 8 and 9 illustrate the differences in sojourn time according to the CCMU of patients. Coherently, patients with higher priority spend less time in the system than those with lower priority.

Conclusion

We presented in this study a stochastic optimization formulation for an ED shift scheduling problem. Schedules of interest are computed once for some representative period such as winter or summer season or weekdays and weekends. During this period, the schedules are repeated daily. The formulation follows the flow of patients through the ED and takes into account the stochastic nature of arrivals and service times. The constraints used to follow the evolution of patients through the ED mirror those in stock management literature. The optimization model is solved using a deterministic Sample Average Approximation (SAA) method. This model assumes many simplifications in order to be tractable in a commercial linear programming solver. The solution schedules obtained by the optimization model are evaluated using a discrete event simulation model under various test conditions to verify the validity of the assumptions and the robustness of the solutions. The simulation model used to evaluate the results has several improvements over the optimization model. Improvements such as patient prioritization and multiple tasks for resources (administrative tasks for physicians and biological exams for nurses) make the simulation model more realistic. The evaluation demonstrates that the assumptions made hold for optimizing the average waiting time. Nonetheless, the simulation model remains a simplification of the ED and hence lacks some elements that can be taken into account in future research. For example the service time of patients is approximated with an exponential distribution. Even if this approximation is very common in the literature, service times are usually not exponentially distributed. Hence, a possible extension to our work would be to test detailed patient service times to be collected from our partner hospital. Furthermore, excessive waiting time is only one aspect among many that define overcrowding in ED. Average waiting time is important and influences other criteria such as the maximum waiting time but other service quality criteria such as limited bed capacity contribute to overcrowding and should be considered in future research.

Real data from the UHC of Lille France are used to evaluate the quality and the performance of the schedules obtained. The proposed optimization approach allows to find promising cyclic schedules. The framework proposed is easily extensible and allows the integration of several strategical and operational constraints that are not possible using other methods.

Figure 1 :

 1 Figure 1: Preliminary analysis of the data from the pediatrics ED of Lille Hospital

Figure 3 :

 3 Figure 3: Process chart of patients in the ED

3 :

 3 Parameters of the system and of the optimization algorithm

Figure 4 :

 4 Figure 4: The evolution of waiting time with the number of scenarios used in the optimization model

Figure 5 :Figure 6 :

 56 Figure 5: Resulting staffing levels with shifts fixed to 8 hours

Figure 7 :

 7 Figure 7: Resulting staffing levels for shifts varying from 1-12 hours

Figure 8 :

 8 Figure 8: Expected sojourn time for the different acuity classes in normal conditions

Figure 9 :

 9 Figure 9: Expected sojourn time for the acuity classes in epidemic conditions

Table 1 :

 1 The parameters of the scheduling model.

		Meaning		Domain
	t	The different periods	[1..T ]
		of the day
	n	Number of resources of	[1..N i ]
		each type
	i	The different type of	{1,2}
		resources available
	q	The queue number	[1..Q]
	d i	Maximum number of	[1..S i ]
		different starts for each
		resource
	T T i	Number of working
		hours available to
		schedule for resource
		of type i
	LBD	Lower bound on the	[1..47]
		shift length allowable
	U BD	Upper bound on the	[2..48]
		shift length allowable
	δ	The delay at the auxil-
		iary exams
	A t,q (ω)	Poisson distributed ar-	N+
		rivals in period t for
		queue q
	L i,n,t (ω)	Sum of exponentially	N+
		distributed	consul-
		tation times for n
		resources of type i at
		period t
		Objective:
	min	Ẽ

ω∈Ω [ t q

Table 2 :

 2 The variables of the scheduling model.

	Variable	Meaning	Domain
	x i,n,t	= 1 if there are exactly	{0,1}
		n resources working at
		period t
	p i,t	Number of resources of	[1..N i ]
		type i present at pe-
		riod t
	s i,t	Number of resources of	[1..N i ]
		type i starting at pe-
		riod t
	e i,t	Number of resources of	[1..N i ]
		type i ending at period
		t
	z i,t	Indicator variable that	{0,1}
		is equal to 1 if at least
		one resource of type i
		starts working at t
	W t,q (ω)	Number of patients	R+
		that are waiting in
		queue q a the start of
		period t
	O t,q (ω)	Number of patients in	R+
		queue q that have been
		served during period t

Table 4 :

 4 Parameters for the scheduling strategies

		LBD(h) U BD(h)	d 1	d 2	T T 1	T T 2
	ref	4	12	7 (week), 5(weekend) 6 178 (week), 130 (weekend) 124
	(4-12h)	4	12	7 (week), 5(weekend) 6 178 (week), 130 (weekend) 124
	(8h)	8	8	7 (week), 5(weekend) 6 178 (week), 130 (weekend) 124
	(1 -24h)	1	24	7 (week), 5(weekend) 6 178 (week), 130 (weekend) 124

Table 5 :

 5 Optimization results for the weekend scenarios

	1)	0.41	1730	2581	1131	0.00	0
	(2)	0.39	1767	2175	1200	0.00	0
	(3)	0.47	1919	2939	1289	0.00	0
	8hrs (1)	0.27	1449	1415	683	0.02	240
	(2)	0.26	1416	1311	738	0.01	240
	(3)	0.31	1645	1690	735	0.11	240
	4-12hrs (1)	0.21	1283	1101	431	0.00	20
	(2)	0.20	1143	1133	415	0.00	34
	(3)	0.24	1334	1356	522	0.00	42
	1-24hrs (1)	0.21	1236	1109	469	0.00	180
	(2)	0.20	1112	1130	400	0.00	53
	(3)	0.24	1340	1342	523	0.00	51

Table 6 :

 6 ShiftsWait (mins) Q phys (mins) Q phys max (mins) Q nurs (mins) Q nurs max (mins) Simulation results for the weekend schedules

	ref	125,23 ± 6,22	99,24 ± 5,6	977,07 ± 43,24	25,99 ± 1,5	422,26 ± 23,08
	8hrs (1)	79,94 ± 4,85	54,66 ± 4,21	861,81 ± 46,89	25,28 ± 1,75	465,12 ± 38,88
	(2)	87,28 ± 5,8	59,23 ± 5,13	910,35 ± 49,42	28,05 ± 1,87	499,15 ± 35,75
	(3)	83,82 ± 7,61	58,73 ± 6,75	864,21 ± 52,76	25,09 ± 1,94	412,3 ± 39,43
	4-12hrs (1)	62,43 ± 4,3	48,91 ± 4,08	832,22 ± 43,19	13,52 ± 1,01	315,84 ± 32,67
	(2)	63,13 ± 4,27	48,54 ± 3,94	836,35 ± 47,46	14,59 ± 0,99	374,4 ± 34,51
	(3)	64,46 ± 3,7	50,72 ± 3,38	842,91 ± 34,87	13,74 ± 0,85	330,66 ± 28,85
	1-24hrs (1) 64,97 ± 4,58	51,06 ± 4,35	871,16 ± 45,72	13,91 ± 0,9	324 ± 30,8
	(2)	64,55 ± 4,63	49,92 ± 4,16	855,5 ± 51,54	14,63 ± 1,02	369,36 ± 31,86
	(3)	64,27 ± 4,16	48,18 ± 3,69	831,45 ± 42,44	16,09 ± 1,09	381,73 ± 28,08

Table 7 :

 7 Simulation results for weekend schedules during an epidemic period

		Wait	Q phys	Q phys max	Q nurs	Q nurs max
	ref	242,99 ± 13	199,2 ± 12,06 1323,22 ± 34,88 43,79 ± 2,61 559,87 ± 23,74
	8hrs (1)	191,1 ± 13,32 148,81 ± 13,11 1268,17 ± 45,18 42,29 ± 3,38 651,89 ± 45,34
	(2)	191,32 ± 14,34 147,3 ± 13,53	1263,06 ± 44,4 44,02 ± 2,76 659,27 ± 45,17
	(3)	190,79 ± 13,6	149,63 ± 13	1264,16 ± 45,57 41,16 ± 2,75 633,62 ± 44,73
	4-12hrs(1) 148,74 ± 10,86 125,47 ± 10,41 1218,3 ± 46,26 23,27 ± 1,85 457,79 ± 43,62
	(2)	155,95 ± 12,04 133,56 ± 11,65 1258,86 ± 43,98 22,38 ± 1,43 494,64 ± 38,05
	(3)	150,31 ± 10,85 128,77 ± 10,55 1242,86 ± 42,17 21,54 ± 1,59 477,88 ± 42,1
	1-24hrs(1) 155,76 ± 13,59 132,37 ± 13,22 1211,44 ± 49,83 23,39 ± 1,69 482,04 ± 41,28
	(2)	146,73 ± 11,67 122,78 ± 11,02 1212,04 ± 49,64 23,94 ± 1,56 501,33 ± 30,19
	(3)	142,07 ± 11,26 116,78 ± 10,99 1180,36 ± 48,45 25,29 ± 1,65 525,05 ± 34,35

Table 8 :

 8 Simulation results for week schedules during an epidemic period ± 45,73 14,53 ± 1,07 367,98 ± 32,31 (2) 37,53 ± 2,84 22,7 ± 2,36 635,05 ± 46,81 14,83 ± 1,21 379,98 ± 34,39 (3) 38,48 ± 2,52 24,53 ± 2,27 654,31 ± 38,59 13,96 ± 0,97 384,82 ± 35,06

	Shifts	Wait	Q phys	Q phys max	Q nurs	Q nurs max
	ref	142,07 ± 11,26 116,78 ± 10,99 1180,36 ± 48,45 25,29 ± 1,65 525,05 ± 34,35
	8hrs (1)	53,14 ± 3,17	22,53 ± 1,57	564,15 ± 42,14 30,61 ± 2,24 490,83 ± 37,81
	(2)	51,62 ± 2,43	24,45 ± 1,45	580,12 ± 35,17 27,17 ± 1,65 502,22 ± 40,29
	(3)	54,54 ± 3,44	21,44 ± 1,64	528,09 ± 42,14	33,1 ± 2,56	601,4 ± 36,75
	4-12hrs(1)	37,5 ± 2,62	12,8 ± 0,92	498,01 ± 30,82	24,7 ± 2,27 541,19 ± 37,59
	(2)	35,11 ± 2,19	11,41 ± 0,75	417,48 ± 30,38	23,7 ± 1,82 524,46 ± 35,12
	(3)	40,63 ± 2,4	13,58 ± 0,86	510,86 ± 28,89	27,05 ± 2	598,06 ± 36,17
	1-24hrs(1)	35,22 ± 1,95	11,94 ± 0,85	454,38 ± 30,59 23,27 ± 1,61 526,38 ± 33,41
	(2)	35,39 ± 2,13	11,22 ± 0,73	414,83 ± 31,08 24,18 ± 1,77 549,97 ± 37,27
	(3)	40,91 ± 2,22	13,32 ± 0,8	499,48 ± 26,06 27,59 ± 1,88 602,06 ± 32,71
	Shifts	Wait	Q phys	Q phys max	Q nurs	Q nurs max
	ref	88,59 ± 4,7 62,59 ± 3,63 871,71 ± 45,88 25,99 ± 1,92 430,6 ± 30,93
	4-12hrs (1) 38,52 ± 2,96	24 ± 2,4	652,18

Table 9 :

 9 Simulation results for schedules spanning an entire week

	Shifts	Wait	Q phys	Q phys max	Q

nurs Q nurs max ref 140,58 ± 6,63 102,25 ± 5,09 1087,38 ± 42,46 38,33 ± 2,52 561,25 ± 43,66 4-12hrs(1) 69,31 ± 4,59 46,13 ± 3,74 941,59 ± 56,66 23,18 ± 1,9 504,82 ± 36,2 (2) 70,46 ± 4,61 43,86 ± 3,72 941,56 ± 49,76 26,6 ± 2,05 573,99 ± 38,44 (3) 71,09 ± 4,06 46,73 ± 3,32 974,81 ± 51,18 24,36 ± 2,12 508,22 ± 43,41

Table 10 :

 10 Simulation results for schedules spanning an entire week during an epidemic period

Emergency Department Queuing NetworkIn order to dynamically match the staff schedules and patient flow, we include in our system the dynamics of the patient flow through the ED. We present a queuing system with the key treatment steps and resources

acknowledgements

This research is partially supported the French National Research Agency "ANR" under grant number ANR-11-TECS-0010 of project HOST.


Mohan K Ramamurthy

Robert B Wilhelmson

Roy D Pea

Louis M Gomez

Daniel C Edelson

CoVis: A National Science Education Collaboratory

Introduction

Human interactions have largely been shaped by physical space. Except for a few technologies like the telephone. fax and perhaps electronic mail, the way we work. learn and play has been constrained by geography. This will change with the National Information Infrastructure (NII) as it creates a new "place" for human activities. This confluence of computing. communications, and networking technologies is expected to touch all aspects of American life. What will the NII mean to schools and learning communities, for science education and teacher development?

There is not one answer. Just as school buildings and the communities they house are shaped by factors like population density, local economy, and prevailing views of pedagogy. the NII will take shape in learning communities in diverse ways. No single research and development effort can be a model of all of these. The Learning Through Collaborative Visualization" or more simply, CoVis, is an NSF-NIE testbed that focuses on how to use applications of high performance computing and communications technologies (HPCC) to support science education reform. CoVis is centered at Northwestern University and UTUC' s Department of Atmospheric Sciences is a key participant in CoVis development. The CoVis community includes teachers and students, research scientists. museum-based informal science educators, and science education researchers, in a "distributed multimedia learning environment" (Pea & Gomez. 1992a).

The CoVis philosophy is grounded in a constructivist approach to science learning and teaching that emphasizes authentic, challenging projects as the nucleus of activities for "learning communities" which include students, teachers, scientists. and other participants. The goal is to create learning communities that more closely resemble the collaborative practice of science, which increasingly relies on HPCC technologies to create "collaboratories" [START_REF] Lederberg | Towards a National Collaboratory: Report of an Invitational Workshop at the Rockefeller University[END_REF]. In CoVis we have been using HPCC to support the formation and work activities of learning communities with media-rich communication and scientific visualization tools in a highly-interactive networked collaborative context (Pea & Gomez, 1992b;[START_REF] Pea | Distributed multimedia learning[END_REF]. CoVis has focused on three areas-project-enhanced science learning, collaboration, and scientific visualization-as means for transforming science education. In this process, we have worked with high school teachers in development activities to transform their classrooms from traditional teacher-centered classes to projectenhanced classes in which students learn about science through personal and group inquiries.

CoVis Network

To bring the practices of science to classrooms, the CoVis network extends today to Evanston Township High School (ETHS), New Trier High School (NTHS), Northwestern's School of Education and Social Policy, the Department of Atmospheric Sciences at University of Illinois, Urbana-Champaign (UIUC) and the Exploratorium Science Museum. The network enables high school students to join with other students at remote locations in collaborative groups. Students also use the network to communicate with university researchers and other scientific experts in teleapprenticing relations. Our experiences in constructing a collaboratory highlight system integration and new software design and implementation in classrooms, two challenges that will face all National Infrastructure for Education (NIE) testbeds and other NII efforts.

One major goal of the CoVis project is to combine prototype and off-the-shelf applications to create a reliable, networked environment that showcases HPCC technologies for K-12 learning communities.

Our key result is that the network is running and in daily use by approximately 300 people. mainly high school students. The challenge of this effort has been to take a collection of technologies, many only demonstrated or tested in small-scale lab and demo situations, and place them into daily service in demanding conditions. Our progress culminated in a stage-by-stage installation during Fall 1993 of the CoVis network testbed using public-switched ISDN services.

The network design and implementation is the result of intensive collaboration between Northwestern, Ameritech, and Bellcore. and it uses the Primary Rate Integrated Services Data Network (PRI-ISDN) as the transport layer for the CoVis network. In the immediate term, ISDN is the network service that offers the best combination of high bandwidth and ubiquity in a switched service. Bellcore predicts that by 1996 more than 70% of the nation's population will have access to ISDN service. A key benefit of ISDN for the CoVis Project is that its bandwidth can be broken up into call channels, which can be dedicated to different functions. We used this feature to create a two-function "overlay" network that gives student workstations access to both ethernet-based packet-switched data services and circuit-switched desktop audiolvideo conferencing. One group of 6 64 kbls ISDN channels is being used to create a virtual ethernet to each school running at 384 kbls. With compression, this network has a performance close to 1 Mbls. Other channels provide 384 kbls switched video teleconferencing for each of the CoVis workstations in the schools. Since ISDN is "public switched service," CoVis participants can, in principle, place calls to any other ISDN line in the country.

Within each school. the CoVis network supports synchronous and asynchronous communication. The CoVis Project supplied each school with five workstations per classroom plus one workstation at an alternative location for student access outside classes. All workstations are connected to an ethernet which is bridged via ISDN lines to the Internet. The CoVis communications and collaboration suite includes the Collaboratory Notebook (see below), email. file transfer. Usenet news (filtered for suitability), and access to the World Wide Web.

In addition to these applications. the communications suite includes screen sharing and video telecotflerencing.

CoVis participants may collaborate synchronously through screen sharing, in which one user can see exactly what appears on the screen of another user, even though at a distance, using the commercial application Timbuktu, produced by CoVis' industry partner Farallon Computing. Desktop video teleconferencing is another critical element of the CoVis testbed, and examinations of its utility for learning and teaching are a key part of our research. Students use the CruiserTM application. provided by Bellcore (Fish et al., 1993), to establish video teleconferencing calls. Cruiser allows students to place calls, both point-topoint and point-to-multi-point. to other CoVis addressees by selecting the name of the individual(s) from a directory. Cruiser is a client application of Touring Machine, the network management software developed by Bellcore (Bellcore Information Networking Research Laboratory, 1993) which manages the heterogeneous resources (e.g. cameras. microphones, monitors, switch ports, directory services) in the CoVis network. It is significant that CoVis Project needs and Ameritech (one of the baby Bell companies) interests drove the first integration by Bellcore of Touring Machine into an ISDN network. To our knowledge, CoVis is the first school-based application of ISDN desktop video conferencing.

CoVis Testbed Components

The CoVis testbed seeks to provide students with authentic scientific inquiry experiences across geographically dispersed sites. To succeed in this endeavor, it has been necessary to develop two new application environments:

(1) a groupware application to support collaborative student inquiry, and (2) tools to make scientific investigation techniques. specifically data visualization, accessible to high school students.

Collaboratorv Notebook.

The Collaboratory Notebook is a central and unique element of the CoVis environment, serving several roles for projectenhanced science learning (Edelson & ONeill, 1994). Briefly, the Notebook is groupware for scientific inquiry. It is a shared. hypermedia database built on top of an Oracle database connected to the Internet. The Notebook provides a place for students to record their activities, observations, and hypotheses as they work on projects. It provides a means for planning and tracking the progress of a project and for collaborators to share and comment upon each other's work. Within the Notebook, there is a small, fixed set of page and link types. These types provide a scaffold intended to assist students in structuring their open-ended inquiry process. For example, a page that records a set of visualization activities can be linked to questions raised during those activities. Those questions can, in turn, be linked to conjectures that address the questions, and to plans for investigating the questions. The goal of the Notebook is to provide students with a "scaffolding structure" for open-ended scientific inquiry, and a mechanism for collaborative work within or across schools.

Scientific Visualization Environments.

Today atmospheric and other scientists use data visualization tools and work with standard data sets routinely (e.g., [START_REF] Searight | ENVISION: A collaborative analysis and display system for large geophysical data sets[END_REF][START_REF] Wilhelmson | February: NCSA environments: The Collaborative Visualiz-PATHFINDER: Probing ATmospHeric Flows ation Project[END_REF][START_REF] Wilhelmson | February: NCSA environments: The Collaborative Visualiz-PATHFINDER: Probing ATmospHeric Flows ation Project[END_REF]. These tools and data sets are mainly useful to highly specialized members of technical communities (Gordin & Pea, in press). To allow students to work with the same data sets as scientists in similar ways, we have adapted the tools used by atmospheric scientists to be appropriate for high school students. (2) The Weather Visualizer (Fishman & D'Amico, 1994) is a tool for examining current weather conditions throughout the U.S. in the form of: satellite images in visible and infrared spectrums; customized weather maps displaying up to 14 different variables at five different altitudes for any region or city in the U.S. at a variety of zoom factors; "six-panel images" displaying temperature, pressure, wind speed. wind direction, dew point, and moisture convergence for the entire U.S.; and textual reports providing local conditions and local and state forecasts for all reporting stations. The Weather Visualizer is implemented as a front end to wxmap, a UNIX program developed at the University of Illinois. The data for the Weather Visualizer currently comes from our collaborator University of Illinois' Weather Machine, which. in turn, receives data from the National Weather Service's Family of Services DD+ feed and from GOES satellites [START_REF] Ramamurthy | A Networked Desktop Synoptic Laboratory[END_REF]. Through its gopher server for current weather images and information, the Weather Machine at UIUC is providing a valuable service to a community well beyond K-12, including researchers and educators nationwide. Over 100,000 requests for images and text are received per day in peak usage periods (Ramamurthy & Kemp, 1993; Ramamurthy et al., 1994; Ramarnurthy & Wilhelmson, 1993).

(3) The Greenhouse Effects Visualizer (Gordin, Pea, & Edelson, 1994) coordinates a collection of data sets that include the sun's incoming radiation (insolation), the amount reflected by the earth (albedo), the temperature on Earth's surface, and the earth's outgoing radiation. to allow students to examine the balance of incoming and outgoing radiation for the earth (Greenhouse effect.) Multimedia Modules In addition to providing realtime weather information, one of UIUC's main contributions to CoVis has been the development of an array of Internet-accessible multimedia instructional modules, consisting of text, color diagrams, movies, audio, and scanned images, that introduce and explain a variety of important concepts in atmospheric sciences as they arise in project inquiry. These multimedia instructional modules on various topics are being developed for use at the high school level, and are available from The Daily PlanetTM server, A Web server at UIUC. The modules are being tested at the two current CoVis schools in the Chicago area, and they are being revised and refined based on the feedback from them. Such multimedia-based instruction provides an alternative approach to learning, one in which the student, through interaction with the computer, becomes actively involved in the learning process.

The first set of modules that has been developed describes pressure and wind, various types of weather maps, satellite and radar images, and their use in weather analysis and forecasting [START_REF] Ramamurthy | Networked Multimedia Systems and Collaborative Visualization[END_REF], Sridhar et al., 1994). Through the use of colorful diagrams, video clips, text, and audio narration, a student becomes acquainted with topics like pressure, high and low pressure centers, and the balance of forces that generate winds. CoVis teachers at the two Chicago-area schools incorporate appropriate resources from these modules and our online weather databases into their courses. Other modules currently under development include a: (1) Cloud Catalog, (2) Guide to Atmospheric Optics, (3) Tornado Spotters Guide, and (4) Severe Storms Guide. The Tornado Spotters Guide, in addition to informative text and graphic inserts, contains clips of live tornado footage. The ultimate goal is to deliver extensive and broadly useful multimedia resources over the Internet. to support very diverse project inquiries. The multimedia modules are not only improving education at the K-12 level by making it more interactive through the use of advanced computer technologies, but are also providing a collection of curriculum resources for the whole Internet community.

Use of the CoVis Tool Suite

CoVis technology is in daily use by the entire community. A measure of use can be provided by a look at application uses: From Jan-Mar 1994, CoVis school-based users launched approximately 14,000 applications. The overwhelming proportion of use is of Internet tools (e.g. e-mail, Gopher) at 59%. with an additional 13% representing CoVis tool launches (e.g. Collaboratory Notebook, Climate Visualizer, Weather Visualizer), 13% graphic tools. 8% word processors or spreadsheets, and 7% utilities and games. The CoVis community has not had time to develop well-defined patterns of tool use. but early impressions are that CoVis applications are very popular and may increase in use percentage with familiarity. Video conferencing was introduced to students mid-January '94. We found considerable increases in HPCC uses for the student population from Fall 1993 to Spring 1994.

In its ongoing research. the CoVis Project studies and reports on the design, implementation and use of these network-based and media-rich learning environments for an audience of learning scientists, educators, educational telecommunications policy analysts. and corporations who are defining "new media" applications and services. CoVis is examining pedagogy and technology questions such as: How should next-generation information networking be implemented to spur science educational reform? What are proper educational support roles for networked multimedia technology, desktop videoconferencing, and other next-generation communication and computing technologies? What are the details of a pedagogy which will support diverse communities of practice? How can today's teachers transform their work-roles in new learning environments? What new cumculum materials and tools will be needed to support revitalized science curriculum that keeps pace with developments in the sciences and changes in the national information infrastructure?

New Developments in CoVis

To significantly scale the CoVis testbed over the next three years. we have developed strategies for realizing the innovative concepts and benefits of the CoVis broadband technology approach for a spectrum of schools with very different levels of technological readiness and infrastructures. We have defined three levels we describe in terms of a Technology Pyramid. Each level corresponds to a specific richness of technology infrastructure. At Level 1, the Pyramid's apex, will be a relatively small number of schools with the complete suite of CoVis technologies, including new applications and services to be developed. Moving down the pyramid, Levels 2 and 3 represent increasingly larger numbers of schools. requiring successively lower levels of technology infrastructure. Our goals are to include as many schools as possible to leverage use of the more common levels of installed technology in our testbed, and to define affordable entry levels for migration paths to higher levels of the pyramid. The levels are not rigid but serve as a realistic representation of the spectrum of schools that will come to join the NII. Schools will migrate across levels in both directions and combine different capabilities within a building. Including schools at these diverse technology levels will enable us to provide key data concerning the cost-effectiveness of the different levels for educational networking connectivity for science education reform outcomes.

At the top of the pyramid representing our Level 1 sites, we will intensively work with a few schools but increase their number and diversity from our current 2 suburban Chicago schools (involving 12 classes) to six total schools by 1996-97. These schools will include urban, suburban, and rural sites and will cross states. In six Level 1 schools, we will continue exploring high-end HPCC technological infusion and implementation for schools at the cutting-edge (below). The considerable diversity of new sites at this level will help us to understand the challenges and particular benefits of adding high-bandwidth connections to schools in different types of communities, since their technical suite will approximate the current CoVis school profile: broadband data connections to the Internet (384Kbls or better), and at least three desktop videoconference stations per school. Schools at Level 2 of the pyramid will have similar data networks to Level 1 schools except for desktop video conferencing and video server access. However, through ordinary phone lines and screensharing, Level 2 sites can participate in audio teleconferencing and will have access to all CoVis software and materials via the Internet. Schools at Level 3 will have low-bandwidth connections to the Internet, via dialup, and will represent the typical network connection paradigm for U.S. schools today. Through SLIP or PPP protocols, they may access CoVis software and materials on the Internet, but will not have any form of synchronous conferencing. To support these Level 3 schools, we will be developing and distributing video tapes and CD-ROMs to help them take advantage of the materials/pedagogy we are developing throughout the CoVis Collaboratory testbed.

In adding new functionalities to the Collaboratory over the next three years, as described below, we seek to build on the existing CoVis network architecture in order to extend the range of ways that students, teachers, and other members of the community can communicate and collaborate with each other. In building and extending the CoVis technology infrastructure, our challenge continues to be taking innovations that have been used in limited ways in research tests and demonstrations and placing them into service so that they can reliably serve the needs of a demanding population.

(1) $ 5 .

In the early years of the CoVis Project we have developed an architecture for collaboration that combines the Collaboratory Notebook, speciallydeveloped software for collaborative inquiry. video conferencing, remote screen sharing, and a standard package of Internet tools. In the next several years, we will continue development of the Notebook as we extend from a single community of 12 classes to multiple communities of thousands of classes. This will involve, for example, the development of "libraries" of notebooks that will allow students to locate relevant prior work by other students through easy-to-use search mechanisms. In addition, it will be necessary to provide easy administration of the Notebook to school personnel. This goal will be achieved in collaboration with the National School Network Testbed Project at Bolt, Beranek & Newman (BBN) in Cambridge, Massachusetts. We will migrate the management of user accounts for the Collaboratory Notebook to BBN's Copemicus server, which already supports many important administration functions for schools.

(2) Enhanced Video Conferencing Services. Today our video conferencing network is used for point-topoint video calls. As part of our new work on the CoVis testbed. we will have multi-point video conference calls available. This ability to involve participants in a variety of locations in a single call lets us extend how the video network is being used to include two telepresence experiments.

(3) Video server. The CoVis video server will allow users to both view and record digital video in real time. Unlike current networked applications such as Gopher and Mosaic, the users will not have to download compressed video to the local workstation before viewing it. Instead, the video will be streamed live between the video server and the user's workstation, in either playback or recording modes. The video server will be supported by StarWorksm, a video applications server produced by industry leader Starlight Networks (Mountain View, CA).

(4) Geosciences Server. A multi-institutional design will be developed and implemented for a World-Wide Web Server for Geosciences Education to include tools, datasets, and diverse multimedia materials for use in K-12 science education involving the earth, atmosphere, and environment. Initial contributors to design and materials available over the server nodes will include Northwestern. UIUC, U. Michigan, U. Colorado, Exploratorium Museum, and select schools. Materials will include: datasets, editorially-reviewed student projects in Collaboratory Notebooks, directory services for participants, and a comprehensive indexing scheme. We will seek to assure compatibility of testbed science curriculum resources and activities with the leading state frameworks and national science education standards. This same server will provide the major dissemination vehicle for the project, and will include publications, papers, reports, images, animations, and brief QuickTirne video clips to share its results on an ongoing basis with a broad community. For Level 1 schools that have video conferencing capability, the Geosciences Server will provide an interface to materials on the video server.

The ultimate goal of the server is to develop a new paradigm for Environmental Sciences education. Our consortium will develop an on-line weather laboratory, to provide interactive access to a wide range of weather information. An important aspect of the server is that it will provide access to observations, local forecasts, watches and warnings, satellite images and numerical model forecasts from any computer that is connected to the Internet. Not only will any computer on the Internet have access to the server, but we will also structure the information such that others who create their own servers can follow our model in setting up servers that point to ours.

The educational and informational material on the server will initially be focused on atmospheric sciences but will grow to include a broad range of earth science topics. One section of the server will be devoted to weather. The access to up-to-the-hour weather data that is currently available through CoVis Weather Visualizer will be augmented with historical data that covers recent years at dady or twice daily intervals and that covers major weather events during those years at hourly intervals. A second section of the server will be devoted to climate. An example of the resources to be available there is information drawn from the Midwestern Climate Atlas, which was recently prepared by the Midwest Climate Center at the Illinois State Water Survey. The statistics in the atlas include temperature, rainfall. snowfall, and extremes and probabilities of occurrence. In addition to these primary climatic elements, the atlas includes a variety of other derived variables such as heating; cooling; and growing degree days, growing season length, and frost dates. Most of the development of the server and the resources on it will be conducted at UIUC with close consultation on pedagogical matters from team members at Northwestern and the Exploratorium.

The server will also contain Exploratorium-produced Video Answers to FAQs (frequently asked questions). These will be produced multimedia responses to questions on geosciences created using Exploratorium resources (exhibits, materials, media) that are distributed on demand from Exploratorium World Wide Web and the CoVis Geosciences Server. These Video FAQ's will also be available for realtime viewing through the CoVis video server. This material will be developed based on participation in the Collaboratory activities and from responses from teachers and students. In addition, a video introduction to the museum will be available for the users to help them understand what they can get from the Exploratorium and to give a personal introduction to the museum and staff.

To increase the level of interaction between atmospheric scientists and CoVis students, UIUC will be conducting daily weather briefings via the Cruiser videoconferencing system to CoVis sites. These weather briefings will be tailored to the CoVis community, and offered by UIUC faculty and students. During these video weather briefings, we will illustrate, through interpretation and analysis of weather charts, satellite and radar animations, and forecast products, key concepts that will enable a student to conceptualize the structure and dynamics of the atmosphere. Students may also participate in discussions of weather processes as depicted by weather maps, and learn techniques of forecasting weather. The depiction of atmospheric kinematic and dynamic processes on weather charts will be emphasized. We plan to record and digitize some of the weather briefings and eventually make them available to the CoVis sites and explore the use of video server technologies in instruction and collaboration. Such video servers are currently under development at several places, including NCSA at University of Illinois. Urbana-Champaign.

Concluding Remarks

CoVis envisions widespread use of learning environments where next-generation communication and computing technologies enable students, teachers, scientists and other professionals to work together in networked communities focused on science education. Todav CoVis is a small-scale working model of this visiin in two high schools. in the next phase of the CoVis Project, we are poised to provide some of the key national research and development required to inform large-scale and costeffective implementations of reform-oriented science educational networking. There are over 18,000 high schools and 12.000 middleljunior high schools in the nation. We will be developing and researching the CoVis testbed as a National Science Education Collaboratory, by systematically addressing the scaling issues inherent in achieving goals of critical mass of participation and in diversity of schools, teachers. students and other participants in such an enterprise. In addition, CoVis is expected to grow from a venue for addressing research and development questions to an experimental facility for informing governments and businesses about how to do the large-scale implementation of HPCC technologies within the NII in a cost-effective manner that meets the reform needs of school communities.

  To date, CoVis has developed two such visualization environments. The Climate Visualizer and The Weather Visualizer, and is developing a third, The Greenhous Effects Visualizer. All three visualization environments are tightly integrated with the Collaboratory Notebook. (1) T h e Climate Visualizer allows students to construct scientific visualizations to explore global climate patterns (Gordin, Polman & Pea. in press). It contains 25 years of twice daily weather values (temperature, pressure, and wind) for most of the northern hemisphere. In the Climate Visualizer, temperature is encoded as a raster color image, altitude as contours, and wind as arrows (or vectors), with an optional overlay showing continents. Students can interactively sample values in a visualization by selecting locations with a mouse and can view trends across time by subtracting one image from another. For example. seasonal differences can be seen by subtracting January temperature from July. Such a visualization might highlight the differing properties of land and water in absorbing heat. The Climate Visualizer is s front-end to Spyglass Transform, a commercial visualization package. and uses a data set available on CD-ROM from the National Meteorological Center's Grid Point Data Set.

Acknowledgements

This paper will appear in the Proceedings of the Fourth Annual American Meteorological Society Education Symposium, January 1995, Dallas, TX. We are grateful for research support of the CoVis Project by the National Science Foundation Grants #MDR-9253462 and #RED-9454729, by Apple Computer, Inc., External Research. by Sun Microsystems, by our major industrial partners Ameritech and Bellcore, and by contributions from Aldus, Farallon, ScienceKit, Sony, and Spyglass. We would also like to thank our colleagues from the CoVis Project and community of users for extended discussions, and continual useful feedback on design, rationale, and pedagogical issues. For further information, seeThe CoVis World Wide Web Server (url: http: 1lwww.covis.nwu.edu).