What you should know about approximate dynamic programming

Approximate dynamic programming (ADP) is a broad umbrella for a modeling and algorithmic strategy for solving problems that are sometimes large and complex, and are usually (but not always) stochastic. It is most often presented as a method for overcoming the classic curse of dimensionality that is well‐known to plague the use of Bellman's equation. For many problems, there are actually up to three curses of dimensionality. But the richer message of approximate dynamic programming is learning what to learn, and how to learn it, to make better decisions over time. This article provides a brief review of approximate dynamic programming, without intending to be a complete tutorial. Instead, our goal is to provide a broader perspective of ADP and how it should be approached from the perspective of different problem classes. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

New product introduction against a predator: A bilevel mixed‐integer programming approach

We consider a scenario with two firms determining which products to develop and introduce to the market. In this problem, there exists a finite set of potential products and market segments. Each market segment has a preference list of products and will buy its most preferred product among those available. The firms play a Stackelberg game in which the leader firm first introduces a set of products, and the follower responds with its own set of products. The leader's goal is to maximize its profit subject to a product introduction budget, assuming that the follower will attempt to minimize the leader's profit using a budget of its own. We formulate this problem as a multistage integer program amenable to decomposition techniques. Using this formulation, we develop three variations of an exact mathematical programming method for solving the multistage problem, along with a family of heuristic procedures for estimating the follower solution. The efficacy of our approaches is demonstrated on randomly generated test instances. This article contributes to the operations research literature a multistage algorithm that directly addresses difficulties posed by degeneracy, and contributes to the product variety literature an exact optimization algorithm for a novel competitive product introduction problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Testing of software with an operational profile

One of the important features of any software system is its operational profile. This is simply the set of all operations that a software is designed to perform and the occurence probabilities of these operations. We present a new model on optimal software testing such that testing is done sequentially using a set of test cases. There may be failures due to the operations in each of these cases. The model parameters, consisting of testing costs and failure rates, all depend on the cases used and the operations performed. Our aim is to find the optimal testing durations in all of the cases in order to minimize the total expected cost. This problem leads to interesting decision models involving nonlinear programming formulations that possess explicit analytical solutions under reasonable assumptions. © 2000 John Wiley & Sons, Inc., Naval Research Logistics 47: 620–634, 2000     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

A risk function for the stochastic modeling of electric capacity expansion

We present a stochastic optimization model for planning capacity expansion under capacity deterioration and demand uncertainty. The paper focuses on the electric sector, although the methodology can be used in other applications. The goals of the model are deciding which energy types must be installed, and when. Another goal is providing an initial generation plan for short periods of the planning horizon that might be adequately modified in real time assuming penalties in the operation cost. Uncertainty is modeled under the assumption that the demand is a random vector. The cost of the risk associated with decisions that may need some tuning in the future is included in the objective function. The proposed scheme to solve the nonlinear stochastic optimization model is Generalized Benders' decomposition. We also exploit the Benders' subproblem structure to solve it efficiently. Computational results for moderate‐size problems are presented along with comparison to a general‐purpose nonlinear optimization package. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:662–683, 2001     

求解整数规划问题的一个搜索方法

本文整数规划问题给出一种搜索方法,它类似于求解连续变量优化问题的迭代方法,从一个好的初始可行解出发,寻找一个搜索方向,沿着这个方向求出改进的可行解,然后又开始下一次迭代。此方法简单易行,可以求出问题的最优解或近似最优解,对于整数线性规划问题和整数非线性规划问题的求解都适用,并且容易推广到求解大规校整数线性规划问题。文中附有计算例子,说明方法是有效的。     

目标选择优化模型及算法

提出了可用于大威力武器火力分配的目标选择优化模型及算法。内容包括：问题的数学描述、问题的等价变换与分解、问题求解的动态规划算法和不同算法的计算次数比较。     

Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures

In this paper, we study the problem of scheduling quay cranes (QCs) at container terminals where incoming vessels have different ready times. The objective is to minimize the maximum relative tardiness of vessel departures. The problem can be formulated as a mixed integer linear programming (MILP) model of large size that is difficult to solve directly. We propose a heuristic decomposition approach to breakdown the problem into two smaller, linked models, the vessel‐level and the berth‐level models. With the same berth‐level model, two heuristic methods are developed using different vessel‐level models. Computational experiments show that the proposed approach is effective and efficient. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

VB程序设计课程教学的探索与实践

实践表明,对影响VB程序设计课程教学中存在的突出问题进行认真分析,充分利用网络教学平台,改革课堂教学方法、抓好上机实践环节。此举有效地激发了学生的学习兴趣,提高学生的编程能力,同时也有助于提高教学质量和效果。