اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNon-indexability of the Stochastic Appointment Scheduling Problem
191
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Consider a set of jobs with independent random service times to be scheduled on a single machine. The jobs can be surgeries in an operating room, patients appointments in outpatient clinics, etc. The challenge is to determine the optimal sequence and appointment times of jobs to minimize some function of the server idle time and service start-time delay. We introduce a generalized objective function of delay and idle time, and consider $l_1$-type and $l_2$-type cost functions as special cases of interest. Determining an index-based policy for the optimal sequence in which to schedule jobs has been an open problem for many years. For example, it was conjectured that `least variance first (LVF) policy is optimal for the $l_1$-type objective. This is known to be true for the case of two jobs with specific distributions. A key result in this paper is that the optimal sequencing problem is non-indexable, i.e., neither the variance, nor any other such index can be used to determine the optimal sequence in which to schedule jobs for $l_1$ and $l_2$-type objectives. We then show that given a sequence in which to schedule the jobs, sample average approximation yields a solution which is statistically consistent.
قيم البحث
اقرأ أيضاً
We consider the problem of scheduling appointments for a finite customer population to a service facility with customer no-shows, to minimize the sum of customer waiting time and server overtime costs. Since appointments need to be scheduled ahead of
time we refer to this problem as an optimization problem rather than a dynamic control one. We study this optimization problem in fluid and diffusion scales and identify asymptotically optimal schedules in both scales. In fluid scale, we show that it is optimal to schedule appointments so that the system is in critical load; thus heavy-traffic conditions are obtained as a result of optimization rather than as an assumption. In diffusion scale, we solve this optimization problem in the large horizon limit. Our explicit stationary solution of the corresponding Brownian Optimization Problem translates the customer-delay versus server-overtime tradeoff to a tradeoff between the state of a reflected Brownian motion in the half-line and its local time at zero. Motivated by work on competitive ratios, we also consider a reference model in which an oracle provides the decision maker with the complete randomness information. The difference between the values of the scheduling problem for the two models, to which we refer as the stochasticity gap (SG), quantifies the degree to which it is harder to design a schedule under uncertainty than when the stochastic primitives (i.e., the no-shows and service times) are known in advance. In the fluid scale, the SG converges to zero, but in the diffusion scale it converges to a positive constant that we compute.
In this paper, we develop a new formulation of changeover constraints for mixed integer programming problem (MIP) that emerges in solving a short-term production scheduling problem. The new model requires fewer constraints than the original formulati
on and this often leads to shorter computation time of a MIP solver. Besides that, the new formulation is more flexible if the time windows for changeover tasks are given.
This paper investigates optimal consumption in the stochastic Ramsey problem with the Cobb-Douglas production function. Contrary to prior studies, we allow for general consumption processes, without any a priori boundedness constraint. A non-standard
stochastic differential equation, with neither Lipschitz continuity nor linear growth, specifies the dynamics of the controlled state process. A mixture of probabilistic arguments are used to construct the state process, and establish its non-explosiveness and strict positivity. This leads to the optimality of a feedback consumption process, defined in terms of the value function and the state process. Based on additional viscosity solutions techniques, we characterize the value function as the unique classical solution to a nonlinear elliptic equation, among an appropriate class of functions. This characterization involves a condition on the limiting behavior of the value function at the origin, which is the key to dealing with unbounded consumptions. Finally, relaxing the boundedness constraint is shown to increase, strictly, the expected utility at all wealth levels.
In this paper we study a Markovian two-dimensional bounded-variation stochastic control problem whose state process consists of a diffusive mean-reverting component and of a purely controlled one. The main problems characteristic lies in the interact
ion of the two components of the state process: the mean-reversion level of the diffusive component is an affine function of the current value of the purely controlled one. By relying on a combination of techniques from viscosity theory and free-boundary analysis, we provide the structure of the value function and we show that it satisfies a second-order smooth-fit principle. Such a regularity is then exploited in order to determine a system of functional equations solved by the two monotone continuous curves (free boundaries) that split the control problems state space in three connected regions. Further properties of the free boundaries are also obtained.
In this paper, we aim to solve the high dimensional stochastic optimal control problem from the view of the stochastic maximum principle via deep learning. By introducing the extended Hamiltonian system which is essentially an FBSDE with a maximum co
ndition, we reformulate the original control problem as a new one. Three algorithms are proposed to solve the new control problem. Numerical results for different examples demonstrate the effectiveness of our proposed algorithms, especially in high dimensional cases. And an important application of this method is to calculate the sub-linear expectations, which correspond to a kind of fully nonlinear PDEs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
