Deadlock-free scheduling in flexible manufacturing systems using Petri nets. (English) Zbl 1083.90505
Summary: This paper addresses the deadlock-free scheduling problem in Flexible Manufacturing Systems. An efficient deadlock-free scheduling algorithm was developed, using timed Petri nets, for a class of FMSs called Systems of Sequential Systems with Shared Resources (S\(^4\)R). The algorithm generates a partial reachability graph to find the optimal or near-optimal deadlock-free schedule in terms of the firing sequence of the transitions of the Petri net model. The objective is to minimize the mean flow time (MFT). An efficient truncation technique, based on the siphon concept, has been developed and used to generate the minimum necessary portion of the reachability graph to be searched. It has been shown experimentally that the developed siphon truncation technique enhances the ability to develop deadlock-free schedules of systems with a high number of deadlocks, which cannot be achieved using standard Petri net scheduling approaches. It may be necessary, in some cases, to relax the optimality condition for large FMSs in order to make the search effort reasonable. Hence, a User Control Factor (UCF) was defined and used in the scheduling algorithm. The objective of using the UCF is to achieve an acceptable trade-off between the solution quality and the search effort. Its effect on the MFT and the CPU time has been investigated. Randomly generated examples are used for illustration and comparison. Although the effect of UCF did not affect the mean flow time, it was shown that increasing it reduces the search effort (CPU time) significantly.
MSC:
| 90B30 | Production models |
| 90B35 | Deterministic scheduling theory in operations research |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | DOI: 10.1007/BF01438223 · doi:10.1007/BF01438223 |
| [2] | BEN ABDALLAH, I., ELMARAGHY, H. and ELMEKKAWY, T. A logic programming approach for finding minimal siphons in S3PR nets applied to manufacturing systems. Proceedings of the IEEE SMC’97. October, Orlando, Florida, USA. pp.1710–1715. |
| [3] | BEN ABDALLAH, I., ELMARAGHY, H. and ELMEKKAWY, T. An efficient search algorithm for deadlock-free scheduling in FMS using Petri nets. Proceedings of the IEEE International Conference on Robotics and Automation. May, Leuven, Belgium. pp.1793–1798. |
| [4] | BENABDALLAH, I., ELMEKKAWY, T. and ELMARAGHY, H. On deadlock-free scheduling in FMS. Proceedings of the IEEE SMC’98. October, La Jolla, California, USA. pp.366–371. |
| [5] | DOI: 10.1109/70.63273 · doi:10.1109/70.63273 |
| [6] | BARKAOUI, K. and BEN ABDALLAH, I. A deadlock prevention method for a class of FMS. Proceedings, IEEE International Conference on Systems, Man, and Cybernetics. Vancouver, British Columbia, Canada. Vol. 5, pp.4119–4124. |
| [7] | BARKAOUI, K. and BENABDALLAH, I. Analysis of a resource allocation problem in FMS using structure theory of Petri nets. Proceedings, First International Workshop on Manufacturing and Petri Nets. Osaka, Japan. pp.1–15. |
| [8] | BOUCHER T. O., IIE Transactions 32 pp 975– (2000) |
| [9] | CARLIER J., Advances in Petri Nets, LNCS 340 pp 62– (1988) |
| [10] | DiCESARE F., Practice of Petri Nets in Manufacturing (1993) · Zbl 0775.93171 · doi:10.1007/978-94-011-6955-4 |
| [11] | ELMEKKAWY T., Deadlock resolution in flexible manufacturing systems: a Petri nets based approach (2001) |
| [12] | ELMEKKAWY, T., BENABDALLAH, I. and ELMARAGHY, H. A heuristic search approach for deadlock-free scheduling in FMSs using Petri nets and AI techniques. Proceedings of 1998 ASME Computers in Engineering Conference. September, Atlanta, GA, USA. pp.1–8. |
| [13] | DOI: 10.1109/70.370500 · doi:10.1109/70.370500 |
| [14] | DOI: 10.1109/70.585898 · doi:10.1109/70.585898 |
| [15] | FANTI M. P., IEEE Transactions on Systems, Man, and Cybernetics 30 (2000) |
| [16] | DOI: 10.1109/70.282544 · doi:10.1109/70.282544 |
| [17] | DOI: 10.1023/A:1008097430956 · doi:10.1023/A:1008097430956 |
| [18] | JENG, M. D., CHIOU, W. D. and WEN, Y. L. Deadlock-free scheduling of flexible manufacturing systems based on heuristic search and Petri net structures. Proceedings of the IEEE SMC’98. October, La Jolla, California, USA. pp.26–31. |
| [19] | DOI: 10.1080/002075497195119 · Zbl 0943.90579 · doi:10.1080/002075497195119 |
| [20] | DOI: 10.1080/00207549408957073 · Zbl 0902.90082 · doi:10.1080/00207549408957073 |
| [21] | DOI: 10.1109/70.768182 · doi:10.1109/70.768182 |
| [22] | DOI: 10.1080/00207540050117378 · doi:10.1080/00207540050117378 |
| [23] | DOI: 10.1023/A:1007937925728 · doi:10.1023/A:1007937925728 |
| [24] | DOI: 10.1080/00207549508904872 · Zbl 0912.90121 · doi:10.1080/00207549508904872 |
| [25] | DOI: 10.1109/70.282537 · doi:10.1109/70.282537 |
| [26] | DOI: 10.1109/41.334577 · doi:10.1109/41.334577 |
| [27] | MINOURA T., International Journal of Robotics and Automation 6 pp 149– (1991) |
| [28] | PEARL J., Heuristics: Intelligent Search Strategies for Computer Problem Solving (1984) |
| [29] | PINEDO M., Scheduling: Theory, Algorithms, and Systems (1995) · Zbl 1145.90393 |
| [30] | DOI: 10.1109/70.499821 · doi:10.1109/70.499821 |
| [31] | DOI: 10.1109/70.744598 · doi:10.1109/70.744598 |
| [32] | DOI: 10.1109/70.544768 · doi:10.1109/70.544768 |
| [33] | DOI: 10.1109/9.633824 · Zbl 0892.90093 · doi:10.1109/9.633824 |
| [34] | DOI: 10.1016/0166-3615(92)90125-7 · doi:10.1016/0166-3615(92)90125-7 |
| [35] | SHIH, H. and SEKIGUCHI, T. A timed Petri net and beam search based on-line FMS scheduling system with routing flexibility. Proceedings of 1991 IEEE International Conference on Robotics and Automation. Sacramento, California, USA. pp.2548–2553. |
| [36] | VANDERAALST W. M. P., Application and Theory of Petri Nets, LNCS 691 pp 453– (1993) |
| [37] | DOI: 10.1109/70.63257 · doi:10.1109/70.63257 |
| [38] | DOI: 10.1109/5326.760564 · doi:10.1109/5326.760564 |
| [39] | DOI: 10.1109/9.481550 · Zbl 0845.90067 · doi:10.1109/9.481550 |
| [40] | XIONG, H. H., ZHOU, M. C. and CAUDIL, R. J. A hybrid heuristic search algorithm for scheduling flexible manufacturing systems. Proceedings of 1996 IEEE International Conference on Robotics and Automation. Minneapolis, Minnesota, USA. pp.2793–2797. |
| [41] | YALCIN A., Architectures for automated manufacturing cells with routing flexibility (2000) |
| [42] | DOI: 10.1109/70.864237 · doi:10.1109/70.864237 |
| [43] | DOI: 10.1080/002075497194606 · Zbl 0943.90542 · doi:10.1080/002075497194606 |
| [44] | DOI: 10.1007/978-1-4615-3126-5 · doi:10.1007/978-1-4615-3126-5 |
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.
