Double layer programming model to the scheduling of remote sensing data processing tasks

Min-Fan He; Li-Ning Xing; Wen Li; Shang Xiang; Xu Tan

doi:10.3934/dcdss.2019104

Article Contents

2019, Volume 12, Issue 4&5: 1515-1526. Doi: 10.3934/dcdss.2019104 open access

This issue Previous Article Multi-machine and multi-task emergency allocation algorithm based on precedence rules Next Article A novel approach to improve the accuracy of the box dimension calculations: Applications to trabecular bone quality

Double layer programming model to the scheduling of remote sensing data processing tasks

1.
School of Mathematics and Big Data, Foshan University, Foshan 528000, China
2.
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
3.
Business School of Hunan University, Changsha 410082, China
4.
School of Software Engineering, Shenzhen Institute of Information Technology, Shenzhen 518172, China

* Corresponding author: Wen Li
* Corresponding author: Wen Li

Received: May 31, 2017

Revised: November 30, 2017

Published: March 2019

Abstract Full Text(HTML) Figure(6) / Table(1) Related Papers Cited by

Abstract

Remotely sensed data are widely used in disaster and environment monitoring. To complete the tasks associated with processing these data, it is a practical and pressing problem to match the resources for these data with data processing centers in real or near-real time and complete as many tasks on time as possible. However, scheduling remotely sensed data processing tasks has two phases, namely, task assignment and task scheduling. This paper presents a model using bilevel optimization, which considers task assignment and task scheduling as a single problem. Using this architecture, a mathematical model for both levels of the problem is presented. To solve the mathematical model, this paper presents a cooperative coevolution algorithm that combines the advantages of a very fast simulated annealing algorithm with a learnable ant colony optimization algorithm. Finally, the effectiveness and feasibility of the proposed approach compared with the conventional method is demonstrated through empirical results.

Keywords:

Mathematics Subject Classification: 90B35.

Citation:

FullText(HTML)

Figure 1. RSDPTCS module using bi-level programming

Download: Full-size image PowerPoint slide

Figure 2. Cooperative coevolution algorithm

Download: Full-size image PowerPoint slide

Figure 3. Maximum computation time comparison

Download: Full-size image PowerPoint slide

Figure 4. Average resource node load comparison

Download: Full-size image PowerPoint slide

Figure 5. Late completion comparison

Download: Full-size image PowerPoint slide

Figure 6. Processing time comparison

Download: Full-size image PowerPoint slide

Table 1. Distances between stations and processing

station1			station2
PC1	PC2	PC3	PC1	PC2	PC3
3420	3568	2954	2486	1471	1770

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	G. Aloisio, M. Cafaro and R. Williams, The digital Puglia project: An active digital library of remote sensing data, in Proceedings of the 7^th International Conference on High Performance Computing and Networking, HPCN-Europe, 1593 (1999), 563-572.
[2]	G. Aloisio, M.. Cafaro, R. Williams and P. Messina, A Distributed Web-Based Metacomputing Environment, in International Conference and Exhibition on High-Performance Computing and Networking, HPCN-Europe, 1225 (1997), 480-486.
[3]	G. Aloisio, M. Cafaro, S. Fiore and G. Quarta, A Grid-Based Architecture for Earth Observation Data Access, in ACM Symposium on Applied Computing, Santa Fe, New Mexico, USA, 2005.
[4]	G. Bai, L. Xing and Y. Chen, Scheduling multi-platforms collaborative disasters monitoring based on coevolution algorithm, Research Journal of Chemistry and Environment, 16 (2012), 43-50.
[5]	G. Bai, L. Xing and Y. Chen, The knowledge-based genetic algorithm to the disasters monitoring task allocation problem, Research Journal of Chemistry & Environment, 16 (2012), 27-34.
[6]	P. Caccetta, S. Collings, K. Hingee, D. McFarlane and X. Wu, Fine-Scale Monitoring of Complex Environments Using Remotely Sensed Aerial, Satellite, and Other Spatial Data, 2011 International Symposium on Image and Data Fusion, Tengchong, Yunnan, (2011), 1-5.
[7]	Y. Cao, S. Wang, L. Kang and Y. Gao, A TQCS-based service selection and scheduling strategy in cloud manufacturing, The International Journal of Advanced Manufacturing Technology, 82 (2016), 235-251.
[8]	Z. Chen, Y. Xue, J. Dong, J. Liu and Y. Li, The task scheduling for Remote Sensing Quantitative Retrieval based on hierarchical grid computing platform, 2012 IEEE International Geoscience and Remote Sensing Symposium, Munich, (2012), 487-490.
[9]	P. Chinnasamy and M. G. Sunde, Improving spatiotemporal groundwater estimates after natural disasters using remotely sensed data--a case study of the Indian Ocean Tsunami, Earth Science Informatics, 9 (2016), 101-111.
[10]	S. D. Dao, K. Abhary and R. Marian, An integrated production scheduling model for multi-product orders in VCIM systems, International Journal of System Assurance Engineering and Management, 8 (2017), 12-27.
[11]	J. Dong, Y. Xue, Z. Chen, H. Xu and Y. Li, Analysis of remote sensing quantitative inversion in cloud computing, 2011 IEEE International Geoscience and Remote Sensing Symposium, Vancouver, BC, (2011), 4348-4351.
[12]	J. Dong, Y. Xue, Z. Chen, H. Xu, Y. Li and C. Wu, A study of grid workflow dynamic customization for remote sensing quantitative retrieval, 2012 IEEE International Geoscience and Remote Sensing Symposium, Munich, (2012), 5382-5385.
[13]	Y. Guan, W. Xiao, R. Cheung and C. Li, A multiprocessor task scheduling model for berth allocation: Heuristic and worst-case analysis, Operations Research Letters, 30 (2002), 343-350. doi: 10.1016/S0167-6377(02)00147-5.
[14]	R. He and L. Xing, A learnable ant colony optimization to the mission planning of multiple satellites, Research Journal of Chemistry and Environment, 16 (2012), 18-26.
[15]	T. Jena and J. R. Mohanty, GA-based customer-conscious resource allocation and task scheduling in multi-cloud computing, Arabian Journal for Science and Engineering, (2017), 1-16.
[16]	A. Kamalinia and A. Ghaffari, Hybrid task scheduling method for cloud computing by genetic and DE algorithms, Wireless Personal Communications, to be published.
[17]	S. S. Karamchand, Operator Scheduling in a Distributed Stream Management System for Remotely Sensed Imagery, Ph.D thesis, University of California in Davis, USA, 2006.
[18]	I. Kucukkoc and D. Z. Zhang, Integrating ant colony and genetic algorithms in the balancing and scheduling of complex assembly lines, The International Journal of Advanced Manufacturing Technology, 82 (2016), 265-285.
[19]	W. Li, Y.-W. Chen, J.-F. Li and P. Gao, Remotely sensed data processing task scheduling based on limited concentration model, PIC2010, Shanghai, China, (2001), 15-18.
[20]	J. F. Li and L. Xing, Integrative Forest Fire Monitoring System Framework Design Aim to Early Warning Tasks, Disaster Advances, 5 (2012), 726-729.
[21]	H. Liu, Y. Fan, X. Deng and S. Ji, Parallel Processing Architecture of Remotely Sensed Image Processing System Based on Cluster, 2009 2^nd International Congress on Image and Signal Processing, Tianjin, (2009), 1-4.
[22]	Y. Ma, L. Wang, A. Y. Zomaya, D. Chen and R. Ranjan, Task-Tree Based Large-Scale Mosaicking for Massive Remote Sensed Imageries with Dynamic DAG Scheduling, IEEE Transactions on Parallel and Distributed Systems, 25 (2014), 2126-2137.
[23]	P. Myszkowski, M. E. Skowro$\acute{\rm{v}}$ski, L. P. Olech and K. Oślizłiptono, Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem, Soft Computing, 19 (2015), 3599-3619.
[24]	S. Nguyen, Y. Mei and M. Zhang, Genetic programming for production scheduling: A survey with a unified framework, Complex & Intelligent Systems, 3 (2017), 41-66.
[25]	S. Nguyen, A learning and optimizing system for order acceptance and scheduling, The International Journal of Advanced Manufacturing Technology, 86 (2016), 2021-2036.
[26]	S. K. Panda, I. Gupta and P. K. Jana, A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis, Information Systems Frontiers, to be published.
[27]	T. J. Pultz and R. A. Scofield, Applications of remotely sensed data in flood prediction and monitoring: Report of the CEOS Disaster Management Support Group flood team, IEEE International Geoscience and Remote Sensing Symposium, 2 (2002), 768-770.
[28]	M. A. Salido, J. Escamilla, A. Giret and F. Barber, A genetic algorithm for energy-efficiency in job-shop scheduling, The International Journal of Advanced Manufacturing Technology, 85 (2016), 1303-1314.
[29]	Y Shen, N Zhao, M Xia and X Du, A deep Q-learning network for ship stowage planning probleM, Polish Maritime Research, 24 (2017), 102-109.
[30]	S. Tehraniana, Y.-S. Zhao, T. Harveya, A. Swaroopa and M. Keith, A robust framework for real-time distributed processing of satellite data, Journal of Parallel Distributed Computing, 66 (2006), 403-418.
[31]	J. T. Tsai, J. C. Fang and J. H. Chou, Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm, Computers & Operations Research, 40 (2013), 3045-3055.
[32]	Z. Wang -F, Predictive Control of Networked Control Systems, Ph.D thesis, Zhe Jiang University, Zhe Jiang, China, 2008.
[33]	L. Wen, G. Peng, C. Ying-Wu and L. Ju-Fang, Approach of remotely sensed data processing task scheduling problem based on ant colony optimization, Proceedings of 2011 International Conference on Modelling, Identification and Control, Shanghai, (2011), 532-536.
[34]	C. S. Wong, F. T. S. Chan and S. H. Chung, A joint production scheduling approach considering multiple resources and preventive maintenance tasks, International Journal of Production ResearcH, 51 (2013), 883-896.
[35]	S. Wu, P. Zhang, F. Li, F. Gu and Y. Pan, A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems, Journal of Central South University, 23 (2016), 421-429.
[36]	B. Xiang, G. Q. Li, D. S. Liu and J. S. Li, Research on task management and scheduling of high performance remote sensing satellite ground pre-processing system, Journal of Astronautics, 29 (2008), 1443-1446.
[37]	Y. Xu, K. Li, J. Hu and K. Li, A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues, Information Sciences, 270 (2014), 255-287. doi: 10.1016/j.ins.2014.02.122.
[38]	K. Yang and L. Xing, The Learnable Ant Colony Optimization to Satellite Ground Station System Scheduling Problems, Przeglad Elektrotechniczny, 88 (2012), 62-65.
[39]	F. Yao and L. Xing, The Model, Algorithm and Application to Scheduling Problem of Agile Earth Observing Satellites, Disaster Advances, 5 (2012), 1112-1116.
[40]	H. Zheng, L. Wang and X. Zheng, Teaching--learning-based optimization algorithm for multi--skill resource constrained project scheduling problem, Soft Computing, 21 (2017), 1537-1548.
[41]	M. Zhu, G. Wang and T. Oyana, Parallel spatiotemporal autocorrelation and visualization system for large-scale remotely sensed images, The Journal of Supercomputing, 59 (2012), 83-103.
[42]	X. Zuo, G. Zhang and W. Tan, Self-adaptive learning pso-based deadline constrained task scheduling for hybrid iaas cloud, IEEE Transactions on Automation Science and Engineering, 11 (2014), 564-573.