Transactions of the Institute of Measurement and Control

This paper develops a recursive algorithm for estimating the least-cost planning sequence in a manufacturing system that is modelled by a labelled Petri net. We consider a setting where we are given a sequence of labels that represents a sequence of tasks that need to be executed during a manufacturing process, and we assume that each label (task) can potentially be accomplished by a number of different transitions, which represent alternative ways of accomplishing a specific task. The processes via which individual tasks can be accomplished and the interactions among these processes in the given manufacturing system are captured by the structure of the labelled Petri net. Moreover, each transition in this net is associated with a non-negative cost that captures its execution cost (eg, in terms of the amount of workload or power required to execute the transition). Given the sequence of labels (ie, the sequence of tasks that has to be accomplished), we need to identify the transition firing sequence(s) (ie, the sequence(s) of activities) that has (have) the least total cost and accomplishes (accomplish) the desired sequence of tasks while, of course, obeying the constraints imposed by the manufacturing system (ie, the dynamics and structure of the Petri net). We develop a recursive algorithm that finds the least-cost transition firing sequence(s) with complexity that is polynomial in the length of the given sequence of labels (tasks). An example of two parallel working machines is also provided to illustrate how the algorithm can be used to estimate least-cost planning sequences.

Inspired by the Hierarchical D* (HD*) algorithm of Cagigas (Robotics and Autonomous Systems 52, 190—208, 2005), in this paper we introduce a novel hierarchical path planning algorithm called the Focussed Hierarchical D* (FHD *). Unlike the original HD* algorithm, the FHD* algorithm guarantees the optimality of the global path, and requires considerably less time for the path replanning operations. This is achieved by several modifications: (1) optimal placement of the so-called bridge nodes needed for hierarchy creation, (2) focusing the search around the optimal path, which reduces the search area without loss of optimality, and (3) introduction of partial starts and partial goals, which further reduce computational time of replanning operations. The FHD* algorithm was tested in a multi-room indoor environment and compared with the original HD* algorithm, non-hierarchical D* algorithm, and Focussed D* algorithm under the same conditions. The FHD* algorithm significantly outperforms other algorithms with respect to the computational time. Furthermore, it can be easily extended to the problem of path planning between different floors or buildings.

In this article, we address issues related to modelling of a discrete event system in a way that would effectively provide an easy implementation of the scheduling policy on the actual controller and at the same time would provide an answer on how profound the utilization of the system resources is. Herein we propose a method that relies on usage of a matrix model and a max-plus algebra model. The idea is to use the advantages of each of the given models. A system, initially given in matrix form, can be transferred into a max-plus model under the given sequence. In the case of structural changes, the system matrix model can be easily modified and hence supervisory matrix controller redesign is straightforward. On the other hand, the max-plus model is suitable for performance analysis, which in some cases could be difficult if a matrix model is used. Moreover, max-plus algebra represents the system on the higher level of abstraction, which is suitable for investigation of particular properties of discrete event systems. In addition, using both models, we propose a method for determining a scheduling sequence that is not well formed.

The electricity trade is expensive, and requires substantial expertise and efficient co-ordination methodologies. Several trading mechanisms including auctions have been adopted in the current energy market. To pursue success in this market, we present a protocol to support many-to-many bilateral multiple-issue negotiation in a competitive market where one or more self-interested electricity sellers can provide electricity to one or more buyers while buyers can choose the preferred sellers. Negotiation is a technique for reaching mutually beneficial agreement among autonomous entities. A concurrent negotiation problem occurs when one entity needs to negotiate simultaneously with several other entities to reach agreement. In the context of wholesale electricity trading, our described protocol enables both electricity buyers and sellers to manage several negotiation processes in parallel. This protocol allows the negotiating participants to make durable commitments to reduce the occurrence of the decommitment situation. Since coloured Petri nets are intuitive and can represent concurrency graphically, we use them to represent our negotiation protocol and facilitate our analysis of desirable properties.

Behaviour permissiveness is an important criterion in evaluating the performance of a liveness-enforcing supervisor for discrete event systems. The existence of uncontrollable events is a standard feature in the supervisory control of discrete event systems. A natural problem arising in this area is the existence of an optimal supervisor when there exist uncontrollable events in a plant. For a class of Petri net models of flexible manufacturing systems, whose optimal liveness-enforcing Petri net supervisors can be synthesized by a particular method through the addition of a set of monitors, this paper aims to identify a set of transitions such that the existence of an optimal liveness-enforcing net supervisor depends on their controllability. The controllability of a transition is decided by solving a linear programming problem to verify whether a monitor with arcs to the transition can act to inhibit it when it is otherwise enabled. A number of examples are presented to demonstrate the application of the proposed methods.

Cluster tools are widely used in wafer fabrication nowadays. Photolithography equipment, the most expensive equipment in wafer fabrication, is comprised of a serial of cluster tools. So far, there has been much research on the assignment of wafers processing in photolithography equipment. Since a production lot may include several kinds of wafer with different routes and the sequence order of wafers in a lot is stochastic, deadlock may occur at any time. Hence, we are not able to determine a schedule before the production batch starts; instead, we need a deadlock-free wafer dispatching method that can not only complete the requested wafer routine procedures but also reduce the total makespan. Here, we employ a transition digraph to check the occurring deadlock and a coloured Petri net (CPN) approach to model the photolithography equipment to ascertain clearly the system state via identification of the kind of wafers situated on respective positions and obtain a smooth and satisfactory control for the executed process. The employed CPN model is a timed high-level Petri net. Also, a well known CPN Tool (http://wiki.daimi.au.dk/cpntools/cpntools.wiki) is used for model editing, simulating and analysing. Accompanied by the photolithography equipment model built, a deadlock-avoidance supervisor is designed to ensure wafer deadlock-free dispatching at each step. This graphic model is easy to understand and can be extended to more complex cases.

Because of the high possibility of uncertain production disturbances, an established optimized schedule may not keep its optimality or even feasibility. Production rescheduling, which gives attention to both optimal scheduling and dynamic scheduling, is proposed in this background. One of the most important issues in rescheduling research is the rescheduling strategy that refers to rescheduling start-up decision making and rescheduling methodology adoption. It is ill structured, and involves some fuzzy and random information. In order to solve it, a fuzzy Petri net model for rescheduling (FPN-R) is proposed. Based on it, a fuzzy reasoning approach for rescheduling decision-making is discussed. Finally, a case study from a wafer fabrication plant is used to show the application and feasibility of the proposed FPN-R model and reasoning approach.

The transportation of crude oil from production fields to refineries is a very important operation in the oil industry. In this paper, an inventory routing problem for crude oil transportation is studied, where the crude oil is transported from a central depot to a set of customers with dynamic demand using multiple transportation modes. Oil can be transported through marine routes, pipelines or a combination of the two modes. The marine transportation of crude oil is performed by a heterogeneous fleet of tankers with limited capacity owned by an oil distributor itself and/or the tankers of different types rented from a third party. Each transportation operation has a lead time and the storage capacity of oil at each customer is limited. The problem is to determine over a given planning horizon an optimal oil transportation plan that minimizes the total transportation and inventory costs subject to various constraints. The plan defines the number of tankers of each type to rent and the number of tankers of each type to dispatch on each route in each period. A mixed-integer programming model is established for the problem. Because of the high complexity and large size of the problem, the model is too complicated to be solved exactly. A metaheuristic method, the Greedy Randomized Adaptive Search Procedure (GRASP) enhanced by an intensification strategy based on Path Relinking is developed to find its near-optimal solutions. Numerical test results of the method demonstrate the effectiveness of the method.