A Two-Step Iterative Local Search for the Harvester Scheduling Problem With Splittable Workloads

Hongyu Lin; Jing Liang; Bo Jin; Caitong Yue; Yaonan Wang

doi:10.1109/JAS.2025.125768

Volume 13 Issue 7

Jul. 2026

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 18.3, Top 1 (SCI Q1)

CiteScore: 28.2, Top 1% (Q1)
Google Scholar h5-index: 95， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2026 > 13(7): 1584-1599

H. Lin, J. Liang, B. Jin, C. Yue, and Y. Wang, “A two-step iterative local search for the harvester scheduling problem with splittable workloads,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 7, pp. 1584–1599, Jul. 2026. doi: 10.1109/JAS.2025.125768

Citation:

H. Lin, J. Liang, B. Jin, C. Yue, and Y. Wang, “A two-step iterative local search for the harvester scheduling problem with splittable workloads,” IEEE/CAA J. Autom. Sinica, vol. 13, no. 7, pp. 1584–1599, Jul. 2026. doi: 10.1109/JAS.2025.125768

Citation:

PDF( 3472 KB)

A Two-Step Iterative Local Search for the Harvester Scheduling Problem With Splittable Workloads

doi: 10.1109/JAS.2025.125768

Funds: This work was supported in part by the National Natural Science Foundation of China (62106230, U23A20340, 62376253, 62176238), China Postdoctoral Science Foundation (2023M743185), and Henan Provincial Natural Science Foundation Project (242300420277)

More Information

Author Bio:
Hongyu Lin received the M.S. degree from Zhengzhou University. He is currently pursuing the Ph.D. degree at Zhengzhou University. His current research interests include evolutionary computing, multiobjective optimization, and combination optimization

Jing Liang (Senior Member, IEEE) received the B.E. degree in automation from Harbin Institute of Technology in 2003, and the Ph.D. degree in electrical and electronic engineering from Nanyang Technological University, Singapore, in 2009. She is currently a Professor with the School of Electrical Engineering and Automation, Henan Institute of Technology, and also with the School of Electrical and Information Engineering, Zhengzhou University. Her research interests include evolutionary computation, swarm intelligence, multiobjective optimization, and neural network

Bo Jin received the Ph.D. degree in management sciences from City University of Hong Kong, Hong Kong, China, in 2015. He is currently an Associate Professor at the College of Management, Shenzhen University. His research interests include mathematical modeling and optimization algorithms, with applications in production, manufacturing, transportation, and logistics

Caitong Yue received the B.E. degree and the Ph.D. degree from the School of Electrical Engineering, Zhengzhou University. He studied at the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, from June 2019 to June 2020. He is currently a Professor at the School of Electrical and Information Engineering, Zhengzhou University. His research interests include multimodal multiobjective optimization, pattern recognition, neural network, and particle swarm optimization

Yaonan Wang received the B.S. degree in computer engineering from East China Institute of Technology in 1981, and the M.S. and Ph.D. degrees in control engineering from Hunan University in 1990 and 1994, respectively. He is currently a Professor with the College of Electrical and Information Engineering, Hunan University. His research interests include machine vision, special robots, and intelligent control
Corresponding author: Jing Liang, e-mail: liangjing@zzu.edu.cn
Received Date: 2025-02-25
Revised Date: 2025-06-21
Accepted Date: 2025-08-05

Available Online: 2026-07-20

Abstract

Abstract

With the growing emphasis on intelligent agriculture, scheduling problems involving multiple harvesters in large-scale croplands have attracted increasing attention. In these scenarios, harvesters collaboratively perform tasks in expansive croplands, with each harvester taking on a portion of the workload. This study defines such problems as the harvester scheduling problem with splittable workloads (HSPSW). Unlike most multi-robot task allocation problems, HSPSW requires collaboration among several harvesters and involves more harvesters than croplands. These features increase the complexity of harvester-cropland interactions. To address these challenges, this paper proposes a novel two-step iterative local search (TSILS) algorithm. A greedy strategy that prioritizes croplands with higher workloads is proposed to generate initial solutions. Subsequently, a two-step iterative search strategy is employed to obtain high-quality solutions: the first step uses a predefined objective to facilitate rapid workload allocation for feasible solutions, and the second step integrates specific neighborhood operators and fine-grained local search to improve its search capability. Experimental results demonstrate that the proposed method TSILS significantly outperforms existing approaches in both algorithmic performance and computational efficiency.
- Cooperative operations,
- heuristic,
- local search,
- multi-harvester scheduling

FullText(HTML)

References(53)

References

[1]	J. Zhang, “Evaluation of farmers’ wheat production technical efficiency based on income increasing,” Ciênc. Rural, vol. 53, no. 6, Art. no. e20210828, 2023.
[2]	X. Yang, L. Shu, J. Chen, M. A. Ferrag, J. Wu, E. Nurellari, and K. Huang, “A survey on smart agriculture: Development modes, technologies, and security and privacy challenges,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 2, pp. 273–302, Feb. 2021. doi: 10.1109/JAS.2020.1003536
[3]	C. Zhang, L. Jia, S. Liu, G. Dou, Y. Liu, and B. Kong, “Dynamic job allocation method of multiple agricultural machinery cooperation based on improved ant colony algorithm,” Sci. Rep., vol. 14, no. 1, Art. no. 22414, Sep. 2024.
[4]	D. Bochtis and C. G. Sørensen, “The vehicle routing problem in field logistics part I,” Biosyst. Eng., vol. 104, no. 4, pp. 447−457, Dec. 2009.
[5]	T. Oksanen and A. Visala, “Coverage path planning algorithms for agricultural field machines,” J. Field Robot., vol. 26, no. 8, pp. 651–668, Aug. 2009. doi: 10.1002/rob.20300
[6]	Z. Lu, Y. Wang, F. Dai, Y. Ma, L. Long, Z. Zhao, Y. Zhang, and J. Li, “A reinforcement learning-based optimization method for task allocation of agricultural multi-robots clusters,” Comput. Electric. Eng., vol. 120, Art. no. 109752, Dec. 2024. doi: 10.1016/j.compeleceng.2024.109752
[7]	K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,” Comput. Ind. Eng., vol. 99, pp. 300–313, Sep. 2016. doi: 10.1016/j.cie.2015.12.007
[8]	P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia, USA: Society for Industrial and Applied Mathematics, 2002.
[9]	C. Archetti, M. G. Speranza, and M. W. P. Savelsbergh, “An optimization-based heuristic for the split delivery vehicle routing problem,” Transp. Sci., vol. 42, no. 1, pp. 22−31, Feb. 2008.
[10]	A. Allahverdi, “A survey of scheduling problems with no-wait in process,” Eur. J. Oper. Res., vol. 255, no. 3, pp. 665–686, Dec. 2016. doi: 10.1016/j.ejor.2016.05.036
[11]	H. Xiong, S. Shi, D. Ren, and J. Hu, “A survey of job shop scheduling problem: The types and models,” Comput. Oper. Res., vol. 142, Art. no. 105731, Jun. 2022. doi: 10.1016/j.cor.2022.105731
[12]	C. Archetti and M. G. Speranza, “The split delivery vehicle routing problem: A survey,” in The Vehicle Routing Problem: Latest Advances and New Challenges, B. Golden, S. Raghavan, and E. Wasil, Eds. Boston, USA: Springer, 2008, pp. 103−122.
[13]	P. Chen, B. Golden, X. Wang, and E. Wasil, “A novel approach to solve the split delivery vehicle routing problem,” Int. Trans. Operational Res., vol. 24, no. 1−2, pp. 27–41, Jan.–Mar. 2017. doi: 10.1111/itor.12250
[14]	G. Gao, Y. Mei, Y. H. Jia, W. N. Browne, and B. Xin, “Adaptive coordination ant colony optimization for multipoint dynamic aggregation,” IEEE Trans. Cybern., vol. 52, no. 8, pp. 7362–7376, Aug. 2022. doi: 10.1109/TCYB.2020.3042511
[15]	I. Kulachenko and P. Kononova, “A matheuristic for the drilling rig routing problem,” in Proc. 19th Int. Conf. Mathematical Optimization Theory and Operations Research, Novosibirsk, Russia, 2020, pp. 343−358.
[16]	P. Hansen and N. Mladenović, “Variable neighborhood search,” in Search Methodologies, E. K. Burke and G. Kendall, Eds. Boston, USA: Springer, 2005: 211−238.
[17]	P. He and J. K. Hao, “Memetic search for the minmax multiple traveling salesman problem with single and multiple depots,” Eur. J. Oper. Res., vol. 307, no. 3, pp. 1055–1070, Jun. 2023. doi: 10.1016/j.ejor.2022.11.010
[18]	S. Mahmoudinazlou and C. Kwon, “A hybrid genetic algorithm for the min-max multiple traveling salesman problem,” Comput. Oper. Res., vol. 162, Art. no. 106455, Feb. 2024. doi: 10.1016/j.cor.2023.106455
[19]	X. Bai, A. Fielbaum, M. Kronmüller, L. Knoedler, and J. Alonso-Mora, “Group-based distributed auction algorithms for multi-robot task assignment,” IEEE Trans. Autom. Sci. Eng., vol. 20, no. 2, pp. 1292–1303, Apr. 2023. doi: 10.1109/TASE.2022.3175040
[20]	W. Dai, A. Bidwai, and G. Sartoretti, “Dynamic coalition formation and routing for multirobot task allocation via reinforcement learning,” in Proc. IEEE Int. Conf. Robotics and Automation, Yokohama, Japan, 2024, pp. 16567−16573.
[21]	A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot task allocation: A review of the state-of-the-art,” in Cooperative Robots and Sensor Networks 2015, A. Koubâa and J. R. Martínez-de Dios, Eds. Cham, Germany: Springer, 2015, pp. 31−51.
[22]	L. Ke, Q. Zhang, and R. Battiti, “MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and AntColony,” IEEE Trans. Cybern., vol. 43, no. 6, pp. 1845–1859, Dec. 2013. doi: 10.1109/TSMCB.2012.2231860
[23]	X. Liu, Y. Fang, Z. Zhan, and J. Zhang, “Strength learning particle swarm optimization for multiobjective multirobot task scheduling,” IEEE Trans. Syst., Man, Cybern.: Syst., vol. 53, no. 7, pp. 4052–4063, Jul. 2023. doi: 10.1109/TSMC.2023.3239953
[24]	T. Qian, X. F. Liu, and Y. Fang, “A cooperative ant colony system for multiobjective multirobot task allocation with precedence constraints,” IEEE Trans. Evolut. Comput., vol. 29, no. 3, pp. 734–748, Jun. 2025. doi: 10.1109/TEVC.2024.3364493
[25]	M. Guo, B. Xin, Y. Wang, and J. Chen, “A local-search-based heuristic for coalition formation in urgent missions,” IEEE Trans. Syst., Man, Cybern.: Syst., vol. 54, no. 11, pp. 6924–6935, Nov. 2024. doi: 10.1109/TSMC.2024.3443860
[26]	S. Lu, B. Xin, J. Chen, and M. Guo, “An adaptive large neighborhood search for the multi-point dynamic aggregation problem,” Control Theory Technol., vol. 22, no. 3, pp. 360−378, Jan. 2024.
[27]	M. Li, Z. Wang, K. Li, X. Liao, K. Hone, and X. Liu, “Task allocation on layered multiagent systems: When evolutionary many-objective optimization meets deep Q-learning,” IEEE Trans. Evol. Computat., vol. 25, no. 5, pp. 842–855, Oct. 2021. doi: 10.1109/TEVC.2021.3049131
[28]	E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” TIK Report, vol. 103, ETH Zurich: Computer Engineering and Networks Laboratory, May 2001.
[29]	S. Li, M. Zhang, N. Wang, R. Cao, Z. Zhang, Y. Ji, H. Li, and H. Wang, “Intelligent scheduling method for multi-machine cooperative operation based on NSGA-III and improved ant colony algorithm,” Comput. Electron. Agric., vol. 204, Art. no. 107532, Jan. 2023. doi: 10.1016/j.compag.2022.107532
[30]	M. Lippi, J. Gallou, J. Palmieri, A. Gasparri, and A. Marino, “Human-multi-robot task allocation in agricultural settings: A mixed integer linear programming approach,” in Proc. 32nd IEEE Int. Conf. Robot and Human Interactive Communication, Busan, South Korea, 2023, pp. 1056−1062.
[31]	M. Wang, B. Zhao, Y. C. Liu, L. G. Wei, F. Z. Wang, and X. F. Fang, “Dynamic task allocation method for the same type agricultural machinery group,” Trans. Chin. Soc. Agric. Eng., vol. 37, no. 9, pp. 199–210, May 2021.
[32]	R. G. Smith, “The contract net protocol: High-level communication and control in a distributed problem solver,” IEEE Trans. Comput., vol. C-29, no. 12, pp. 1104–1113, Dec. 1980. doi: 10.1109/TC.1980.1675516
[33]	R. Cao, S. Li, Y. Ji, Z. Zhang, H. Xu, M. Zhang, M. Li, and H. Li, “Task assignment of multiple agricultural machinery cooperation based on improved ant colony algorithm,” Comput. Electron. Agric., vol. 182, Art. no. 105993, Mar. 2021. doi: 10.1016/j.compag.2021.105993
[34]	M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput. Intell. Mag., vol. 1, no. 4, pp. 28–39, Nov. 2006. doi: 10.1109/MCI.2006.329691
[35]	L. Liu, T. Chen, S. Gao, Y. Liu, S. Yang, and X. Wang, “Optimization of agricultural machinery allocation in Heilongjiang reclamation area based on particle swarm optimization algorithm,” Teh. Vjesn., vol. 28, no. 6, pp. 1885−1893, 2021.
[36]	N. Wang, X. Yang, T. Wang, J. Xiao, M. Zhang, H. Wang, and H. Li, “Collaborative path planning and task allocation for multiple agricultural machines,” Comput. Electron. Agric., vol. 213, Art. no. 108218, Oct. 2023. doi: 10.1016/j.compag.2023.108218
[37]	E. W. Dijkstra, “A note on two problems in connexion with graphs,” in Edsger Wybe Dijkstra: His Life, Work, and Legacy, K. R. Apt and T. Hoare, Eds. New York, USA: Association for Computing Machinery, 2022, pp. 287−290.
[38]	J. F. Yao, G. F. Teng, L. M. Huo, Y. C. Yuan, and F. Zhang, “Optimization of cooperative operation path for multiple combine harvesters without conflict,” Trans. Chin. Soc. Agric. Eng., vol. 35, no. 17, pp. 12–18, Sep. 2019.
[39]	M. A. F. Jensen, D. Bochtis, C. G. Sørensen, M. R. Blas, and K. L. Lykkegaard, “In-field and inter-field path planning for agricultural transport units,” Comput. Ind. Eng., vol. 63, no. 4, pp. 1054–1061, Dec. 2012. doi: 10.1016/j.cie.2012.07.004
[40]	K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints,” IEEE Trans. Evol. Computat., vol. 18, no. 4, pp. 577–601, Aug. 2014. doi: 10.1109/TEVC.2013.2281535
[41]	T. K. Ralphs, L. Kopman, W. R. Pulleyblank, and L. E. Trotter, “On the capacitated vehicle routing problem,” Math. Program., vol. 94, no. 2−3, pp. 343–359, Jan. 2003.
[42]	C. Archetti, M. G. Speranza, and A. Hertz, “A tabu search algorithm for the split delivery vehicle routing problem,” Transp. Sci., vol. 40, no. 1, pp. 64–73, Feb. 2006. doi: 10.1287/trsc.1040.0103
[43]	F. Pezzella, G. Morganti, and G. Ciaschetti, “A genetic algorithm for the Flexible Job-shop Scheduling Problem,” Comput. Oper. Res., vol. 35, no. 10, pp. 3202–3212, Oct. 2008. doi: 10.1016/j.cor.2007.02.014
[44]	A. K A, D. Udayan J, and U. Subramaniam, “A systematic literature review on multi-robot task allocation,” ACM Comput. Surv., vol. 57, no. 3, Art. no. 68, Mar. 2025. doi: 10.1145/3700591
[45]	S. H. Dai, Y. H. Jia, W. N. Chen, Y. Mei, and Q. Yang, “Multistage particle swarm optimization for heterogeneous multipoint dynamic aggregation,” IEEE Trans. Syst., Man, Cybern.: Syst., vol. 55, no. 7, pp. 4614–4628, Jul. 2025. doi: 10.1109/TSMC.2025.3553553
[46]	M. M. Silva, A. Subramanian, and L. S. Ochi, “An iterated local search heuristic for the split delivery vehicle routing problem,” Comput. Oper. Res., vol. 53, pp. 234–249, Jan. 2015. doi: 10.1016/j.cor.2014.08.005
[47]	H. Guo, Z. Miao, J. Ji, and Q. Pan, “An effective collaboration evolutionary algorithm for multi-robot task allocation and scheduling in a smart farm,” Knowl.-Based Syst., vol. 289, Art. no. 111474, Apr. 2024. doi: 10.1016/j.knosys.2024.111474
[48]	P. Hansen and N. Mladenović, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 449–467, May 2001. doi: 10.1016/S0377-2217(00)00100-4
[49]	Y. Yang, X. Su, B. Zhao, G. Li, P. Hu, J. Zhang, and L. Hu, “Fuzzy-based deep attributed graph clustering,” IEEE Trans. Fuzzy Syst., vol. 32, no. 4, pp. 1951–1964, Apr. 2024. doi: 10.1109/TFUZZ.2023.3338565
[50]	L. Wang, K. Liu, and Y. Yuan, “GT-A2T: Graph tensor alliance attention network,” IEEE/CAA J. Autom. Sinica, vol. 12, no. 10, pp. 2165–2167, Oct. 2025. doi: 10.1109/JAS.2024.124863
[51]	Y. Yuan, Y. Wang, and X. Luo, “A node-collaboration-informed graph convolutional network for highly accurate representation to undirected weighted graph,” IEEE Trans. Neural Netw. Learning Syst., vol. 36, no. 6, pp. 11507–11519, Jun. 2025. doi: 10.1109/TNNLS.2024.3514652
[52]	Y. Yang, G. Li, D. Li, J. Zhang, P. Hu, and L. Hu, “Integrating fuzzy clustering and graph convolution network to accurately identify clusters from attributed graph,” IEEE Trans. Netw. Sci. Eng., vol. 12, no. 2, pp. 1112–1125, Mar.–Apr. 2025. doi: 10.1109/TNSE.2024.3524077
[53]	L. Hu, X. Pan, Z. Tang, and X. Luo, “A fast fuzzy clustering algorithm for complex networks via a generalized momentum method,” IEEE Trans. Fuzzy Syst., vol. 30, no. 9, pp. 3473–3485, Sep. 2022. doi: 10.1109/TFUZZ.2021.3117442