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, 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.

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

[6]

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

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

[8]

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

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

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

[11]

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

[12]

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

[13]

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

[14]

Z. WangL. 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. 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.

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

[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. ZhangY. 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. ZhangG. 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. ZhangG. 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. 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.

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.

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

[6]

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

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

[8]

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

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

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

[11]

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

[12]

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

[13]

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

[14]

Z. WangL. 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. 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.

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

[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. ZhangY. 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. ZhangG. 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. ZhangG. 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. 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.

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]

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 & 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 & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076

[3]

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 & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[4]

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 & Optimization, 2012, 2 (1) : 45-56. doi: 10.3934/naco.2012.2.45

[5]

Tzu-Hsin Liu, Jau-Chuan Ke. On the multi-server machine interference with modified Bernoulli vacation. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1191-1208. doi: 10.3934/jimo.2014.10.1191

[6]

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

[7]

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

[8]

Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1233-1249. doi: 10.3934/dcdss.2019085

[9]

Marcelo J. Villena, Mauricio Contreras. Global and local advertising strategies: A dynamic multi-market optimal control model. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-11. doi: 10.3934/jimo.2018084

[10]

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 & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53

[11]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1413-1426. doi: 10.3934/dcdss.2019097

[12]

Bong Joo Kim, Gang Uk Hwang, Yeon Hwa Chung. Traffic modelling and bandwidth allocation algorithm for video telephony service traffic. Journal of Industrial & Management Optimization, 2009, 5 (3) : 541-552. doi: 10.3934/jimo.2009.5.541

[13]

Abderrahman Iggidr, Josepha Mbang, Gauthier Sallet, Jean-Jules Tewa. Multi-compartment models. Conference Publications, 2007, 2007 (Special) : 506-519. doi: 10.3934/proc.2007.2007.506

[14]

Geoffrey Beck, Sebastien Imperiale, Patrick Joly. Mathematical modelling of multi conductor cables. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 521-546. doi: 10.3934/dcdss.2015.8.521

[15]

Xin Li, Ziguan Cui, Linhui Sun, Guanming Lu, Debnath Narayan. Research on iterative repair algorithm of Hyperchaotic image based on support vector machine. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1199-1218. doi: 10.3934/dcdss.2019083

[16]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[17]

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

[18]

Franz Achleitner, Anton Arnold, Eric A. Carlen. On multi-dimensional hypocoercive BGK models. Kinetic & Related Models, 2018, 11 (4) : 953-1009. doi: 10.3934/krm.2018038

[19]

Anatoli F. Ivanov. On global dynamics in a multi-dimensional discrete map. Conference Publications, 2015, 2015 (special) : 652-659. doi: 10.3934/proc.2015.0652

[20]

Vivi Rottschäfer. Multi-bump patterns by a normal form approach. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 363-386. doi: 10.3934/dcdsb.2001.1.363

2017 Impact Factor: 0.561

Article outline

Figures and Tables

[Back to Top]