排序方式: 共有42条查询结果,搜索用时 15 毫秒
1.
Flos Spieksma 《Annals of Operations Research》1991,28(1):273-295
Recently Dekker and Hordijk [3,4] introduced conditions for the existence of deterministic Blackwell optimal policies in denumerable Markov decision chains with unbounded rewards. These conditions include- uniform geometric recurrence.The-uniform geometric recurrence property also implies the existence of average optimal policies, a solution to the average optimality equation with explicit formula's and convergence of the value iteration algorithm for average rewards. For this reason, the verification of-uniform geometric convergence is also useful in cases where average and-discounted rewards are considered.On the other hand,-uniform geometric recurrence is a heavy condition on the Markov decision chain structure for negative dynamic programming problems. The verification of-uniform geometric recurrence for the Markov chain induced by some deterministic policy together with results by Sennott [14] yields the existence of a deterministic policy that minimizes the expected average cost for non-negative immediate cost functions.In this paper-uniform geometric recurrence will be proved for two queueing models: theK competing queues and the two centre open Jackson network with control of the service rates.The research of the author is supported by the Netherlands Organization for Scientific Research N.W.O. 相似文献
2.
3.
4.
We generalize the concept of a break by considering pairs of arbitrary rounds. We show that a set of home-away patterns minimizing the number of generalized breaks cannot be found in polynomial time, unless P=NP. When all teams have the same break set, the decision version becomes easy; optimizing remains NP-hard. 相似文献
5.
Arie Hordijk Olaf Passchier Floske Spieksma 《Mathematical Methods of Operations Research》1997,45(2):281-301
In this paper we will consider two-person zero-sum games and derive a general approach for solving them. We apply this approach to a queueing problem. In section 1 we will introduce the model and formulate the Key-theorem. In section 2 we develop the theory that we will use in section 3 to prove the Key-theorem. This includes a general and useful result in Lemma 2.1 on the sufficiency of stationary policies. 相似文献
6.
7.
Frits C. R. Spieksma Gerhard J. Woeginger Zhongliang Yu 《Annals of Operations Research》1995,57(1):251-264
We investigate the problem of Scheduling with Safety Distances (SSD) that consists in scheduling jobs on two parallel machines without machine idle time. Every job is already assigned to its machine, and we just have to specify an ordering of the jobs for each machine. The goal is to find orderings of the jobs such that the minimum time elapsed between any two job completion times is maximized. We prove that this problem is NP-hard in general and give polynomial time algorithms for special cases. These results combined establish a sharp borderline between NP-complete and polynomial solvable versions of the problem SSD.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, PR China. 相似文献
8.
Dries Goossens Sergey Polyakovskiy Frits C. R. Spieksma Gerhard J. Woeginger 《Optimization Letters》2010,4(1):7-16
We discuss two special cases of the three-dimensional bottleneck assignment problem where a certain underlying cost function satisfies the triangle inequality. We present polynomial time 2-approximation algorithms for the broadest class of these special cases, and we prove that (unless P = NP) this factor 2 is best possible even in the highly restricted setting of the Euclidean plane. 相似文献
9.
The transportation problem with exclusionary side constraints 总被引:1,自引:0,他引:1
Dries Goossens Frits C. R. Spieksma 《4OR: A Quarterly Journal of Operations Research》2009,7(1):51-60
We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of
the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of
suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate
within a constant factor (unless P = NP).
This research was partially supported by FWO Grant No. G.0114.03. 相似文献
10.
S Coene A Arnout F C R Spieksma 《The Journal of the Operational Research Society》2010,61(12):1719-1728
This paper deals with a study on a variant of the Periodic Vehicle Routing Problem (PVRP). As in the traditional Vehicle Routing Problem, customer locations each with a certain daily demand are given, as well as a set of capacitated vehicles. In addition, the PVRP has a horizon, say T days, and there is a frequency for each customer stating how often within this T-day period this customer must be visited. A solution to the PVRP consists of T sets of routes that jointly satisfy the demand constraints and the frequency constraints. The objective is to minimize the sum of the costs of all routes over the planning horizon. We develop different algorithms solving the instances of the case studied. Using these algorithms we are able to realize considerable cost reductions compared to the current situation. 相似文献