A generalization of the weighted set covering problem

We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b‐matching problem. In general, we may use a polynomial‐time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256–278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383–390], and V. Chvatal [A greedy heuristic for the set‐covering problem, Math Oper Res 4(3) (1979), 233–235] to get an approximate solution for the problem. We find a worst‐case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Bayes假设检验及样本数量问题研究

针对Bayes方法在工程实践中未能得到广泛应用的实际情况分析了Bayes方法存在的问题,以正态总体期望为背景研究并改进了Bayes方法,进一步推导了Bayes假设检验样本数量确定方法。     

磨合预处理对有机钼添加剂摩擦学性能的影响

采用MMW-1万能摩擦磨损试验机,考察了磨合预处理工况(时间、载荷)对两种有机钼添加剂在CF-4 15W-40柴油机油中抗磨减摩性能的影响。采用扫描电子显微镜和能谱仪分析了磨斑表面形貌和表面元素组成。结果表明,适当的磨合预处理可有效增强有机钼添加剂在柴油机油中的抗磨减摩性能,且经过磨合预处理的磨斑表面形貌较没有处理时平整,添加剂主要功能元素在摩擦表面的质量分数增加。     

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     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

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     

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     

Finite Markov chain models skip-free in one direction

Finite Markov processes are considered, with bidimensional state space, such that transitions from state (n, i) to state (m, j) are possible only if m ≤ n + 1. The analysis leads to efficient computational algorithms, to determine the stationary probability distribution, and moments of first passage times.