A surrogate-assisted multi-objective evolutionary algorithm is proposed for simultaneous optimization of robot motion planning and layout design in robotic cellular manufacturing systems. A sequence-pair is used to represent the layout of components in a robotic cell to avoid overlapping in the evolutionary computation. The robot motion planning with Rapidly exploring Random Trees Star (RRT*) is applied to compute the total operation time of a robot arm for each layout. Non-dominated Sorting Genetic Algorithm II (NSGA-II) is used to minimize the total required layout area and the operation time for a robot arm. The proposed surrogate model can estimate the robot’s operation time with 98% of accuracy without explicit computations of the motion planning algorithm. The experimental results with a physical 6 Degree of Freedom (DOF) manipulator show that the total computation time is approximately 1/400, significantly shorter than the conventional methods. • A surrogate-assisted optimization is proposed to solve layout design and motion planning. • A new multi-objective optimization problem is formulated to minimize both the area and the time. • The proposed method can significantly reduce the total computation time. • The performance of the proposed method is validated with a physical robot manipulator.

Inventory control is an essential component in supply chain management. Several attempts have been made to optimize the inventory problem using surrogate-assisted optimization methods. However, these studies have assumed that the decision-maker has access to all the supply chain information for building the simulation model. This study proposes a surrogate-assisted evolutionary algorithm for distributed simulation-based inventory optimization in serial supply chains. We propose a surrogate-assisted multi-strategy differential evolution algorithm. Two search strategies are used to generate candidate solutions, and two surrogate models filter the candidate solutions. A regression model is used to estimate the total cost, and a classification model is trained to estimate the feasibility of the solutions. Then, we develop a distributed simulation method for estimating each stage's performance for a given inventory policy while allowing the simulation models to be located in different locations. Our proposed approach is evaluated using 10-stage serial supply chain problems. The results show that the proposed surrogate-assisted distributed simulation-based optimization method can obtain significantly better solutions than the baseline algorithms. In addition, the distributed simulation method can accurately estimate the supply chain's total cost and service level.

In recent years, a form of production known as high-mix low-volume production has attracted attention. Mass customization is a production strategy that manufactures produce products to meet diverse customer demands while maintaining production efficiency close to mass production. Modular production is one of the production methods to achieve mass customization, and products are manufactured by combining modules. This production method allows a manufacturer to increase its total profit by manufacturing products suited to individual customers while reducing costs. In actual production planning, production costs and customer demands are uncertain. By considering these uncertainties, robust production planning can be achieved. Various robust production planning methods have been proposed in previous studies, however, no previous studies have reported cases of modular production that reflect customer decisions. Therefore, in this study, the production planning problem is formulated as a bilevel production planning problem consisting of customers and a manufacturer, and robust optimization is applied. Finally, we verify the usefulness of the proposed method for customer demand uncertainty by comparing the conventional model with the robust optimization model.

This paper studies the solution procedure to the problem of conflict-free route planning for automated guided vehicles for just-in-time delivery to minimize the earliness and tardiness of a specified delivery time while minimizing the total completion time. The characteristic of the problem is that a vehicle can have an idle time at any nodes considering dispatching of dynamic task arrivals. This problem is modeled by a time-space network where the pickup and delivery tasks are dynamically scheduled. A heuristic solution procedure is developed to derive a conflict-free routing problem such that earliness and tardiness penalties are minimized while the total completion time of each task is also minimized under dynamic task arrivals. The effectiveness of the proposed method is demonstrated by comparing the performance with Gurobi from computational results. The results show that the proposed method can obtain a better solution that is close to an optimal solution with significantly shorter computational time than that derived from Gurobi. The trade-off relationship between earliness/tardiness penalties and the total completion time is investigated in various situations. The effects of the interval of task assignment on the performance of earliness/tardiness and the total completion time are studied. The computational results show the conditions when the trade-off relationship can be obtained.Note to Practitioners—The multiple AGVs are used in public transportation and social systems with rapid development of artificial intelligence and optimization methods. The benefits of AGV affect the reduction of congestion, traffic police, legal services, and economic savings in the manufacturing and logistics industries. In order to satisfy the customer’s demands, it is requested to deliver the products just-in-time for the desired time without decreasing the total system performance. This paper presents the dispatching and conflict-free routing of AGVs for just-in-time transportation while minimizing the total completion time of the tasks. In many real factories with multiple production processes, the shortest time transportation may sometimes cause the congestions of AGVs waiting for handling or overstocked. Just-in-time transportation is required not only to reduce inventories but also to supply only when it is needed. Computational results show the situations when the just-in-time delivery and the minimization of the total completion time can be achieved.

We propose an optimization system for motion planning of robot arms using Petri Nets. The proposed optimization system consists of four sub-systems consisting of automatic generation of Petri Nets from event log data, optimization system of firing sequence of derived Petri Net model, verification system using Petri Net simulation, and an automatic program generation system. The model generation system automatically generates the Petri Net model from the event logs using process mining. The Petri Net verification system is used to check the consistency of the generated Petri Nets to obtain the optimal firing sequence for robot motion. The motion planning algorithm generates motion programs for robots based on optimal firing sequences. The proposed optimization model is applied to a 6-DOF (Degree of Freedom) robot manipulator (Niryo Ned). Experimental results show that the proposed method achieves motion plan optimization for the pick-and-place operation with different robot configurations.

The berth allocation problem is one of the important problems in the maritime ship operations. Efficient sea transportation can be realized by optimizing the berth operation schedule. The dynamic berth allocation problem asks to determine the allocation and berthing time of each vessel to the berth that minimizes the total service time given a set of vessels and a set of berths. The branch and bound algorithms have been used to solve the problem as an exact solution algorithm. However, it becomes intractable to solve the problem by the conventional branch and bound algorithms when the number of ships and berths is increased. In this paper, we propose a new branch-and-bound algorithm called Neural Network Assisted Branch-and-Bound (NN-B&B) to determine the search priority of each node to reduce the total computation time of the branch-and-bound method. By determining the search priority of the node from the result of the neural network, the optimal solution is quickly searched for the learned problem. We compare the performance of the proposed method with the conventional branch and bound method from computational experiments.

This article discusses the guide path design of automated guided vehicle (AGV) systems for which we propose a model that incorporates a dynamic multicommodity flow with capacity constraints from a pickup to a delivery point. The problem is formulated as the selection of a guide path connecting a given set of pickup/delivery points. A cell-based local search that is based on an original neighborhood technique is developed. In the proposed method, the guide path is effectively optimized based on a local search of cell-based neighborhood search preserving connectivity constraints and the subsequent solution of a dynamic multicommodity flow problem. The performance of the proposed method is strengthened by the redundant elimination of arcs and intensification of search according to the concept of the flow-concentrated cell. The effectiveness of the proposed method is demonstrated by comparing it with a general-purpose solver and recent algorithms for fixed-charge capacitated multicommodity network design problems. A real case study is presented to demonstrate the applicability of the proposed method by using simulation software.

For multiple Automated Guided Vehicles (AGVs) system, it is required to realize just-in-time delivery to minimize the earliness and tardiness of the specified delivery time not only to minimize the total traveling time. In this paper, we propose a heuristic algorithm for just-in-time and conflict-free routing problem of AGVs. The proposed method can derive a near-optimal task assignment and routing and scheduling of multiple AGVs to improve both the JIT performance and the total completion time. In the proposed method, a strategy to avoid collisions ensuring feasibility is proposed. The effectiveness of the proposed method is demonstrated by comparing the performance with CPLEX from computational results. The results show that the proposed method can obtain a better solution which is close to an optimal solution with a significantly shorter computational time than that derived from CPLEX.

Scheduling of multicluster tools has received much attention due to its complexity of interaction among cluster tools. A cluster tool comprises several modules such as processing modules, a transfer module with a single or dual-armed handling robot, and loadlock modules. A multicluster tool comprises two, three, or more cluster tools that are interconnected with each other. In this paper, we propose a deadlock prevention policy for noncyclic scheduling of dual-armed multicluster tools. The proposed deadlock prevention policy is effective for generating an efficient schedule for two or three-connected multicluster tools with a single or a dual-path flow. This is proven by analyzing the strict minimal siphon of the Petri net model. The performance of the proposed method is compared with that of a maximal permissible deadlock prevention policy. The results demonstrate that the proposed method is computationally efficient for larger state spaces and more suitable than conventional deadlock prevention policies for generating effective schedules for noncyclic scheduling of multicluster tools. Note to Practitioners-Scheduling of multicluster tools has recently attracted attention in the growing semiconductor manufacturing industry. Most conventional studies on multicluster tools focus on cyclic scheduling to minimize cycle time with swap strategy. The challenge addressed by this paper is to derive a deadlock-free schedule for multicluster tools with noncyclic operations. We propose a simple deadlock prevention policy that can be applied to large-scale timed Petri net (PN) model of general multicluster tools without enumeration of siphon computations or solution of mixed integer programming. A timed PN model is developed for noncyclic operations of dual-armed multicluster tools with a dual ath. The computational results show that the approximately 10% of the total throughput of the proposed method is better than those of the conventional methods. It enables more efficient operations for noncyclic scheduling under transient periods including cleaning operations.

Supply chain risk management is one of significant issues in the design and operations of supply chains. It is well-known that leader-follower relationship influences the decision making of decentralized supply chains. In this paper, we address a game theoretical analysis of the leadership structure in the decentralized supply chain with risky supplier under demand uncertainty. The risky supplier has a risk of unavailability of the supply product for the ordered product according to the probability of supplier availability. The equilibrium solution is analytically derived for a single supplier, a single risky supplier and a single retailer. The influence of the probability of risky supplier availability to the optimal leadership structure is investigated. Numerical examples are provided to show the validity of the proposed game theoretical analysis.

In this paper, the modeling and solution strategies of a practical airline crew scheduling problem are studied. The airline crew scheduling problem to achieve the equalization of working time taking into account for practical constraints such as international and domestic flights, holiday assignments, and grouping constraints is formulated as an integer programming problem. The problem is reformulated as a set partitioning problem by Dantzig-Wolfe decomposition. The column generation algorithm is applied to solve the linear relaxation of the original problem. In order to improve the performance of the algorithm, a column fixing strategy with backtracking is proposed. In the proposed method, the schedule for all crews is obtained efficiently by exploiting the fixing of columns and the execution of the column generation procedure. The backtracking is introduced to find a feasible solution efficiently. The computational results show that the proposed algorithm can find better solutions than greedy-heuristics and the branch and bound procedure solving the original problem by a commercial solver.

Semiconductor cluster tools are the integrated equipment to process a variety of silicon wafers for the fabrication of microelectronic components. The cluster tool system consists of several loadlock modules, processing chambers, and material handling armed robots for transferring wafers between them. Most scheduling problems for dual-armed cluster tools adopt cyclic scheduling with the assumption of swap sequence of the robot arm. A deadlock-free and non-cyclic scheduling is highly required to improve total throughput of cluster tools for various types of wafer flow patterns and various changes of equipment configurations. In this paper, we propose a Petri net decomposition approach to derive a near-optimal solution of deadlock-free and non-cyclic scheduling of dual-armed cluster tools to reduce the computational complexity. A timed Petri net model is introduced to represent a non-cyclic scheduling model for dual-armed cluster tools. In order to obtain a deadlock-free and non-cyclic schedule efficiently, we propose a deadlock avoidance control policy that restricts the markings to prevent unmarked siphons. Deadlock condition for the dual-armed cluster tools is characterized by the structure of Petri net model. The performance of the non-cyclic scheduling model by the proposed method is compared with that of the cyclic scheduling model. Computational results show the effectiveness of the non-cyclic scheduling model compared with the cyclic scheduling model for multiple wafer flow patterns.

We propose a new two-level decomposition algorithm for shift scheduling problems. The problem determines the assignment of duties and rest days to the set of staff members to minimize the given objective function. The constraint on the set of staff members are considered. The objective of this paper is to achieve the minimization of total costs with fairness of working conditions. The proposed method decomposes the original problem into the master and the subproblems. These subproblems are iteratively solved with embedding cuts into the master problem. Computational results show that the performance of the proposed method outperforms a general-purpose constraint logic programming solver.

Multi-cluster tools are widely used for semiconductor silicon wafer production. The multi-cluster tools system consists of two or more cluster tools connected with buffer or process modules. Deadlocks are frequently caused in the multi-cluster tools by the restriction of transfer modules and limited number of available spaces. In this paper, we propose a novel deadlock prevention policy for multi-cluster tools. A timed Petri net model for multi-cluster tools is developed. A new deadlock prevention policy is proposed. The proposed deadlock prevention policy is applied to dual-armed multi-cluster tool with dual path. The deadlock-freeness is confirmed by deriving empty siphons for the Petri net model. The computational results show that the performance of scheduling with the proposed deadlock prevention policy is better than the conventional deadlock prevention policy.

In this paper, we propose a column generation heuristics to a continuous time model of conflict-free pickup and delivery vehicle routing problems. The transportation system is divided into several regions with regular intervals. A network model of conflict-free multi-vehicle routing problem with acceleration and deceleration motions is developed. A column generation heuristics is used to find a near-optimal solution. The pricing problem for each vehicle routing problem is formulated as a resource constrained shortest path problem, which is effectively solved by a labeling algorithm. Computational results demonstrate the effectiveness of the proposed method.

In this paper, we address a Petri net decomposition approach for simultaneous dispatching and conflict-free routing for bidirectional automated guided vehicle (AGV) systems in dynamic environments. To solve the dynamic problem, static problems for finding near-optimal dispatching and conflict-free routing are solved each time when transportation requests are given. The static problem is converted to an optimal firing sequence problem for a timed Petri net. A Petri net decomposition approach is applied to solve the problem efficiently. In the algorithm, the entire Petri net is decomposed into task and AGV subnets. The penalty function method is used to derive a solution for all subnets. A deadlock avoidance method is embedded in the proposed methodology to ensure the feasibility and the quality of the solution. Computational results show that the proposed method with a deadlock avoidance algorithm efficiently maximizes the throughput for dynamic situations.

In this paper, we propose a Petri Net decomposition approach for solving the bi-objective conflict-free routing for AGV systems. The objective is to minimize the deviation of delivery time and to minimize the total transportation time. The dispatching and conflict-free routing problem for AGVs is represented as an optimal firing sequence problem for Petri Net. A Petri Net decomposition approach is applied to solve the multi-objective optimization problem efficiently. The convergence of the algorithm is improved by reducing the search region. The effectiveness of the proposed method is compared with that of the conventional method. Computational results show the effectiveness of the proposed method.

We propose a column generation algorithm for solving sequence dependent flowshop scheduling problems (SDST flowshop) to minimize the total weighted tardiness. The continuous relaxation of the set partitioning formulation of the Dantzig-Wolfe decomposition for SDST flowshop is solved by the column generation. The pricing subproblem for the column generation is decomposed into each job-level subproblem. In order to strengthen the lower bound, the additional constraints are imposed to the pricing problems in the proposed algorithm. The cut generation algorithm is developed for the column generation. Computational experiments show that the proposed method can derive the solutions with a smaller duality gap compared with those of the conventional algorithm of ordinary column generation and Lagrangian relaxation with cuts.

In this paper, we propose a Petri Net decomposition approach for dynamic dispatching and routing for bi-directional AGV systems. For dynamic dispatching and routing, the static problem to determine an optimal firing sequence problem for Petri Net is solved repeatedly. A Petri Net decomposition approach is applied to solve the optimal firing sequence problem efficiently. In the decomposition algorithm, the entire Petri Net is decomposed into task subnets and AGV subnets. The penalty function algorithm is used to coordinate the solution of each subnet. A deadlock avoidance policy for bi-directional lane is used to ensure the generation of conflict-free routing. Computational results show the effectiveness of the proposed Petri Net decomposition approach with deadlock avoidance policy for dynamic situations.

In this paper, we propose a Petri Net (PN) decomposition approach to the optimization of route planning problems for automated guided vehicles (AGVs) in semiconductor fabrication bays. An augmented PN is developed to model the concurrent dynamics for multiple AGVs. The route planning problem to minimize the total transportation time is formulated as an optimal transition firing sequence problem for the PN. The PN is decomposed into several subnets such that the subnets are made independent by removing the original shared places and creating its own set of resource places for each subnet with the appropriate connections. The partial solution derived at each subnet is not usually making a feasible solution for the entire PN. The penalty function algorithm is used to integrate the solutions derived at the decomposed subnets. The optimal solution for each subnet is repeatedly generated by using the shortest-path algorithm in polynomial time with a penalty function embedded in the objective function. The effectiveness of the proposed method is demonstrated for a practical-sized route planning problem in semiconductor fabrication bay from computational experiments.

In this paper, we propose a general decomposition method for transition firing sequence problems for first order hybrid Petri nets. The optimal transition firing sequence problem for first-order hybrid Petri nets is formulated as a mixed integer programming problem. We propose a Lagrangian relaxation method for solving optimal transition firing sequence problems. The hybrid Petri net is decomposed into several subnets in which the optimal firing sequence for each subnet is easily solved. The optimality of solution can be evaluated by duality gap derived by Lagrangian relaxation method. The proposed method is applied to a small-scale example. Computational experiments demonstrate the validity of the proposed formulation.

In this paper, we address a new integration of column generation and Lagrangian relaxation for solving flowshop scheduling problems to minimize the total weighted tardiness. In the proposed method, initial columns are generated by using near-optimal dual solution using the Lagrange multipliers derived by Lagrangian relaxation method. After the generation of base columns, the column generation is executed. Computational results demonstrate that the integrated column generation and Lagrangian relaxation can drastically speed up the conventional column generation.

In this paper, we propose a decomposition and coordination method for timed automata for modeling and solution of scheduling problems. Parallel composition of timed automata makes it possible to describe concurrent dynamics for several submodels represented by timed automata. To reduce state space explosion for parallel composition of timed automata, a decomposition and coordination method is developed. In the proposed method, a feasible solution is derived by coordinating the solution of each decomposed subproblem. Computational experiments demonstrate the feasibility of the proposed method.

Planning coordination for multiple companies has received much attention from viewpoints of global supply chain management. In practical situations, a plausible plan for multiple companies should be created by mutual negotiation and coordination without sharing such confidential information as inventory costs, setup costs, and due date penalties for each company. In this paper, we propose a framework for distributed optimization of supply chain planning using an augmented Lagrangian decomposition and coordination approach. A feature of the proposed method is that it can derive a near-optimal solution without requiring all of the information. The proposed method is applied to supply chain planning problems for a petroleum complex, and a midterm planning problem for multiple companies. Computational experiments demonstrate that the average gap between a solution derived by the proposed method and the optimal solution is within 3% of the performance index, even though only local information is used to derive a solution for each company.

In this paper, we propose a general decomposition and coordination method for timed Petri nets to determine an optimal transition firing sequence to minimize an objective function. A timed Petri net model for multiple entities is decomposed into several subnets in which the optimal firing sequence for each subnet is easily solved in polynomial computational complexity. The solution of each subproblem is coordinated by repetitive optimization of the number of tokens for duplicated places. The proposed method is applied to a flowshop scheduling problem. The effectiveness of the proposed method is confirmed by comparing the performance between the simulated annealing method

In this paper, we propose a distributed routing method for multiple mobile robots under uncertain motion delays. The feature of the proposed method is that each AGV subsystem creates the routing to minimize the sum of the transportation time and the penalty for collision avoidance constraints taking into account motion delay disturbances for other AGVs. The computational results show that the total transportation time obtained by the proposed method is shorter than that of the conventional method under various type of motion delay disturbances.

We propose a distributed routing system for multi-robot cooperative transportation using parallel multiple processors with asynchronous data exchange. In the proposed method, each robot generates a routing to minimize each objective function comprising of traveling time and the penalty for violating constraints of cooperation with other robots. A near optimal routing is generated by repeating the generation of each routing and data exchange among the robots. Asynchronous data exchange is adopted to reduce the computation time. In order for the solution not to be trapped in a local optimum, the weighting factors violating the constraints are updated with a time-dependent method during parallel computation. The proposed method is applied to motion planning for cooperative transportation of an experimental 4 real robots system. The effectiveness of the proposed method is investigated on various types of experimental conditions.

Coordination and optimization of supply chain planning among multiple companies have widely been received much attention from viewpoints of global supply chain management. Conventional system for supply chain planning is configured on the assumption that correct information for entire company is available by sharing the detailed information among multiple companies. It is required to generate a near optimal plan for multiple companies without sharing the confidential information such as inventory costs, set up costs and due date penalties among competing companies. In this paper, we propose a framework of a distributed supply chain planning for multiple companies by using an augmented Lagrangian relaxation approach. The proposed method features that a feasible solution can be derived without using the entire information by exchanging the data which is not directly related to cost data. From the computational experiments, it has been shown that the average gap between the solution derived by the proposed method and an optimal solution is within 1% of the performance index even though only the local information is used to derive a solution for each company

To enable efficient transportation in semiconductor fabrication bays, it is necessary to generate route planning of multiple automated guided vehicles (AGVs) efficiently to minimize the total transportation time without collision among AGVs. In this paper, we propose a distributed route-planning method for multiple mobile robots using an augmented Lagrangian decomposition and coordination technique. The proposed method features a characteristic that each AGV individually creates a near-optimal routing plan through repetitive data exchange among the AGVs and local optimization for each AGV. Dijkstra's algorithm is used for local optimization. The optimality of the solution generated by the proposed method is evaluated by comparing the solution with an optimal solution derived by solving integer linear programming problems. A near-optimal solution, within 3% of the average gap from the optimal solution for an example transportation system consisting of 143 nodes and 14 AGVs, can be derived in less than 5 s of computation time for 100 types of requests. The proposed method is implemented in an experimental system with three AGVs, and the routing plan is derived in the configuration space, taking the motion of the robot into account. It is experimentally demonstrated that the proposed method is effective for various problems, despite the fact that each route for an AGV is created without minimizing the entire objective function.

Coordination of planning among several companies has been widely received much attention from the viewpoint of global supply chain management. In a practical situations, a plausible plan for several companies should be created by the negotiation and coordination among the companies without sharing the confidential information such as inventory costs, set up costs and due date penalties for each company. In this paper, we propose a framework of a distributed optimization of supply chain planning using a new augmented Lagrangian relaxation method. The feature of the proposed method is that a feasible solution can be derived without using the procedure of heuristic generation of feasible solutions. From the computational experiments, it has been shown that the average gap between the solution derived by the proposed method and an optimal solution is within 1% of the performance index even though only the local information is used to derive a solution for each company.

For the transportation in semiconductor fabricating bay, route planning of multiple AGVs (Automated Guided Vehicles) is expected to minimize the total transportation time without collision and deadlock among AGVs. In this paper, we propose a distributed route planning method for multiple mobile robots using Lagrangian decomposition technique. The proposed method has a characteristic that each mobile robot individually creates a near optimal route through the repetitive data exchange among the AGVs and the local optimization of its route using Dijkstra's algorithm. The proposed method is successively applied to transportation route planning problem in semiconductor fabricating bay. The optimality of the solution generated by the proposed method is evaluated by using the duality gap derived by using Lagrangian relaxation method. A near optimal solution within 5% of duality gap for a large scale transportation system consisting of 143 nodes and 15 AGVs can be obtained only within five seconds of computation time. The proposed method is implemented on 3 AGVs system and the route plan is derived taking the size of AGV into account. It is experimentally shown that the proposed method can be found to be effective for various types of problems despite the fact that each route for AGV is created without considering the entire objective function.

In the conventional Lagrangian relaxation approach, the scheduling problems are decomposed into job-level sub-problems or operation-level sub-problems. However, these approaches are not applicable to the flowshop problems with the changeover cost which depends on the sequence of operations. In this paper, we propose a machine-oriented decomposition method for the flowshop problems using the Lagrangian decomposition and coordination technique. In the proposed method, each sub-problem for single machine is solved by the simulated annealing method. The solutions of the sub-problems are used to generate a feasible schedule by a heuristic procedure. The effectiveness of the proposed method is verified by comparing the results of the example problems solved by the proposed method with those solved by the conventional method. Furthermore, it has been shown that the proposed approach is easily applicable to the flow hop problem with resource constrains minimizing the changeover costs and due date penalties.