A hybrid actor and blackboard approach to manufacturing cell control

Cell control forms one level of a hierarchical approach to the control of automated manufacturing systems. This paper describes the application of the artificial intelligence techniques of blackboard and actor-based systems for intelligent cell control in a framework termed Production Logistics and Timings Organizer (PLATO-Z). The blackboards required are described and the implementation is overviewed.The original version of this paper was presented at the 2nd International Symposium on Robotics and Manufacturing (ISRAM), Albuquerque, New Mexico, 16–18 November 1988. The published proceedings of this meeting may be ordered from: CAD Laboratory for Systems/Robotics, EECE Dept., UNM, Albuquerque, NM 87131, U.S.A.     

Knowledge-based process planning for electronic assembly

The conventional method of electronic assembly planning is subjective and depends greatly on the skills, memory, knowledge and experience of the planners. This gives rise to inconsistencies which in turn create problems in the manufacturing environment. Since the computer logics are systematic and consistent, it is conceivable that an automatic electronic assembly planning system would have advances over manual systems. Due to the frequent advances in technology the electronic industry is a very dynamic one. This affects the effectiveness of the current process plans and the applicability of the system that generates them. In this paper important issues which address the automatic generation of process plans will be presented. The framework of a system which takes into account the dynamic nature of the environment will be introduced as an example.The original version of this paper was presented at the 2nd International Symposium on Robotics and Manufacturing (ISRAM), Albuquerque, New Mexico, 16–18 November 1988. The published proceedings of this meeting may be ordered from: CAD Laboratory for Systems/Robotics, EECE Dept., UNM, Albuquerque, NM 87131, U.S.A.     

Learning control system analysis and design based on 2-D system theory

The connections between two research areas, intelligent control systems and multi-dimensional systems, are established. Two-dimensional (2-D) system theory is used to analyze a class of learning control system. The 2-D state-space model of a learning control system is given. A class of learning control laws is proposed and the convergence of the learning process can be checked based on a 2-D model of the learning control system. The theory and methods proposed in this paper not only provide the learning control system with powerful tools for analysis and design, but also offer a multi-dimensional system theory with a new field of application as well as some new problems for further exploration.The original version of this paper was presented at the 2nd International Symposium on Robotics and Manufacturing (ISRAM), Albuquerque, New Mexico, 16–18 November 1988. The published proceedings of this meeting may be ordered from: CAD Laboratory for Systems/Robotics, EECE Dept., UNM, Albuquerque, NM 87131, U.S.A.     

Live remote control of a robot via the Internet

In April 24, 1997, at the International Conference on Robotics and Automation in Albuquerque, an operator pulled a joystick in Albuquerque that controlled the motions of a Puma robot in Tarn's laboratory more than 1,500 kilometers away. The teleoperations feat was a major step for the burgeoning field of robotics, and it was a giant leap for telecommunications, adding a previously unexplored dimension to the Internet-remote control and providing new horizons for other applications in long-distance learning, research opportunities, and hands-on experimentation. The event-based planning and control scheme has been extended to solve the challenging problem in intelligent control of manufacturing systems     

Network-based hybrid genetic algorithm for scheduling in FMS environments

Scheduling in flexible manufacturing systems (FMS) must take account of the shorter lead-time, the multiprocessing environment, the flexibility of alternative workstations with different processing times, and the dynamically changing states. The best scheduling approach, as described here, is to minimize makespan t _M, total flow time t _F, and total tardiness penalty p _T. However, in the case of manufacturing system problems, it is difficult for those with traditional optimization techniques to cope with this. This article presents a new flow network-based hybrid genetic algorithm (hGA) approach for generating static schedules in a FMS environment. The proposed method is combined with the neighborhood search technique in a mutation operation to improve the solution of the FMS problem, and to enhance the performance of the genetic search process. We update the change in swap mutation and the local search-based mutation ration. Numerical experiments show that the proposed flow network-based hGA is both effective and efficient for FMS problems.This work was presented in part at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24–26, 2003     

Revisiting state space exploration of timed coloured petri net models to optimize manufacturing system’s performance

Due to constant fluctuations in market demands, nowadays scheduling of flexible manufacturing systems is taking great importance to improve competitiveness. Coloured Petri Nets (CPN) is a high level modelling formalism which have been widely used to model and verify systems, allowing representing not only the system’s dynamic behaviour but also the information flow. One approach that focuses in performance optimization of industrial systems is the one that uses the CPN formalism extended with time features (Timed Coloured Petri Nets) and explores all the possible states of the model (state space) looking for states of particular interest under industrial scope. Unfortunately, using the time extension, the state space becomes awkward for most industrial problems, reason why there is a recognized need of approaches that could tackle optimization problems such as the scheduling of manufacturing activities without simplifying any important aspect of the real system. In this paper a timed state space approach for properties verification and systems optimization is presented together with new algorithms in order to get better results when time is used as a cost function for optimizing the makespan of manufacturing systems. A benchmarking example of a job-shop is modelled in CPN formalism to illustrate the improvements that can be achieved with the proposed implementations.     

A new hybrid GA solution to combinatorial optimization problems— an application to the multiprocessor scheduling problem

The multiprocessor scheduling problem is one of the classic examples of NP-hard combinatorial optimization problems. Several polynomial time optimization algorithms have been proposed for approximating the multiprocessor scheduling problem. In this paper, we suggest a geneticizedknowledge genetic algorithm (gkGA) as an efficient heuristic approach for solving the multiprocessor scheduling and other combinatorial optimization problems. The basic idea behind the gkGA approach is that knowledge of the heuristics to be used in the GA is also geneticized alongiside the genetic chromosomes. We start by providing four conversion schemes based on heuristics for converting chromosomes into priority lists. Through experimental evaluation, we observe that the performance of our GA based on each of these schemes is instance-dependent. However, if we simultaneously incorporate these schemes into our GA through the gkGA approach, simulation results show that the approach is not problem-dependent, and that the approach outperforms that of the previous GA. We also show the effectiveness of the gkGA approach compared with other conventional schemes through experimental evaluation. This work was presented, in part, at the Second International Symposium on Artifiical Life and Robotics, Oita, Japan, February 18–20, 1997     

An object-oriented approach for multi-objective flexible job-shop scheduling problem

Flexible manufacturing systems are very complex to control and it is difficult to generate controlling systems for this problem domain. Flexible job-shop scheduling problem (FJSP) is one of the instances in this domain. It is a problem which inherits the job-shop scheduling problem (JSP) characteristics. FJSP has additional routing sub-problem in addition to JSP. In routing sub-problem each operation is assigned to a machine out of a set of capable machines. In scheduling sub-problem the sequence of assigned operations is obtained while optimizing the objective function(s). In this paper an object-oriented (OO) approach is presented for multi-objective FJSP along with simulated annealing optimization algorithm. Solution approaches in the literature generally use two-string encoding scheme to represent this problem. However, OO analysis, design and programming methodology help to present this problem on a single encoding scheme effectively which result in a practical integration of the problem solution to manufacturing control systems where OO paradigm is frequently used. OO design of FJSP is achieved by using UML class diagram and this design reduces the problem encoding to a single data structure where operation object of FJSP could hold its data about alternative machines in its own data structure hierarchically. Many-to-many associations between operations and machines are transformed into two one-to-many associations by inserting a new class between them. Minimization of the following three objective functions are considered in this paper: maximum completion time, workload of the most loaded machine and total workload of all machines. Some benchmark sets are run in order to show the effectiveness of the proposed approach. It is proved that using OO approach for multi-objective FJSP contributes to not only building effective manufacturing control systems but also achieving effective solutions.     

Dynamic structuring of distributed manufacturing systems

The paper addresses the problem of dynamic structuring of manufacturing systems. The approach presented in this paper is based on the decomposition of manufacturing objectives and the allocation of tasks to autonomous building blocks, i.e. work systems, in a dynamic environment. The allocation is based on a market mechanism that enables the self-structuring and optimization of a manufacturing system by evaluation and selection among competing work systems. The mechanism presented is based on logic relations and constraints. It enables the building of task-oriented manufacturing structures of work systems acting in series and/or in parallel. The approach is discussed in an example in the part fabrication domain.     

An active learning genetic algorithm for integrated process planning and scheduling

In traditional approaches, process planning and scheduling are carried out sequentially, where scheduling is done separately after the process plan has been generated. However, the functions of these two systems are usually complementary. The traditional approach has become an obstacle to improve the productivity and responsiveness of the manufacturing system. If the two systems can be integrated more tightly, greater performance and higher productivity of a manufacturing system can be achieved. Therefore, the research on the integrated process planning and scheduling (IPPS) problem is necessary. In this paper, a new active learning genetic algorithm based method has been developed to facilitate the integration and optimization of these two systems. Experimental studies have been used to test the approach, and the comparisons have been made between this approach and some previous approaches to indicate the adaptability and superiority of the proposed approach. The experimental results show that the proposed approach is a promising and very effective method on the research of the IPPS problem.     

A genetic algorithm for permutation flow shop scheduling under make to stock production system

The permutation flow shop scheduling is a well-known combinatorial optimization problem that arises in many manufacturing systems. Over the last few decades, permutation flow shop problems have widely been studied and solved as a static problem. However, in many practical systems, permutation flow shop problems are not really static, but rather dynamic, where the challenge is to schedule n different products that must be produced on a permutation shop floor in a cyclical pattern. In this paper, we have considered a make-to-stock production system, where three related issues must be considered: the length of a production cycle, the batch size of each product, and the order of the products in each cycle. To deal with these tasks, we have proposed a genetic algorithm based lot scheduling approach with an objective of minimizing the sum of the setup and holding costs. The proposed algorithm has been tested using scenarios from a real-world sanitaryware production system, and the experimental results illustrates that the proposed algorithm can obtain better results in comparison to traditional reactive approaches.     

A hybrid heuristic to solve the parallel machines job-shop scheduling problem

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.     

Sensor selection for model-based real-time optimization: relating design of experiments and design cost

Real-time optimization systems have become a common tool, in the continuous manufacturing industries, for improving process performance. Typically, these are on-line, steady-state, model-based optimization systems, whose effectiveness depends on a large number of design decisions. The work presented here addresses one of these design decisions and proposes a systematic approach to the selection of sensors to be used by the RTO system. This paper develops a sensor system selection metric based on a trade-off between two approaches to the design of experiments, which is shown to be consistent with the design cost approach of Forbes and Marlin [Computers Chem Eng 20 (1996) 7/7]. The resulting design metric is incorporated into a systematic procedure for RTO sensor selection problem. Finally, the proposed RTO sensor selection procedure is illustrated with a case study using the Williams–Otto [AIEE Trans 79 (1960), 458] plant.     

Hierarchical production planning for complex manufacturing systems

A hierarchical approach to production planning for complex manufacturing systems is presented. A single facility comprising a number of work-centers that produce multiple part types is considered. The planning horizon includes a sequence of time periods, and the demand for all part types is assumed known. The production planning problem consists of minimizing the holding costs for all part types, as well as the work-in-process and the backlogging costs for the end items. We present a two-level hierarchy that is based on aggregating parts to part families, work-centers to manufacturing cells and time periods to aggregate time periods. The solution at the aggregate level is imposed as a constraint to the detailed level problems which are formulated for each manufacturing cell separately. This architecture uses a rolling horizon strategy to perform the production management function. We have employed perturbation analysis techniques to adjust certain parameters of the optimization problems at the detailed level to reach a near-optimal detailed production plan. Numerical results for several realistic example problems are presented and the solutions obtained from the hierarchical and monolithic approaches are compared. The results indicate that the hierarchical approach offers major advantages in computational efficiency, while the loss of optimality is acceptable.     

A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation

Job-shop scheduling problem (abbreviated to JSP) is one of the well-known hardest combinatorial optimization problems. During the last three decades, the problem has captured the interest of a significant number of researchers and a lot of literature has been published, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms (GAs) to address it. The purpose of this paper and its companion (Part II: Hybrid Genetic Search Strategies) is to give a tutorial survey of recent works on solving classical JSP using genetic algorithms. In Part I, we devote our attention to the representation schemes proposed for JSP. In Part II, we will discuss various hybrid approaches of genetic algorithms and conventional heuristics. The research works on GA/JSP provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for JSP may be useful for other scheduling problems in modern flexible manufacturing systems and other combinatorial optimization problems.     

Path-planning and navigation of a mobile robot as discrete optimization problems

There is huge diversity among navigation and path-planning problems in the real world because of the enormous number and great variety of assumptions about the environments, constraints, and tasks imposed on a robot. To deal with this diversity, we propose a new solution to the path-planning and navigation of a mobile robot. In our approach, we formulated the following two problems at each time-step as discrete optimization problems: (1) estimation of a robot's location, and (2) action decision. For the first problem, we minimize an objective function that includes a data term, a constraint term, and a prediction term. This approach is an approximation of Markov localization. For the second problem, we define and minimize another objective function that includes a goal term, a smoothness term, and a collision term. Simulation results show the effectiveness of our approach. This work was presented in part at the Fifth International Symposium on Artificial Life and Robotics, Oita, Japan, January 26–28, 2000     

Integrating the grouping and layout problems in cellular manufacturing systems

In this paper, the simultaneous solution of the machine grouping and layout problems in cellular manufacturing systems is explored. A model for the combined problem is presented. Since the model is complex to solve using traditional optimization techniques, a suboptimal procedure involving the use of a simulated annealing based algorithm is suggested. Results with a numerical example are presented. An alternative formulation based on quandratic assignment problem is also presented.     

基于动态维度交叉的粒子群高维函数优化

提出一种优化高维函数的改进粒子群算法.粒子群算法在高维函数优化方面精度比较低,种群容易陷入停滞,分析粒子群算法在针对高维函数方面难以优化的原因,提出一种基于动态维度交又的改进粒子群算法,通过对五个典型测试函数的仿真,说明该算法具有摆脱较快的收敛能力和较高的收敛精度.     

Mathematical modeling and heuristic approaches to flexible job shop scheduling problems

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problem with traditional optimization approaches owing to the high computational complexity. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e., assignment and sequencing are considered independently, where in integrated approaches, assignment and sequencing are not differentiated. In this paper, a mathematical model and heuristic approaches for flexible job shop scheduling problems (FJSP) are considered. Mathematical model is used to achieve optimal solution for small size problems. Since FJSP is NP-hard problem, two heuristics approaches involve of integrated and hierarchical approaches are developed to solve the real size problems. Six different hybrid searching structures depending on used searching approach and heuristics are presented in this paper. Numerical experiments are used to evaluate the performance of the developed algorithms. It is concluded that, the hierarchical algorithms have better performance than integrated algorithms and the algorithm which use tabu search and simulated annealing heuristics for assignment and sequencing problems consecutively is more suitable than the other algorithms. Also the numerical experiments validate the quality of the proposed algorithms.