An algorithm to find the minimal initial markings of resource places ensuring liveness of finite-capacity S3PR

Deadlock prevention can be achieved by configuring proper initial markings to obtain a live Petri net model. For a class of Petri nets called finite-capacity Systems of Simple Sequential Processes with Resources (S³PR), an algorithm is proposed to find the minimal initial markings of resource places ensuring its liveness. First, conditions on initial markings of resource places are computed under which the strict minimal siphons (SMS) can never be emptied. Then, the minimal initial markings of resource places are computed to ensure liveness of the net. By the proposed algorithm, a live net can be obtained without changing the structure of the original model. The main practical implication of our work is that it can lower the facility cost. A simple example is used to illustrate the application of the algorithm.     

Deadlock prevention technique using additional transitions for Petri nets

ABSTRACT

Siphon control has been utilized as a general methodology for systems of simple sequential process with resource (S³PR) deadlock systems. Although siphon control imposes additional control places on S³PR systems, it cannot guarantee that the maximum permissiveness is achieved. To solve the problem of deadlock prevention for S³PR, a new policy to design a deadlock-free supervisor with the maximally permissive system is proposed using additional transitions. Additionally, this approach can solve the problem of deadlock prevention for systems of sequential systems with shared resources (S4PR) system models.     

A new optimal control policy for a well-known S3PR (systems of simple sequential processes with resources)

There are many studies reported in the literature comparing the effectiveness of new control policies by testing them against a well-known S³PR (systems of simple sequential processes with resources) model. We propose a new approach that recovers the system from empty-siphon states to former live states. It therefore attains the same number of states as the original uncontrolled model by adding monitors (and control arcs) similar to the prevention approach. There is no need to perform a reachability analysis. INA (integrated net analyser) analysis indicates that the resulting controlled model is live and reaches all 26,750 states (in the uncontrolled model), more than the maximally permissive 21,581 states. Only seven monitors are employed, fewer than in most other approaches. This arises from the fact that no new problematic siphons are generated due to the added monitors. We discuss the disadvantages (a variant of the scheme to overcome the disadvantages is also discussed) and physical meaning of the policy. We further propose a lossless approach by colouring some arcs. This not only avoids material loss, but also tackles the livelock problem.     

Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.