# American Institute of Mathematical Sciences

August & September  2019, 12(4&5): 1501-1513. doi: 10.3934/dcdss.2019103

## Multi-machine and multi-task emergency allocation algorithm based on precedence rules

 1 School of Information Science and Technology, Agricultural University of Hebei, Baoding 071000, China 2 Graduate School, Agricultural University of Hebei, Baoding 071000, China 3 School of Agricultural Mechanization, Agricultural University of Hebei, Baoding 071000, China 4 University College of Southeast Norway, Kongsberg, 3603 Vestfold, Norway 5 School of Foreign Language, Hebei University of Technology, Tianjin 300401, China

* Corresponding author: Guifa Teng

Received  July 2017 Revised  December 2017 Published  November 2018

Aiming at the problems of asymmetric information and unreasonable emergency allocation schemes in the current cross-regional emergency operation, the emergency deployment process of multi-machine and multi-task is analyzed, and the emergency allocation model with the goal of minimizing the allocation cost and loss is established in the paper. Emergency allocation algorithm based on rule of nearest-distance-first, which allocate machinery for the nearest farmland firstly, and emergency allocation algorithm based on rule of max-ability-first, by which machinery with maximum ability to farmland is allocated firstly, are proposed. The operational data of farmland and agricultural machinery generated randomly are calculated and analyzed. The results show that when the amount of agricultural machinery is sufficient, the algorithm based on the maximum contribution capacity priority is better. When the agricultural machinery is insufficient, the calculation results of the emergency allocation algorithm based on the nearest distance priority are better. When the number of farmland is not more than 30, the average operation time of the two algorithms in this paper is not more than 3.8 seconds, and both two algorithm have good performance.

Citation: Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103
##### References:
 [1] D. D. Bochtis, P. Dogoulis, P. Busato, C. G. Sorensen, R. Berruto and T. Gemtos, A flow-shop problem formulation of biomass handling operations scheduling, Computers and Electronics in Agriculture, 49 (2013), 49-56. [2] D. D. Bochtisa, C. G. C. Sorensena and P. Busato, Advances in agricultural machinery management: A review, Biosystems-Engineering, 2014, 69-81. [3] H. Ge and N. Liu, A stochastic programming model for relief resources allocation problem based on complex disaster scenarios, Systems Engineering-Theory & Practice, 2014, 3034-3042. [4] Z. Hu, A green reaping farm machine scheduling model, Acta Agriculture Shanghai, 30 (2014), 133-135. [5] M. A. Jensen, D. D. Bochtis, C. G. Sorensen, M. R. Blas and K. L. Lykkegaard, In-field and inter-field path planning for agricultural transport units, Computers & Industrial Engineering, 63 (2012), 1054-1061. [6] P. Jin, Study on agricultural machinery scheduling management system, Chinese Academy of Agricultural Sciences, 2012. [7] H. Li, G. Yao and L. Chen, Farm machinery monitoring and scheduling system based on GPS, GPRS and GIS, Transactions of the CSAE, 24 (2008), 119-122. [8] T. Li, Simulation modeling of agricultural machinery emergency deployment under extreme weather, Bulletin of Science and Technology, 12 (2014), 193-195. [9] B. Liu, H. Huang, S. Zhu and B. Xiang, Integrated management system of grain combine harvester based on Beidou & GPS, Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 31 (2015), 204-210. [10] A. Orfanou, P. Busato, D. D. Bochtis, G. Edwards and D. Pavlou, Scheduling for machinery fleets in biomass multiple-field operations, Computers & electronics in agriculture, 94 (2013), 12-19. [11] C. G. Sorensen and D. D. Bochtis, Conceptual model of fleet management in agriculture, Biosystems Engineering, 105 (2010), 41-50. [12] Spekken, Bruin and Sytze, Optimized routing on agricultural fields by minimizing maneuvering and servicing time, Precision Agriculture, 14 (2013), 224-244. [13] S. Wang, W. Zhuang and X. Wang, Research on agricultural machinery remote control management system, Journal of Agricultural Mechanization Research, 37 (2015), 264-268. [14] Z. Wang, L. Chen and Y. Liu, Design and implementation of agricultural machinery monitoring and scheduling system, Computer Engineering, 36 (2010), 232-234,237. [15] S. Wei, Real-time monitoring system of combine harvester based on GPS and GIS, China Agricultural University, 2010. [16] C. Wu, Y. Cai, M. Luo, H. Su and L. Ding, Time-windows based temporal and spatial scheduling model for agricultural machinery resources, Transactions of the Chinese Society of Agricultural Machinery, 44 (2013), 237-241. [17] H. Yang and W. Chen, Study on Emergency Vehicle Scheduling under Transportation network with uncertain disaster points, Safety and Environmental Engineering, 24 (2017), 26-30. [18] L. Yang, C. Li, S. Jia, X. Li, C. Wu, Zh. Li and J. Gao, Design and implementation of Beijing agricultural machinery management system, Journal of Agriculture, 8 (2014), 96-100. [19] F. Zhang, Study on Farm Machinery Scheduling and Allocating Strategies, Agricultural university of Hebei, 2012. [20] F. Zhang, Y. Gao and Y. Li, Research on Cross-Regional Emergency Scheduling and Allocating Strategies, 9 (2016), 89-98. [21] F. Zhang, Y. Li and C. Chen, Research on search-based scheduling and allocating algorithm, International Journal of Grid and Distributed Computing, 9 (2016), 167-180. [22] F. Zhang, G. Teng and S. Chang, Study on Farm Machinery Scheduling and allocating problem with heuristic priority rules, ICIC Express Letters, 7 (2012), 1797-1802. [23] F. Zhang, G. Teng and J. Ma, Research on multitask collaborative scheduling problem with heuristic strategies, Applied Mechanics and Materials, 68 (2011), 758-763. [24] F. Zhang, G. Teng, J. Yao and S. Dong, Research on Influenced Factors about Routing Selection Scheme in Agricultural Machinery Allocation, International Conference on Internet Technology Applications, 2010. [25] X. Zhu, R. Yani and H. Wang, Harvesting scheduling operations for the machinery owners under multi-farmland, multi-type situation with time window-an empirical study arising in agricultural contexts in China, INMATEH-Agricultural Engineering, 46 (2015), 175-182.

show all references

##### References:
 [1] D. D. Bochtis, P. Dogoulis, P. Busato, C. G. Sorensen, R. Berruto and T. Gemtos, A flow-shop problem formulation of biomass handling operations scheduling, Computers and Electronics in Agriculture, 49 (2013), 49-56. [2] D. D. Bochtisa, C. G. C. Sorensena and P. Busato, Advances in agricultural machinery management: A review, Biosystems-Engineering, 2014, 69-81. [3] H. Ge and N. Liu, A stochastic programming model for relief resources allocation problem based on complex disaster scenarios, Systems Engineering-Theory & Practice, 2014, 3034-3042. [4] Z. Hu, A green reaping farm machine scheduling model, Acta Agriculture Shanghai, 30 (2014), 133-135. [5] M. A. Jensen, D. D. Bochtis, C. G. Sorensen, M. R. Blas and K. L. Lykkegaard, In-field and inter-field path planning for agricultural transport units, Computers & Industrial Engineering, 63 (2012), 1054-1061. [6] P. Jin, Study on agricultural machinery scheduling management system, Chinese Academy of Agricultural Sciences, 2012. [7] H. Li, G. Yao and L. Chen, Farm machinery monitoring and scheduling system based on GPS, GPRS and GIS, Transactions of the CSAE, 24 (2008), 119-122. [8] T. Li, Simulation modeling of agricultural machinery emergency deployment under extreme weather, Bulletin of Science and Technology, 12 (2014), 193-195. [9] B. Liu, H. Huang, S. Zhu and B. Xiang, Integrated management system of grain combine harvester based on Beidou & GPS, Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 31 (2015), 204-210. [10] A. Orfanou, P. Busato, D. D. Bochtis, G. Edwards and D. Pavlou, Scheduling for machinery fleets in biomass multiple-field operations, Computers & electronics in agriculture, 94 (2013), 12-19. [11] C. G. Sorensen and D. D. Bochtis, Conceptual model of fleet management in agriculture, Biosystems Engineering, 105 (2010), 41-50. [12] Spekken, Bruin and Sytze, Optimized routing on agricultural fields by minimizing maneuvering and servicing time, Precision Agriculture, 14 (2013), 224-244. [13] S. Wang, W. Zhuang and X. Wang, Research on agricultural machinery remote control management system, Journal of Agricultural Mechanization Research, 37 (2015), 264-268. [14] Z. Wang, L. Chen and Y. Liu, Design and implementation of agricultural machinery monitoring and scheduling system, Computer Engineering, 36 (2010), 232-234,237. [15] S. Wei, Real-time monitoring system of combine harvester based on GPS and GIS, China Agricultural University, 2010. [16] C. Wu, Y. Cai, M. Luo, H. Su and L. Ding, Time-windows based temporal and spatial scheduling model for agricultural machinery resources, Transactions of the Chinese Society of Agricultural Machinery, 44 (2013), 237-241. [17] H. Yang and W. Chen, Study on Emergency Vehicle Scheduling under Transportation network with uncertain disaster points, Safety and Environmental Engineering, 24 (2017), 26-30. [18] L. Yang, C. Li, S. Jia, X. Li, C. Wu, Zh. Li and J. Gao, Design and implementation of Beijing agricultural machinery management system, Journal of Agriculture, 8 (2014), 96-100. [19] F. Zhang, Study on Farm Machinery Scheduling and Allocating Strategies, Agricultural university of Hebei, 2012. [20] F. Zhang, Y. Gao and Y. Li, Research on Cross-Regional Emergency Scheduling and Allocating Strategies, 9 (2016), 89-98. [21] F. Zhang, Y. Li and C. Chen, Research on search-based scheduling and allocating algorithm, International Journal of Grid and Distributed Computing, 9 (2016), 167-180. [22] F. Zhang, G. Teng and S. Chang, Study on Farm Machinery Scheduling and allocating problem with heuristic priority rules, ICIC Express Letters, 7 (2012), 1797-1802. [23] F. Zhang, G. Teng and J. Ma, Research on multitask collaborative scheduling problem with heuristic strategies, Applied Mechanics and Materials, 68 (2011), 758-763. [24] F. Zhang, G. Teng, J. Yao and S. Dong, Research on Influenced Factors about Routing Selection Scheme in Agricultural Machinery Allocation, International Conference on Internet Technology Applications, 2010. [25] X. Zhu, R. Yani and H. Wang, Harvesting scheduling operations for the machinery owners under multi-farmland, multi-type situation with time window-an empirical study arising in agricultural contexts in China, INMATEH-Agricultural Engineering, 46 (2015), 175-182.
Schematic diagram of emergency allocation of agricultural machinery
Flow Chart of Emergency Allocation Algorithm with Rules of Short-Distance First
Flow Chart of Emergency Allocation Algorithm with Rules of Max-Ability First
The basic information of emergent farmland.
 N0 Areas/hm$^{2}$ Longitude Latitude F$_{1}$ 0.333 114.413521 36.531836 F$_{2}$ 0.267 114.613724 36.452427 F$_{3}$ 0.433 114.682483 36.436548 F$_{4}$ 0.400 114.653451 36.675132 F$_{5}$ 0.333 114.533785 36.511864 F$_{6}$ 0.533 115.020156 36.672432
 N0 Areas/hm$^{2}$ Longitude Latitude F$_{1}$ 0.333 114.413521 36.531836 F$_{2}$ 0.267 114.613724 36.452427 F$_{3}$ 0.433 114.682483 36.436548 F$_{4}$ 0.400 114.653451 36.675132 F$_{5}$ 0.333 114.533785 36.511864 F$_{6}$ 0.533 115.020156 36.672432
The basic information of available agricultural machinery
 N0 Type of machinery Longitude Latitude M$_{1}$ 1 114.527263 36.495766 M$_{2}$ 1 114.323553 36.475637 M$_{3}$ 2 114.876027 36.301018 M$_{4}$ 2 115.162425 36.420928 M$_{5}$ 3 115.235720 36.442845 M$_{6}$ 3 114.593689 36.5024681 M$_{7}$ 1 115.299793 36.368265 M$_{8}$ 1 114.599927 36.573633 M$_{9}$ 2 114.852262 36.496237 M$_{10}$ 2 114.873121 36.552312 M$_{11}$ 3 115.014362 36.495874 M$_{12}$ 3 115.06645 36.530413
 N0 Type of machinery Longitude Latitude M$_{1}$ 1 114.527263 36.495766 M$_{2}$ 1 114.323553 36.475637 M$_{3}$ 2 114.876027 36.301018 M$_{4}$ 2 115.162425 36.420928 M$_{5}$ 3 115.235720 36.442845 M$_{6}$ 3 114.593689 36.5024681 M$_{7}$ 1 115.299793 36.368265 M$_{8}$ 1 114.599927 36.573633 M$_{9}$ 2 114.852262 36.496237 M$_{10}$ 2 114.873121 36.552312 M$_{11}$ 3 115.014362 36.495874 M$_{12}$ 3 115.06645 36.530413
the types information of agricultural machinery
 Working ability Operating fuel Types hm$^{2}$/h consumption L/h 1 3.5 0.47 2 5.4 0.67 3 7.2 1
 Working ability Operating fuel Types hm$^{2}$/h consumption L/h 1 3.5 0.47 2 5.4 0.67 3 7.2 1
Comparison results of two algorithms
 Losses/ Cost/ Total Completion Algorithm Yuan Yuan distances/Km ratio /% NDF 0.00 14537.50 652.30 100% MAF 0.00 14239.50 627.50 100%
 Losses/ Cost/ Total Completion Algorithm Yuan Yuan distances/Km ratio /% NDF 0.00 14537.50 652.30 100% MAF 0.00 14239.50 627.50 100%
the comparison of emergent allocation schemes with insufficient agricultural machinery
 No Losses/yuan Cost/yuan Total distances/Km NDF MAF NDF MAF NDF MAF 1 2534.50 2647.50 11304.40 11935.30 475.50 509.50 2 2741.50 2928.50 12126.10 12763.45 495.20 517.50 3 2495.00 2613.50 11465.50 12021.20 488.50 526.10 4 2839.50 3325.00 11867.50 12574.20 499.60 523.50 5 2864.00 2985.50 10457.20 11064.60 469.50 503.80 6 2930.50 3073.00 12629.50 12317.50 536.50 514.70 7 2205.00 2365.50 10522.70 10213.40 468.20 425.50 8 3359.50 3516.50 12625.50 11921.90 558.50 512.60
 No Losses/yuan Cost/yuan Total distances/Km NDF MAF NDF MAF NDF MAF 1 2534.50 2647.50 11304.40 11935.30 475.50 509.50 2 2741.50 2928.50 12126.10 12763.45 495.20 517.50 3 2495.00 2613.50 11465.50 12021.20 488.50 526.10 4 2839.50 3325.00 11867.50 12574.20 499.60 523.50 5 2864.00 2985.50 10457.20 11064.60 469.50 503.80 6 2930.50 3073.00 12629.50 12317.50 536.50 514.70 7 2205.00 2365.50 10522.70 10213.40 468.20 425.50 8 3359.50 3516.50 12625.50 11921.90 558.50 512.60
The comparison of emergent deployment schemes with adequate agricultural machinery
 No Losses/yuan Cost/yuan Total distances/Km NDF MAF NDF MAF NDF MAF 1 0.00 0.00 13247.20 13046.50 557.40 521.30 2 0.00 0.00 12646.30 12453.60 510.80 487.60 3 0.00 0.00 13527.70 13407.50 583.90 561.40 4 0.00 0.00 14216.50 14003.50 619.40 596.20 5 0.00 0.00 14639.70 14522.00 648.50 617.30 6 0.00 0.00 13257.90 13153.60 540.50 527.60 7 0.00 0.00 13863.50 13597.50 572.40 551.50 8 0.00 0.00 14739.50 14586.80 635.20 617.90
 No Losses/yuan Cost/yuan Total distances/Km NDF MAF NDF MAF NDF MAF 1 0.00 0.00 13247.20 13046.50 557.40 521.30 2 0.00 0.00 12646.30 12453.60 510.80 487.60 3 0.00 0.00 13527.70 13407.50 583.90 561.40 4 0.00 0.00 14216.50 14003.50 619.40 596.20 5 0.00 0.00 14639.70 14522.00 648.50 617.30 6 0.00 0.00 13257.90 13153.60 540.50 527.60 7 0.00 0.00 13863.50 13597.50 572.40 551.50 8 0.00 0.00 14739.50 14586.80 635.20 617.90
the comparison of average operation time among the two Algorithms
 Number of Average Operation Time/S Increasing Ratio Farmland NCG NDF MAF IR$_{1}$ IR$_{2}$ 6 3.185 2.214 2.345 30.49% 26.37% 10 4.257 2.624 2.648 38.36% 37.80% 15 5.368 3.215 3.198 40.11% 40.42% 30 6.463 3.524 3.699 45.47% 42.77%
 Number of Average Operation Time/S Increasing Ratio Farmland NCG NDF MAF IR$_{1}$ IR$_{2}$ 6 3.185 2.214 2.345 30.49% 26.37% 10 4.257 2.624 2.648 38.36% 37.80% 15 5.368 3.215 3.198 40.11% 40.42% 30 6.463 3.524 3.699 45.47% 42.77%
 [1] Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057 [2] Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076 [3] Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190 [4] Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial and Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11 [5] Raymond Ching Man Chan, Henry Ying Kei Lau. An AIS-based optimal control framework for longevity and task achievement of multi-robot systems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 45-56. doi: 10.3934/naco.2012.2.45 [6] Tzu-Hsin Liu, Jau-Chuan Ke. On the multi-server machine interference with modified Bernoulli vacation. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1191-1208. doi: 10.3934/jimo.2014.10.1191 [7] Xinwei Ma, Danli Wang, Nan Zheng, Song Zhang. Aggregation and Adjustment mechanisms for disaster relief task allocation with uneven distribution. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022015 [8] Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667 [9] Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085 [10] Zongwei Chen. An online-decision algorithm for the multi-period bank clearing problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021091 [11] Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140 [12] Irina Kareva, Faina Berezovkaya, Georgy Karev. Mixed strategies and natural selection in resource allocation. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1561-1586. doi: 10.3934/mbe.2013.10.1561 [13] Marcelo J. Villena, Mauricio Contreras. Global and local advertising strategies: A dynamic multi-market optimal control model. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1017-1048. doi: 10.3934/jimo.2018084 [14] T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial and Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53 [15] Ata Allah Taleizadeh, Biswajit Sarkar, Mohammad Hasani. Delayed payment policy in multi-product single-machine economic production quantity model with repair failure and partial backordering. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1273-1296. doi: 10.3934/jimo.2019002 [16] Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063 [17] Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097 [18] Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066 [19] Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151 [20] Bong Joo Kim, Gang Uk Hwang, Yeon Hwa Chung. Traffic modelling and bandwidth allocation algorithm for video telephony service traffic. Journal of Industrial and Management Optimization, 2009, 5 (3) : 541-552. doi: 10.3934/jimo.2009.5.541

2020 Impact Factor: 2.425