Algorithm Research Of Manufacturing System Scheduling Problem Based On Labeled Petri Nets

With the scale of manufacturing system continues to expand,the reasonable manufacturing process has become an important to reduce production costs.This paper mainly studies the problem of estimating the least-cost based on the labeled Petri nets.According to obtained transition sequences,the manufacturing process is gained to complete the assembly task with the minimum cost.The main research work of this paper is as follows:1.To solve the least-cost planning sequences problem of a manufacturing system which is modeled by labeled Petri nets,a recursive algorithm based on backtracking method is proposed.Given a labeled Petri net with its structure and an initial marking,the search stage is divided into parts according to the given labeled sequence.In each stage,the transition with the minimal cost fires at first.With the observation of all the labels following this rule,the sum of the costs of transitions in the firing sequence is the minimum total cost.The least-cost planning sequences and the corresponding total cost are stored.Our proposed method traverses the solution space tree according to the depth-first strategy.By taking the current least total cost as the constraint condition,we can eliminate the markings and the sequence of transitions that do not need to be searched,and the searching space is reduced.2.In order to better fit the manufacturing systems,transitions are divided into observable and unobservable transitions in labeled Petri nets.The search stage is divided into parts according to the given labeled sequence.The observable transition cost fires at first,and then the unobservable transition fires in each stage.They formed a sequence containing unobservable transitions.Each transition is associated with a non-negative cost in the net,and the total cost of the sequence is the sum of the costs of the fired transitions in a stage.After observing the labeled sequence,the least-cost planning sequences is obtained by comparing the sum of the total cost of the transition sequences at all stages.The results show that the reasonable manufacturing process can be gained according to the least-cost transition sequences obtained in the labeled Petri nets,and the assembly task can be completed with the minimum cost.It has a certain guiding significance for the research of manufacturing system scheduling problem.