Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (2): 231-240.doi: 10.11896/jsjkx.210400249

• Artificial Intelligence • Previous Articles     Next Articles

Dynamic Task Scheduling Method for Space Crowdsourcing

SHEN Biao, SHEN Li-wei, LI Yi   

  1. School of Computer Science,Fudan University,Shanghai 201203,ChinaShanghai Key Laboratory of Data Science (Fudan University),Shanghai 201203,China
  • Received:2021-04-23 Revised:2021-06-08 Online:2022-02-15 Published:2022-02-23
  • About author:SHEN Biao,born in 1996,postgraduate.His main research interests include the fusion of the ternary human-machine-thing and mobile cloud computing software system.
    SHEN Li-wei,born in 1982,Ph.D,associate professor.His main researchin-terests include the fusion of the ternary human-machine-thing,mobile application development and analysis,etc.
  • Supported by:
    National High Technology Research and Development Program of China(2018YB1004800).

PDF (PC)

683

Abstract: Space crowdsourcing is used to solve offline crowdsourcing tasks with time and space constraints,and it has developed rapidly in recent years.Task scheduling is an important research direction of space crowdsourcing.The difficulty lies in the dynamic uncertainty of tasks and workers in the scheduling process.In order to efficiently perform task scheduling,a dynamic task scheduling method for space crowdsourcing that considers the uncertainty of tasks and workers at the same time is proposed.The method has been improved in three aspects.First,the factors that need to be considered for scheduling are expanded.In addition to considering the uncertainty of the temporal and spatial attributes of the newly added tasks,it also considers the uncertainty of the transportation mode and temporal and spatial attributes of the newly added workers.Then,the scheduling strategy is improved.By using the aggregate scheduling strategy,the dynamically added tasks are aggregated first,and then the task allocation and path optimization are performed.Compared with the traditional non-aggregated scheduling,the calculation time is significantly reduced.The last aspect is to improve the scheduling algorithm.Based on the traditional genetic algorithm,the task allocation and path optimization operations are performed iteratively.Compared with the scheduling algorithm that first allocates tasks and then optimizes the path,it improves the accuracy of the optimal results.In addition,a simulation platform for dynamic scheduling of space crowdsourcing task paths based on real map navigation is designed and implemented,and the method is verified by this platform.

Key words: Genetic algorithm, Route planning, Space crowdsourcing, Task allocation, Task scheduling

CLC Number: 

  • TP311
[1]FAN Z J,SHEN L W,PENG X,et al.Multi stage task allocation on constrained spatial crowdsourcing[J].Chinese Journal of Computers,2019,42(12):2722-2741.
[2]WANG K,WANG Z J.Crowdsourcing Collaboration ProcessRecovery Method[J].Computer Science,2020,47(10):19-25.
[3]GUMMIDI S R B,XIE X,PEDERSEN T B.A survey of spatial crowdsourcing[J].ACM Transactions on Database Systems,2019,44(2):1-46.
[4]SUN D,XU K,CHENG H,etal.Online delivery route recommendation in spatial crowdsourcing[J].World Wide Web,2019,22(5):2083-2104.
[5]TAO Q,ZENG Y,ZHOU Z,et al.Multi-worker-aware taskplanning in real-time spatial crowdsourcing[C]//International Conference on Database Systems for Advanced Applications.Springer,2018:301-317.
[6]LIU G R.Study on express route optimization problem withsimultaneous delivery and pickup under dynamic demands[D].Chongqing :Chongqing University,2018.
[7]LIU M,SHEN Y,SHI Y.A hybrid brain storm optimization algorithm for dynamic vehicle routing problem[C] //International Conference on Swarm Intelligence.Springer,2020:251-258.
[8]LU X,TANG K,MENZEL S,et al.A competitive co-evolutio-nary optimizationmethod for the dynamic vehicle routing pro-blem[C]//Symposium Series on Computational Intelligence.IEEE,2020:305-312.
[9]SBAI I,KRICHEN S.An adaptive genetic algorithm for dyna-mic vehicle routingproblem with backhaul and two-dimensional loa-ding constraints[C]//International Multi-Conference on Organization of Knowledge and Advanced Technologies.IEEE,2020:1-7.
[10]TONG Y,ZHOU Z,ZENG Y,et al.Spatial crowdsourcing:asurvey[J].The VLDB Journal,2020,29(1):217-250.
[11]DENG D,SHAHABI C,DEMIRYUREK U.Maximizing thenumber of worker's self-selected tasks in spatial crowdsourcing[C]//21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2013:324-333.
[12]COSTA C F,NASCIMENTO M A.In-route task selection incrowdsourcing[C]//26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2018:524-527.
[13]ZHANG J,YANG F,WENG X.An evolutionary scatter search particle swarm optimization algorithm for the vehicle routing problem with time windows[J].IEEE Access,2018,6:63468-63485.
[14]YU D H,CHENG T,YUAN X.Software Crowdsourcing TaskRecommendation Algorithm Based on Learning to Rank[J].Computer Science,2020,47(12):106-113.
[15]LI Y,YIU M L,XU W.Oriented online route recommendationfor spatial crowd sourcing task workers[C]//International Symposium on Spatial and Temporal Databases.Springer,2015:137-156.
[16]COSLOVICH L,PESENTI R,UKOVICH W.A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem[J].European Journal of Operational Research,2006,175(3):1605-1615.
[17]ASGHARI M,SHAHABI C.On on-line task assignment in spatial crowdsourcing[C]//International Conference on Big Data (Big Data).IEEE,2017:395-404.
[18]HU Z H,SHEU J B,ZHAO L,et al.A dynamic closed-loop vehicle routingproblem with uncertainty and incompatible goods[J].Transportation Research Part C:Emerging Technologies,2015,55:273-297.
[19]MU Q,FU Z,LYSGAARD J,et al.Disruption management ofthe vehicle routingproblem with vehicle breakdown[J].Journal of the Operational Research Society,2011,62(4):742-749.
[20]GÜNER A R,MURAT A,CHINNAM R B.Dynamic routingunder recurrentand non-recurrent congestion using real-time its information[J].Computers & Operations Research,2012,39(2):358-373.
[21]CHO E,MYERS S A,LESKOVEC J.Friendship and mobility:user movement inlocation-based social networks[C]//17th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2011:1082-1090.
[22]SUN Y,WANG J,TAN W.Dynamic worker-and-task assignment on uncertain spatial crowdsourcing[C]//22nd Internatio-nal Conference on Computer Supported Cooperative Work in Design.IEEE,2018:755-760.
[23]FELDMAN J,MEHTA A,MIRROKNI V,et al.Online sto-chastic matching:Beating 1-1/e[C]//50th Symposium on Foundations of Computer Science.IEEE,2009:117-126.
[1] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] TAN Zhen-qiong, JIANG Wen-Jun, YUM Yen-na-cherry, ZHANG Ji, YUM Peter-tak-shing, LI Xiao-hong. Personalized Learning Task Assignment Based on Bipartite Graph [J]. Computer Science, 2022, 49(4): 269-281.
[3] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[4] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[5] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
[6] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[7] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[8] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[9] CAO Bo, CHEN Feng, CHENG Jing, LI Hua, LI Yong-le. Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search [J]. Computer Science, 2021, 48(11A): 77-80.
[10] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[11] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[12] CAI Ling-feng, WEI Xiang-lin, XING Chang-you, ZOU Xia, ZHANG Guo-min. Failure-resilient DAG Task Rescheduling in Edge Computing [J]. Computer Science, 2021, 48(10): 334-342.
[13] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[14] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[15] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.