Computational bounds for elevator control policies by large scale linear programming

We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems.     

Evolutionary bi-objective optimisation in the elevator car routing problem

The paper introduces a genetic algorithms based elevator group control system utilising new approaches to multi-objective optimisation in a dynamically changing process control environment. The problem of controlling a group of elevators as well as the basic principles of the existing single-objective genetic elevator group control method are described. The foundations of the developed multi-objective approach, Evolutionary Standardised-Objective Weighted Aggregation Method, with a PI-controller operating as an interactive Decision Maker, are introduced. Their operation as a part of bi-objective genetic elevator group control is presented together with the performance results obtained from simulations concerning a high-rise office building. The results show that with this approach it is possible to regulate the service level of an elevator system, in terms of average passenger waiting time, so as to bring it to a desired level and to produce that service with minimum energy consumption. This has not been seen before in the elevator industry.     

Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models

We develop and experimentally compare policies for the control of a system of k elevators with capacity one in a transport environment with ? floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each request and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average squared waiting times can be implemented to run in real-time (1 s) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used policies like multi-server variants of greedy and nearest neighbor.     

Waiting time based routing policies to parallel queues with percentiles objectives

We develop a method to obtain near-optimal routing policies to parallel queues with decisions based on customers’ wait and performance objectives which include percentiles of the waiting time. We formulate and explicitly derive a value function where the waiting time is used as a decision variable. This allows us to apply a one-step policy improvement method to obtain an efficient routing solution. Numerical illustrations reveal that classical monotone policies are not always optimal.     

Approximate steady-state distribution for a large repairable item inventory system

This paper examines a model for a repairable inventory system where some items are condemned upon failure. These condemnations require an ordering policy which we take to be an (s, S) policy. We model this system as a version of the classical machine repair problem using continuous time Markov processes. We develop solution procedures based on approximations to the steady state probability distribution, which enable us to obtain the operating characteristics of (s, S) policies very easily, with or without an ordering leadtime. The approximate models are found to be very accurate and computationally very efficient.     

Continuous time Markovian decision processes average return criterion

Continuous time Markovian decision models with countable state space are investigated. The existence of an optimal stationary policy is established for the expected average return criterion function. It is shown that the expected average return can be expressed as an expected discounted return of a related Markovian decision process. A policy iteration method is given which converges to an optimal deterministic policy, the policy so obtained is shown optimal over all Markov policies.     

Optimal parking of idle elevators under myopic and state-dependent policies

In this paper we discuss the problem of optimally parking single and multiple idle elevators under light-traffic conditions. The problem is analyzed from the point of view of the elevator owner whose objective is to minimize the expected total cost of parking and dispatching the elevator (which includes the cost incurred for waiting passengers). We first consider the case of a single elevator and analyze a (commonly used but suboptimal) state-independent myopic policy that always positions the idle elevator at the same floor. Building on the results obtained for the myopic policy, we then show that the optimal non-myopic (state-dependent) policy calls for dispatching the idle elevator to the state-dependent median of a weight distribution. Next, we consider the more difficult case of two elevators and develop an expression for the expected dispatching distance function. We show that the objective function for the myopic policy is non-convex. The non-myopic policy is found to be dependent on the state of the two idle elevators. We compute the optimal state-dependent policy for two elevators using the results developed for the myopic policy. Next, we examine the case of multiple elevators and provide a general recursive formula to find the expected dispatching distance functions. Finally, we generalize the previous models by incorporating a fixed cost for parking the idle elevators that results in a two-sided optimal policy with different regions. Every policy that we introduce and analyze is illustrated by an example. The paper concludes with a short summary and suggestions for future research.     

高层电梯系统运行方案的建模与求解

随着社会的发展,运用垂直交通系统的高层建筑和智能化建筑不断出现。而有效的电梯交通配置,是垂直交通系统高效运行的基本保证。本文针对高层商务建筑中的电梯运行管理方案设计问题,分析了影响电梯耗能和用户满意度的主要因素。分别建立了电梯数目已知和电梯数目未知情况下的电梯调度优化模型,并设计相应动态规划算法和遗传算法。结合算例,求解算例中的电梯优化调度方案,以验证模型的合理性。最后根据我们建立的电梯调度模型,借助VC++作出可视化的电梯调度示意界面,将本文的研究结果用于实际的电梯调度中。     

Optimizing System Availability Under Minimal Repair with Non-Negligible Repair and Replacement Times

Availability measures are given for a repairable system under minimal repair with constant repair times. A new policy and an existing replacement policy for this type of system are discussed. Each involves replacement at the first failure after time T, with T representing total operating time in the existing model and total elapsed time (i.e. operating time + repair time) in the new model. Optimal values of T are found for both policies over a wide range of parameter values. These results indicate that the new and administratively easier policy produces only marginally smaller optimal availability values than the existing policy.     

电梯决策问题的占线算法分析

结合现实生活中电梯的运营状况,从占线算法角度分析并解决了电梯运行中碰到的两个问题:乘客如何选择乘坐电梯的策略以及多少楼层以上应该开放电梯.通过对问题的描述,建立了求解模型并提出一种竞争策略;运用占线算法得到该策略的竞争比,并将此策略作为等待电梯的较优策略;通过对竞争策略的分析,并利用实地考察得到的数据,得出楼层达到4层及以上时才应该开放电梯的结论,并以此为基础对电梯运营者提出相关建议.     

The production–inventory problem of a product with time varying demand,production and deterioration rates

In this paper, we consider the production–inventory problem in which the demand, production and deterioration rates of a product are assumed to vary with time. Shortages of a cycle are allowed to be backlogged partially. Two models are developed for the problem by employing different modeling approaches over an infinite planning horizon. Solution procedures are derived for determining the optimal replenishment policies. A procedure to find the near-optimal operating policy of the problem over a finite time horizon is also suggested.     

A total standard WIP estimation method for wafer fabrication

The standard work-in-process (WIP) level in a wafer fabrication factory is an important parameter which can be properly used to trigger the decision of when to release specific wafer lots. There are many WIP-based release control policies which have been proven to be effective for wafer fabrication manufacturing, few methods have been proposed to find the suitable WIP-level as a parameter for these release policies. This paper proposes a queueing network-based algorithm to determine the total standard WIP level so that the Fixed-WIP release algorithm to determine the total standard WIP level so that the Fixed-WIP release control policy can apply. A numerical example is provided to elaborate the algorithm. A simulation model of a real-world wafer fabrication factory in Taiwan is built and analyzed. Results of simulation experiment indicate that under the Fixed-WIP control policy, the total standard WIP level estimated from this study achieves a target throughput rate while keeping the corresponding cycle time relatively low. Results also demonstrate that the queueing network-based algorithm is a very useful method to determine the standard WIP level efficiently.     

Transient policies in discrete dynamic programming: Linear programming including suboptimality tests and additional constraints

This paper investigates the computation of transient-optimal policies in discrete dynamic programming. The model, is quite general: it may contain transient as well as nontransient policies. and the transition matrices are not necessarily substochastic. A functional equation for the so-called transient-value-vector is derived and the concept of superharmonicity is introduced. This concept provides the linear program to compute the transientvalue-vector and a transient-optimal policy. We also discuss the elimination of suboptimal actions, the solution of problems with additional constraints, and the computation of an efficient policy for a multiple objective dynamic programming problem.     

Managing capacity flexibility in make-to-order production environments

This paper addresses the problem of managing flexible production capacity in a make-to-order (MTO) manufacturing environment. We present a multi-period capacity management model where we distinguish between process flexibility (the ability to produce multiple products on multiple production lines) and operational flexibility (the ability to dynamically change capacity allocations among different product families over time). For operational flexibility, we consider two polices: a fixed allocation policy where the capacity allocations are fixed throughout the planning horizon and a dynamic allocation policy where the capacity allocations change from period to period. The former approach is modeled as a single-stage stochastic program and solved using a cutting-plane method. The latter approach is modeled as a multi-stage stochastic program and a sampling-based decomposition method is presented to identify a feasible policy and assess the quality of that policy. A computational experiment quantifies the benefits of operational flexibility and demonstrates that it is most beneficial when the demand and capacity are well-balanced and the demand variability is high. Additionally, our results reveal that myopic operating policies may lead a firm to adopt more process flexibility and form denser flexibility configuration chains. That is, process flexibility may be over-valued in the literature since it is assumed that a firm will operate optimally after the process flexibility decision. We also show that the value of process flexibility increases with the number of periods in the planning horizon if an optimal operating policy is employed. This result is reversed if a myopic allocation policy is adopted instead.     

An efficient heuristic for inventory control when the customer is using a (s,S) policy

We consider a capacitated supply chain in which the supplier has the information of the (s,S) policy used by the retailer as well as the end-customer demand distribution. For the resulting inventory control problem at the supplier, optimal policies and structural properties were presented by Gavirneni et al. (Management Sci. 45(1) (1999) 16). They detailed an efficient solution procedure for the uncapacitated problem and resorted to computationally expensive infinitesimal perturbation analysis (IPA) for the capacitated situation. In this paper, we study a heuristic, based on the uncapacitated solution, for the capacitated situation. A detailed computational study showed that this heuristic is very efficient in that the costs increased by only 3.3% on the average. The heuristic was especially effective at higher capacities, lower holding costs, and extreme values of demand variance.     

Optimal preventive maintenance of a production system with an intermediate buffer

In this paper we consider a model consisting of a deteriorating installation that transfers a raw material to a production unit and a buffer which has been built between the installation and the production unit. The deterioration process of the installation is considered to be nonstationary, i.e. the transition probabilities may depend not only on the working conditions of the installation but on its age as well. The problem of the optimal preventive maintenance of the installation is considered. Under a suitable cost structure it is shown that, for fixed age of the installation and fixed buffer level, the optimal policy is of control-limit type. When the deterioration process is stationary, an efficient Markov decision algorithm operating on the class of control-limit policies is developed. There is strong numerical evidence that the algorithm converges to the optimal policy. Two generalizations of this model are also discussed.     

On the determination of the control parameters of the optimal can-order policy

This paper considers the well-known class of can-order policies. This type of coordinated replenishment policies accounts for a joint set-up cost structure, where a major set-up cost is incurred for any order and an individual minor set-up cost is charged for each item in the replenishment. Recent comparative studies have pointed out that the performance of the optimal can-order policy is poor, compared to other coordinated replenishment strategies, when the major set-up cost is high. This paper shows that it is the approximate decomposition method to calculate the optimal canorder parameters which performs bad in such situations and not the policy itself. Attention is focused to a subclass of can-order policies, which is close to the optimal can-order policy for high major set-up costs. A solution procedure is developed to calculate the optimal control parameters of this policy. It is shown that a properly chosen combination of the solution procedures to calculate can-order parameters leads to a can-order strategy which performs as well as other coordinated replenishment policies.     

A transient stochastic simulation–optimization model for operational fuel planning in-theater

Army fuel planners are responsible for developing daily loading plans that specify which tankers to load, with what fuel, and where to send the loaded tankers. The tools used to accomplish this task are custom built spreadsheets which require large amounts of time and effort to use, update, and keep free of errors. This research presents a transient stochastic simulation–optimization model of the in-theater bulk fuel supply chain, where the simulation model is used to simulate the performance of the fuel supply chain under a particular fuel distribution policy and the optimization portion is used to update the policy so that it results in the performance desired by the Army fuel planner. The fuel distribution policy can then be used to derive the daily loading plan. Due to the multi-objective nature of the problem, the set of policies that form the efficient frontier are all candidate policies for the Army fuel planner to select from. Results of experimentation with a wide variety of supply chain scenarios indicate that, for a given supply chain scenario, the optimization portion of the model identifies a set of fuel distribution policies that address the objectives of the Army fuel planner. In addition, the simulation–optimization model comfortably solves the largest supply chain scenarios the Army fuel planner would reasonably be expected to encounter.     

An Optimum Repair Policy for the Machine Interference Problem

This paper presents two repair policies for the machine interference problem where machines have two failure modes. In policy I priority of repair is assigned to one failure mode over the other, while in policy II the two failure modes have equal probability of repair. Computer programs were developed to obtain the optimal number of machines to be allocated to a single repair crew for the two policies. Under the same operating conditions, policy II is superior to policy I. The repair crew efficiency and machine availability were evaluated for both policies.     

马氏决策规划的加速逼近算法与最小方差问题

我们涉及的折扣马氏决策规划(有些著者称为马氏决策过程),具有状态空问与每个状态可用的决策集均为可数无穷集、次随机转移律族、有界报酬函数.给出了一个求(ε_)最优平稳策略的加速收敛逐次逼近算法,比White的逐次逼近算法更快地收敛于(ε_)最优解,并配合有非最优策略的检验准则,使算法更加得益. 设β为折扣因子,一般说β(或(ε,β))_最优平稳策略,往往是非唯一的,甚至与平稳策略类包含的策略数一样多.我们自然希望在诸β(或(ε,β))_最优平稳策略中寻求方差齐次地(关于初始状态)达(ε_)最小的策略.我们证明了这种策略确实存在,并给出了获得这种策略的算法.