Although the paradigm of Cyber-Physical Systems (CPS) enable manufacturers to respond to challenges in the dynamic business environment, it relies on an effective resource allocation mechanism to optimize production processes. In the past years, the production processes optimization problem in CPS has been formulated and solved by applying discrete version of Particle Swarm Optimization (PSO) called DPSO and binary Differential Evolution (DE) called BDE. The DPSO algorithm is based on a transformation function that maps real values into discrete values. The BDE algorithm uses mutation mechanism that create mutant vectors based on logical operations on individuals in the population without relying on a transformation function. In this paper, another discrete version of Differential Evolution (DE) called DDE is proposed and applied to optimize production processes in CPS. We conduct experiments to compare these algorithms based on numerical results.

One of the reason that hinders ridesharing from acceptance by general public is due to the safety concern to share a vehicle. Recently, the problem to meeting trust requirements in ridesharing systems has been formulated. As this problem is a complex discrete decision problem, it can be solved by metaheuristic algorithms. In the literature, one solution algorithm based on Particle Swarm Optimization (PSO) and another solution algorithm based on Firefly algorithm were developed to solve this problem. The goal of this study is to develop another solution algorithm based on Differential Evolution (DE) approach and compare the proposed algorithm with PSO and Firefly algorithms. Several mutation strategies in DE approach have been implement to solve the optimization problems. We evaluate the DE based algorithms by conducting experiments. We analyze the results to illustrate effectiveness of the DE based algorithms.

Due to the capability to effectively deal with changing demand and uncertainty, Cyber-Physical Systems (CPS) emerge as a paradigm for manufacturers to face challenges in the real business environment based on dynamic configuration of resources such as machines and robots. CPS relies on the development of an effective mechanism to make resources collaborate to meet the requirements of production processes. How to develop a mechanism for dynamic configuration of resources in CPS is an important issue. Motivated by this need, this paper aims to propose a methodology to support dynamic teaming between resources such as machines and robots in CPS. In this paper, we propose a method to achieve dynamic teaming of resources in CPS based on evolutionary computation approach and multi-agent system (MAS) architecture. To facilitate specification of production process and capabilities of resources, a modeling method based on Petri nets is adopted. A problem is formulated to meet the requirements of production processes based on Petri net models. Two evolutionary computation algorithms, one based on Particle Swarm Optimization (PSO) approach and the other based on binary Differential Evolution (DE) approach, have been developed to solve the problem. We illustrate and compare effectiveness of the proposed algorithms by examples.

Although combinatorial double auctions make buyers and sellers trade goods more conveniently, the winner determination problem (WDP) in combinatorial double auctions poses a challenge due to computation complexity. Differential evolution (DE) is a competitive evolutionary algorithm widely adopted to deal with complex optimization problems. In this paper, a combinatorial double auction problem with transaction costs, supply constraints and non-negative surplus constraints is considered. The WDP of combinatorial double auction problem is formulated as an integer programming problem. To deal with computational complexity of the WDP for combinatorial double auctions, we propose an algorithm for finding solutions based on two variants of discrete DE approach. The effectiveness of the proposed algorithm is also demonstrated by several numerical examples.

Carpooling is an effective transport model that can significantly reduce transportation costs. The problem to match passengers with drivers is a difficult problem due to complex constraints to be satisfied in the solution processes. The goals of this paper are to propose a model and a solution methodology that is seamlessly integrated with existing geographic information system to determine drivers/passengers for ride sharing. In this paper, we formulate a car pooling problem and propose a solution algorithm for it based on a meta-heuristic approach. Differential evolution (DE) is a competitive evolutionary algorithm widely utilized in the science and engineering fields. The simple and straightforward evolving mechanisms of DE endow it with the powerful capability to solve optimization problems. To achieve the goal, we first formulate the carpooling optimization problem as an integer programming problem. We then develop variants of DE algorithm for it. We also conduct experiments to illustrate and compare effectiveness of the proposed DE algorithms.

Car pooling is a collective transportation model based on shared use of private cars. The objective of car pooling is to reduce the number of cars in use by grouping people. By exploiting car pooling model, it can significantly reduce congestion, fuel consumption, air pollution, parking demands and commuting costs. This paper aims to develop a prototype car pooling system to match passengers and drivers based on their trajectories. We propose a heuristic method to solve the car pooling problem. In our approach, we collect the trajectory data of passengers and drivers first. We then propose a matching algorithm to assign passengers to drivers' cars based on their trajectories. The car pooling system proposed in this study combines a matching algorithm that is seamlessly integrated with Google Maps API, dynamic web pages and database system. We also conduct experiments to illustrate our proposed method.

Reconfigurable Manufacturing Systems (RMS) is a paradigm to flexibly deal with frequent changing demand and technologies. With the advancement of technology and more and more sensors and machines are connected, the world quickly enter the era of Internet of Things (IoT), which provides infrastructure for RMS. However existing studies lack a formalism that provides a framework for the development of RMS, from modeling, design to implementation. In particular, an important issue is design of dynamic process planner for RMS. This paper focuses on the development of a dynamic process planning method for the development of RMS. Modeling and managing RMS in manufacturing sector are challenging issues due to the complex workflows in the system. Recent progress in artificial intelligence and bio-inspired optimization technology provides a solid background to develop a framework to provide dynamic process planning for RMS in IoT-enabled manufacturing environment. In this paper, we propose a process planning method based on multi-agent systems (MAS) using Petri Nets to specify the workflows and capabilities of resources in the system and develop a solution algorithm based on a meta-heuristic method to solve the process planning problem based on discrete Particle swarm optimization (DPSO) approach The proposed method is illustrated by a several examples.

Transportation costs constitute an important part in delivering goods to customers and have a significant influence on competitive advantage of a company. How to reduce transportation costs. Vehicle routing is a critical factor in reducing transportation costs. An effective scheme to manage fleets and determine vehicle routes for delivering goods is important for carriers to survive. In the existing literature, a variety of capacitated vehicle routing problems (VRP) have been studied. Although VRP has been extensively studied, most research results focus on one single carrier. How to achieve lower transportation costs through cooperation of carriers while fulfilling the customers' requests is an important issue. This paper aims to propose a framework to support cooperation of carriers based on a clustering algorithm and discrete particle swarm optimization (DPSO) method. To address this issue, we propose two decision models for two carriers. In the first decision model, each carrier makes decisions independently by applying the DPSO method. In the second decision model, two carriers cooperate by applying a clustering algorithm first to divide all the requests into two clusters, one cluster for each carrier, and then apply the DPSO method to each carrier to determine the routes for the corresponding cluster of requests. We have developed a simulation environment to conduct experiments to compare the performance for these two decision models. The simulation results indicate that the cooperative decision outperforms that of the independent decision model.

Although combinatorial auctions have been extensively studied, the factor of transportation cost for delivering goods from the seller to the winners (buyers) is ignored in most of the existing literature. The existence of transportation cost may not only influence decision making but also may lead to suboptimal solutions. Furthermore, ignoring transportation cost may result in discrepancy between the expected revenue and the actual revenue of the seller. Motivated by the discussion above, the goals of this paper are to propose a decision support model that considers transportation cost in combinatorial auctions, develop an associated solution methodology with and study the influence of transportation cost on combinatorial auctions. To achieve these goals, we propose two models for handling transportation cost in combinatorial auctions, one model considers transportation cost in determining the winners whereas the other does not take transportation cost into account in determining winners but calculates the transportation cost based on the solution obtained. We formulate the problems for these two models, develop solution algorithms and compare the two models by conducting an experiment based on our proposed algorithm.

Due to sophisticated and frequently changing demands from customers, global competition and technological advances, the next generation advanced manufacturing technologies will rely on cooperation and collaboration of business partners to share costs, risks and expertise as no single company has all the expertise needed. To respond to these challenges, development of an effective scheme for managing collaborative workflows is required. In this paper, we propose a framework to achieve coherent and consistent workflows that can meet order requirements based on multi-agent systems (MAS). Scheduling collaborative workflow is a challenging problem due to the computational complexity involved, distributed architecture and dependency of different partners' workflows. We propose an approach that combines MAS, contract net protocol, workflow models and optimization theories. We have implemented a prototype system based on industrial standards, including FIPA and the Petri net workflow specification model. Our solution algorithm has been developed based on transformation of the workflow model to optimization models to find the solutions.

In procurement, a buyer who wants to obtain some goods at the lowest possible cost can hold a reverse auction to try to obtain the goods from a set of sellers who can provide the goods. If there is complementarity or substitutability between the goods, a combinatorial reverse auction can be beneficial. Each seller places bids for each bundle of goods he can provide. The problem is to determine the winners. In this paper, we consider a winner determination problem in which a buyer wants to acquire items from a set of sellers to process the task on hand. The task requires a minimal set of items for executing the operations. Each seller owns a set of items to bid for the task. The problem is to determine the winners to minimize the total cost to acquire the required items. The main results include: (1) a problem formulation for the combinatorial reverse auction problem; (2) a solution methodology based on Lagrangian relaxation; (3) an economic interpretation and (4) specification of the requirements for the implementation of our solution algorithms.

Many manufacturing systems are formed by interconnection of assembly and/or disassembly subprocesses. How to develop effective methodologies to analyze the dynamic behaviours of the overall processes is a challenge due to the complexity. We consider manufacturing processes formed based on flexible interconnection of assembly/disassembly subprocesses. A non-ordinary flexible assembly/disassembly Petri net (NFADPN) model based on non-ordinary Petri nets has been proposed for this class of systems. To quickly respond to resource failures, we concentrate on robustness analysis for NFADPN. Robustness analysis provides an alternative way to analyze a perturbed system without re-analysis. Although we have analyzed the robustness properties of several subclasses of assembly Petri nets, the subclass of NFADPN has not been considered. In this paper, we will extend robustness analysis to NFADPN by exploiting its structure. We identify several patterns of resource failures and characterize the conditions to maintain operation in the presence of resource failures.

We propose a controlled assembly Petri net with alternative route (CAPN-AR) model for a class of flexible assembly processes with alternative routes and unreliable resources. Alternative routes significantly enhance the reliability through the routing flexibility of the system. It is not required for a CAPN-AR to be live to maintain production. For this reason, we propose the concept of persistent production for the CAPN-AR. However, alternative routes also add complexity to the analysis of the systems. As the PNs grow rapidly with the scale of the problem, an existing reachability-tree method is feasible only for small nets. We propose an analysis method that can scale with the problems based on structural decomposition of the CAPN-AR. We study the conditions for persistent production, propose a deadlock avoidance algorithm with polynomial complexity for CAPN-AR, and access its robustness property with respect to resource failures.

Resource failure is a common problem in real systems. In case of resource failures, reanalysis of the perturbed system is required. Robustness analysis provides an alternative way to analyze a perturbed system without re-analysis. Robustness analysis aims to provide a quick and effective way to deal with resource failures in the systems. In our previous research, we have analyzed the robustness of several subclasses of ordinary controlled Petri nets. However, robustness of non-ordinary controlled Petri nets has not been studied. In this paper, we will extend the robustness analysis to non-ordinary controlled Petri nets.

Although a variety of techniques have been proposed in literature to deal with deadlocks in assembly processes, there is a lack of research on reconfigurability property for flexible assembly processes with alternative processes and unreliable resources. In this paper, we study the reconfigurability property for a class of flexible assembly processes based on the controlled assembly Petri net with alternative routes (CAPN-AR) we proposed previously. Based on this model, we proposed a reconfigurable control algorithm for CAPN-AR based on structural decomposition.

Unreliable resources pose challenges in design of deadlock avoidance algorithms as resources failures have negative impacts on scheduled production activities and may bring the system to dead states or deadlocks. This paper focuses on the development of a suboptimal polynomial complexity deadlock avoidance algorithm that can operate in the presence of unreliable resources for assembly processes. We formulate a fault-tolerant deadlock avoidance controller synthesis problem for assembly processes based on controlled assembly Petri net (CAPN), a class of Petri nets (PNs) that can model such characteristics as multiple resources and subassembly parts requirement in assembly production processes. The proposed fault-tolerant deadlock avoidance algorithm consists of a nominal algorithm to avoid deadlocks for nominal system state and an exception handling algorithm to deal with resources failures. We analyze the fault-tolerant property of the nominal deadlock avoidance algorithm based on resource unavailability models. Resource unavailability is modeled as loss of tokens in nominal Petri Net models to model unavailability of resources in the course of time-consuming recovery procedures. We define three types of token loss to model 1) resource failures in a single operation, 2) resource failures in multiple operations of a production process and 3) resource failures in multiple operations of multiple production processes. For each type of token loss, we establish sufficient conditions that guarantee the liveness of a CAPN after some tokens are removed. An algorithm is proposed to conduct feasibility analysis by searching for recovery control sequences and to keep as many types of production processes as possible continue production so that the impacts on existing production activities can be reduced.

Although there are some existing results addressing the deadlock avoidance problem in assembly systems with un-reliable machines, there is still a lack of research for assembly processes with alternative production routes and failure prone machines. This paper extends our previous results to cope with unreliable resource in assembly systems with routing flexibility. Our results include: (1) a controlled assembly Petri net with alternative routes (CAPN-AR) for assembly processes (2) a liveliness condition for CAPN-AR and (3) a deadlock avoidance algorithm.

Although there are a few results regarding deadlock avoidance problem for non-sequential production processes in literature, there is a lack of comparison for the existing results. The goal of this paper is to compare two existing results concerning deadlock avoidance in assembly manufacturing systems. This paper considers a subclass of the existing controlled assembly Petri nets (CAPN) with each operation requiring only one unit of arbitrary number of types resources called CAPNU. Analysis shows that the synthesis method proposed in our previous work is less conservative than that proposed in an existing result for the class of CAPNU.

Modern manufacturing systems are subject to uncertainties, shrinking time to market and fast advance of technology innovation. Evolution capability endows a design with the ability to tailor itself to fit the constantly changing demands to improve customer satisfaction and to reduce the risks. Cross-fertilization of multi-agent system theory with evolutionary computation theory is one possible way to robustly and proactively achieve the production objectives and continuously optimize the performance in constantly changing environment. This paper focuses on development of evolutionary agents based on fusion of multi-agent framework and evolutionary computational theory to design evolvable manufacturing systems. The problem is to form the production process and allocate resources to meet the product demands cost effectively. Our results include: (1) a multi-agent model based on contract net collaboration process and Petri net theory and (2) an evolutionary computational algorithm to continuously improve the system performance based on the available resources and product demands. The preliminary results provide a theoretical framework to support the implementation of evolvable multi-agent manufacturing systems.

Deadlock is a highly undesirable situation in which a set of parts or jobs are requested or waiting for resources held by other parts or jobs in the same set, with the set of parts or jobs in circular waiting. Although deadlock has attracted considerable attention in the context of automated manufacturing systems, most existing results focus on development of suboptimal deadlock avoidance algorithms to reduce the computational complexity involved. The paper considers a subclass of sequential processes whose optimal deadlock avoidance policy can be found in polynomial time. Our results include: (1)a re-entrant process model (2) analysis for single re-entrant process and (3)examples and extension to multiple work flows.

Contract manufacturing is one of the most prevalent supply-chain models. The formation of a contract manufacturing supply-chain (CMSC) network tends to be more dynamic as the establishment of a partnership is based on the contracted orders. Optimization of CMSC networks is much more difficult than traditional production networks. This paper proposes a self-organization framework for CMSCs. We define several constraint-satisfaction genetic operators to model key activities such as changing upstream or downstream partners or re-allocation of production capacities among partners in CMSCs. Our results include: (a) a mathematical model for CMSC networks, (b) a self-organization framework based on an evolutionary approach, (c) a comparison on different types of supply-chain alliances, and (d) a constraint satisfaction algorithm.

This paper focuses on synthesis of controllers that can operate in the presence of machine failure. We formulate a deadlock avoidance controller synthesis problem for assembly production processes with unreliable machines based on resource unavailability models, which regard unavailability of resources as loss of tokens in nominal Petri net models. We define two types of token losses to model different modes of machine failure. For each type of token loss, we establish sufficient conditions that guarantee the liveness of the Petri nets after tokens are removed. An algorithm is proposed to conduct feasibility analysis by searching for recovery control sequence and to make the resources released from blocking situation so that all the remaining available resources can be effectively utilized for production. Our algorithm synthesizes control logics that try to minimize the recovery or reset operations that need to be conducted, so that the impacts on existing production schedule can be reduced.

Holonic manufacturing systems (HMS) are the next wave of manufacturing revolution to deal with dynamic changes. A HMS can be modeled as a cooperative multi-agent system with constraints of production processes and finite resources. Deadlocks may also take place in HMS. Although there are many works on HMS, there is still lack of research known to the author addressing the issue of deadlock in HMS. This paper focuses on the modeling of HMS and development of deadlock free task distribution and resource allocation protocol and algorithm based on the framework of multi-agent systems. Our results include: (1) a mathematical multi-agent model for the HMS; (2) characterization of deadlock free conditions for task distribution and resource allocation; (3) a collaboration network formation process for coordination and negotiation among agents; and (4) a class of deadlock free task distribution and resource allocation algorithms based on deadlock free conditions.

Guarantee of deadlock-free operations is a prerequisite for achieving high resource utilization in flexible manufacturing systems. As production processes may contend for shared resources, the addition or removal of production processes has impacts on the liveness property of the systems. Uncertainties in manufacturing systems may result in unavailability of resources and may in turn lead to deadlocks and have negative impacts on the scheduled activities and performance. The design of deadlock avoidance control logics for manufacturing systems with unreliable machines to meet changeable, high-variety of product demands is a challenging problem. We develop deadlock avoidance control synthesis algorithms that are: (1) reconfigurable to incorporate or remove production processes while maintaining the liveness property, (2) robust to cope with uncertainties, and (3) scalable for realistic cases.

This paper develops a new method for synthesizing deadlock avoidance controllers (DACs) that realize job and machine dispatching policies of a flexible manufacturing system (FMS) into deadlock free control actions. Such controllers not only keep the FMS capable of repeating any of its operations, but also achieve a high resource utilization under any given dispatching policy. Our methodology is based on an untimed Petri net formalism. It consists of four ingredients: 1) a bottom-up approach for synthesizing a controlled production Petri net (CPPN) model of a FMS; 2) a necessary and sufficient liveness condition based on decomposition of the CPPN into controlled production subnets and the concept of minimal resource requirements; 3) a sufficient procedure to test whether the liveness condition is kept after a control action is executed; and 4) an algorithm that combines the test procedure with the given dispatching policy to generate valid and utilization maximizing control actions. We assess that this method is of polynomial time complexity and show that it results in a much larger class of controls than that of an existing deadlock avoidance scheme.>

The authors present an integrated framework for order and production scheduling of a discrete-part, make-to-order flow shop. They first formulate the integrated problem and then decompose it by applying Lagrangian relaxation into subproblems of order scheduling, production scheduling, and overtime capacity allocation, which match the operational functions in a manufacturing organization, and form a dual problem to optimize the Lagrange multipliers for relaxation. which are interpreted as marginal costs. The solution algorithm has a structure that clearly captures the interrelationship among subproblems and provides a framework for integration. Exploiting such a framework. effective rescheduling algorithms for handling new order insertion and capacity loss are developed.>