A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

基于磁导率法的零部件硬度电磁无损检测技术研究

传统的机械压痕法虽能测量火炮零部件的硬度,但对其表面有损害,且某些零部件工作面并不允许使用打点测量方式．为解决这一问题,基于硬度与材料磁导率之间的对应关系,设计了一种硬度电磁无损检测系统,采用DDS技术实现参数可控的正弦信号源,以满足磁导率测试所需的激励条件．为了提高检测灵敏度,利用交流电桥拾取由硬度变化引起的检测线圈和参考线圈电压差分信号,并进一步在调理电路中采用正交锁相放大技术对这一微弱信号进行放大和噪声抑制．硬度试验结果表明,该系统能以无损的检测方式有效地区分零部件的硬度值,为火炮定型试验中的硬度测量提供了新途径．     

高硬再制造表面强化层的加热切削研究

应用高性能硬质合金、陶瓷刀具和CBN刀具对常温条件下难以加工的高硬堆焊材料进行加热切削试验。试验结果表明：尽管加热条件下冲击效应降低,但CBN刀具仍然破损严重;陶瓷刀具虽然也无法实现理想的切削,但切削过程中刀具破损模式从崩碎式失效转变为磨损失效;3种刀具中高性能硬质合金应用效果最佳,其最佳参数条件下,一个切削里程后刀面VB值仅为0．3mm,试验过程中,刀具磨损随表面加热温度、切削速度、切削深度的提高而增大,但随进给量取值的增大而减小,其中切削速度对刀具VB值的影响最大,而进给量和削切深度对刀具VB值的影响较小。综合分析还表明：试验中刀具磨损速率仍然受刀具红硬性极限的限制。     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

超声辅助喷射电沉积Ni镀层的表面形貌及硬度

试验以直接超声方式,在喷射电沉积装置的基础上加载超声设备,分别在20℃和50℃两种镀液温度下在A3钢基体上制备了加载超声和不加载超声Ni镀层,研究了超声波及温度对Ni镀层表面形貌和硬度的影响。试验结果分析表明：在20℃条件下,超声可避免镀层裂纹的产生,提高镀层的硬度;在50℃条件下,超声可细化镀层的组织,且可显著提高镀层硬度;超声波对喷射电沉积层组织和性能的影响机理主要在于超声空化引起的析氢减少、细晶强化和加工硬度。     

The stochastic single resource service‐provision problem

The service‐provision problem described in this paper comes from an application of distributed processing in telecommunications networks. The objective is to maximize a service provider's profit from offering computational‐based services to customers. The service provider has limited capacity and must choose which of a set of software applications he would like to offer. This can be done dynamically, taking into consideration that demand for the different services is uncertain. The problem is examined in the framework of stochastic integer programming. Approximations and complexity are examined for the case when demand is described by a discrete probability distribution. For the deterministic counterpart, a fully polynomial approximation scheme is known 2 . We show that introduction of stochasticity makes the problem strongly NP‐hard, implying that the existence of such a scheme for the stochastic problem is highly unlikely. For the general case a heuristic with a worst‐case performance ratio that increases in the number of scenarios is presented. Restricting the class of problem instances in a way that many reasonable practical problem instances satisfy allows for the derivation of a heuristic with a constant worst‐case performance ratio. Worst‐case performance analysis of approximation algorithms is classical in the field of combinatorial optimization, but in stochastic programming the authors are not aware of any previous results in this direction. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Ni-P-SiC 化学复合镀

采用化学共沉淀法对Ni P SiC化学复合镀研究 ,通过能谱仪和扫描电镜分析了镀层的组成与形貌 ,并对镀层的硬度、耐腐蚀性能进行了研究。结果表明 ,镀层硬度随SiC微粒浓度加大而增加 ;镀液中SiC微粒的浓度和镀液的pH值对镀层中SiC微粒的含量有影响 ;在SiC浓度为 7 5g/L时镀层中SiC含量达到最大值 1 6 81 % ;而pH值的最佳值为 4 7;同时 ,由于SiC微粒的加入 ,镀层表面色泽变暗 ,外观较粗糙 ,镀层的耐腐蚀性降低。     

基于仪器化压入技术的结构陶瓷材料断裂韧性测试

利用自主研制的仪器化压入仪,采用Vickers压头对氮化硅和氧化锆2种结构陶瓷进行了仪器化压入试验,通过压入载荷-深度曲线可识别材料的弹性模量E,通过测量压痕对角线直径可确定材料的维氏硬度HV,再通过测量压痕裂纹扩展长度即可得到材料的断裂韧性KIC,实现了在单一压入仪上基于Vickers压头对结构陶瓷材料断裂韧性的测试。与传统压痕法利用硬度计或纳米压入仪测试陶瓷材料断裂韧性相比,试验更简单快捷,可靠性高,同时测得信息量也更为丰富。试验测得2种结构陶瓷的断裂韧性分别为4.77～5.82 MPa.m1/2和7.22～8.94 MPa.m1/2。     

Investigation on the process parameters of TIG-welded aluminum alloy through mechanical and microstructural characterization

Multi-pass TIG welding was conducted on plates (15×300×180 mm3) of aluminum alloy Al-5083 that usually serves as the component material in structural applications such as cryogenics and chemical processing industries. Porosity formation and solidification cracking are the most common defects when TIG welding Al-5083 alloy, which is sensitive to the welding heat input. In the experiment, the heat input was varied from 0.89 kJ/mm to 5 kJ/mm designed by the combination of welding torch travel speed and welding current. Tensile, micro-Vicker hardness and Charpy impact tests were executed to witness the impetus response of heat input on the mechanical properties of the joints. Radiographic inspection was performed to assess the joint's quality and welding defects. The results show that all the specimens displayed inferior mechanical properties as compared to the base alloy. It was established that porosity was progressively abridged by the increase of heat input. The results also clinched that the use of me-dium heat input (1-2 kJ/mm) offered the best mechanical properties by eradicating welding defects, in which only about 18.26% of strength was lost. The yield strength of all the welded specimens remained unaffected indicated no influence of heat input. Partially melted zone (PMZ) width also affected by heat input, which became widened with the increase of heat input. The grain size of PMZ was found to be coarser than the respective grain size in the fusion zone. Charpy impact testing revealed that the absorbed energy by low heat input specimen (welded at high speed) was greater than that of high heat input (welded at low speed) because of low porosity and the formation of equiaxed grains which induce better impact toughness. Cryogenic (-196 C) impact testing was also performed and the results corroborate that impact properties under the cryogenic environment revealed no appreciable change after welding at designated heat input. Finally, Macro and micro fractured surfaces of tensile and impact specimens were analyzed using Stereo and Scanning Electron Microscopy (SEM), which have supported the experimental findings.     

Scheduling with variable time slot costs

In this article, we study a class of new scheduling models where time slot costs have to be taken into consideration. In such models, processing a job will incur certain cost which is determined by the time slots occupied by the job in a schedule. The models apply when operational costs vary over time. The objective of the scheduling models is to minimize the total time slot costs plus a traditional scheduling performance measure. We consider the following performance measures: total completion time, maximum lateness/tardiness, total weighted number of tardy jobs, and total tardiness. We prove the intractability of the models under general parameters and provide polynomial‐time algorithms for special cases with non‐increasing time slot costs.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010