An efficient algorithm for finding an optimal deadlock-free schedule in amanufacturing system with very limited buffer is presented. This algorithm is based on the effectivegenetic algorithm (GA) search method, and a ...An efficient algorithm for finding an optimal deadlock-free schedule in amanufacturing system with very limited buffer is presented. This algorithm is based on the effectivegenetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect thetoken player assuring deadlock-free. In order to make the scheduling strategy generated by GA meetthe required constraint of deadlock-free, Petri net is involved to make the implementation of thejob scheduling in an FMS deadlock-free. The effectiveness and efficiency of the proposed approach isillustrated by using an example.展开更多
In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its s...In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.展开更多
Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding an optimal deadlock-free schedules in a manufacturing system with very limited buffer is presented. This algorithm ...Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding an optimal deadlock-free schedules in a manufacturing system with very limited buffer is presented. This algorithm is based on the effective genetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect the token player assuring deadlock-free. In order to make the scheduling strategy generated by GA meet the required constraint of deadlock-free, some results of the structure analysis of Petri net are involved as a criterion to select deadlock-free schedule from the population generated by GA. The effectiveness and efficiency of the proposed approach is illustrated by using an example.展开更多
基金National Natural Science Foundation of China (No.60074011,70071017)
文摘An efficient algorithm for finding an optimal deadlock-free schedule in amanufacturing system with very limited buffer is presented. This algorithm is based on the effectivegenetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect thetoken player assuring deadlock-free. In order to make the scheduling strategy generated by GA meetthe required constraint of deadlock-free, Petri net is involved to make the implementation of thejob scheduling in an FMS deadlock-free. The effectiveness and efficiency of the proposed approach isillustrated by using an example.
基金This project is supported by Key Science-Technology Project of Shanghai City Tenth Five-Year-Plan, China (No.031111002)Specialized Research Fund for the Doctoral Program of Higher Education, China (No.20040247033)Municipal Key Basic Research Program of Shanghai, China (No.05JC14060)
文摘In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.
基金This project was supported by the National Natural Science Foundation of China (60074011, 70071017).
文摘Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding an optimal deadlock-free schedules in a manufacturing system with very limited buffer is presented. This algorithm is based on the effective genetic algorithm (GA) search method, and a formal Petri net structure is introduced to detect the token player assuring deadlock-free. In order to make the scheduling strategy generated by GA meet the required constraint of deadlock-free, some results of the structure analysis of Petri net are involved as a criterion to select deadlock-free schedule from the population generated by GA. The effectiveness and efficiency of the proposed approach is illustrated by using an example.
