-
作者：DE, P; GHOSH, JB; WELLS, CE
摘要：We discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. This paper presents a dynamic programming algorithm that is pseudopolynomial in complexity. We also propose a fully polynomial approximation scheme and derive a lower bound that is useful in its implementation. Furthermore, we show that the dynamic programming solution is easy to extend to a bicriteria version of th...
-
作者：PHILIPPE, B; SAAD, Y; STEWART, WJ
作者单位：University of Minnesota System; University of Minnesota Twin Cities; North Carolina State University
摘要：This paper describes and compares several methods for computing stationary probability distributions of Markov chains. The main linear algebra problem consists of computing an eigenvector of a sparse, nonsymmetric matrix associated with a known eigenvalue. It can also be cast as a problem of solving a homogeneous, singular linear system. We present several methods based on combinations of Krylov subspace techniques, single vector power iteration/relaxation procedures and acceleration technique...
-
作者：KRASS, D; FILAR, JA; SINHA, SS
作者单位：University System of Maryland; University of Maryland Baltimore County; Indian Statistical Institute; Indian Statistical Institute Delhi
摘要：The two most commonly considered reward criteria for Markov decision processes are the discounted reward and the long-term average reward. The first tends to neglect the future, concentrating on the short-term rewards, while the second one tends to do the opposite. We consider a new reward criterion consisting of the weighted combination of these two criteria, thereby allowing the decision maker to place more or less emphasis on the short-term versus the long-term rewards by varying their weig...
-
作者：BEAN, JC; HOPP, WJ; DUENYAS, I
作者单位：Northwestern University
摘要：We formulate a mixed integer program to determine whether a finite time horizon is a forecast horizon in a nonhomogeneous Markov decision process. We give a Bender's decomposition approach to solving this problem that evaluates the stopping rule, eliminates some suboptimal combinations of actions, and yields bounds on the maximum error that could result from the selection of a candidate action in the initial stage. The integer program arising from the decomposition has special properties that ...
-
作者：NG, KYK
作者单位：University of Ottawa
摘要：This note reports a multicriteria optimization approach to aircraft loading. Only cargo manifests or standard loads provided (or approved) by experienced loadmasters are employed in the optimization procedure. The familiarity of the load manifests that comprise the solution makes the model truly operable. In testing with actual data, the model reduced the number of aircraft loads required to complete an airlift by 9%, as compared to the traditional, manual method presently used. More important...
