Search

This article proposes a novel and efficient dual-space co-evolutionary memetic algorithm (DCMA) to tackle a practical hybrid differentiation flowshop scheduling problem with limited buffer constraints. In this scheduling problem, jobs are divided into different types and each job consists of multiple parts. The manufacturing of a job involves three stages: 1) parts fabrication on first-stage parallel machines; 2) parts assembly on second-stage single machine; and 3) job differentiation on one of third-stage dedicated machines. Due to the assembly operation and limited buffers between adjacent stages, deadlock and blocking will occur. We formulate the problem and present a deadlock handling policy to guarantee all schedules feasible. Then, we propose the DCMA metaheuristic to approximate the optimal solutions in acceptable time. Global exploration of DCMA is performed by a hybrid of three parts: 1) a continuous optimizer to be executed in continuous search space; 2) a discrete optimizer to be executed in combinatorial solution space; and 3) a meta-Lamarckian learning-based selection mechanism for adaptively determining that which optimizer is more suitable for current global exploration campaign. To balance exploration and exploitation, three problem-special local search strategies are presented, which collaborates with each other and are adaptively started to avoid high computational costs. The effect of parameter setting on DCMA is checked by the Taguchi method of design of experiment. The computational experiments demonstrate the effectiveness of DCMA special designs, and show that DCMA performs better than the existing algorithms for the considered problem.

This research presents an original and efficient elite archive-assisted adaptive memetic algorithm (EAMA) to deal with a realistic hybrid differentiation flowshop scheduling problem (HDFSP) with the objective of total completion time minimization. In this scheduling problem, each job consists of multiple parts and the jobs are divided into different types. The manufacturing of a job is comprised of three consecutive stages: parts fabrication on first-stage parallel machines, parts assembly on second-stage single machine, and job differentiation on one of third-stage dedicated machines. We provide a mixed integer programming model, derive three lower bounds, and further present the EAMA metaheuristic for HDFSP. The EAMA is initialized heuristically, and its global exploration is performed by a differential evolution which includes three newly designed operators: elite-driven discretized differential mutation, probability crossover and biased selection. To enhance the local search, an external elite archive is set and evolved in parallel with global exploration by a meta-Lamarckian learning-based adaptive multi-stage local search and a variable length-based adaptive block-insertion local search. After the global exploration and local exploitation, an elite sharing strategy is used to exchange the excellent information between population and elite archive, and an adaptive restart strategy is used to diversify the population. The influence of parameter setting on EAMA is surveyed by using an improved design-of-experiment. The statistical results from extensive computational experiments demonstrate the effectiveness of the special designs and show that EAMA performs more efficient than the existing algorithms in solving the problem under consideration.

This article focuses on the problem of deadlock for sequential automated manufacturing systems (AMSs) that allow for the general resource allocation and flexible routings. A class of Petri nets, systems of sequential systems with shared resources (S4PR), are used to model these considered AMSs. Our previous work has showed that deadlocks in S4PR are characterized by saturated perfect activity-circuit (PA-circuit). In this article, we divide all saturable PA-circuits into two categories: 1) dependent and 2) independent. An algorithm is proposed to compute all independent saturable PA-circuits. We prove that by adding a monitor for each independent PA-circuit to ensure that it is not saturated, all dependent PA-circuits cannot be saturated either and deadlocks in S4PR are successfully prevented. The presented method simplifies the structure of the deadlock controller without imposing tight constraints on the system. Finally, the proposed controller is illustrated by some examples.

Scheduling of assembly manufacturing systems has received much attention in recent years, but the scheduling problem of deadlock-prone flexible assembly systems (FASs) is rarely studied. Based on the Petri net models of FASs, this article studies the scheduling problem of deadlock-prone FASs, and the heuristic beam search (HBS) algorithm is proposed to minimize the makespan. In HBS, the state space of the FAS is searched level by level, and two types of evaluation functions are proposed to ensure that only the most promising states are explored. To find a better solution in an acceptable time, the HBS algorithm is integrated with the iterative policy, and the iterative widen heuristic beam search (IWHBS) algorithm is obtained. Experimental and comparison results validate the effectiveness and superiority of the IWHBS algorithm over other heuristic search algorithms.

This article addresses the scheduling problem of deadlock-prone flexible manufacturing systems subject to no-wait constraints for the first time, and develops a new scheduling algorithm based on the place-timed Petri net (PN) model and heuristic search. The considered problem can be solved by two procedures: 1) timetabling and 2) sequencing. The timetabling is to translate a given job sequence into a feasible schedule that satisfies the deadlock-free and no-wait constraints. A novel timetabling algorithm based on the controlled PN model is then proposed for solving it. The goal of sequencing is to find a job sequence so that the makespan of the corresponding schedule is the minimum. To this end, a hybrid heuristic search (HHS) is developed by combining the ${A}$ * algorithm and dynamic window. Two new heuristic functions are designed to guide the search, and the dynamic window is used to limit the searched space. The performance of HHS with different heuristic functions and deadlock controllers is evaluated by ten instances. The computational results demonstrate that through the proposed approach, optimal or suboptimal feasible schedules can be obtained within a reasonable time.

This paper investigates the exponential synchronization analysis of master–slave chaotic uncertain delayed generalized reaction-diffusion neural networks (GRDNNs) with event-triggered control scheme. A delay GRDNNs system model for the analysis is constructed by investigating the effect of the network transmission delay. By constructing a novel Lyapunov–Krasovskii functional and using a delay system approach for designing event-triggered controllers and some inequality techniques like Jensen’s inequality, Wirtinger’s inequality and Halanay’s inequality, the criteria are obtained for the event-triggered synchronization analysis and control synthesis of delayed GRDNNs. The synchronization criteria are formulated in terms of linear matrix inequalities. Finally, we conclude that the slave systems synchronize with the master systems. Two examples show the proposed theoretical results are feasible and effective.

In the context of customization and personalization, the multistage fine-manufacturing system has become emerging in modern manufacturing industries. In this study, the scheduling problem of such a system called distributed hybrid differentiation flowshop scheduling problem is addressed for the first time to minimize makespan. The manufacturing process has three dedicated stages, including distributed fabrication for jobs, assembly from jobs to products, and further differentiation for products to meet customized requirements. Due to the scheduling complexity of the problem, the evolutionary algorithm is designed. First, the population is initialized heuristically and divided into three subpopulations with different identities based on the quality. The identity will be transited dynamically along with evolution. Second, a distributed heterogeneous global exploration strategy is designed to coevolve three subpopulations. According to identity differences, different subpopulations will choose their suitable learning operators and learning strengths to make full use of superior search knowledge. Third, to enhance search intensification, a problem-specific local exploitation strategy consisting of a variable neighborhood local search and a random block local search is devised and carried out adaptively. Fourth, by organizing the global exploration and local exploitation, a novel distributed heterogeneous co-evolutionary algorithm (DHCA) is proposed. The effect of parameter setting on DHCA is investigated by design-of-experiment and computational experiments are carried out to evaluate the algorithm. The results validate the effectiveness of special designs and show that DHCA are more effective and efficient than the compared state-of-the-art algorithms in solving the considered problem.

Deadlock-free scheduling and control is critical for optimizing the performance of flexible assembly systems (FASs). Based on the Petri net models of FASs, this paper integrates a deadlock prevention policy with local search and develops a novel deadlock-free scheduling algorithm. A solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the deadlock prevention policy, a repairing algorithm (RA) is developed to repair unfeasible chromosomes. A perturbation strategy based on estimation of distribution algorithm is developed to escape from local optima. Moreover, to improve population diversity, an acceptance criterion (AC) based on Pareto dominance is proposed. The chromosome representation, RA, perturbation strategy, and AC together support the cooperative aspect of local search for scheduling problems strongly.

It has been an active research area to develop robust supervisory control policies for production systems with unreliable resources. So far, most methods for robust deadlock resolution apply only to systems without flexible routes, where each processing step of any part type requires a unique prespecified resource. In this paper, we address deadlock avoidance control problem in production systems with both failure-prone resources and flexible routings, which allow that a part has options when deciding the resource acquisition at each step. This paper presents properties that a controller with robustness must satisfy. Specifically, at any system reachable state, neither the failed resources nor part instances trapped in these resources should have too much detrimental effect on the other portions of the system. Thus, the full range of part types’ production could be assured at all time. After defining the notions of reduced system and reduced state with respect to unreliable resources, we identify and prove conditions for determining whether or not the state resulting from the occurrence of an event is feasible. Subsequently, we develop a method for robust deadlock avoidance, which uses the solutions to state safety checking problem for the reduced production system with only reliable resources. An illustrative example shows the effectiveness of this method. Finally, we conduct a comparison investigation of some representative approaches in the literature about robust supervisory control for deadlock resolution in resource allocation systems with routing flexibility.

Recently, the problem of robust control for automated manufacturing systems (AMSs) with unreliable resources receives increasing attentions. Almost all the existing related works are only concerned with the failure-prone AMSs in which each part stage utilizes only one unit of resources. While, in real-world AMS, it is often necessary to use multiple units of different resources to complete a part. This paper focuses on the robust control of such complex AMSs with a type of unreliable resources. General Petri nets are used to model all the behavior of such AMSs. By adding a control place to the Petri net models for each considered siphon, we develop robust deadlock controllers for the considered AMS. Such a robust controller ensures that the parts of all types can be processed continuously through any of its processing routes, even if one of the unreliable resources fails. Finally, some examples are used to illustrate the proposed method.

In the context of automated manufacturing systems (AMSs) with unreliable resources, most existing robust deadlock controllers have high computational complexity or relatively low permissiveness. This work focuses on the deadlock control problem of AMSs with a kind of unreliable resources. Petri nets are used to model the dynamic behaviors of such failure-prone AMSs. First a robust deadlock prevention controller is developed for a large class of AMSs under consideration. Such a robust controller guarantees that the system can process all types of parts continuously through any one of their routes, even if one of unreliable resources fails. Also, this robust controller is proved to be optimal, i.e., maximally permissive, during one resource failure period. Then by using the one-step look-ahead method, we establish a polynomial-complexity robust deadlock avoidance policy (DAP) with the same permissiveness as the obtained robust deadlock prevention controller. That is, such a robust DAP not only has low computational complexity, but also is maximally permissive during one resource failure period.

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 &#x0028 MBA &#x0029 to ensure that all resources required by these jobs can be freed. Moreover, a Petri net based deadlock avoidance policy &#x0028 DAP &#x0029 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.

This paper focuses on the liveness analysis and deadlock control for automated manufacturing systems (AMSs) with multiple resource requirements. Such an AMS is modeled by a class of generalized Petri nets called systems of simple sequential processes with multiple resources (S3PMR). It is shown that a deadlock of the considered AMSs can be characterized by the saturation of a structural object in S3PMR, called perfect resource transition-circuit (PRT-circuit). As a consequence, an S3PMR is live if and only if no PRT-circuit is saturated at any reachable marking. To ensure the system liveness, one has to prevent all PRT-circuits from being saturated at all reachable markings. To develop a structurally simple Petri net deadlock controller, we present the concept of an effective transition cover, which is a special subset of PRT-circuits that may be saturated. Then by designing a control place with a proper control variable for each PRT-circuit in an effective transition cover, we obtain a deadlock controller for the system. The needed control variables are determined by an integer linear program. Since the number of PRT-circuits in an effective transition cover is much less than that of all PRT-circuits that need to control, our controller is of small structural size. For an AMS with saturable PRT-circuits, there exists at least a transition cover. An algorithm is presented for checking the effectiveness of transition covers, and transforming noneffective transition covers into effective ones. Finally, some examples are used to illustrate the proposed method.

This article focuses on the production scheduling problem in the flexible job shop (FJS) environment with limited buffers. Limited manufacturing resources and buffers may lead to blockage and deadlock phenomenon. In order to establish production scheduling with minimum makespan, the timed Petri net (PN) model of a production process is established. Based on this PN model, a novel Hybrid Estimation-of-Distribution Algorithm (HEDA) is proposed for solving the considered scheduling problem. A candidate solution for the problem is coded as an individual that consists of a route sequence for processing jobs and a permutation with repetition of jobs. A deadlock prevention policy is used to check the feasibility of individuals, such that it can be decoded into a feasible sequence of transitions, i.e., a feasible schedule. By using an effective voting procedure of elite individuals, two probability models in HEDA corresponding to different subsections of individuals are constructed. Based on the probability models, offspring individuals are then produced. As an improvement strategy, simulated-annealing-based local search is designed and incorporated into HEDA to enhance the entire algorithm’s search ability. The proposed hybrid HEDA is tested on FJS examples. The results show its feasibility and effectiveness.

This paper studies a novel and practical distributed flexible assembly permutation flowshop scheduling problem with makespan criterion, which has attracted wide attention due to important applications in modern manufacturing. The problem integrates two machine environments of distributed production and flexible assembly, which can process and assemble the jobs into customized products. We first present a mixed integer linear programming model to characterize the problem essence and to solve small-size problems. Due to the NP-hard, we further propose an efficient memetic algorithm, which consists of a global exploration optimizer designed based on improved social spider optimization and two local exploitation optimizers designed based on meta-Lamarckian learning and simplex search, respectively. To implement the algorithm, a problem-specific encoding scheme is presented. Algorithmic parameters are calibrated by a design of experiments, and a comprehensive computational campaign is conducted to evaluate the performance of the mathematical model and algorithms. Statistical results show that their problem-solving abilities are effective, and especially the proposed memetic algorithm outperforms the existing algorithms significantly.

This paper presents a liveness analysis method for sequential automated manufacturing systems (AMSs), which can be modeled by a class of Petri nets named systems of sequential systems with shared resources (S4PR). We show that deadlocks in S4PR can be characterized by the saturation of its structural object named a perfect activity circuit (PA-circuits). Thus, S4PR is live if and only if no PA-circuits in it is saturated at all reachable states. A PA-circuits of an S4PR may not be saturated at any state; hence, we propose an integer linear program (ILP) to determine whether a PA-circuits can be saturated or not. Then an algorithm is proposed to compute the set of PA-circuits that may be saturated. This presented method nontrivially generalizes deadlock characterization and liveness condition of ordinary Petri nets to a broader class of nonordinary ones. Note to Practitioners —In the context of AMS, liveness is the most important property since it implies that there is no partial deadlock during the system evolution, and hence, all part types can be produced smoothly. We study the problem of liveness for AMS with the most general resource allocation and flexible routing, which can be modeled by S4PRs or disjunctive/conjunctive (D/C) resource allocation systems (RASs). Given such a complex AMS, based on its Petri net model, this paper presents a sufficient and necessary liveness condition by utilizing the structural properties, and develops an algorithm to identify all the structural objects that may lead the systems to deadlocks. This paper is significant in liveness-enforcing supervisor design for S4PR.

This paper addresses the distributed limited-buffer flowshop scheduling problem with makespan minimization criterion for the first time. The manufacturing layout consists of multiple homogeneous factories and each one is set as a permutation flowshop with limited buffers between any two adjacent machines. Compared with traditional single shop scheduling, this problem is more realistic because of the distribution and limited buffer constraints. Given that the NP-hardness, this paper focuses on the approximate approaches, and successively proposes two constructive heuristics for generating fast schedule and providing good initialization of meta-heuristics, a differential evolution algorithm run in continuous search space to further better the so-obtained schedules, and a discrete differential evolution algorithm implemented directly in combinatorial search space. Extensive experimental results validate that the performance of discrete differential evolution perform the best and other algorithms proposed in this paper are all with satisfactory evaluations.

This paper considers the multiobjective scheduling of flexible manufacturing systems (FMSs). Due to high degrees of route flexibility and resource sharing, deadlocks often exhibit in FMSs. Manufacturing tasks cannot be finished if any deadlock appears. For solving such problem, this work develops a deadlock-free multiobjective evolutionary algorithm based on decomposition (DMOEA/D). It intends to minimize three objective functions, i.e., makespan, mean flow time, and mean tardiness time. The proposed algorithm can decompose a multiobjective scheduling problem into a certain number of scalar subproblems and solves all the subproblems in a single run. A type of a discrete differential evolution (DDE) algorithm is also developed for solving each subproblem. The mutation operator of the proposed DDE is based on the hamming distance of two randomly selected solutions, while the crossover operator is based on Generalization of Order Crossover. Experimental results demonstrate that the proposed DMOEA/D can significantly outperform a Pareto domination-based algorithm DNSGA-II for both 2-objective and 3-objective problems on the studied FMSs.

This paper proposes robust deadlock prevention controllers for automated manufacturing systems (AMSs) with a type of unreliable resources, and the aim is to ensure that the parts of all types can be processed continuously through any of their processing routes, even if one of unreliable resources fails. These AMSs under consideration can be modeled by Petri nets , where deadlocks are characterized by strict minimal siphons (SMSs). The design of our robust controller consists of two stages. The first stage, called SMS-based control, adds a control place to the original net for each SMS so as to prevent it from being emptied even if one of unreliable resources fails. This controller is maximal permissive for preventing all SMSs from being emptied during one resource failure period. Since some so-called augmented-siphon is created after the first stage, the second stage, called augmented-siphon-based control, is required. This stage adds a control place to each minimal augmented-siphon with its output arcs pointing to the source transitions of the system such that no new siphon is created. In addition, an algorithm based on mix integer programming (MIP) is used to find all minimal augmented-siphons. Finally, some examples are used to illustrate the proposed method.

Based on the Petri net (PN) models of the flexible manufacturing systems (FMSs), this paper focuses on solving the scheduling problem of minimizing the total energy consumption of FMSs. In the view of different energy consumption rates of resources under different working statuses, two energy consumption functions are considered. The dynamic programming (DP) models of the scheduling problems based on PNs are established, where a reachable marking of a PN model, start processing time vector, route vector, and the transition sequence leading to the reachable marking from the initial one, is regarded as a state, and the Bellman equation is based on transition firing. For small-size scheduling problems, their optimal solutions can be obtained by the presented DP algorithm. However, it is difficult to solve larger-scale ones since the number of explored states increases exponentially with the problem size, which makes DP computationally infeasible. To obtain an optimal or suboptimal schedule in an acceptable time, modified DP (MDP) algorithm is proposed, in which fewer states are explored. In MDP, two ways are introduced through which only the most promising states are explored. One is keeping only one transition sequence for each marking through an evaluation function. Another is selecting the most promising states in each stage for further exploration through a heuristic function. To guarantee that the generated states are safe, a deadlock controller is applied in the recursion procedure of MDP. Experimental results on manufacturing systems and comparisons with existing works are provided to show the effectiveness of MDP. Note to Practitioners —This paper is motivated by the need of optimizing the energy consumption of manufacturing systems, considering the increasing energy cost and environmental concerns. Existing studies on energy optimization rarely focus on flexible manufacturing systems (FMSs) which exhibit a high degree of resource sharing and route flexibility and can be highly adaptable to various production plans and goals. Scheduling becomes more challenging when facing deadlock-prone FMSs. This paper provides a method to solve this complex scheduling problem efficiently. In this paper, dynamic programming (DP) is formulated for it, and the optimal energy consumption schedules are found. Considering the computational burden of implementing DP in the scheduling of large-size FMSs, a novel scheduling method named modified DP (MDP) is proposed. Experimental tests on an FMS and a stamping system suggest that MDP can successfully find feasible solutions. Besides, it can be applied to other FMS scheduling problems and industrial cases, once their processing time of operations and energy consumption of resources per unit time are known.

This paper studies the distributed two-stage assembly flowshop problem with separate setup times, which is a generalisation for the regular two-stage assembly flowshop problem in the distributed manufacturing environment. The optimization objective is to find a suitable job schedule such that the criterion of total completion time is minimized. To deal with such a problem, we propose a novel memetic algorithm (MA) based on a recently developed social spider optimization (SSO). To the best of our knowledge, it is the first effort to explore the SSO-based MA (MSSO) and to apply SSO in the field of combinational optimization. In the proposed MSSO algorithm, we first modify the original version of SSO to adapt to the distributed problems, and then integrate two improvement techniques, problem-special local search and self-adaptive restart strategy, within MA framework. In the numerical experiment, the parameters used in MSSO are calibrated and suitable parameter values are suggested based on the Taguchi method. Experimental results and comparisons with the existing algorithms validate the effectiveness and efficiency of the proposed MSSO for addressing the considered problem. In addition, the effect of problem scale parameters on MSSO and the effectiveness of the proposed improvement techniques are also investigated and demonstrated.

This article proposes hybrid branch and bound algorithms to minimise the makespan for the two-stage assembly scheduling problem with separated setup times. In the studied problem, there are multiple machines at the first stage, each of which produces a component of a job. When all components are available, a single assembly machine at the second stage completes the job. Existing algorithms are based on the state space search and hence suffer from the state space explosion problem. In order to reduce the search space, lower and upper bounds for a partial schedule are proposed. Also, a heuristic function and a dominance rule are developed to guide the search process. Moreover, accelerated factors are introduced to increase the speed of the search. Experimental results indicate that our algorithms outperform an existing method, and can find the optimal or near-optimal schedules in a short time for all tested problems with up to ten thousand jobs and nine first-stage machines.

Blockage and deadlock are undesirable in an automated manufacturing system (AMS). Thus, addressing these issues is essential to ensure smooth production evolution via system supervisory control. If an AMS contains unreliable resources which may break down unexpectedly, then the situation is complicated and problems become challenging. This work investigates the robust supervision for such AMSs from the perspective of management and control of resource allocation. The ultimate goal of this study is to develop a controller for allocating buffer space, such that any failure does not propagate through blocking to stall the rest of the system. In other words, the continual production of every part type not requiring any of the failed resources must be guaranteed at all time. We propose a supervisory control policy that satisfies the above desired property by using formal tools of automata and Petri nets. The policy relaxes the assumption made in previous work that each part type requires at most one failure-prone resource in the predefined production route. Meanwhile, the policy execution and implementation do not need any central buffers. We also present a survey and some comparative studies of various approaches in the literature about robust supervision for deadlock resolution in AMSs.

A novel fuzzy control scheme with adaptation algorithms is developed for robot manipulators’ system. At the beginning, one adjustable parameter is introduced in the fuzzy logic system, the robot manipulators system with uncertain nonlinear terms as the master device and a reference model dynamic system as the slave robot system. To overcome the limitations such as online learning computation burden and logic structure in conventional fuzzy logic systems, a parameter should be used in fuzzy logic system, which composes fuzzy logic system with updated parameter laws, and can be formed for a new fashioned adaptation algorithms controller. The error closed-loop dynamical system can be stabilized based on Lyapunov analysis, the number of online learning computation burdens can be reduced greatly, and the different kinds of fuzzy logic systems with fuzzy rules or without any fuzzy rules are also suited. Finally, effectiveness of the proposed approach has been shown in simulation example.

Efficient deadlock controllers are critical in the operation of automated manufacturing systems. This work focuses on a deadlock control problem for flexible assembly systems (FAS). Petri nets are used to model the systems. Through their liveness analysis, it characterizes two kinds of structural objects. Each object can lead to a siphon, and may cause the system to deadlock. Based on such objects, a necessary and sufficient condition about the liveness of Petri net models is obtained. In order to prevent each such object from causing FAS to deadlock, a Petri net controller is designed such that its induced siphon cannot be empty. The conjunction of all these controllers is proved to be capable of ensuring deadlock-free operation of a large class of FAS. The effectiveness of the proposed approach is shown via an FAS example.

This paper focuses on the scheduling problem of flexible assembly systems (FASs) without intermediate buffers. The main characteristic of the problem is that as no intermediate buffer exists between consecutive machines, blocking and deadlock constraints must be considered. Petri nets are used to model the considered FASs, and a novel hybrid particle swarm optimization (HPSO) algorithm is proposed to minimize the makespan. The proposed algorithm is the combination of the discrete PSO, particle repairing algorithm, particle improvement strategy, and local search method. First, each candidate solution for the problem is encoded as a permutation with repetition of part numbers, and can be uniquely decoded into a sequence of transitions. To ensure the feasibility of solutions, a repairing algorithm is developed, in which a deadlock avoidance policy is used. Then, a particle improvement policy is proposed to improve the performance of particles. Meanwhile, a local search method is designed and incorporated into HPSO to improve its search ability. Experiments are conducted to verify the effectiveness of the particle improvement policy and local search method. Comparisons between HPSO and ten other algorithms are performed. The comparison results and analysis show that our proposed algorithm can find feasible solutions for all tested instances, and is superior to other scheduling algorithms in terms of finding better solutions and performance stability.

The scheduling problems under distributed production or flexible assembly settings have achieved increasing attention in recent years. This paper considers scheduling the integration of these two environments and proposes an original distributed flowshop scheduling problem with flexible assembly and set-up time. Distributed production stage is deployed several homogeneous flowshop factories that process the jobs to be assembled into final products in the flexible assembly stage. The objective is to find a schedule, including a production subschedule for jobs and an assembly subschedule for products, to minimise the makespan. Such a scheduling problem involves four successive decisions: assigning jobs to production factories, sequencing jobs at every factory, designating an assembly machine for each product and sequencing products on each assembly machine. The computational model is first established, and then a constructive heuristic (TPHS) and two hybrid metaheuristics (HVNS and HPSO) are proposed. Numer...

So far, the majority of deadlock control policies for automated manufacturing systems (AMSs) are based on the assumption that no resource fails; while for AMSs with unreliable resources, the main concerns are deadlock avoidance problems. This paper focuses on the robust deadlock prevention problem for AMSs with a type of unreliable resources, and assumes that at most one of unreliable resources fails at a time. Petri net is introduced to model the considered AMS. Deadlock can be characterized in terms of maximal perfect resource transition-circuits (MPRT-circuits). To develop robust Petri net deadlock controllers with small structures for the system, a new concept of strong transition covers is presented, which is a special kind of transition covers. By designing a control place with a proper control variable to each MPRT-circuit in the strong transition cover, a 1-robust Petri net controller is obtained, whereas the control variables can be determined by an integer linear programming. Such a 1-robust controller ensures that the system can process all types of parts infinitely even if one of unreliable resources fails. Since the number of MPRT-circuits in a strong transition cover is much less than that of all MPRT-circuits, our Petri net controller is of small structural size. Each AMS with a type of unreliable resources has at least a transition cover. An algorithm is presented for checking the strongness of transition covers, and transforming weak transition covers into strong ones. Finally, some examples are given to illustrate the effectiveness of the proposed method.

Display OmittedBased on the Petri net models of flexible manufacturing systems, this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies, and two hybrid heuristic search algorithms for deadlock-free scheduling of FMSs are proposed. Deadlock control and scheduling for flexible manufacturing system is integrated.Deadlock control policy is embedded into the heuristic search algorithm.Two hybrid deadlock-free scheduling algorithms for flexible manufacturing system are proposed. Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.

Take total energy consumption of flexible manufacturing systems as an objective.Consider two ways of dividing resources states.Two energy consumption functions are proposed.Deadlock situation is avoided by adopting an optimal deadlock avoidance policy.Experiments on a typical FMS and an industrial stamping system are provided. In recent years, there has been growing interest in reducing energy consumption and emissions of manufacturing systems. Except for adopting new equipment or techniques, scheduling is crucial to reduce the total energy consumption of manufacturing systems. This paper focuses on the scheduling problem for flexible manufacturing systems (FMSs) with the objective of minimizing the total energy consumption, and proposes a novel scheduling algorithm for FMSs based on Petri net models and genetic algorithm. Considering that energy consumptions in different states of resources are different, this paper takes two ways for calculating total energy consumptions. In the proposed genetic algorithm, a potential schedule is represented by a chromosome consisting of route selection and operation sequence. Crossover and mutation operations are performed on the operation sequence to guarantee the population diversity. For deadlock-prone FMSs, not all chromosomes can be directly decoded to a feasible schedule. To check the feasibility of chromosomes and convert infeasible chromosomes into feasible ones, a repair algorithm is developed with the help of the deadlock avoidance policy. Experiment results on a typical FMS and an industrial stamping system are provided to show the effectiveness of our proposed scheduling algorithm.

In this paper, we propose hybrid reaction–diffusion Cohen–Grossberg neural networks (RDCGNNs) with variable coefficients and mixed time delays. By using the Lyapunov–Krasovkii functional approach, stochastic analysis technique and Hardy inequality, some novel sufficient conditions are derived to ensure the pth moment exponential stability of hybrid RDCGNNs with mixed time delays. The obtained sufficient conditions are relevant to the diffusion terms. The results of this paper are novel and improve some of the previously known results. Finally, two numerical examples are provided to verify the usefulness of the obtained results.

Supervisory control that ensures deadlock-free and nonblocking operation has been an active research area of manufacturing engineering. So far, most of deadlock control policies in the existing literature assume that allocated resources are reliable. Additionally, a large number of methods are for systems of simple sequential processes with resources (S3PRs), where a part uses only one copy of one resource at each processing step. In contrast, we investigate the automated manufacturing systems (AMSs) that can be modeled by a class of Petri nets, namely S*PUR. S*PUR is a generalization of the S*PR Petri net model, while S*PR is a superclass of S3PR. This work addresses the robust supervision for deadlock avoidance in S*PUR. Specifically, we take into account unreliable resources that may break down while working or being in idle, and the considered AMSs allow the use of multiple copies of different resources per operation stage. Our objective is to control the system so that: 1) when there are breakdowns, the system can continue producing parts of some types whose production does not need any failed resources; and 2) given the correction of all faults, it is possible to complete all the on-going part instances remaining in the system. We illustrate the characteristics of a desired supervisor through several examples, define the corresponding properties of robustness, and develop a control policy that satisfies such properties.

Over the past two decades, the development of supervisory controllers that guarantee deadlock-free operation for automated manufacturing systems (AMSs) has been an active area of research. Most work to date assumes that the system resources are reliable. This paper focuses on the robust supervisory control problem of AMSs with a single unreliable resource. Our objective is to develop a robust supervisory control policy under which the system can continue producing in the face of the unreliable resource’s failure or recovery. To do so, we integrate an optimal deadlock avoidance policy based on a Petri net with a modified Banker’s Algorithm and present a novel robust supervisory control policy. It is proven to be of polynomial complexity and more permissive than two existing policies. Also, experimental results on a set of AMSs generated randomly indicate its superiority over all other existing policies.