Single machine scheduling with a restricted rate‐modifying activity

In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

基于权值的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     

A sequential auction‐bargaining procurement model

One of the most important decisions that a firm faces in managing its supply chain is a procurement decision: selecting suitable suppliers among many potential competing sellers and reducing the purchase cost. While both auctions and bargaining have been extensively studied in the literature, the research that combines auctions and bargaining is limited. In this article, we consider a combined auction‐bargaining model in a setting where a single buyer procures an indivisible good from one of many competing sellers. The procurement model that we analyze is a sequential model consisting of the auction phase followed by the bargaining phase. In the auction phase, the sellers submit bids, and the seller with the lowest bid is selected as the winning bidder. In the bargaining phase, the buyer audits the cost of the winning seller and then negotiates with him to determine the final price. For this auction‐bargaining model, we find a symmetric equilibrium bidding strategy for the sellers in a closed form, which is simple to understand and closely related to the classical results in the auction and bargaining literature. We also show that the auction‐bargaining model generates at least as much profit to the buyer as the standard auction or sequential bargaining model. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Dynamic coordination of production planning and sales admission control in the presence of a spot market

We consider the decision‐making problem of dynamically scheduling the production of a single make‐to stock (MTS) product in connection with the product's concurrent sales in a spot market and a long‐term supply channel. The spot market is run by a business to business (B2B) online exchange, whereas the long‐term channel is established by a structured contract. The product's price in the spot market is exogenous, evolves as a continuous time Markov chain, and affects demand, which arrives sequentially as a Markov‐modulated Poisson process (MMPP). The manufacturer is obliged to fulfill demand in the long‐term channel, but is able to rein in sales in the spot market. This is a significant strategic decision for a manufacturer in entering a favorable contract. The profitability of the contract must be evaluated by optimal performance. The current problem, therefore, arises as a prerequisite to exploring contracting strategies. We reveal that the optimal strategy of coordinating production and sales is structured by the spot price dependent on the base stock and sell‐down thresholds. Moreover, we can exploit the structural properties of the optimal strategy to conceive an efficient algorithm. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010