Scheduling manufacturing systems with blocking: a Petri net approach. (English) Zbl 1198.90195
Summary: This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | DOI: 10.1287/opre.48.1.177.12451 · Zbl 1106.90334 · doi:10.1287/opre.48.1.177.12451 |
| [2] | DOI: 10.1080/00207540210136496 · Zbl 1083.90505 · doi:10.1080/00207540210136496 |
| [3] | DOI: 10.1016/j.ejor.2004.04.020 · Zbl 1066.90538 · doi:10.1016/j.ejor.2004.04.020 |
| [4] | Applegate D, ORSA Journal on Computing 3 pp 149– (1991) · Zbl 0755.90039 · doi:10.1287/ijoc.3.2.149 |
| [5] | DOI: 10.1057/palgrave.jors.2601359 · Zbl 1059.90063 · doi:10.1057/palgrave.jors.2601359 |
| [6] | Baker K, Introduction to sequencing and scheduling (1974) |
| [7] | Brandimarte P, Annals of Operations Research 22 pp 158– (1993) |
| [8] | DOI: 10.1016/S0925-5273(99)00104-8 · doi:10.1016/S0925-5273(99)00104-8 |
| [9] | DOI: 10.1109/70.650158 · doi:10.1109/70.650158 |
| [10] | DOI: 10.1145/356586.356588 · doi:10.1145/356586.356588 |
| [11] | Damasceno, B. 1999.Ordonnancement des systèmes de production multi-resources avec la prise en compte de blocage. Thesis (PhD). Université de Met. 1999, France. |
| [12] | Damasceno, BC and Xie, XL. 1999. Petri nets and deadlock-free scheduling of multiple-resource operations.In: Proceedings of the IEE Conference on Systems.Man and Cybernetics. 1999. Vol. 1, pp.878–883. |
| [13] | DOI: 10.1287/moor.1.2.117 · Zbl 0396.90041 · doi:10.1287/moor.1.2.117 |
| [14] | DOI: 10.1016/j.omega.2005.07.004 · doi:10.1016/j.omega.2005.07.004 |
| [15] | DOI: 10.1287/opre.44.3.510 · Zbl 0864.90060 · doi:10.1287/opre.44.3.510 |
| [16] | Huang B, International Journal of Production Research 1 pp 1– (2007) |
| [17] | DOI: 10.1023/A:1008097430956 · doi:10.1023/A:1008097430956 |
| [18] | DOI: 10.1016/j.apm.2006.10.023 · Zbl 1144.90383 · doi:10.1016/j.apm.2006.10.023 |
| [19] | Lawrence S, Resource constraint scheduling: an experimental investigation of heuristic scheduling techniques (1984) |
| [20] | DOI: 10.1109/70.282537 · doi:10.1109/70.282537 |
| [21] | DOI: 10.1080/00207540150504403 · Zbl 1060.90647 · doi:10.1080/00207540150504403 |
| [22] | DOI: 10.1016/S0377-2217(01)00338-1 · Zbl 1082.90528 · doi:10.1016/S0377-2217(01)00338-1 |
| [23] | DOI: 10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y · Zbl 1028.90018 · doi:10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y |
| [24] | Mati, Y, Rezg, N and Xie, X. Scheduling Problem of Job Shop with Blocking: a Taboo Search Approach.In:Proceedings of the MIC’2001–4th Metaheuristics International Conference. 16–20 July2001, Porto. pp.643–648. Portugal |
| [25] | DOI: 10.1023/A:1012260622596 · doi:10.1023/A:1012260622596 |
| [26] | DOI: 10.1287/opre.37.6.925 · Zbl 0689.90048 · doi:10.1287/opre.37.6.925 |
| [27] | Mejía G, Annals of Operations Research (2007) |
| [28] | DOI: 10.1016/S0278-6125(05)80009-3 · doi:10.1016/S0278-6125(05)80009-3 |
| [29] | Murata, T. 1989. Petri nets: properties, analysis and applications.In: Proceedings of the IEEE. 1989. pp.541–580. 77 (4) |
| [30] | DOI: 10.1016/j.ejor.2006.04.007 · Zbl 1180.90121 · doi:10.1016/j.ejor.2006.04.007 |
| [31] | DOI: 10.1016/j.rcim.2004.11.004 · doi:10.1016/j.rcim.2004.11.004 |
| [32] | DOI: 10.1109/70.499821 · doi:10.1109/70.499821 |
| [33] | DOI: 10.1016/S0166-3615(01)00124-5 · doi:10.1016/S0166-3615(01)00124-5 |
| [34] | DOI: 10.1109/21.23085 · doi:10.1109/21.23085 |
| [35] | DOI: 10.1057/palgrave.jors.2601220 · Zbl 1181.90125 · doi:10.1057/palgrave.jors.2601220 |
| [36] | Russel S, Artificial intelligence: a modern approach (1995) |
| [37] | DOI: 10.1016/S0360-8352(97)00325-2 · doi:10.1016/S0360-8352(97)00325-2 |
| [38] | DOI: 10.1109/41.334576 · doi:10.1109/41.334576 |
| [39] | DOI: 10.1109/66.705373 · doi:10.1109/66.705373 |
| [40] | DOI: 10.1016/S0360-8352(02)00212-7 · doi:10.1016/S0360-8352(02)00212-7 |
| [41] | DOI: 10.1016/j.ejor.2004.07.051 · Zbl 1085.90026 · doi:10.1016/j.ejor.2004.07.051 |
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.
