DEADLOCK-FREE SCHEDULING METHOD BASED ON PETRI NET AND GA

An efficient algorithm for finding an optimal deadlock-free schedule in amanufacturing system with very limited buffer is presented. This algorithm is based on the effectivegenetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect thetoken player assuring deadlock-free. In order to make the scheduling strategy generated by GA meetthe required constraint of deadlock-free, Petri net is involved to make the implementation of thejob scheduling in an FMS deadlock-free. The effectiveness and efficiency of the proposed approach isillustrated by using an example.

Kind of deadlock-free scheduling method

Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding an optimal deadlock-free schedules in a manufacturing system with very limited buffer is presented. This algorithm is based on the effective genetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect the token player assuring deadlock-free. In order to make the scheduling strategy generated by GA meet the required constraint of deadlock-free, some results of the structure analysis of Petri net are involved as a criterion to select deadlock-free schedule from the population generated by GA. The effectiveness and efficiency of the proposed approach is illustrated by using an example.

MANUFACTURING SYSTEM SCHEDULING BASED ON MULTI-AGENT COOPERATION GAME

Aiming at the flexible manufacturing system with multi-machining and multi-assembly equipment, a new scheduling algorithm is proposed to decompose the assembly structure of the products, thus obtaining simple scheduling problems and forming the cOrrespOnding agents. Then, the importance and the restriction of each agent are cOnsidered, to obtain an order of simple scheduling problems based on the cooperation game theory. With this order, the scheduling of sub-questions is implemented in term of rules, and the almost optimal scheduling results for meeting the restriction can be obtained. Experimental results verify the effectiveness of the proposed scheduling algorithm.

Optimal deadlock avoidance Petri net supervisors for automated manufacturing systems

Deadlock avoidance problems are investigated for automated manufacturing systems with flexible routings. Based on the Petri net models of the systems, this paper proposes, for the first time, the concept of perfect maximal resourcetransition circuits and their saturated states. The concept facilitates the development of system liveness characterization and deadlock avoidance Petri net supervisors. Deadlock is characterized as some perfect maximal resource-transition circuits reaching their saturated states. For a large class of manufacturing systems, which do not contain center resources, the optimal deadlock avoidance Petri net supervisors are presented. For a general manufacturing system, a method is proposed for reducing the system Petri net model so that the reduced model does not contain center resources and, hence, has optimal deadlock avoidance Petri net supervisor. The controlled reduced Petri net model can then be used as the liveness supervisor of the system.

Robust Deadlock Avoidance Policy for Automated Manufacturing System With Multiple Unreliable Resources

This work studies the robust deadlock control of automated manufacturing systems with multiple unreliable resources. Our goal is to ensure the continuous production of the jobs that only require reliable resources. To reach this goal, we propose a new modified Banker's algorithm(MBA) to ensure that all resources required by these jobs can be freed. Moreover,a Petri net based deadlock avoidance policy(DAP) is introduced to ensure that all jobs remaining in the system after executing the new MBA can complete their processing smoothly when their required unreliable resources are operational. The new MBA together with the DAP forms a new DAP that is robust to the failures of unreliable resources. Owing to the high permissiveness of the new MBA and the optimality of the DAP, it is tested to be more permissive than state-of-the-art control policies.

Deadlock prevention for flexible manufacturing system

Deadlock must be prevented via the shop controller during the flexible manufacturing system （FMS） performing. Various models have been tried for the analysis and design of shop controller. Petri net is suitable to describe the dynamic behavior of the discrete event system, such as concurrency, conflict and deadlock, however, the verification of the .system behavior needs structure analysis with complex theoretical proof method. Temporal logic model checking has important advantages over traditional theorem prover. It is flatly automatic and can produce possible counter-example which is particularly important in finding subtle error in complex transition systems. In this paper, a new method for the deadlock prevention based on Petri net and Temporal Logic model checking is presented. The specification in the Temporal Logic is expressed according to some result of structure analysis of the Petri net. The model checking is employed to execute the formal verification, which will conduct an exhaustive exploration of all possible behaviors. Finally, an example is presented to demonstrate how the method works.

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.

Modeling of Agile Intelligent Manufacturing-oriented Production Scheduling System

Agile intelligent manufacturing is one of the new manufacturing paradigms that adapt to the fierce globalizing market competition and meet the survival needs of the enterprises, in which the management and control of the production system have surpassed the scope of individual enterprise and embodied some new features including complexity, dynamicity, distributivity, and compatibility. The agile intelligent manufacturing paradigm calls for a production scheduling system that can support the cooperation among various production sectors, the distribution of various resources to achieve rational organization, scheduling and management of production activities. This paper uses multi-agents technology to build an agile intelligent manufacturing-oriented production scheduling system. Using the hybrid modeling method, the resources and functions of production system are encapsulated, and the agent-based production system model is established. A production scheduling-oriented multi-agents architecture is constructed and a multi-agents reference model is given in this paper.

Event-driven Dynamic and Intelligent Scheduling for Agile Manufacturing Based on Immune Mechanism and Expert System

Based on the biological immune concept, immune response mechanism and expert system, a dynamic and intelligent scheduling model toward the disturbance of the production such as machine fault,task insert and cancel etc. Is proposed. The antibody generation method based on the sequence constraints and the coding rule of antibody for the machining procedure is also presented. Using the heuristic antibody generation method based on the physiology immune mechanism, the validity of the scheduling optimization is improved, and based on the immune and expert system under the event-driven constraints, not only Job-shop scheduling problem with multi-objective can be solved, but also the disturbance of the production be handled rapidly. A case of the job-shop scheduling is studied and dynamic optimal solutions with multi-objective function for agile manufacturing are obtained in this paper. And the event-driven dynamic rescheduling result is compared with right-shift rescheduling and total rescheduling.

A Beam Search-based Algorithm for Flexible Manufacturing System Scheduling

A new algorithm is proposed for the flexible manufacturing system (FMS) scheduling problem in this paper. The proposed algorithm is a heuristic based on filtered beam search. It considers the machines and automated guided vehicle (AGV) as the primary resources. It utilizes system constraints and related manufacturing and processing information to generate machines and AGV schedules. The generated schedules can be an entire scheduling horizon as well as various lengths of scheduling periods. The proposed algorithm is also compared with other well-known dispatching rules-based FMS scheduling. The results indicate that the beam search algorithm is a simple, valid and promising algorithm that deserves further research in FMS scheduling field.

Simultaneous scheduling of machines and automated guided vehicles in flexible manufacturing systems using genetic algorithms

The problem of simultaneous scheduling of machines and vehicles in flexible manufacturing system (FMS) was addressed.A spreadsheet based genetic algorithm (GA) approach was presented to solve the problem.A domain independent general purpose GA was used,which was an add-in to the spreadsheet software.An adaptation of the propritary GA software was demonstrated to the problem of minimizing the total completion time or makespan for simultaneous scheduling of machines and vehicles in flexible manufacturing systems.Computational results are presented for a benchmark with 82 test problems,which have been constructed by other researchers.The achieved results are comparable to the previous approaches.The proposed approach can be also applied to other problems or objective functions without changing the GA routine or the spreadsheet model.

Design of Scheduling Decision Mechanism for Agile Manufacturing System

Design of scheduling decision mechanism is a key issue of scheduling decision method and strategy for agile manufacturing system. Effective scheduling decision mechanism helps to improve the operational agility of manufacturing system. Several scheduling decision mechanisms are discussed, including scheduling forecasting mechanism, cooperation mechanism and cell scheduling mechanism. Also soft decision mechanism is put forward as a promising prospect for agile manufacturing system, and some key techniques in soft decision mechanism are introduced.

Modeling the Scheduling Problem in Cellular Manufacturing Systems Using Genetic Algorithm as an Efficient Meta-Heuristic Approach

This paper presents a new,bi-criteria mixed_integer programming model for scheduling cells and pieces within each cell in a manufacturing cellular system.The objective of this model is to minimize the makespan and intercell movements simultaneously,while considering sequence-dependent cell setup times.In the cellular manufacturing systems design and planning,three main steps must be considered,namely cell formation(i.e,piece families and machine grouping),inter and intra-cell layouts,and scheduling issue.Due to the fact that the cellular manufacturing systems problem is NP-Hard,a genetic algorithm as an efficient meta-heuristic method is proposed to solve such a hard problem.Finally,a number of test problems are solved to show the efficiency of the proposed genetic algorithm and the related computational results are compared with the results obtained by the use of an optimization tool.

Deadlock-free Supervisor Design for Robotic Manufacturing Cells With Uncontrollable and Unobservable Events

In this paper,a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism.First,a Petri net for the deadlock control of such systems is defined.Its admissible markings and first-met inadmissible markings(FIMs)are introduced.Next,place invariants are designed via an integer linear program(ILP)to survive all admissible markings and prohibit all FIMs,keeping the underlying system from reaching deadlocks,livelocks,bad markings,and the markings that may evolve into them by firing uncontrollable transitions.ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition.In addition,the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs.The condition under which the supervisor is maximally permissive in behavior is given.Finally,experimental results with the proposed method and existing ones are given to show its effectiveness.

Research on Flexible Flow⁃Shop Scheduling Problem with Lot Streaming in IOT⁃Based Manufacturing Environment

It is urgent to effectively improve the production efficiency in the running process of manufacturing systems through a new generation of information technology.According to the current growing trend of the internet of things(IOT)in the manufacturing industry,aiming at the capacitor manufacturing plant,a multi-level architecture oriented to IOT-based manufacturing environment is established for a flexible flow-shop scheduling system.Next,according to multi-source manufacturing information driven in the manufacturing execution process,a scheduling optimization model based on the lot-streaming strategy is proposed under the framework.An improved distribution estimation algorithm is developed to obtain the optimal solution of the problem by balancing local search and global search.Finally,experiments are carried out and the results verify the feasibility and effectiveness of the proposed approach.

Optimization Model in Manufacturing Scheduling for the Garment Industry

The garment industry in Vietnam is one of the country’s strongest industries in the world.However,the production process still encounters problems regarding scheduling that does not equate to an optimal process.The paper introduces a production scheduling solution that resolves the potential delays and lateness that hinders the production process using integer programming and order allocation with a make-to-order manufacturing viewpoint.A number of constraints were considered in the model and is applied to a real case study of a factory in order to viewhowthe tardiness and latenesswould be affected which resulted in optimizing the scheduling time better.Specifically,the constraints considered were order assignments,production time,and tardiness with an objective function which is to minimize the total cost of delay.The results of the study precisely the overall cost of delay of the orders given to the plant and successfully propose a suitable production schedule that utilizes the most of the plant given.The study has shown promising results that would assist plant and production managers in determining an algorithm that they can apply for their production process.

The Cloud Manufacturing Resource Scheduling Optimization Method Based on Game Theory

In order to optimize resource integration and optimal scheduling problems in the cloud manufacturing environment,this paper proposes to use load balancing,service cost and service quality as optimization goals for resource scheduling,however,resource providers have resource utilization requirements for cloud manufacturing platforms.In the process of resource optimization scheduling,the interests of all parties have conflicts of interest,which makes it impossible to obtain better optimization results for resource scheduling.Therefore,amultithreaded auto-negotiation method based on the Stackelberg game is proposed to resolve conflicts of interest in the process of resource scheduling.The cloud manufacturing platform first calculates the expected value reduction plan for each round of global optimization,using the negotiation algorithm based on the Stackelberg game,the cloud manufacturing platformnegotiates andmediateswith the participants’agents,to maximize self-interest by constantly changing one’s own plan,iteratively find multiple sets of locally optimized negotiation plans and return to the cloud manufacturing platform.Through multiple rounds of negotiation and calculation,we finally get a target expected value reduction plan that takes into account the benefits of the resource provider and the overall benefits of the completion of the manufacturing task.Finally,through experimental simulation and comparative analysis,the validity and rationality of the model are verified.

A TQCS-based Scheduling Approach for Manufacturing Grid

With Open Grid Service Architecture (OGSA) as system framework, and Globus Toolkit3.0 (GT3) as developing tools, Manufacturing Grid (MG) is proposed in this research to realize resource sharing and collaborative working among manufacturing resources, and task scheduling is one of the most critical components in this system. Nevertheless, the Globus Resource Allocation Manager (GRAM) does not provide scheduling system by default, and traditional performance-guided or economy-guided schedulers cannot satisfy our needs in MG. So, in this paper, a TQCS (Time, Quality, Cost, Service)-based scheduling approach is presented and the corresponding scheduler (Manufacturing Grid Task Scheduler, MGTS) is implemented with the functions of Global Process Planning (GPP) analyzing, resource discovery, resource selection, AHP (Analytic Hierarchy Process)-based resource mapping, and fault-tolerant handling. Furthermore, the application architecture is depicted at the end of the paper to illustrate the utilization of our scheduler.

Location Selection and Scheduling Optimization of Material Storage in Manufacturing Workshop

Based on improved immune algorithm, the location of material storage in manufacturing workshop is studied. Intelligent optimization algorithms include particle swarm optimization algorithm, genetic selection algorithm, simulated annealing algorithm, tabu search algorithm and so on. According to the non-linear constraints, the objective function is established to solve the minimum energy consumption of material distribution. The improved immune algorithm can solve the complex problem of manufacturing workshop, and the material storage location and scheduling scheme can be obtained by combining simulation software. Scheduling optimization involves material warehousing, sorting, loading and unloading, handling and so on. Using the one-to-one accurate distribution principle and MATLAB software to simulate and analyze, the location of material warehousing in manufacturing workshop is determined, and the material distribution and scheduling are studied.

IMPROVED ACO SCHEDULING ALGORITHM BASED ON FLEXIBLE PROCESS

An improved ant colony optimization （ACO） algorithm is utilized in cell scheduling of the flexible manufaturing process for considering the instrument constraint, manufacturing cost and time. Firstly, the initial weighted directional diagram is set up. Secondly, the algorithm based on the dynamic pheromone updating ensures the quick convergence and the optimal solution, thus improving the feasibility and the stability of the schedule system. Aiming at reducing collaboration with external partners, decreasing the total cost and balancing the production process, the algorithm is efficient in supporting the management process of the manufacturing cell and in strengthening the information arrangement capabitity of the scheduling system. Finally, experimental results of the improved algorithm are compared with those of other algorithms.