Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

Economic design of unit load-based FMSs employing AGVs for transport

A methodology to economically configure an automated guided vehicle based flexible manufacturing system (FMS) in terms of machine and material handling requirements is presented. The procedure uses the concept of simultaneous design to determine the number of machines required at each workstation in the FMS and the number of automated guided vehicles required to service the material handling needs of the system. The technique integrates decisions on machine requirements, vehicle requirement, and vehicle/container carrying capacity into a single cost model. Solution to the model automatically yields the best resource configuration for the shop that achieves the set production target while minimizing total manufacturing cost. A hybrid algorithm that combines numerical search, simulation, and statistical analysis is employed for solving the problem. The application of the design procedure is demonstrated with an example problem. Sensitivity analysis on machine and vehicle requirements due to changes in job attributes and unit transport quantities are also performed.     

Coloured timed Petri net model for real-time control of automated guided vehicle systems

Automated guided vehicle systems (AGVS) are material-handling devices representing an efficient and flexible option for products management in automated manufacturing systems. In AGVS, vehicles follow a guide-path while controlled by a computer that assigns the route, tasks, velocity, etc. Moreover, the design of AGVS has to take into account some management problems such as collisions and deadlocks. The paper presents a novel control strategy to avoid deadlock and collisions in zone-controlled AGVS. In particular, the control scheme manages the assignments of new paths to vehicles and their acquisition of the next zone. Moreover, the use of coloured Petri nets is proposed to model the dynamics of AGVS and implement the control strategy stemming from the knowledge of the system state. Additionally, extending the coloured Petri net model with a time concept allows investigation of system performance. Several simulations of an AGVS with varying fleet size while measuring appropriate performance indices show the effectiveness of the proposed control strategy compared with an alternative policy previously presented.     

AGV dispatching based on workload balancing

We consider a manufacturing job shop with automated guided vehicles. Such a system is characterized by several complex features such as the random pattern of material flows between machines, the limited capacity of machine buffers, shop deadlock phenomena, floating bottlenecks, etc. We will describe a heuristic procedure for the control of materials flows and automated guided vehicles in such a system. The procedure is based on the idea of workload balancing; it tries to balance the workload among machines as well as the workload between the machines and the transporters. A deadlock prevention algorithm is embedded in the procedure. We then present the results of simulation experiments to evaluate the performance of the proposed procedure.     

Performance evaluation of an auction-based manufacturing system using coloured Petri nets

The next generation of manufacturing systems is assumed to be intelligent enough to make decisions and automatically adjust to variations in production demand, shop-floor breakdowns etc. Auction-based manufacturing is a control strategy in which various intelligent entities in the manufacturing system bid themselves, accept bids and make selections among the bids available based on a heuristic. This paper deals with the simulation modelling and performance evaluation of a push-type auction (negotiation) based manufacturing system embedded in a pulltype production system using coloured Petri nets. Three different models of an auction-based manufacturing system have been discussed. This methodology helps in developing systems for real-time control, anticipation of deadlocks, and evaluation of various performance metrics like machine utilization, automated guided vehicle (AGV) utilization, waiting times, work in process (WIP) etc. Various decision-making rules were identified for the real-time control of auction-based manufacturing systems.     

Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net model

This paper addresses the problem of deadlock control in automated guided vehicle (AGV) systems for automated manufacturing systems with unidirectinal guided paths. First, a Petri net (PN) model was developed for the problem. Then, by using the PN model developed, the condition for deadlock-free operation in AGV system and a control law are presented. To avoid deadlocks in AGV systems by this law, one needs only to observe the state of the system and check the number of free spaces available in some of the circuits. It is estimated that the proposed control law is simple enough to be used in the real-time control of contemporary system configuration. Three examples are used to show the application and efficiency of the proposed control law.     

A multi-attribute dispatching rule for automated guided vehicle systems

This paper considers the dispatching problem associated with operations of automated guided vehicles (AGVs). A multi-attribute dispatching rule for dispatching of an AGV is developed and evaluated. The multi-attribute rule, using the additive weighting method, considers three system attributes concurrently: the remaining space in the outgoing buffer of a workstation, the distance between an idle AGV and a workstation with a job waiting for the vehicle to be serviced, and the remaining space in the input buffer of the destination workstation of a job. A neural network approach is used to obtain dynamically adjusting attribute weights based on the current status of the manufacturing system. Simulation analysis of a job shop is used to compare the multi-attribute dispatching rule with dynamically adjusting attribute weights to the same dispatching rule with fixed attribute weights and to several single attribute rules. Results show that the multi-attribute dispatching rule with the ability to adapt attribute weights to job shop operational conditions provides a better balance among the performance measures used in the study.     

A structured approach to deadlock detection,avoidance and resolution in flexible manufacturing systems

Production scheduling models that determine part mix ratios and detailed schedules do not usually account for deadlocks that can be caused by part flow. Deadlocks must be prevented for operational control (especially in automated systems). The major thrust of this paper is in developing a structured model for deadlock detection, avoidance and resolution caused by part flow in manufacturing systems. A system status graph can be constructed for the parts currently in the system. Deadlock detection amounts to determining deadlocks in the system status graph. On the other hand, deadlock avoidance amounts to restricting parts movement so that deadlocks are completely avoided in the future. While deadlock detection is a one-step look ahead procedure, deadlock avoidance is a complete look ahead procedure. Deadlock resolution or recovery amounts to judiciously using a limited queue to recover from deadlocks. Deadlock detection and avoidance are absolutely crucial to uninterrupted operation of automated manufacturing systems. A model based in graph theory has been formulated to detect and avoid deadlocks in automated manufacturing systems.     

Requests network model for deadlock detection and avoidance in automated manufacturing systems

A modern competitive environment requires rapid and effective responses to varying production demands with shorter life cycles. A feasible solution to cope with such unpredictable situations is to introduce an automated manufacturing system characterized by high flexibility, autonomy and cooperation. Much research has been done on negotiation-based scheduling and control under the distributed control architecture due to its operational flexibility and scalability. Despite many advantages, the probability of the system stalling at a deadlock state is high. Specifically, it is difficult to detect impending part flow deadlocks within the system. A system request network model is defined here to analyse various deadlock situations. Request cycles are then identified by a virtual part flow control mechanism. No request cycle in the system request network represents ‘no system deadlock’. For any request cycle, a deadlock analysis is performed. If any request cycle exists that represents either a part flow deadlock or an impending part flow deadlock, then the system will be deadlocked. The proposed model can analyse all types of impending part flow deadlocks. Furthermore, it is more efficient through the reduction of search space, is applicable to various configurations and is less restrictive in dynamic shop floor control.     

Design and operation of single-loop dual-rail inter-bay material handling system

Asynchronized automated material handling systems, e.g. automated electrified monorail systems and automated guided vehicle systems, have been playing important roles in manufacturing. Reliability becomes a critical issue as manufacturing enterprises are moving toward automation. In the past, reliability tissue has not been analysed explicitly for these types of systems. In this research, a new measure was proposed to specify reliability. A mixed integer programming model was developed to design flow paths for a special class of material handling systems, i.e. single-loop dual-rail systems. The model can be used to design systems with higher reliability. The model and application procedure in design and analysis were demonstrated through two case studies.     

A model for the design of zone control automated guided vehicle systems

An analytical modelling strategy is proposed as a screening device for use prior to the simulation phase in the design of zone control automated guided vehicle systems (AGVS). The proposed model predicts the effects of the major AGVS design variables on system-performance measures including maximum throughput capacity and risk factors associated with shop locking. This is done through a process which specifically evaluates the system operating dynamics associated with vehicle fleet size, guidepath layout, workstation storage capacity, routeing, and, to a less precise extent, vehicle dispatching. Operating dynamics are defined to include vehicle blocking resulting from guidepath contention and variation of in-process storage levels. The objective of the analytical model is to reduce the extent of simulation modelling necessary to design a zone-control AGVS for a given materials-handling workload. The model is illustrated for a sample AGVS with variation in the fleet size, workstation storage capacity and dispatching rule demonstrated.     

A formal control-theoretic model of a human–automation interactive manufacturing system control

This paper describes a human–automation interactive manufacturing system and presents a formal model for describing and controlling the system. The model presented in this paper considers a system from two perspectives: structural and operational perspectives. Human and an automated controller are considered agents that cooperate to achieve given goals by executing assigned tasks. A human–automation interaction is described with a particular communication model between two agents that exchanges messages. A system control schema and human tasks are modelled separately and then integrated in a formal manner using a modified communicating finite state machine framework. An interface model that coordinates the message exchanges between two agents is then introduced. An automated shop floor control system with a human material handler is modelled with the proposed framework and a simple illustrative example is provided.     

Impact of empty vehicle flow on performance of single-loop AGV systems

With the increasing trend in the use of automated guided vehicles systems (AGVS) in manufacturing, the need for design tools becomes greater. The problem is that optimized static design models do not ensure expected performance due to the difficulty in capturing the dynamic operational characteristics of the vehicle system. This study shows that by using the single-loop guide path configuration some of the dynamic features of the system, like the impact the empty vehicle flow has on the system's performance, is reduced. Thus, a more reliable prediction of system performance is achieved     

Job shop control

The paper defines batch or job shop production and reviews the functions of production planning and production control in a job shop manufacturing situation. It argues that the separation of planning and control has resulted in the artificial isolation of the sequencing problem in job shop research. It attempts to redefine the production control function for a job shop, now called job shop control, and discuss the activities it involves. The major decision-making problems associated with job shop control are highlighted and an objective function of costs to aid in management decision making is evolved.     

A max-algebra approach to the robust distributed control of repetitive AGV systems

This paper presents a new approach for distributed control of automatic guided vehicle systems (AGVS) that uses max-algebra formalism to model system operation. The proposed method differs from previous works on performance analysis and control of such systems in that it constructs a feasible schedule by exploiting the repetitive character of the flow of automated guided vehicles. The AGVS is treated as a distributed system composed of autonomous and repetitive processes of AGV flows. Its periodic behaviour follows from the type of operation characterizing the job shops considered. The proposed approach employs a concept of asynchronous traffic semaphores that provide the local mechanism for vehicle flow synchronization. Setting the timing of particular semaphores results in distributed control of vehicle flows possessing self-synchronization capabilities.     

Loading and control policies for a flexible manufacturing system

An experimental investigation of operating strategies for a computer-controlled flexible manufacturing system is reported. The system is a real one, consisting of nine machines, an inspection station and a centralized queueing area—all interconnected by an automatic material-handling mechanism. The operating strategies considered involve policies for loading (allocating operations and tooling to machines) and real-time flow control. A detailed simulation was employed to test alternatives. The results are different from those of classical job shop scheduling studies, showing the dependence of system performance on the loading and control strategies chosen to operate this flexible manufacturing system. Loading and control methods are defined that significantly improve the system's production rate when compared to methods which were previously applied to the system. Finally, some conclusions are presented concerning the control of these automated systems.     

Applying Job Shop Scheduling to SMEs Manufacturing Platform to Revitalize B2B Relationship

A small and medium enterprises (SMEs) manufacturing platform aims to perform as a significant revenue to SMEs and vendors by providing scheduling and monitoring capabilities. The optimal job shop scheduling is generated by utilizing the scheduling system of the platform, and a minimum production time, i.e., makespan decides whether the scheduling is optimal or not. This scheduling result allows manufacturers to achieve high productivity, energy savings, and customer satisfaction. Manufacturing in Industry 4.0 requires dynamic, uncertain, complex production environments, and customer-centered services. This paper proposes a novel method for solving the difficulties of the SMEs manufacturing by applying and implementing the job shop scheduling system on a SMEs manufacturing platform. The primary purpose of the SMEs manufacturing platform is to improve the B2B relationship between manufacturing companies and vendors. The platform also serves qualified and satisfactory production opportunities for buyers and producers by meeting two key factors: early delivery date and fulfillment of processing as many orders as possible. The genetic algorithm (GA)-based scheduling method results indicated that the proposed platform enables SME manufacturers to obtain optimized schedules by solving the job shop scheduling problem (JSSP) by comparing with the real-world data from a textile weaving factory in South Korea. The proposed platform will provide producers with an optimal production schedule, introduce new producers to buyers, and eventually foster relationships and mutual economic interests.     

Hybrid simulated annealing with memory: an evolution-based diversification approach

This study presents an efficient metaheuristic approach for combinatorial optimisation and scheduling problems. The hybrid algorithm proposed in this paper integrates different features of several well-known heuristics. The core component of the proposed algorithm is a simulated annealing module. This component utilises three types of memories, one long-term memory and two short-term memories. The main characteristics of the proposed metaheuristic are the use of positive (reinforcement) and negative (inhibitory) memories as well as an evolution-based diversification approach. Job shop scheduling is selected to evaluate the performance of the proposed method. Given the benchmark problem, an extended version of the proposed method is also developed and presented. The extended version has two distinct features, specifically designed for the job shop scheduling problem, that enhance the performance of the search. The first feature is a local search that partially explores alternative solutions on a critical path of any current solution. The second feature is a mechanism to resolve possible deadlocks that may occur during the search as a result of shortage in acceptable solutions. For the case of job shop scheduling, the computational results and comparison with other techniques demonstrate the superior performance of the proposed methods in the majority of cases.     

Performance evaluation of tandem and conventional AGV systems using generalized stochastic Petri nets

This paper investigates the different policies and concepts followed in the traffic management of automated guided vehicle (AGV) systems, and develops the controls for automatically eliminating potential vehicle conflicts in an AGV system. The planning of the AGV system is performed in such a way that there are no conflicts or deadlocks for the vehicles using stochastic Petri nets (SPNs). The major effort is devoted to determining the benefits of the tandem AGV control in comparison with the conventional AGV control method. SPNs have been used to model the different designs of flexible manufacturing systems (FMSs) and with different policies for the movement of material, vehicle path control, inventory planning and tool control. The SPN model is solved and the performance of the system can be evaluated. In this study, the effort is directed to model an FMS with two different types of AGV traffic management methods, namely the conventional and tandem AGV control. A SPN program is used which takes the FMS Petri net model as the input and evaluates the different properties of the Petri net. Finally the performance measures are obtained, which helps in evaluating and comparing the two different AGV traffic management methods.     

Potentials for bi-directional guide-path for automated guided vehicle based systems

Most current applications of automated guided vehicle systems (AGVS) in manufacturing shop environments employ uni-directional guide-paths for vehicle routing despite the fact that bi-directional vehicles exist. In this paper comparisons and issues regarding unidirectional and bi-directional flows are presented. Also presented is a model of a bi-directional traffic flow guide-path. The effect of the traffic flow pattern on the shop throughput is demonstrated and compared to that of a uni-directional flow system of an equivalent facility. The model is implemented using computer simulation.