Single courier single restaurant meal delivery (without routing)

We investigate optimization models for meal delivery that do not involve routing. We focus on the simplest case, with a single restaurant and a single courier, and reduce it to the throughput maximization single machine scheduling problem, with release times and bounded slacks. In the meal delivery setting, slacks are small for QoS purposes and we indeed show that the scheduling problem can be solved in polynomial time when slacks are bounded. We discuss extensions to more couriers and restaurants.     

Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

中国人CD59cDNA克隆、序列分析及其表达

用ＲＴ－ＰＣＲ方法从中国人胚胎总ｍＲＮＡ中扩增出４２０ｂｐ人补体终末阶段同源限制因子（ＣＤ５９）的ｃＤＮＡ，序列分析结果表明，所获得的ＣＤ５９ｃＤＮＡ与文献报道中的基因序列完全一致，含ＣＤ５９全长编码区．构建了真核表达质粒，在３Ｔ３细胞中得到了表达．     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

A survey of surface mount device placement machine optimisation: Machine classification

The optimisation of a printed circuit board assembly line is mainly influenced by the constraints of the surface mount device (SMD) placement machine and the characteristics of the production environment. This paper surveys the characteristics of the various machine technologies and classifies them into five categories (dual-delivery, multi-station, turret-type, multi-head and sequential pick-and-place), based on their specifications and operational methods. Using this classification, we associate the machine technologies with heuristic methods and discuss the scheduling issues of each category of machine. We see the main contribution of this work as providing a classification for SMD placement machines and to survey the heuristics that have been used on different machines. We hope that this will guide other researchers so that they can subsequently use the classification or heuristics, or even design new heuristics that are more appropriate to the machine under consideration.     

Batching in single operation manufacturing systems

We introduce a new decision problem important to the efficient operation of resources in manufacturing systems. This problem of ‘batching’ is considered for single machine activities. It is shown that even for these simple models, lot splitting may occur and that these batching decisions may have a dramatic impact on the manufacturing lead time of items to be processed.     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

Graph algorithms for DNA sequencing – origins,current models and the future

With the ubiquitous presence of next-generation sequencing in modern biological, genetic, pharmaceutical and medical research, not everyone pays attention to the underlying computational methods. Even fewer researchers know what were the origins of the current models for DNA assembly. We present original graph models used in DNA sequencing by hybridization, discuss their properties and connections between them. We also explain how these graph models evolved to adapt to the characteristics of next-generation sequencing. Moreover, we present a practical comparison of state-of-the-art DNA de novo assembly tools representing these transformed models, i.e. overlap and decomposition-based graphs. Even though the competition is tough, some assemblers perform better and certainly large differences may be observed in hardware resources utilization. Finally, we outline the most important trends in the sequencing field, and try to predict their impact on the computational models in the future.