Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems

In this paper, a deadlock prevention policy for flexible manufacturing systems (FMS) is proposed, which can obtain a maximally permissive liveness-enforcing Petri net supervisor while the number of control places is compressed. By using a vector covering approach, the sets of legal markings and first-met bad markings (FBM) are reduced to two small ones, i.e., the minimal covering set of legal markings and the minimal covered set of FBM. A maximally permissive control purpose can be achieved by designing control places such that all markings in the minimal covered set of FBM are forbidden and no marking in the minimal covering set of legal markings is forbidden. An integer linear programming problem is designed to minimize the number of control places under an assumption that a control place is associated with a P-semiflow. The resulting net has the minimal number of control places on the premise that the assumption holds, and possesses all permissive states of a plant. The only problem of the proposed method is its computational complexity that makes it inapplicable to large-scale Petri net models. An FMS example from the literature is presented to illustrate the proposed method.     

含扩散项不可靠生产系统最优生产控制的数值求解

针对含扩散项不可靠随机生产系统最优生产控制的优化命题, 采用数值解方法来求解该优化命题最优控制所满足的模态耦合的非线性偏微分HJB方程. 首先构造Markov链来近似生产系统状态演化, 并基于局部一致性原理, 把求解连续时间随机控制问题转化为求解离散时间的Markov决策过程问题, 然后采用数值迭代和策略迭代算法来实现最优控制数值求解过程. 文末仿真结果验证了该方法的正确性和有效性.     

Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach

The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems’ (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.     

Modelling for flexible manufacturing systems and structural properties of optimal work routing policy

We consider flexible manufacturing systems (FMSs) which are composed of a set of workstations linked together with a material handling system (MHS). Each workstation consists of an input buffer, a single machine and an output buffer. The MHS consisting of a single cart routes work among the workstations according to the process paths required by the work. We deal with an optimal control problem in this FMS. We model the FMS as a closed queueing network. In the model, the cart routes the work to the workstations in accordance with a Markov routing with exponentially distributed routing time, and the machines process work with exponentially distributed processing time. An objective is to find a work routing policy that maximizes the total expected reward earned by operating machines. This optimal control problem is formulated as an undiscounted semi-Markov decision process. Structural properties of an optimal policy are analysed. Moreover, a sufficient condition is derived for the optimal policy to be of control limit type. An example is given to illustrate the result.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

Exact and metaheuristic algorithms for the vehicle routing problem with a factory-in-a-box in multi-objective settings

Emergencies, such as pandemics (e.g., COVID-19), warrant urgent production and distribution of goods under disrupted supply chain conditions. An innovative logistics solution to meet the urgent demand during emergencies could be the factory-in-a-box manufacturing concept. The factory-in-a-box manufacturing concept deploys vehicles to transport containers that are used to install production modules (i.e., factories). The vehicles travel to customer locations and perform on-site production. Factory-in-a-box supply chain optimization is associated with a wide array of decisions. This study focuses on selection of vehicles for factory-in-a-box manufacturing and decisions regarding the optimal routes within the supply chain consisting of a depot, suppliers, manufacturers, and customers. Moreover, in order to contrast the options of factory-in-a-box manufacturing with those of conventional manufacturing, the location of the final production is determined for each customer (i.e., factory-in-a-box manufacturing with production at the customer location or conventional manufacturing with production at the manufacturer locations). A novel multi-objective optimization model is presented for the vehicle routing problem with a factory-in-a-box that aims to minimize the total cost associated with traversing the edges of the network and the total cost associated with visiting the nodes of the network. A customized multi-objective hybrid metaheuristic solution algorithm that directly considers problem-specific properties is designed as a solution approach. A case study is performed for a vaccination project involving factory-in-a-box manufacturing along with conventional manufacturing. The case study reveals that the developed solution method outperforms the ε-constraint method, which is a classical exact optimization method for multi-objective optimization problems, and several well-known metaheuristics.     

Maximizing biogas production from the anaerobic digestion

This paper presents an optimal control law policy for maximizing biogas production of anaerobic digesters. In particular, using a simple model of the anaerobic digestion process, we derive a control law to maximize the biogas production over a period T using the dilution rate as the control variable. Depending on initial conditions and constraints on the actuator (the dilution rate D(·)), the search for a solution to the optimal control problem reveals very different levels of difficulty. In the present paper, we consider that there are no severe constraints on the actuator. In particular, the interval in which the input flow rate lives includes the value which allows the biogas to be maximized at equilibrium. For this case, we solve the optimal control problem using classical tools of differential equations analysis. Numerical simulations illustrate the robustness of the control law with respect to several parameters, notably with respect to initial conditions. We use these results to show that the heuristic control law proposed by Steyer et al., 1999 [20] is optimal in a certain sense. The optimal trajectories are then compared with those given by a purely numerical optimal control solver (i.e. the “BOCOP” toolkit) which is an open-source toolbox for solving optimal control problems. When the exact analytical solution to the optimal control problem cannot be found, we suggest that such numerical tool can be used to intuiter optimal solutions.     

Improved hybrid simulated annealing algorithm for navigation scheduling for the two dams of the Three Gorges Project

The purpose of this paper is to deal with the optimal navigation co-scheduling (NCS) for the two dams of the Three Gorges Project in China, i.e., the Three Gorges Dam and the Gezhouba Dam. The co-scheduling includes the operational scheduling for all five locks of the two dams, and the dispatching scheduling to ships applying to pass the dams. Compared with the flexible manufacturing system (FMS), a mixed-integer nonlinear programming model is designed for the NCS, and an improved hybrid algorithm of simulated annealing and local search is addressed to obtain optimal scheduling. Experiments based on real historical execution data show that the approach is feasible.     

Dynamic routing in reentrant flexible manufacturing systems

Consider a flexible manufacturing system (FMS), with several parallel production lines. Each line is statistically balanced. Due to process time and yield variations, some workstations may be temporarily starved of parts during the FMS operation, while others may have too many. The purpose of the dynamic routing algorithm described here is to achieve real-time load balancing in a stochastic processing environment and thus to increase the performance of the system in throughput, workload balance and reduced work-in-process queues. We formulate the problem and develop an optimal stationary policy (for two lines that have a material handling transport between them) based on the input buffer state of each station.     

A simulation optimization based control policy for failure prone one-machine,two-product manufacturing systems

This paper presents the optimal flow control for a one-machine, two-product manufacturing system subject to random failures and repairs. The machine capacity process is assumed to be a finite state Markov chain. The problem is to choose the production rates so as to minimize the expected discounted cost of inventory/backlog over an infinite horizon. We first show that for constant demand rates and exponential failure and repair time distributions of the machine, the hedging point policy is optimal. Next, the hedging point policy is extended to non-exponential failure and repair time distributions models. The structure of the hedging point policy is parameterized by two factors representing the thresholds of involved products. With such a policy, simulation experiments are coupled with experimental design and response surface methodology to estimate the optimal control policy. Our results reveal that the hedging point policy is also applicable to a wide variety of complex problems (i.e. non-exponential failure and repair time distributions) where analytical solutions may not be easily obtained.     

Fault-tolerant and maximally-permissive FMS controllers right out of the box—an automatic design approach

This paper presents a comprehensive, all-in-one approach to automatic generation of high-level coordination controllers for flexible manufacturing systems (FMS). The approach comprises an intuitive graphical world wide web (WWW) user interface to specify the FMS layout and the desired production sequences. It also includes algorithms (a) to generate a proper Petri Net model for the specified plant, (b) to set up optimal (i.e. minimally restrictive) collision and deadlock avoidance policies together with a proper supervisory controller to enforce these policies, and (c) to react to disturbances such as machine breakdowns. These algorithms run in the design (offline) phase without user interaction. During online operation the operator only needs to indicate the arrival of new raw materials and the removal of finished products using the same user interface as mentioned before. An example implementation demonstrates the applicability and efficiency of the proposed approach.     

Manufacturing flow control and preventing maintenance: a stochasticcontrol approach

A stochastic control model for simultaneously planning production and maintenance in a flexible manufacturing system (FMS) is proposed, and an efficient technique for computing the optimal control policy is developed. The model extends previous formulations by including an age-dependent machine failure rate and by allowing the control to influence some jump rates (namely the preventive maintenance activities). By using an adaptation to the case of piecewise-deterministic systems of the approximation technique initially proposed by H.J. Kushner (1977) in the realm of the optimal control of diffusions, one shows how it is possible to computer the optimal control for a two-machine system     

Developing a coordinated vendor–buyer model in two-stage supply chains with stochastic lead-times

This paper develops an approach to determine the optimal production and shipment policy for an integrated vendor–buyer problem. The vendor manufactures the product in batches at a finite rate and ships the output to the buyer. All shipments to the buyer are equal-sized batches. Despite previous papers in the literature, we assume that the supply lead-time between vendor and buyer is stochastic and shortage is also allowed. The objective is to minimize the expected total cost of both buyer and vendor. We derive the expected annual integrated total cost function and propose an analytic solution procedure to determine the optimal policy. To illustrate the significance of cost-reduction of the integrated approach in comparison with independent decisions by buyer or vendor, some numerical examples are also presented.     

Online Optimization of Swimming and Crawling in an Amphibious Snake Robot

An important problem in the control of locomotion of robots with multiple degrees of freedom (e.g., biomimetic robots) is to adapt the locomotor patterns to the properties of the environment. This article addresses this problem for the locomotion of an amphibious snake robot, and aims at identifying fast swimming and crawling gaits for a variety of environments. Our approach uses a locomotion controller based on the biological concept of central pattern generators (CPGs) together with a gradient-free optimization method, Powell's method. A key aspect of our approach is that the gaits are optimized online, i.e., while moving, rather than as an off-line optimization process. We present various experiments with the real robot and in simulation: swimming, crawling on horizontal ground, and crawling on slopes. For each of these different situations, the optimized gaits are compared with the results of systematic explorations of the parameter space. The main outcomes of the experiments are: 1) optimal gaits are significantly different from one medium to the other; 2) the optimums are usually peaked, i.e., speed rapidly becomes suboptimal when the parameters are moved away from the optimal values; 3) our approach finds optimal gaits in much fewer iterations than the systematic search; and 4) the CPG has no problem dealing with the abrupt parameter changes during the optimization process. The relevance for robotic locomotion control is discussed.     

Parametric Transformation of Timed Weighted Marked Graphs: Applications in Optimal Resource Allocation

Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems.Due to the existence of multiplicities(i.e.,weights)on edges,the performance analysis and resource optimization of such graphs represent a challenging problem.In this paper,we develop an approach to transform a timed weighted marked graph whose initial marking is not given,into an equivalent parametric timed marked graph where the edges have unitary weights.In order to explore an optimal resource allocation policy for a system,an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net.Finally,we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach.Simulation analysis shows that the developed approach is superior to the heuristic approach.     

Peer‐to‐peer financing choice of SME entrepreneurs in the re‐emergence of supply chain localization

While peer‐to‐peer (P2P) financing mechanisms have recently gained significant popularity, small and medium sized enterprise (SME) entrepreneurs still harbor a considerable degree of skepticism about the role of governments in promoting alternative supply chain finance (SCF) solutions in the re‐emergence of supply chain (SC) localization. This paper studies the SC financing problem of a capital‐constrained SME entrepreneur under two alternative financing schemes provided by an online P2P lending‐investment platform, namely debt financing (DF) and equity financing (EF). Considering the competition between a local and a foreign SC in a shared market, we investigate the direct (i.e., subsidizing domestic production) and indirect (i.e., subsidizing P2P platform service fee) roles of government intervention toward SC localization. Formulating a three‐level Stackelberg game model, this paper presents a scenario‐based decision‐making framework to jointly evaluate four different SCF scenarios through the lens of local SC, P2P financing platforms, and government. The results reveal that there exist three possible regions (i.e., DF, EF, and Conflict), within which the government and the P2P financing platforms can examine the alternative SCF schemes in order to achieve a mutually agreeable agreement. Our sensitivity analysis on interest rate and exchange ratio suggests that, when financed via an online P2P lending platform (i.e., DF), the local SC always achieves a higher profit under the direct intervention policy. The indirect policy, however, is preferred only when EF is the main source of SCF and the exchange ratio is sufficiently high.     

The queueing equivalence to a manufacturing system with failures

The authors consider optimal production rate control in a failure prone manufacturing system. It is well known that the hedging point policy is the optimum controller for such a system. They show that under the hedging point policy the system can be treated as an M/M/1 queue. Therefore, existing results in queuing theory can be readily applied to obtaining the steady-state probability density function of the production surplus, based on which the optimal hedging point policy can be computed. To a large extent, the approach is based on sample path analysis. It not only provides an alternative way to solve the problem but also reveals some interesting insights     

Object-oriented and distributed approach for programming robotic manufacturing cells

Flexible manufacturing systems (FMS) are essential for small/medium batch and job shop manufacturing. These types of production systems are used to manufacture a considerable variety of products with medium/small production volumes. Therefore, the manufacturing platforms supporting these types of production must be flexible and organized in flexible manufacturing cells (FMC). Programming FMCs remains a difficult task and is an actual area of research and development. This paper reports an object-oriented approach developed for FMC programming. The work presented was first thought for application in industrial robot manipulators, and later extended to other FMC equipments just by putting the underlying ideas in a general framework. Initially, the motivation for this work was to develop means to add force control to a standard industrial robot manipulator. This problem requires remote access to the robot controller, remote programming and monitoring, as also is required to program and monitor any other FMC equipment. The proposed approach is distributed based on a client/server model and runs on Win32 platforms, i.e., Microsoft Windows and Windows NT. Implementation for the special case of industrial robot manipulators is presented, along with some application examples used for educational, research and industrial purposes.     

计算机数控系统光滑时间最优轨迹规划

基于控制向量参数化(CVP)方法, 研究了计算机数控(CNC)系统光滑时间最优轨迹规划方法. 通过在规划问题中引入加加速度约束, 实现轨迹的光滑给进. 引入时间归一化因子, 将加加速度约束的时间最优轨迹规划问题转化为固定时间的一般性最优控制问题. 以路径参数对时间的三阶导数(伪加加速度)和终端时刻为优化变量, 并采用分段常数近似伪加加速度, 将最优控制问题转化为一般的非线性规划(NLP)问题进行求解. 针对加加速度、加速度等过程不等式约束, 引入约束凝聚函数, 将过程约束转化为终端时刻约束, 从而显著减少约束计算. 构造目标和约束函数的Hamiltonian函数, 利用伴随方法获得求解NLP问题所需的梯度.     

基于混合整数规划的非阻塞监督控制器设计

提出一种新的死锁控制策略, 保证含有并发执行装配过程的一类柔性制造系统(Flexible manufacturing system, FMS) G-system的非阻塞性, 即在控制下, 受控系统从任意可达状态都可到达理想状态. 首先对Petri网模型运用混合整数规划算法求取一个最大的死信标, 然后从最大的死信标中求取一个需要受控的极小信标, 并对其添加控制库所, 从而保证所有信标的最大可控. 和现有方法相比, 该策略避免了求取所有的信标, 且添加较少的控制库所即可获得结构简单、许可行为趋于最优的控制器.