A computer program for solving job sequencing problems

A computer method is given for solving n-job, m-machine sequencing problems. The method is an extension of the well known graphical procedure for solving 2-job, m-machine sequencing problems and it is equivalent to finding the shortest path between two nodes in a finite network. The effectiveness of the method in giving an optimal solution, or a good feasible solution, is investigated. It is shown that the method yields good results for flow-shop and job-shop problems. A listing of the computer program is also provided.     

An improved block sequencing method for program restructuring

The execution performance of a program in a virtual memory system is highly dependent on its internal organization. There are several program tools available for reorganizing a program to improve its paging performance. This paper critically analyzes some of the methods in use and proposes a new approach that is experimentally shown to produce better results.     

Pallet operation sequencing based on network part program logic

CAPP systems play a relevant role in aiding planners during setup planning, operation sequencing and pallet configuration activities. The support and automation granted by these techniques, together with the use of non-linear process planning logic, lead to a reduction in the planning time and costs, thus making manufacturers more competitive. This paper presents an approach that integrating process and production planning leads to the definition at the shop-floor level of the optimal operation sequence to machine all of the workpieces on a pallet using a four-axis machine tool. Part programs of non-production movements for each possible sequence of two operations are automatically generated at the shop-floor level and are simulated to obtain the non-production time. The complete sequence of operations is then defined on the basis of the minimisation of the estimated non-production time. This minimisation is performed using a mathematical model that defines a good sequence of operations. Four algorithms are adopted to analyse the proposed solution and to reduce the gap from optimality. The approach is tested on some cases taken from literature and on a real case. The real case was provided by a company that produces mechanical components. The obtained results underline a reduction on production and planning time, and consequently an increment in the company profit.     

基于顺序组件的可共享学习顺序的设计

提出了一种基于IMS简单顺序规范与内容包装规范的可共享学习顺序设计的创新方法,并利用XML的模式实现了该方法.该方法将学习顺序从内容包中分离出来,在一个独立的XML文件中进行设计,形成顺序组件,使得学习顺序能在不同的课件内容包间进行共享与重用.该方法可以有效地解决目前学习顺序规范中,因学习顺序只能在课件内容包中进行设计,并只能在同一内容包中共享与重用,而造成的在不同内容包间存在大量学习顺序重复定义的问题.     

Multi-criteria assembly sequencing

This paper describes the elements of a multi-criteria optimization formulation of the assembly sequencing problem. The criteria considered are: total assembly time and number of reorientations. These two criteria are combined using multi-attribute utility theory to derive a single objective function. The combined objective function has been formulated subject to the precedence constraints of the assembly process. The model has been solved using simulated annealing. The elements of the developed algorithms and their performances are demonstrated in this paper.     

Template-based program verification and program synthesis

Program verification is the task of automatically generating proofs for a program’s compliance with a given specification. Program synthesis is the task of automatically generating a program that meets a given specification. Both program verification and program synthesis can be viewed as search problems, for proofs and programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook programs (e.g., sorting and dynamic programming-based algorithms) and difficult arithmetic programs.     

A simulation sequencing algorithm

In the course of developing a programming project for a course in operating systems, a general purpose language (Burroughs B6700 Algol) possessing concurrency and semaphores was used to provide a process oriented simulation sequencing facility. This facility has been used successfully to simulate several simple operating systems. The facility comprises three procedures along with ‘simulation semaphore’ variables. The first procedure, when called, inserts a simulated time delay into the progress of a simulation model process: the latter two procedures provide a P and a V operation on simulation semaphores, and are used to synchronize processes in a simulation model. The P operation may insert a simulated time delay into the progress of a process. These procedures are explained and presented along with a simple example to show their use.     

Batch sequencing and cooperation

Game theoretic analysis of sequencing situations has been restricted to manufacturing systems which consist of machines that can process only one job at a time. However, in many manufacturing systems, operations are carried out by batch machines which can simultaneously process multiple jobs. This paper aims to extend the game theoretical approach to the cost allocation problems arising from sequencing situations on systems that consist of batch machines. To analyze the allocation problem at hand, it focusses on the existence of core elements, convexity, and the Shapley value.     

Pascal-P,program structure and program behaviour

This note describes some interesting results observed during the implementation of Pascal-P upon a Data General NOVA computer. A significant performance improvement was obtained by altering the program structure of the Pascal-P compiler to reflect the dynamic behaviour of the program. Some implications of this behaviour for the design of computer architectures are discussed.     

The program dependence graph in static program testing

In this paper, new techniques for static program testing are presented. The techniques are based on the program dependence graph, which models the structure of the program in terms of data and control dependences between program instructions. First, a new approach for redundant code detection is proposed. The main idea is based on the observation that each program instruction should have influence on the output of the program, otherwise it is considered redundant. Second, an input-output relationship analysis, which reflects the influence of specific input data on specific output data of the program, is proposed. It is shown that the presented techniques can increase the number of detectable errors as compared with error detection through data flow analysis alone.     

Cassiel: symbolic pulse sequencing

This text presents the motivation and design principles behind the pulse sequencer, a software component used for electronic music composition and performances by Cassiel. The pulse sequencer is a generic, language-based sequence processing engine which can be regarded as an arpeggiator, a sequencer, or anything in between. In fact, arpeggiation and sequencing are special cases of a more general control system. We conclude with some comments about the strengths and weaknesses of the system drawn from several years’ experience in performance projects.     

DNA sequencing and string learning

In laboratories the majority of large-scale DNA sequencing is done following theshotgun strategy, which is to sequence large amount of relatively short fragments randomly and then heuristically find a shortest common superstring of the fragments [26]. We study mathematical frameworks, under plausible assumptions, suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms. We model the DNA sequencing problem as learning a string from its randomly drawn substrings. Under certain restrictions, this may be viewed as string learning in Valiant's distribution-free learning model and in this case we give an efficient learning algorithm and a quantitative bound on how many examples suffice. One major obstacle to our approach turns out to be a quite well-known open question on how to approximate a shortest common superstring of a set of strings, raised by a number of authors in the last 10 years [9], [29], [30]. We give the firstprovably good algorithm which approximates a shortest superstring of lengthn by a superstring of lengthO(n logn). The algorithm works equally well even in the presence of negative examples, i.e., when merging of some strings is prohibited. Some of the results presented in this paper appeared in theProceedings of the 31st IEEE Symposium on the Foundations of Computer Science, pp. 125–134, 1990 [21]. The first author was supported in part by NSERC Operating Grant OGP0046613. The second author was supported in part by NSERC Operating Grants OGP0036747 and OGP0046506.     

Towards weak sequencing for E-LOTOS

In E-LOTOS, a standard process-algebraic language for specification of concurrent and reactive real-time systems, the only form of process sequencing is strong sequencing, meaning that no action of a particular process is ever allowed to occur before complete termination of the preceding process. In the paper, we propose how to enhance the language with weak sequencing, facilitating specification of accelerated action execution, i.e. of partially overlapping processes. Defining an enhanced operational semantics, we formalize the approach for discrete-time basic E-LOTOS processes and give informal guidelines for its generalization to full E-LOTOS.     

The evolution of instruction sequencing

The three distinct phases that constitute the sequencing of an instruction are determining the memory address that contains the instruction, fetching the instruction from memory, and executing the instruction. The evolution of instruction sequencing is traced, with attention focused on the influence of the available technology on the minimum time required for each of these phases and the resulting design decisions. Rather than absolute system performance. the interrelationship of these critical parameters is examined. Memory bandwidth, instruction buffers, caches, and the impact of reduced-instruction-set computers (RISCs) are discussed. Recent innovations are described, and the options and constraints that designers face with respect to future developments are evaluated