Complexity reduction for optimization of deterministic timed Petri-net scheduling by truncation. (English) Zbl 0821.90064
Summary: Methods of applying Petri nets to model and analyze scheduling problems, with constraints such as precedence relationships and multiple resource allocation, have been available in the literature. Searching for an optimum schedule can be implemented by combining the branch-and-bound technique with the execution of the timed Petri net. The resulting complexity problem in a large Petri net is handled by a truncation technique such that the original large Petri net is divided into several smaller subnets. The complexity involved in the analysis of each subnet individually is greatly reduced. However, as illustrated in this paper, the schedules for the subnets obtained by treating them separately may not lead to an optimal overall schedule for the original Petri net. To circumvent this problem, algorithms are developed that can be used to search for a proper schedule for each subnet such that the combination of these schedules yields an overall optimum schedule for the original timed Petri net. These algorithms are based on the idea of Petri net execution and branch-and-bound with modification. Finally, the practical application of the time Petri net truncation technique to scheduling problems in manufacturing systems is illustrated by an example of multirobot task scheduling.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B15 | Stochastic network models in operations research |
Keywords:
Petri nets; constraints; precedence relationships; multiple resource allocation; branch-and-bound; multirobot task schedulingReferences:
| [1] | Baker A., Introduction to sequencing and scheduling (1974) |
| [2] | Bellman R., Mathematical aspect of scheduling and applications (1982) |
| [3] | DOI: 10.1109/70.63270 · doi:10.1109/70.63270 |
| [4] | Carlier J., Adv. Petri Nets pp 62– (1984) |
| [5] | Carlier J., Adu. Petri Nets pp 62– (1988) |
| [6] | Chen , C. L. P. 1991 . Time lower bound for manufacturing aggregate scheduling problems . Proceedings of IEEE International Conference on Robotics and Automation , Sacramento , CA , April , pp. 830 – 835 . |
| [7] | Coffman E. G., Computer and job-shop scheduling theory (1976) · Zbl 0359.90031 |
| [8] | DOI: 10.1109/TC.1973.5009153 · doi:10.1109/TC.1973.5009153 |
| [9] | DOI: 10.1287/opre.21.5.1114 · Zbl 0294.90085 · doi:10.1287/opre.21.5.1114 |
| [10] | Freedman , P., andA. Malowany.1988.The analysis and optimization of repetition within robot workcell sequencing problems.Proceedings of IEEE International Conference on Robotics and Automation, Philadelphia, pp.1276–1281. |
| [11] | Freedman , P. , and A. Rachid . 1990 . Repetitive sequencing: from workcell tasks to workcell cycles . Proceedings of IEEE International Conference on Robotics and Automation , Cincinnati , pp. 1962 – 1967 . |
| [12] | Kusiak A., Intelligent manufacturing systems (1990) · Zbl 0691.90035 |
| [13] | et al. 1989 . Scheduling generation and reconfiguration for parallel machines . Proceedings of IEEE International Conference on Robotics and Automation , Scottsdale , AZ , pp. 528 – 533 . |
| [14] | DOI: 10.1109/70.63276 · doi:10.1109/70.63276 |
| [15] | DOI: 10.1109/5.24143 · doi:10.1109/5.24143 |
| [16] | Shen , L. , et al. 1992 . Truncation of Petri net models of scheduling problems for optimum solutions . Proceedings of 1992 Japan-US. A. Symposium on Flexible Automation , San Francisco , July . |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
