基于权值的NURBS曲线形状修改

针对基于控制顶点的NURBS曲线形状修改的不足,讨论了如何通过修改控制顶点的权值进行NURBS曲线的形状修改问题。NURBS曲线可以看作是高一维空间非有理B样条曲线的中心投影,该B样条的控制顶点为原NURBS曲线的带权控制顶点,并且这样的B样条曲线有无数多条。根据这个性质,以实例的方式通过特定自由参数确定B样条曲线,实现了基于权值的NURBS曲线形状修改。该方法不仅能够较好地确定新的带权控制顶点,还解决了修改后曲线在给定点的切矢问题,具有更好的灵活性。     

回归型支持向量机的机翼结冰冰型预测

飞机结冰严重威胁着飞行安全。针对机翼结冰冰型预测时不确定性因素较多、难以准确预测的问题,提出了一种基于回归型支持向量机的机翼结冰冰型预测方法。在建立冰型模型的基础上,利用回归型支持向量机(Support Vector Regression,SVR)获得冰型多项式系数,从而预测出相关飞行条件和大气条件下的冰型。仿真结果表明,该方法具有较好的预测能力,可以及时提供可靠的结冰信息,为保证结冰条件下的飞行安全提供了保障。     

Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

不同磁浮列车外形的气动性能比较

上海磁浮列车由于流线型车头较短,气动性能并不理想,根据国内厂家给定的列车横断面尺寸和对气动性能的要求,对国产磁浮列车气动外形进行多方案设计,通过求解三维可压N-S方程和k-ε双方程湍流模型,对提出的磁浮列车各种外形方案的气动性能进行数值模拟计算,并根据计算结果进一步改进气动外形,如此反复,直至得出气动性能和外观最优的磁浮列车外形。在最终选定的三种设计方案中,方案3由于水平投影轮廓线较窄、最大纵剖面轮廓线曲率较小,其整车空气阻力和列车交会压力波都较其它两种方案要小,因此为最佳的气动外形方案。通过比较分析,此次选用的国产磁浮列车外形,列车以430km/h运行时三节车总的空气阻力为33.84kN,而上海磁浮列车为54.07kN;国产磁浮列车最大列车交会压力波幅值为2913Pa,而在同等条件下上海磁浮列车为3827Pa,其气动性能明显优于上海磁浮列车。     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

Column generation for stochastic green telecommunication network planning with switchable base stations

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

Capacity investment decisions under risk aversion

This article studies the optimal capacity investment problem for a risk‐averse decision maker. The capacity can be either purchased or salvaged, whereas both involve a fixed cost and a proportional cost/revenue. We incorporate risk preference and use a consumption model to capture the decision maker's risk sensitivity in a multiperiod capacity investment model. We show that, in each period, capacity and consumption decisions can be separately determined. In addition, we characterize the structure of the optimal capacity strategy. When the parameters are stationary, we present certain conditions under which the optimal capacity strategy could be easily characterized by a static two‐sided (s, S) policy, whereby, the capacity is determined only at the beginning of period one, and held constant during the entire planning horizon. It is purchased up to B when the initial capacity is below b, salvaged down to Σ when it is above σ, and remains constant otherwise. Numerical tests are presented to investigate the impact of demand volatility on the optimal capacity strategy. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 218–235, 2016     

On the polyhedral structure of two‐level lot‐sizing problems with supplier selection

In this article, we study a two‐level lot‐sizing problem with supplier selection (LSS), which is an NP‐hard problem arising in different production planning and supply chain management applications. After presenting various formulations for LSS, and computationally comparing their strengths, we explore the polyhedral structure of one of these formulations. For this formulation, we derive several families of strong valid inequalities, and provide conditions under which they are facet‐defining. We show numerically that incorporating these valid inequalities within a branch‐and‐cut framework leads to significant improvements in computation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 647–666, 2017