Lagrangian relaxation method for price-based unit commitment problem

The unit commitment problem consists of determining the schedules for power generating units and the generating level of each unit. The decisions concern which units to commit during each time period and at what level to generate power to meet the electricity demand. The problem is a typical scheduling problem in an electric power system. The electric power industry is undergoing restructuring and deregulation. This article developes a stochastic programming model which incorporates power trading. The uncertainty of electric power demand or electricity price are incorporated into the unit commitment problem. It is assumed that demand and price uncertainty can be represented by a scenario tree. A stochastic integer programming model is proposed in which the objective is to maximize expected profits. In this model, on/off decisions for each generator are made in the first stage. The approach to solving the problem is based on Lagrangian relaxation and dynamic programming.     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

机械设备故障诊断模糊、概率Petri网

根据故障诊断的特点,将概率信息引入模糊Ｐｅｔｒｉ网,提出了模糊,概率Ｐｅｔｒｉ网模型,简称模糊概率网。研究基于模糊概率网模型进行故障诊断的方法,利用概率信息处理反向推理中冲突消解问题,提高了诊断效率;利用模糊信息计算诊断结果的可信度;提出了一种反向推理机制,给出了算法。最后,以机械手掉刀为例,对该诊断方法进行了说明。     

Petri nets and genetic algorithms for complex manufacturing systems scheduling

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.     

A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints

Summary In this paper we deal with the following special vehicle routing problem with time window constraints: Given a non-homogeneous fleet of vehicles and a fixed set of customers, during one time period, i.e. a day or a week, these customers have to be delivered in the first half of the period with a certain amount of goods. Thereby delivery may start at timet _start say at the depot and for every customer there is a so-called cut-off-time for the latest possible delivery. In addition to travel time there is a certain delivery-time associated with every customer. In the second half of the time period the vehicles have to pick-up certain amounts of goods and to ship them to the depot. Again there is a cut-off time for the earliest possible pick-up and a certain time-span consumed for every pick-up. We show how this problem can be formulated as a (highdimensional) set partitioning problem with two additional nontrivial sets of side-constraints. Assuming that the number of customers that can be served by a single vehicle on a delivery or pick-up-pass is at most two, the problem reduces to a matching problem with side-constraints. Although the problem is still NP-complete it becomes practicable in the sense that by relaxation and applying effective optimization techniques from non-smooth optimization and efficient matching software good approximate solutions are constructed in acceptable time.This work was partially supported by a grant from the Deutsche Forschungsgemeinschaft (DFG)     

带有限等待的动态HFS调度的拉格朗日松弛算法

作为基于最优化的近似算法,分析了拉格朗日松弛算法的分解策略,设计了算法的实现优化过程.针对从钢铁生产提炼出的带有限等待时间要求的动态HFS调度,采用基于工件解耦的分解策略,应用拉格朗日松弛算法进行求解,以最小化总加权完成时间和工件等待惩罚之和.该算法将工件耦合约束松弛到目标函数中,将形成的松弛问题分解成多个更易求解的工件级子问题,进而利用动态规划求解这些子问题,通过拉格朗日乘子的更新迭代过程获得原问题的近优解.对不同问题规模的测试结果表明,该算法能在较短的计算时间内得到较好的近优解,说明了拉格朗日松弛算法求解等待时间受限的HFS调度的可行性和有效性.     

Nested coloured timed Petri nets for production configuration of product families

Production configuration is as an effective technique to deal with product variety while maintaining production stability and efficiency. It involves a diverse set of process elements (e.g., machines, operations), a high variety of component parts and assemblies and many constraints arising from product and process variety. Production configuration entails the selection and subsequent arrangement of process elements into complete production processes and the final evaluation of configured multiple alternatives. To better understand production configuration and its implementation, we study the underlying logic for configuring production processes using a dynamic modelling and visualisation approach. This is accomplished by developing a new formalism of nested coloured timed Petri nets (PNs). In view of the inherent modelling difficulties, in the formalism three types of nets–process nets, assembly nets and manufacturing nets–together with a nested net system are defined. Using an industrial example of vibration motors, we show how the proposed formalism can be applied to specify production processes at different levels of abstraction to achieve production configuration.     

Modelling and simulation of a bottling plant using hybrid Petri nets

In this paper we use First–Order Hybrid Petri nets (FOHPN), an hybrid model that combines fluid and discrete event dynamics, to model the concurrent activities of manufacturing systems. In particular we consider an existing mineral water bottling plant and we show how the FOHPN model is extremely suited to describe the high-throughput production lines, that are one of the main components in the considered plant. Some variations with respect to the previous definition of the FOHPN model are also introduced here to better describe the behavior of the conveyor lines. Finally, we show that, thanks to the fluid approximation of some discrete-event dynamics, the considered plant may also be efficiently simulated using FOHPN. This also enabled us to identify, among the most commonly used configurations of the plant, which are the optimal working conditions in terms of maximal throughput and net profit.     

A review on the electric vehicle routing problems: Variants and algorithms

Over the past decade, electric vehicles (EVs) have been considered in a growing number of models and methods for vehicle routing problems (VRPs). This study presents a comprehensive survey of EV routing problems and their many variants. We only consider the problems in which each vehicle may visit multiple vertices and be recharged during the trip. The related literature can be roughly divided into nine classes: Electric traveling salesman problem, green VRP, electric VRP, mixed electric VRP, electric location routing problem, hybrid electric VRP, electric dial-a-ride problem, electric two-echelon VRP, and electric pickup and delivery problem. For each of these nine classes, we focus on reviewing the settings of problem variants and the algorithms used to obtain their solutions.     

Comparative analysis of different routing heuristics for the battery management of automated guided vehicles

This paper explores how different routing techniques for the battery management of automated guided vehicles (AGVs) can affect the performance of a system. Four heuristics available in the literature were the basis of this study. Simulation models were developed to investigate how the routing of an AGV towards a battery station can affect the productivity of a manufacturing facility. Results show that the best productivity can be achieved when a routing heuristic tries to jointly minimise the total travel distance and waiting time at a battery station. The gain in productivity, when compared with the highest possible gain theoretically achievable, is quite substantial. It was also found that higher frequency of decision-making (i.e. decisions with smaller time interval) about battery swapping helps to increase the productivity of a system.     

A price-directed decomposition approach for solving large-scale capacitated part-routing problems

We consider the problem of planning the production steps of several parts through a manufacturing system with both process and routing flexibilities. The problem is formulated as a network flow-based linear programming model which seeks to minimise the total material handling, production, and outsourcing costs subject to satisfying all the part demands and not exceeding any of the machine capacity limits. We develop a price-directed decomposition-based approach that exploits the special structure of the model in order to solve it. An extensive computation experiment is carried out in order to gain some insights into the impacts of flexibility in the manufacturing system on the optimal decision and cost, and to test the efficiency of the procedure in handling large scale problems.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

Decomposition in automatic generation of Petri nets for manufacturing system control and scheduling

Despite the efforts in developing Petri net models for manufacturing control and scheduling, the generation of Petri net models cannot be automated for agile manufacturing control and scheduling without difficulties. The problems lie in the complexity of Petri net models. First of all, it is difficult to visualize the basic manufacturing process flow in a complex Petri net model even for a Petri net modelling expert. The second problem is related to the complexity of using Petri net models for manufacturing system scheduling. In this paper, a decomposition methodology in automatic generation of Petri nets for manufacturing system control and scheduling is developed. The decomposition methodology includes representing a manufacturing process with the Integrated Definition 3 (IDEF3) methodology, decomposing the manufacturing process based on the similarity of resources, transforming the IDEF3 model into a Petri net control model, and aggregating sub Petri net models. Specifically, a sequential cluster identification algorithm is developed to decompose a manufacturing system represented as an IDEF3 model. The methodology is illustrated with a flexible disassembly cell example. The computational experience shows that the methodology developed in this paper reduces the computational time complexity of the scheduling problem without significantly affecting the solution quality obtained by a simulated annealing scheduling algorithm. The advantages of the methodology developed in this paper include the combined benefits of simplicity of the IDEF3 representation of manufacturing processes and analytical and control properties of Petri net models. The IDEF3 representation of a manufacturing process enhances the manmachine interface.     

Deadlock modeling and control of semiconductor track systems using resource-oriented Petri nets

This paper addresses the deadlock avoidance problem in track systems in semiconductor fabrication. For the system without buffer space in it, the existing deadlock avoidance policies tend to be too conservative. Routing flexibility provides a chance to develop better ones, but makes their computation more complex. This paper models a track system using coloured resource-oriented Petri net (CROPN). Based on the model, a sufficient condition for deadlock-free operation and the corresponding control law are presented. This proposed policy is shown computationally efficient and less conservative than existing methods. An example is presented to demonstrate its application.     

Hierarchical Colored Timed Petri Nets for Maintenance Process Modeling of Civil Aircraft

Civil aircraft maintenance process simulation model is an effective method for analyzing the maintainability of a civil aircraft. First, we present the Hierarchical Colored Timed Petri Nets for maintenance process modeling of civil aircraft. Then, we expound a general method of civil aircraft maintenance activities, determine the maintenance level for decomposition, and propose the methods of describing logic of relations between the maintenance activities based on Petri Net. Finally, a time Colored Petri multi-level network modeling and simulation procedures and steps are given with the maintenance example of the landing gear burst tire of a certain type of aircraft. The feasibility of the method is proved by the example.     

Robotics in order picking: evaluating warehouse layouts for pick,place, and transport vehicle routing systems

Motivated by recent technological advances in mobile robotics, this paper explores a novel approach for warehouse order picking. In particular, this work considers two types of commercially available mobile robots – one that can grasp items from a shelf (a picker) and another (a transporter) that can quickly deliver all items from the pick list to the packing station. A new vehicle routing problem is defined which seeks to minimise the time to deliver all items from a pick list to the packing station, a problem termed the pick, place, and transport vehicle routing problem. A mixed integer linear programming formulation is developed to answer three related research questions. First, what combination of picker and transport robots is required to obtain performance exceeding traditional human-based picking operations? Second, how should the composition of the robot fleet be altered to affect the greatest performance improvements? Finally, what are the impacts of warehouse layout designs when coordinated mobile robots are deployed? An extensive numerical analysis reveals that, (1) increasing the number of cross aisles decreases system performance; (2) centrally located packing stations improve system performance; and (3) the average distance from each pick location to the packing station and the average distance between pick locations are effective metrics for identifying specific fleet modifications that are likely to yield system improvements.     

Proper Generalized Decomposition model reduction in the Bayesian framework for solving inverse heat transfer problems

In this paper, the proper generalized decomposition (PGD) is used for model reduction in the solution of an inverse heat conduction problem within the Bayesian framework. Two PGD reduced order models are proposed and the approximation Error model (AEM) is applied to account for the errors between the complete and the reduced models. For the first PGD model, the direct problem solution is computed considering a separate representation of each coordinate of the problem during the process of solving the inverse problem. On the other hand, the second PGD model is based on a generalized solution integrating the unknown parameter as one of the coordinates of the decomposition. For the second PGD model, the reduced solution of the direct problem is computed before the inverse problem within the parameter space provided by the prior information about the parameters, which is required to be proper. These two reduced models are evaluated in terms of accuracy and reduction of the computational time on a transient three-dimensional two region inverse heat transfer problem. In fact, both reduced models result on substantial reduction of the computational time required for the solution of the inverse problem, and provide accurate estimates for the unknown parameter due to the application of the approximation error model approach.