The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

Periodic maintenance and repair rate control in stochastic manufacturing systems

In this paper, we consider a periodic preventive maintenance, repair, and production model of a flexible manufacturing system with failure-prone machines, where the control variables are the repair rate and production rate. We use periodic preventive maintenance to reduce the machine failure rates and improve the productivity of the system. One of the distinct features of the model is that the repair rate is adjustable. Our objective is to choose a control process that minimizes the total cost of inventory/shortage, production, repair, and maintenance. Under suitable conditions, we show that the value function is locally Lipschitz and satisfies an Hamilton-Jacobi-Bellman equation. A sufficient condition for optimal control is obtained. Since analytic solutions are rarely available, we design an algorithm to approximate the optimal control problem. To demonstrate the performance of the numerical method, an example is presented.Research of this author was supported by the Natural Sciences and Engineering Research Council of Canada, Grant OGP0036444.Research of this author was supported in part by the University of Georgia.Research of this author was supported in part by the National Science Foundation, Grant DMS-92-24372.     

A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

A Crop Planning Problem with Fuzzy Random Profit Coefficients

The main purpose of this paper is to present a crop planning problem for agricultural management under uncertainty. It is significant that agricultural managers assign their limited farmlands to cultivation of which crops in a season. This planning is called the crop planning problem and influences their incomes for the season. Usually, the crop planning problem is formulated as a linear programming problem. But there are many uncertain factors in agricultural problems, so future profits for crops are not certain values. A linear programming model with constant profit coefficients may not reflect the environment of decision making properly. Therefore, we propose a model of crop planning with fuzzy profit coefficients, and an effective solution procedure for the model. Furthermore, we extend this fuzzy model, setting the profit coefficients as discrete randomized fuzzy numbers. We show concrete optimal solutions for each models.     

长江三角洲国际性城市群发展战略研究

国际性城市群的建设是我国城市在下世纪参与国际竞争的重要战略 ,以沪宁杭为中心的长江三 角洲城市群是我国参与 21世纪全球城市间国际竞争进而发展成为国际性城市群的主要代表 ,既分工明 确 ,又联合协作 ,是长江三角洲地区各主要中心城市实现国际性城市群战略的基本保证.     

道路约束条件下的移动机器人跟踪

为提高移动机器人的位置估计精度和跟踪效果,提出一种基于道路约束条件下的移动机器人鲁棒约束H∞滤波(CHF)跟踪算法.首先,将机器人移动的道路网络作为跟踪的约束条件,并利用当前统计模型对机器人的运动进行建模.其次,将道路约束条件作为机器人跟踪的非线性状态约束,利用最小协方差估计推导了鲁棒CHF递推方程.通过拉格朗日乘子法对非线性约束优化估计问题进行求解,并利用约束信息对CHF算法的状态更新过程进行了改进.最后,通过对CHF算法和无约束的H∞滤波算法的跟踪性能进行了对比分析和验证.仿真结果表明,该算法可以实现机器人的跟踪,且跟踪精度优于HF算法.     

George Dantzig in the development of economic analysis

The role of optimization is central to economic analysis, particularly in its “neoclassical” phase, since about 1870, and is therefore highly compatible with the impulse behind linear programming (LP), as developed by Dantzig. LP’s stress on alternative activities fits very well with modern economic analysis. The concept of economic equilibrium, properly understood, required the central notion of complementary slackness. so central in LP.

LP was seen as a tool for actual implementation of neoclassical principles precisely at a time when the market was under attack from several directions. The economists Koopmans and Hurwicz played an important role both in stimulating the crucial development of the simplex method and in relating LP to the world of economics.

LP became widely used in national economic planning, particularly for developing countries, and for the study of individual industries, especially the energy sector. The works of Chenery and of Manne are central in these fields.

As respect for the usefulness of the market increased, the emphasis on national planning diminished and was replaced by an emphasis on equilibrium analysis, in which LP still plays a large part in the study of individual sectors, particularly energy.     

Even-aged restrictions with sub-graph adjacency

Restrictions on the size and proximity of clearcuts have led to the development of a variety of exact and heuristic methods to optimize the net present value of timber harvests, subject to adjacency constraints. Most treat harvest units as pre-defined, and impose adjacency constraints on any two units sharing a common border. By using graph theory notation to define sub-graph adjacency constraints, opening size can be considered variable, which may be more appropriate for landscape-level planning. A small example data set is used in this paper to demonstrate the difference between the two types of adjacency constraints for both integer programming and heuristic solution methods.     

On Spectrum Congestion and Capacity of Radio Links

This paper addresses the operation of radio links under mutual interference conditions, an important problem in spectrum management and radio link design. It introduces the capacity loss and isolation index as measures of effective use of radio links and radio frequency spectrum resources.     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.