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

Fan Zhang; Guifa Teng; Mengmeng Gao; Shuai Zhang; Jingjing Zhang

doi:10.3934/dcdss.2019103

Article Contents

2019, Volume 12, Issue 4&5: 1501-1513. Doi: 10.3934/dcdss.2019103 open access

This issue Previous Article An efficient RFID anonymous batch authentication protocol based on group signature Next Article Double layer programming model to the scheduling of remote sensing data processing tasks

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
* Corresponding author: Guifa Teng

Received: June 30, 2017

Revised: November 30, 2017

Published: March 2019

Abstract Full Text(HTML) Figure(3) / Table(7) Related Papers Cited by

Abstract

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.

Keywords:

Emergency allocation algorithm,
precedence rules,
allocating strategies multi-machine and multi-task.

Mathematics Subject Classification: Primary: 68W25; Secondary: 97P99.

Citation:

FullText(HTML)

Figure 1. Schematic diagram of emergency allocation of agricultural machinery

Download: Full-size image PowerPoint slide

Figure 2. Flow Chart of Emergency Allocation Algorithm with Rules of Short-Distance First

Download: Full-size image PowerPoint slide

Figure 3. Flow Chart of Emergency Allocation Algorithm with Rules of Max-Ability First

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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%

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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%

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.