Heuristics approach to printed circuit board insertion problem

This paper studies the operation of a surface mount technology (SMT) machine which basically consists of three main movable parts: an X–Y table containing a printed circuit board (PCB), ten rotating ‘pick-and-place’ heads and a carriage feeder of reels. The machine inserts electronic components into defined positions on a PCB and the components are supplied from a set of reels each containing a tape of identical components. In the current production setup, the assembly plan comprising both the insertion sequence of components and the placement orders of the reels in the feeder is by human experience. Our study suggests that the problem is computationally difficult for its mathematical optimum with the insertion problem alone being NP-complete. We propose a heuristic solution technique of low computational complexity to find a better assembly plan comprising of the assembly sequence of electronic components and the placement order of the reels in the feeder. The algorithm developed combines the physical constraints of the SMT machine and a ‘grouping’ concept that takes advantage of the natural structure of a PCB. Using multiple reels in the PCB insertion problem are also considered. Simulated results are reported on a set of illustrative data.     

A triple objective function with a Chebychev dynamic pick-and-place point specification approach to optimise the surface mount placement machine

Optimisation can play a major role in improving the throughput of surface mount placement machines. Most previous work has reported on improving only the assembly cycle time. The movement of the feeder carrier and PCB table are not always factors which are minimised. In this paper we introduce a triple objective function with a Chebychev dynamic pick-and-place approach to optimise the sequential pick and place machine. We are focusing on improving the feeder setup. The aims are to minimise the robot assembly time, the feeder movements and the PCB table movements. To provide flexibility to our approach, we integrate three weighted parameters into the triple objective function such that one can vary the importance of each factor to be minimised. Experimental results show that our approach gives good robot assembly time and less movement of the feeder carrier and PCB table.     

Modelling the operations of a component placement machine with rotational turret and stationary component magazine

Two major problems faced in the automated assembly of printed circuit boards are the determination of a component placement sequence and the internal arrangement of the component tapes in the feeder mechanism. The forms of these problems depend mainly on the physical design of the placement machine. The definition and solution of these optimization problems are attempted by many researchers and it is possible to find lots of relevant papers in the literature. However, most of these studies are concentrated on certain machine designs. In this study, the focus is on a particular machine type that has a rotational turret and a stationary component magazine. So far, this type of machine has received little attention among the researchers. The definition of the placement sequencing and feeder configuration problems are given and solution procedures are suggested. The performance of the suggested procedures are tested on real and randomly generated PCB assembly data.     

帐号的聚类分析

本文应用聚类分析的方法分析了银行帐号，对于银行系统选择类似帐号校验码的算法这类问题有参考价值。     

一种随机聚类法

本文给出了一种新的随机聚类法 ,并应用这种方法分析了银行帐号 ,对于银行系统选择帐号校验码的算法这类问题有参考价值 .     

Optimization of control setting and size of shunt capacitors on distribution feeders

Loads on electric utility systems have two components: active power (measured in kilowatts) and reactive power (measured in kilovars). Active power has to be generated at the power plant, whereas reactive power can be provided by either power plants or capacitors. It is a well-known fact that shunt power capacitors are the most economical source to meet the reactive power requirements of inductive loads and transmission lines operating at a lagging power factor.This paper describes new contributions to the problem of optimization of size and control setting of shunt capacitors on distribution feeders, so that the losses along the feeder are minimized. The variation of the KVAR of the load on the feeder with the distance from the substation is assumed to be linear. The parameters of this function are estimated from the available KVAR loading on the feeder first by using least-square techniques and then by using least-absolute-value parameter estimation techniques. The results obtained are compared with that obtained if the current profile is assumed to be uniformly distributed on the feeder. Our results show that the optimum size of the capacitor bank as well as its optimum location depend on the parameters of the model used for the load. Also, our results show a large saving in the size of the capacitor banks used with a considerable per-unit-loss reduction along the feeder.This work was supported by the National Science and Engineering Research Council of Canada, Grant No. A4146. The first author acknowledges the help received from Engineer Samy Soliman for reviewing all the mathematical expressions in this paper.     

A dispatching rule-based approach to production scheduling in a printed circuit board manufacturing system

This paper focuses on a production-scheduling problem in a printed circuit board (PCB) manufacturing system that produces multiple product types with different due dates and different manufacturing processes. In the PCB manufacturing system, there is a number of serial workstations, and there are multiple parallel machines at each workstation. Also, setup operations are required at certain workstations or machines, and some product types have re-entrant flows. We develop new dispatching rules for scheduling at each workstation, considering the special features of PCB manufacturing. With the dispatching rules, we determine not only the start time of each lot at a machine but also the batch size of each product at each machine. Simulation experiments are carried out to test the performance of the production-scheduling method and dispatching rules devised in this study. Results show that the production-scheduling method suggested in this study performs better than methods with well-known dispatching rules and heuristic algorithms for lot sizing in terms of the total tardiness of orders.     

适用于多峰函数优化问题的通用演化算法

本文主要研究了非线性规划中多峰问题的优化求解.通过引入精英库、灭绝再生等,提出了一个适用于求解多峰问题的通用演化算法;并且新算法在四个复杂的多峰函数和一个三十维的整数规划问题上进行了试验,得到了数值结果.     

Berth allocation in container terminals that service feeder ships and deep-sea vessels

This paper treats a berth allocation problem (BAP) in dedicated container terminals where feeder ships and container vessels are jointly served. When assigning quay space and a service time to each calling ship particular focus is put on the container exchange between feeder ships and mother vessels, so that the weighted number of containers delivered by feeder missing their intended mother vessel (and vice versa) does not exceed a given upper bound. The resulting BAP is formalized, complexity proofs are provided, and suited optimization procedures are presented and tested.     

存在借贷资金的随机资金预算问题研究

讨论了企业运用自有资金及银行贷款进行投资时的资金预算问题,与以往的研究不同,本文假设投资支出、年投资收益以及银行贷款都为随机变量,而且,文章的研究并不要求待选的投资项目具有相同的投资期或具有相同的寿命周期.给出了随机环境下净现值收益的期望值模型及期望值目标规划模型,并设计了基于随机模拟的遗传算法,给出了模型的一般解决方法,此外,还提供了两个数值例子,用以说明建模思想,并例证算法的有效性.     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

Solving a real-world vehicle routing problem with multiple use of tractors and trailers and EU-regulations for drivers arising in air cargo road feeder services

In this paper we present two approaches for solving a real-world vehicle routing problem arising in the air cargo road feeder service business. The problem is to combine transportation tasks from a given timetable to trips which have to be assigned to tractors and which can be operated by tractor drivers respecting the restrictive rules on driving times from EC Regulation No. 561/2006. Tractor trips which start and end at the hub can be combined to multiple-trips which are operated by the same tractor. Also, to each trip a trailer has to be assigned which is compatible with all tasks in the trip. The primary objective is to minimize the number of required tractors, i.e. the number of multiple-trips. The methods developed are currently applied in practice.     

Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls

Recently, an increasing number of papers on vehicle routing problems with backhauling has been published. Different types of backhauling problems are discussed. Two of them—the vehicle routing problem with backhauls and so-called ‘mixed loads’ (VRPBM) and the vehicle routing problem with simultaneous delivery and pick-up (VRPSDP)—are closely related. In this paper, we discuss that relationship. Our findings are that previously published results for VRPSDP instances obtained by using a heuristic suggested for the VRPBM do not take into account specific properties of the VRPSDP. As a result of the analysis of the relation between both problem types the possibility of solving the VRPBM by applying an insertion heuristic based on the concept of ‘residual capacities’ originally designed for the VRPSDP is investigated. Numerical results indicate that, for certain instances, this approach is more favourable than the application of a heuristic suggested for the VRPBM in the literature.     

Assessing bank efficiency and performance with operational research and artificial intelligence techniques: A survey

This paper presents a comprehensive review of 196 studies which employ operational research (O.R.) and artificial intelligence (A.I.) techniques in the assessment of bank performance. Several key issues in the literature are highlighted. The paper also points to a number of directions for future research. We first discuss numerous applications of data envelopment analysis which is the most widely applied O.R. technique in the field. Then we discuss applications of other techniques such as neural networks, support vector machines, and multicriteria decision aid that have also been used in recent years, in bank failure prediction studies and the assessment of bank creditworthiness and underperformance.     

Heuristics for Large Constrained Vehicle Routing Problems

This paper presents a heuristic for solving very large routing problems (thousands of customers and hundreds of vehicles) with side constraints such as time windows. When applied to traditional benchmarks (Solomon's), we obtain high quality results with short resolution time (a few seconds). We also introduce a LDS (Limited Discrepancy Search) variation that produces state-of-the-art results. The heart of this heuristic is a combination of a look-ahead insertion algorithm, an incremental local optimization scheme and a constraint solver for constrained traveling salesman problems. The incrementality means that instead of visiting some large neighborhood after an initial solution has been found, a limited number of moves is examined, after each insertion, on the partial solution. This incremental version is not only faster, it also yields better results than using local optimization once a full solution has been built. We also show how additional constraints can be used in order to guide the insertion process. Because of its use of separate CP (Constraint Programming) modules, this method is flexible and may be used to solve large dispatching problems that include many additional constraints such as setup times (asymmetrical distance) or skill matching.     

基于零膨胀模型的我国银企关系规模影响因素研究

银企关系是学术界和实务界关注的焦点之一,然而,国内学者鲜有探讨银企关系数量的影响因素。本文使用我国A股上市公司2006-2013年的银企关系计数资料,利用零膨胀模型对企业建立银企关系规模的影响因素进行了分析。研究发现:规模大、资产负债率高、获利能力强的公司倾向于建立更多的银企关系;企业的长期负债率、第一大股东持股比例,是否是国有产权属性和企业的经营风险与银企关系的规模(数量)显著负相关;信贷合约的期限和信贷金额与银企关系的数量显著正相关;进一步比较了零膨胀模型与Poisson回归、负二项分布回归模型等计数模型,统计检验显示,零膨胀模型比较适合零值过多和过度离散的数据结构资料。     

A Near-Quadratic Algorithm for Fence Design

A part feeder is a mechanism that receives a stream of identical parts in arbitrary orientations and outputs them oriented the same way. Various sensorless part feeders have been proposed in the literature. The feeder we consider consists of a sequence of fences that extend partway across a conveyor belt; a polygonal part P carried by the belt is reoriented by each fence it encounters. We present an O(m + n² log³n)-time algorithm to compute a sequence of fences that uniquely orients P, if one exists, where m is the total number of vertices and n is the number of stable edges of P. We reduce the problem to searching for a path in a state graph that has O(n³) edges. By exploiting various geometric properties of this graph, we show that it can be represented implicitly and that a desired path can be computed in O(m + n² log³n) time. We believe that our technique is quite general and could be applicable to other part-manipulation problems as well.     

A multi-unit tender award process: The case of Transantiago

The Transantiago public transit services were grouped into five trunk service units and 10 feeder units, and were awarded to private operators through a simultaneous tender. To avoid problems of ownership concentration, limits were placed on the maximum number of units per operator. This paper describes the issues involved in such simultaneous multi-unit tenders where various actors bid for different business units to be awarded in a single tender process. The general problem is formulated as a minimum cost network flow problem (MCNFP). Tie-breaking criteria are discussed and modeled. The problem is then solved for the Transantiago case. There follows a discussion of the utility of handling this tender using the tool developed here.     

Feasible insertions in job shop scheduling,short cycles and stable sets

Insertion problems arise in scheduling when additional activities have to be inserted into a given schedule. This paper investigates insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and insertion types. First, a class of scheduling problems is introduced, characterized by disjunctive graphs with the so-called short cycle property, and it is shown that in such problems, the feasible selections correspond to the stable sets of maximum cardinality in an associated conflict graph. Two types of insertion problems are then identified where the underlying disjunctive graph is through- or bi-connected. For these cases, it is shown that the short cycle property holds and the conflict graph is bipartite, allowing to derive a polyhedral characterization of all feasible insertions. An efficient method for deciding whether there exists a feasible insertion, and a lower and upper bound procedure for the minimum makespan insertion problem are developed. For bi-connected graphs, this procedure solves the insertion problem to optimality. The obtained results are applied to three extensions of the classical Job Shop, the Multi-Processor Task, Blocking and No-Wait Job Shop, and two types of insertions, job and block insertion.     

Effect of upper and lower withdrawal limits on queue length

A customer has to make transaction through a bank ATM (automated teller machine) if his withdrawal amount is less than the lower limit of withdrawal through a bank teller, or through a bank teller if his withdrawal amount is greater than the upper limit of withdrawal through an ATM. In order to decrease the long customer queue at counters, a bank increases the lower withdrawal limit and/or the upper one. Through a finite-source queue model, this paper analyzes the effects of the lower and/or upper limits on the length of customer queue at counters. Main conclusions are: (1) A bank may simultaneously shorten the queue at counters and improve satisfaction level of customers by increasing the withdrawal limit through an ATM and/or the one through a bank teller and ameliorating waiting environment; (2) The length of the queue at counters decreases with the number of the customers who are free in selecting service provider, bank teller or ATM.