Appointment scheduling algorithm considering routine and urgent patients

This paper derives a solution approach to solve the outpatient appointment schedule problem for given numbers of routine and urgent patients considering a no-show probability to minimize the weighted sum of average patient wait time, physician idle time and overtime. An exact deterministic service time method is proposed to find the optimal schedule. An exponentially distributed service time property is presented to show that the objective function for routine and urgent patients is not multimodular, and consequently a local search algorithm based on multimodulary does not guarantee global optimality. Thus, a heuristic algorithm based on two kinds of shifting policies (HE-TKS) is developed to solve the appointment schedule, which gives a local optimal solution as an upper bound for the optimal schedule. Numerical experiments are conducted to illustrate how the critical factors affect service efficiency of the clinic in practice. It reveals that lower no-show probability, smaller interval lengths, shorter service times, and more urgent patients will benefit both patients and clinics.     

一种远程医疗系统中多专家会诊的调度问题求解*

为解决病人在医疗会诊中多重复杂的问题,提出了用群体决策的方法调度多专家为病人进行远程医疗会诊。该算法分析了多专家会诊调度的特点,把调度问题转换为图论问题,建立了数学模型,采用贪心算法求得目标函数值,进行迭代扫描,逐步求出最优的多专家会诊调度结果。实验结果表明,该算法很好地解决了用较少等待时间来实现较多集体会诊的问题,也很好地解决了每次集体会诊的专家成员数最优问题,为多专家调度会诊问题提供了一个可行性的解。     

A new procedure to estimate waiting time in GI/G/2 system by server observation

Most GI/G/2 queueing formulae need the variance of inter-arrival time, which is in many cases more difficult to estimate than the other values used in the formulae such as the mean of inter-arrival time, mean of service time and variance of service time. This paper presents a new GI/G/2 queueing formula which uses a slightly different set of data easier to obtain than the variance of inter-arrival time. The key variables are the numbers of system busy periods and system idle periods. Also, it is shown, by simulation, that the waiting time estimation error from the new formula is far less than other popular queueing formulae which use the first two moments of service time and inter-arrival time over a wide range of coefficient of variation.Scope and purposeWaiting is very common in our daily life, and the estimation is sometimes very important for the design of service and manufacturing systems. If the number of barbers at a barber's shop is too small, customers frequently wait for the service too long. If the number of machines in a manufacturing shop is too small, the production lead time from order entry to product delivery can be very long.The waiting time is closely related not only to the average service requirement but also to the variability of it. If customers require service at the same time, the average waiting time of the customers will be longer than the average waiting time with even requests. Traditionally, the variance of inter-arrival time has been used to represent the variability; however, estimation of the variance needs observation of customer arrivals, which often needs much effort. This paper presents another procedure to estimate the waiting time. This procedure does not need the observation of customers. The estimation of waiting time for bank teller machines can be a good application example of this new procedure because the machines do not have the arrival data of the customers. The procedure presented here is for a two parallel server case.     

Using tablets in medical consultations: Single loop and double loop learning processes

ObjectiveThis paper investigates the influence of using tablet in waiting rooms and medical examinations on how physicians give information and how patients learn. It further assesses the factors that impact patient satisfaction.MethodsPatients and physicians in a primary care clinic were given a tablet device to search for health information in the waiting room, and when interacting with the physician, while physicians used the tablet device to share information with patients during the medical consultation. 82 patients completed a ‘pre’ survey on using tablets to search for health related information and a ‘post’ survey after their visit. Structural equation modeling was employed to analyze patient's perceptions.ResultsTablet use during consultation has a negative effect on patients' perceptions of physician information giving, but using the tablet in the waiting room has a positive impact on patient learning, perceptions of physicians' information giving and patient satisfaction.ConclusionsThis study indicates the importance of tablet use in ensuring information giving and patient learning. It further highlights the potential for tablets to promote single-loop learning in the medical encounter by better preparing patients for the physician's information giving. Tablets also enable double-loop learning, which leads to greater patient satisfaction.     

A study on tolerable waiting time: how long are Web users willing to wait?

Web users often face a long waiting time for downloading Web pages. Although various technologies and techniques have been implemented to alleviate the situation and to comfort the impatient users, little research has been done to assess what constitutes an acceptable and tolerable waiting time for Web users. This research reviews the literature on computer response time and users' waiting time for download of Web pages, and assesses Web users' tolerable waiting time in information retrieval. It addresses the following questions through an experimental study: What is the effect of feedback on users' tolerable waiting time? How long are users willing to wait for a Web page to be downloaded before abandoning it? The results from this study suggest that the presence of feedback prolongs Web users' tolerable waiting time and the tolerable waiting time for information retrieval is approximately 2 s.     

A performance comparison of locking methods with limited wait depth

A number of recent studies have proposed lock conflict resolution methods to improve the performance of standard locking, i.e., strict two-phase locking with the general waiting method. This paper is primarily concerned with the performance of wait depth limited methods with respect to each other and some other methods. The methods considered include the general waiting, wound-wait, and no-waiting methods, symmetric and asymmetric versions of cautious waiting and running priority methods, the wait depth limited (WDL) method, and a modified version of it. In spite of the availability of analytic solutions for most of wait depth limited methods, for reasons given in-the paper, the performance comparison is based on simulation results. The contributions of this study are as follows: 1) modeling assumptions, i.e., a careful definition of transaction restart options; 2) new results concerning the relative performance of wait depth limited methods, which show that a) the running priority method outperforms cautious waiting and may even outperform the WDL method in a system with limited hardware resource, b) WDL outperforms other methods in high lock contention, high capacity systems, and c) modified WDL has a performance comparable to WDL, but incurs less overhead in selecting the abort victim; and 3) contrary to common belief, Tay's Effective Database Size Paradigm for dealing with shared and exclusive locks and/or skewed database accesses in standard locking is applicable to some wait depth limited methods and provides acceptably accurate approximations in others-as long as locking modes for restarted transactions are not resampled     

基于出租车轨迹数据挖掘的乘客候车时间预测

随着城市人口的增长与交通问题的加剧,出行也变得越来越困难.出租车是重要的公共交通工具;对于乘客来说,了解等候出租车需要花费的时间有助于他们安排行程与选择最优的等候地点.针对这个问题,使用出租车轨迹的历史数据,预测乘客在某时某地等候出租车需要的时间.算法使用参数与非参数模型,通过对空车到达过程的建模,预测单个乘客等候出租车需要的时间.使用大规模的杭州出租车数据,结合仿真来验证预测算法.实验评估结果显示,参数模型对等候时间预测的平均误差约为4.5分钟,并且参数模型预测误差小于5 分钟的概率约为83%.     

The effect of visual feedback types on the wait indicator interface of a mobile application

This study examines the essential effects of visual feedback on users’ perceptions of time and on their evaluations of waiting time for a mobile application user interface. The two variables adopted in this experiment are wait indicator visual feedback and waiting time. Three types of visual feedback were used: bar indicator, pie indicator, and cartoon indicator. Three waiting times were used: 2 s, 5 s, and 10 s. This study was conducted based on the attentional-gate model of Zakay and Block to help investigate user time perceptions. The experiment of this study was a 3 × 3 mixed factorial design to measure the impact of the research variables on the users’ perceptions of waiting time, wait evaluations, and preferences. Results showed that the users’ time perceptions and wait evaluations were affected by the feedback types and waiting times, and the results are consistent with Vierordt's law and the attentional-gate model. Furthermore, there was a positive impact on the participants' preferences when they perceived a shorter waiting time. The cartoon type feedback can help reduce the perception of waiting time, but it does not necessarily improve user experience regarding short waiting time.     

Linearizable counting networks

Summary.  The counting problem requires n asynchronous processes to assign themselves successive values. A solution is linearizable if the order of the values assigned reflects the real-time order in which they were requested. Linearizable counting lies at the heart of concurrent time-stamp generation, as well as concurrent implementations of shared counters, FIFO buffers, and similar data structures. We consider solutions to the linearizable counting problem in a multiprocessor architecture in which processes communicate by applying read-modify-write operations to a shared memory. Linearizable counting algorithms can be judged by three criteria: the memory contention produced, whether processes are required to wait for one another, and how long it takes a process to choose a value (the latency). A solution is ideal if it has low contention, low latency, and it eschews waiting. The conventional software solution, where processes synchronize at a single variable, avoids waiting and has low latency, but has high contention. In this paper we give two new constructions based on counting networks, one with low latency and low contention, but that requires processes to wait for one another, and one with low contention and no waiting, but that has high latency. Finally, we prove that these trade-offs are inescapable: an ideal linearizable counting algorithm is impossible. Since ideal non-linearizable counting algorithms exist, these results establish a substantial complexity gap between linearizable and non-linearizable counting. Received: November 1991 / Accepted: July 1995     

Performance evaluation of candidate appointment schedules using clearing functions

This study is concerned with the problem of reducing the waiting times of outpatients. Both scheduled patients and walk-ins are included among the outpatients to reflect the typical medical environment in Japan. The consultation time of a hospital is divided into several blocks, and each scheduled patient is given the start time of a block as his or her scheduled time of the consultation as an appointment. It is assumed that all scheduled patients arrive at the hospital at their scheduled times, while walk-ins arrive randomly. A set of candidate appointment schedules is given, and the process of selecting promising schedules in terms of average waiting times is the focus of the work. To support the selection process without conducting a conventional simulation, the notion of a clearing function is adopted to evaluate each candidate schedule. The clearing function of a system gives the expected output or throughput of the system under varying levels of workload of the system. Although it is necessary to conduct exploratory experiments in advance to obtain the clearing function, the expected waiting time can be estimated by simple calculations with the aid of the clearing function. The average waiting times of four schedules in two scenarios are calculated and compared with those obtained from conventional simulations. It is revealed that the proposed procedure based on the clearing function gives acceptable estimated average values.     

Applying simulation and DEA to improve performance of emergency department in a Jordanian hospital

The Emergency Department (ED) is considered the most critical department in Jordanian hospitals. Crowdedness and long waiting times of patients in the ED are the most common harmonies problems that hospitals are suffering from. Thus, this study aims at reducing the average waiting time of the patient in the ED, improving the nurses’ utilization, and increasing the number of served patients. A cellular service system is proposed and utilized for developing ten nurse assignment configurations. Simulation is run for a one month period (672 h) each with 10 replicates to evaluate the performance measures for each configuration. The best scenario is then determined using aggressive formulation in Data Envelopment Analysis (DEA). The results showed that the best scenario depends on work load sharing assignments, which results in reducing patient’s average waiting time from 195 to 183 min, increasing the number of patients served from 8853to 8934 patients, and improving the nurses’ utilization from 52% to 62%. In conclusion, nurses’ flexibility in cellular service systems shall provide a great assistance to decision makers in hospitals when improving the performance of ED.     

Analysis of two-tier public service systems under a government subsidy policy

Some public service systems such as healthcare systems consist of both free public service provider with a long wait time and paid private service provider with a short wait time. Such service systems are often called a two-tier service system. In general, more customers will choose the free service provider (SP). To reduce the congestion in the free system, the government may encourage customers to use the pay system by offering them a subsidy. This paper studies whether such a subsidy can reduce the free system’s waiting time and improves the social welfare. While the objective of the free system is to maximize its own total customers’ utility, the objective of the pay system is to maximize its profit. We develop a mixed duopoly game to analyze the Nash equilibrium for the competition between the free and toll systems. Two scenarios with unregulated and regulated prices are considered. When the pay system price is unregulated (the private SP can set prices freely), we find that if customers are less sensitive to the service delay, the subsidy policy can effectively reduce the expected waiting time for the free system and increase the customer utility surplus of the entire two-tier system. However, if customers are more sensitive to the service delay, the subsidy policy may have the opposite effect. When the pay system price is regulated (the price determined by government), the subsidy policy can effectively reduce the expected waiting time for the free system and improve the social welfare of the two-tier system. And there exists an optimal regulated price to maximize the social welfare of the entire public service system.     

A hybrid simulation and genetic algorithm approach to determine the optimal scheduling templates for open access clinics admitting walk-in patients

With the pressing demand for improving patient accessibility, the traditional scheduling system may not be effective for mitigating the adverse effects caused by no-shows, appointment cancellations and late arrivals. For this reason, open access scheduling, which specifies that a portion of clinic appointment slots be reserved for short-notice appointments, was proposed and adopted in recent years. In literature, many studies have developed a variety of approaches and models to optimize the open access scheduling systems, while few considers the inclusion of walk-in patients and the optimal allocation of reserved slots on the scheduling template under the open access configuration. In this paper, we propose a Discrete Event Simulation and Genetic Algorithm (DES–GA) approach to find the heuristic optimal scheduling template under the clinic setting that allows both open access and walk-in patients. The solution can provide scheduling templates consisting of not only the optimal number of reservations for open access appointments and walk-ins, but also the optimized allocation of these reserved slots, by minimizing the average cost per admission of open access or walk-in patient. In this approach, the cost is measured by the weighted summation of patient waiting time, provider idle time, and provider overtime. A case study and sensitivity analysis are conducted to show how the heuristic optimal scheduling template generated from the proposed approach could vary under different scenarios. This also illustrates the viability of our model. The results show that the heuristic optimal scheduling templates are significantly affected by the patient attendance rate, level of demands of same-day appointment and walk-in admissions, as well as the cost coefficients associated with patient waiting time, provider idle time and provider overtime.     

跨表单数据的处理

在实际的复杂的应用中,通常会遇到将几个页面作为输入来等候一同处理.例如可能因为用户创建的页面太长而将其分为两个页面,在处理数据时候就必须区分是那个页面提交的数据.本文通过具体实例,使用设置session的办法来解决这一实际问题.     

A Model for the Delay Management Problem based on Mixed-Integer-Programming

Dealing with delayed vehicles is a necessary issue in the dispositive work of a public transportation company. If a vehicle arrives at some station with a delay, it has to be decided if the connecting vehicles should wait for changing passengers or if they should depart in time. A possible objective function is to minimize the sum of all delays over all customers using the transportation network. In this paper the delay management problem is formulated as a mixed integer linear program, and solution approaches based on this formulation are indicated.     

Exploring wait tolerance in effective batching for video-on-demand scheduling

In a video-on-demand (VOD) environment, batching requests for the same video to share a common video stream can lead to significant improvement in throughput. Using the wait tolerance characteristic that is commonly observed in viewers behavior, we introduce a new paradigm for scheduling in VOD systems. We propose and analyze two classes of scheduling schemes: the Max_Batch and Min_Idle schemes that provide two alternative ways for using a given stream capacity for effective batching. In making a video selection, the proposed schemes take into consideration the next stream completion time, as well as the viewer wait tolerance. We compared the proposed schemes with the two previously studied schemes: (1) first-come-first-served (FCFS) that schedules the video with the longest waiting request and (2) the maximum queue length (MQL) scheme that selects the video with the maximum number of waiting requests. We show through simulations that the proposed schemes substantially outperform FCFS and MQL in reducing the viewer turn-away probability, while maintaining a small average response time. In terms of system resources, we show that, by exploiting the viewers wait tolerance, the proposed schemes can significantly reduce the server capacity required for achieving a given level of throughput and turn-away probability as compared to the FCFS and MQL. Furthermore, our study shows that an aggressive use of the viewer wait tolerance for batching may not yield the best strategy, and that other factors, such as the resulting response time, fairness, and loss of viewers, should be taken into account.     

一种基于MPLS网络的快速故障恢复算法

现有的MPLS故障恢复方案存在不同的性能问题:Makam方案需要提前建立备份路径,浪费了大量网络资源;简单动态方案动态建立备份路径,资源利用率高,但是需要等待路由表收敛,恢复时间长,造成大量丢包.针对这些不足,提出了一种基于MPLS网络的快速故障恢复算法MBFR.MBFR算法在故障发生以后建立备份路径,但是不需要等待路由表收敛,只需根据PIL中信源树和当前故障信息就可以快速计算出备份路径,既不浪费网络资源,又缩小了恢复时间.仿真实验结果验证了MBFR算法的优越性.     

The Effects of the Service Environment on Perceived Waiting Time and Emotions

Because customers’ experience of waiting for service may negatively affect their behavioral approach toward the service organization, improving the service environment may also improve their waiting experience. This study examined the different effects of environmental elements on the perceived waiting time route and the emotional route. We surveyed 326 customers of a leading fast‐food chain restaurant in Taiwan during rush hour. We found that the emotional route is a stronger predictor of customer approach behavior than the perceived waiting time route. Moreover, the explained wait and perceived crowding directly affect both the perceived waiting time route and the emotional route. The effect of the design factor on the customer behavior approach is significant in the emotional route, but it is not significant in the perceived waiting route. In addition, perceived crowding has the strongest effect on the perceived waiting time route, and the explained wait has the strongest effect on the emotional route.     

A queuing model for CPU functional unit and issue queue configuration

In a superscalar processor, instructions of various types flow through an execution pipeline, traversing hardware resources which are mostly shared among many different instruction types. A notable exception to shared pipeline resources is the collection of functional units, the hardware that performs specific computations. In a trade-off of cost versus performance, a pipeline designer must decide how many of each type of functional unit to place in a processor’s pipeline. In this paper, we model a superscalar processor’s issue queue and functional units as a novel queuing network. We treat the issue queue as a finite-sized waiting area and the functional units as servers. In addition to common queuing problems, customers of the network share the queue but wait for specific servers to become ready (e.g., addition instructions wait for adders). Furthermore, the customers in this queue are not necessary ready for service, since instructions may be waiting for operands. In this paper we model a novel queuing network that provides a solution to the expected queue length of each type of instruction. This network and its solution can also be generalized to other problems, notably other resource-allocation issues that arise in superscalar pipelines.     

Effective message synchronization methods for multiplayer online games with maps

A solution for the message synchronization problem of the client-server based game system is to wait for a certain period of time (waiting period) until the server processes the messages from clients. However, identifying a suitable waiting period proves challenging. In this paper, we develop two methods to determine the waiting period using the probability of interaction among participants and ranking of the delay among participants. Our methods take advantage of the property of games with geographical mapping, where each participant usually interacts with other participants only in the immediate surroundings. Simulation is performed for the evaluation of the methods and the shows that the proposed methods produce better results with lower average unfair ratio while keeping the same responsiveness compared to the method with prefixed waiting period.