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 & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103
References:
[1]

D. D. BochtisP. DogoulisP. BusatoC. G. SorensenR. Berruto and T. Gemtos, A flow-shop problem formulation of biomass handling operations scheduling, Computers and Electronics in Agriculture, 49 (2013), 49-56.   Google Scholar

[2]

D. D. Bochtisa, C. G. C. Sorensena and P. Busato, Advances in agricultural machinery management: A review, Biosystems-Engineering, 2014, 69-81. Google Scholar

[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. Google Scholar

[4]

Z. Hu, A green reaping farm machine scheduling model, Acta Agriculture Shanghai, 30 (2014), 133-135.   Google Scholar

[5]

M. A. JensenD. D. BochtisC. G. SorensenM. R. Blas and K. L. Lykkegaard, In-field and inter-field path planning for agricultural transport units, Computers & Industrial Engineering, 63 (2012), 1054-1061.   Google Scholar

[6]

P. Jin, Study on agricultural machinery scheduling management system, Chinese Academy of Agricultural Sciences, 2012. Google Scholar

[7]

H. LiG. Yao and L. Chen, Farm machinery monitoring and scheduling system based on GPS, GPRS and GIS, Transactions of the CSAE, 24 (2008), 119-122.   Google Scholar

[8]

T. Li, Simulation modeling of agricultural machinery emergency deployment under extreme weather, Bulletin of Science and Technology, 12 (2014), 193-195.   Google Scholar

[9]

B. LiuH. HuangS. 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.   Google Scholar

[10]

A. OrfanouP. BusatoD. D. BochtisG. Edwards and D. Pavlou, Scheduling for machinery fleets in biomass multiple-field operations, Computers & electronics in agriculture, 94 (2013), 12-19.   Google Scholar

[11]

C. G. Sorensen and D. D. Bochtis, Conceptual model of fleet management in agriculture, Biosystems Engineering, 105 (2010), 41-50.   Google Scholar

[12]

SpekkenBruin and Sytze, Optimized routing on agricultural fields by minimizing maneuvering and servicing time, Precision Agriculture, 14 (2013), 224-244.   Google Scholar

[13]

S. WangW. Zhuang and X. Wang, Research on agricultural machinery remote control management system, Journal of Agricultural Mechanization Research, 37 (2015), 264-268.   Google Scholar

[14]

Z. WangL. Chen and Y. Liu, Design and implementation of agricultural machinery monitoring and scheduling system, Computer Engineering, 36 (2010), 232-234,237.   Google Scholar

[15]

S. Wei, Real-time monitoring system of combine harvester based on GPS and GIS, China Agricultural University, 2010. Google Scholar

[16]

C. WuY. CaiM. LuoH. 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.   Google Scholar

[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.   Google Scholar

[18]

L. YangC. LiS. JiaX. LiC. WuZh. Li and J. Gao, Design and implementation of Beijing agricultural machinery management system, Journal of Agriculture, 8 (2014), 96-100.   Google Scholar

[19]

F. Zhang, Study on Farm Machinery Scheduling and Allocating Strategies, Agricultural university of Hebei, 2012. Google Scholar

[20]

F. Zhang, Y. Gao and Y. Li, Research on Cross-Regional Emergency Scheduling and Allocating Strategies, 9 (2016), 89-98. Google Scholar

[21]

F. ZhangY. Li and C. Chen, Research on search-based scheduling and allocating algorithm, International Journal of Grid and Distributed Computing, 9 (2016), 167-180.   Google Scholar

[22]

F. ZhangG. Teng and S. Chang, Study on Farm Machinery Scheduling and allocating problem with heuristic priority rules, ICIC Express Letters, 7 (2012), 1797-1802.   Google Scholar

[23]

F. ZhangG. Teng and J. Ma, Research on multitask collaborative scheduling problem with heuristic strategies, Applied Mechanics and Materials, 68 (2011), 758-763.   Google Scholar

[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. Google Scholar

[25]

X. ZhuR. 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.   Google Scholar

show all references

References:
[1]

D. D. BochtisP. DogoulisP. BusatoC. G. SorensenR. Berruto and T. Gemtos, A flow-shop problem formulation of biomass handling operations scheduling, Computers and Electronics in Agriculture, 49 (2013), 49-56.   Google Scholar

[2]

D. D. Bochtisa, C. G. C. Sorensena and P. Busato, Advances in agricultural machinery management: A review, Biosystems-Engineering, 2014, 69-81. Google Scholar

[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. Google Scholar

[4]

Z. Hu, A green reaping farm machine scheduling model, Acta Agriculture Shanghai, 30 (2014), 133-135.   Google Scholar

[5]

M. A. JensenD. D. BochtisC. G. SorensenM. R. Blas and K. L. Lykkegaard, In-field and inter-field path planning for agricultural transport units, Computers & Industrial Engineering, 63 (2012), 1054-1061.   Google Scholar

[6]

P. Jin, Study on agricultural machinery scheduling management system, Chinese Academy of Agricultural Sciences, 2012. Google Scholar

[7]

H. LiG. Yao and L. Chen, Farm machinery monitoring and scheduling system based on GPS, GPRS and GIS, Transactions of the CSAE, 24 (2008), 119-122.   Google Scholar

[8]

T. Li, Simulation modeling of agricultural machinery emergency deployment under extreme weather, Bulletin of Science and Technology, 12 (2014), 193-195.   Google Scholar

[9]

B. LiuH. HuangS. 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.   Google Scholar

[10]

A. OrfanouP. BusatoD. D. BochtisG. Edwards and D. Pavlou, Scheduling for machinery fleets in biomass multiple-field operations, Computers & electronics in agriculture, 94 (2013), 12-19.   Google Scholar

[11]

C. G. Sorensen and D. D. Bochtis, Conceptual model of fleet management in agriculture, Biosystems Engineering, 105 (2010), 41-50.   Google Scholar

[12]

SpekkenBruin and Sytze, Optimized routing on agricultural fields by minimizing maneuvering and servicing time, Precision Agriculture, 14 (2013), 224-244.   Google Scholar

[13]

S. WangW. Zhuang and X. Wang, Research on agricultural machinery remote control management system, Journal of Agricultural Mechanization Research, 37 (2015), 264-268.   Google Scholar

[14]

Z. WangL. Chen and Y. Liu, Design and implementation of agricultural machinery monitoring and scheduling system, Computer Engineering, 36 (2010), 232-234,237.   Google Scholar

[15]

S. Wei, Real-time monitoring system of combine harvester based on GPS and GIS, China Agricultural University, 2010. Google Scholar

[16]

C. WuY. CaiM. LuoH. 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.   Google Scholar

[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.   Google Scholar

[18]

L. YangC. LiS. JiaX. LiC. WuZh. Li and J. Gao, Design and implementation of Beijing agricultural machinery management system, Journal of Agriculture, 8 (2014), 96-100.   Google Scholar

[19]

F. Zhang, Study on Farm Machinery Scheduling and Allocating Strategies, Agricultural university of Hebei, 2012. Google Scholar

[20]

F. Zhang, Y. Gao and Y. Li, Research on Cross-Regional Emergency Scheduling and Allocating Strategies, 9 (2016), 89-98. Google Scholar

[21]

F. ZhangY. Li and C. Chen, Research on search-based scheduling and allocating algorithm, International Journal of Grid and Distributed Computing, 9 (2016), 167-180.   Google Scholar

[22]

F. ZhangG. Teng and S. Chang, Study on Farm Machinery Scheduling and allocating problem with heuristic priority rules, ICIC Express Letters, 7 (2012), 1797-1802.   Google Scholar

[23]

F. ZhangG. Teng and J. Ma, Research on multitask collaborative scheduling problem with heuristic strategies, Applied Mechanics and Materials, 68 (2011), 758-763.   Google Scholar

[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. Google Scholar

[25]

X. ZhuR. 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.   Google Scholar

Figure 1.  Schematic diagram of emergency allocation of agricultural machinery
Figure 2.  Flow Chart of Emergency Allocation Algorithm with Rules of Short-Distance First
Figure 3.  Flow Chart of Emergency Allocation Algorithm with Rules of Max-Ability First
Table 1.  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
Table 2.  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
Table 3.  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
Table 4.  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%
Table 6.  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
Table 5.  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
Table 7.  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]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[2]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[3]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

[4]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019

[5]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[7]

Zhimin Chen, Kaihui Liu, Xiuxiang Liu. Evaluating vaccination effectiveness of group-specific fractional-dose strategies. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021062

[8]

Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159

2019 Impact Factor: 1.233

Article outline

Figures and Tables

[Back to Top]