贪心策略与调度规则融合的煤矸分拣机器人多任务分配方法

曹现刚; 丁文韬; 吴旭东; 王鹏; 藏家松; 刘依哲

doi:10.13272/j.issn.1671-251x.2025010038

贪心策略与调度规则融合的煤矸分拣机器人多任务分配方法

曹现刚^{1, 2,},
丁文韬^{1, 2},
吴旭东^{1, 2},
王鹏^{1, 2},
藏家松^{1, 2},
刘依哲^{1, 2}

1.
西安科技大学机械工程学院，陕西西安　710054
2.
陕西省矿山机电装备智能检测与控制重点实验室，陕西西安　710054

基金项目:

陕西省自然科学基础研究计划项目（2023-JC-YB-362）；陕西省教育厅自然科学研究项目（23JK0548）；陕西省重点研发计划项目（2024GX-YBXM-524）。

详细信息

作者简介:
曹现刚（1970—），男，山东莒南人，教授，博士，研究方向为设备健康维护与管理、机器人技术、煤矿机电装备智能化，E-mail：caoxg@xust.edu.cn

中图分类号: TD67
计量
- 文章访问数: 60
- HTML全文浏览量: 4
- PDF下载量: 5
出版历程
- 收稿日期: 2025-01-13
- 修回日期: 2025-04-09
- 网络出版日期: 2025-03-23
- 刊出日期: 2025-04-14

A multi-task allocation method for coal gangue sorting robots based on the integration of greedy strategy and scheduling rules

CAO Xiangang^{1, 2,},
DING Wentao^{1, 2},
WU Xudong^{1, 2},
WANG Peng^{1, 2},
ZANG Jiasong^{1, 2},
LIU Yizhe^{1, 2}

1.
College of Mechanical Engineering, Xi'an University of Science and Technology, Xi'an 710054, China
2.
Shaanxi Key Laboratory of Mine Electromechanical Equipment Intelligent Detection and Control, Xi'an 710054, China

摘要

摘要:
煤炭复杂的原煤开采工艺与原煤含矸率变化导致带式输送机上矸石的到达率、位置坐标和粒度大小呈现非线性变化，影响煤矸分拣的综合收益。在综合考虑矸石队列特征与排队论调度规则的基础上，提出了贪心策略与调度规则融合的多机械臂煤矸分拣机器人多任务分配方法。构建包含匹配矩阵、效益矩阵和环境状态矩阵的多机械臂煤矸分拣机器人多任务分配基础框架。分析矸石队列各维度信息特点与部分调度规则机理，研究不同调度规则间的组合方法，建立调度规则组合集，通过贪心策略比较不同时间窗口内不同调度规则的综合收益，以煤矸分拣过程中的分拣率与任务完成成功率作为综合收益，按照综合收益最大来选择调度规则进行多任务分配。搭建不同最大过煤量的时变原煤流仿真环境，进行多机械臂煤矸分拣机器人多任务分配仿真实验，结果表明：对于最大过煤量120，150 kg/s的时变原煤流样本，采用贪心策略与调度规则融合的煤矸分拣机器人多任务分配方法时矸石分拣率分别为97.69%，89.10%，较单一调度规则方法分别提升6.82%，5.67%；任务完成成功率为95.64%，86.46%，较单一调度规则方法分别提升3.02%，2.13%；机械臂利用率标准差较小，表明该方法降低了原煤流时变性对煤矸分拣综合收益的影响。
- 煤矸分拣机器人 /
- 多机械臂 /
- 时变原煤流 /
- 多任务分配 /
- 贪心策略 /
- 调度规则组合
Abstract:
The complex raw coal mining process and the variation in the raw coal gangue content result in nonlinear changes in the arrival time, position coordinates, and particle size of the gangue on the belt conveyor, which affects the overall benefits of coal gangue sorting. Based on a comprehensive consideration of the gangue queue characteristics and queuing theory scheduling rules, a multi-task allocation method for coal gangue sorting robots, integrating a greedy strategy and scheduling rules, was proposed. A basic framework for multi-task allocation of multi-arm coal gangue sorting robots was constructed, including a matching matrix, benefit function matrix, and environmental state matrix. The characteristics of each dimension of the gangue queue information and the mechanisms of some scheduling rules were analyzed. The combination methods of different scheduling rules were studied, and a scheduling rule combination set was established. Through the greedy strategy, the overall benefits of different scheduling rules within different time windows were compared, with the sorting rate and task completion success rate in the coal gangue sorting process serving as the overall benefit rate. The scheduling rule that maximized the overall benefit was selected for multi-task allocation. A time-varying raw coal flow simulation environment with different maximum coal throughput was set up for multi-robot coal gangue sorting task allocation simulation experiments. The results showed that for time-varying raw coal flow samples with maximum coal throughput of 120 and 150 kg/s, the coal gangue sorting rates were 97.69% and 89.10%, respectively, when using the proposed multi-task allocation method with a greedy strategy and scheduling rules, which was an improvement of 6.82% and 5.67%, respectively, compared to the single scheduling rule method. The task completion success rates were 95.64% and 86.46%, respectively, showing improvements of 3.02% and 2.13%, respectively. The standard deviation of robot arm utilization was lower, indicating that the method reduced the impact of the time-varying raw coal flow on the overall benefits of coal gangue sorting.
- coal gangue sorting robot /
- multi-robotic arms /
- time-varying raw coal flow /
- multi-task allocation /
- greedy strategy /
- scheduling rule combination

HTML全文

图 1 煤矸分拣机器人系统

Figure 1. Coal gangue sorting robot system

下载: 全尺寸图片幻灯片

图 2 煤矸分拣机器人多任务分配模型

Figure 2. Multi-task assignment model of coal gangue sorting robot

下载: 全尺寸图片幻灯片

图 3 多机械臂工作空间逻辑重构

Figure 3. Logic reconfiguration of multi-robotic armworkspace

下载: 全尺寸图片幻灯片

图 4 贪心策略与调度规则融合的煤矸分拣机器人多任务分配流程

Figure 4. Multi-task assignment process of coal gangue sorting robot integrating greedy strategy and scheduling rules

下载: 全尺寸图片幻灯片

图 5 过煤量及过矸量变化曲线

Figure 5. Change curves of coal throughput and gangue content

下载: 全尺寸图片幻灯片

图 6 多任务分配综合收益

Figure 6. Overall benefit of multi-task allocation

下载: 全尺寸图片幻灯片

图 7 调度规则组合选择次数热力图

Figure 7. Heatmap of scheduling rule selection times

下载: 全尺寸图片幻灯片

表 1 不同调度规则组合序号

Table 1 Corresponding sequence numbers of different scheduling rule combination

序号	规则组合	序号	规则组合
1	FIFO−MF−SPT	6	FIFO−FIFO−SPT
2	FIFO−FIFO−FIFO	7	FIFO−MF−MF
3	MF−MF−MF	8	FIFO−SPT−SPT
4	SPT−SPT−SPT	9	MF−SPT−SPT
5	FIFO−FIFO−MF	10	MF−MF−SPT

下载: 导出CSV

表 2 不同方法的机械臂利用率标准差

Table 2 Standard deviation of robotic arm utilization for different methods

多任务分配方法	不同最大过煤量时机械臂利用率标准差
多任务分配方法	90 kg/s	120 kg/s	150 kg/s
单一调度规则方法	0.035 6	0.027 3	0.017 2
最佳调度规则组合方法	0.007 6	0.007 6	0.009 9
本文方法	0.007 4	0.007 9	0.008 6

下载: 导出CSV

参考文献(28)

[1]	刘峰,郭林峰,赵路正. 双碳背景下煤炭安全区间与绿色低碳技术路径[J]. 煤炭学报,2022,47(1):1-15. LIU Feng,GUO Linfeng,ZHAO Luzheng. Research on coal safety range and green low-carbon technology path under the dual-carbon background[J]. Journal of China Coal Society,2022,47(1):1-15.
[2]	金向阳,李杨,于雷,等. 煤矿区绿色低碳评价指标构建及应用[J]. 煤炭科学技术,2024,52(4):131-142. DOI: 10.12438/cst.2023-1806 JIN Xiangyang,LI Yang,YU Lei,et al. Construction and application of green and low-carbon evaluation indicators for coal mining areas[J]. Coal Science and Technology,2024,52(4):131-142. DOI: 10.12438/cst.2023-1806
[3]	MIJAŁ W,TORA B. Development of dry coal gravity separation techniques[J]. IOP Conference Series:Materials Science and Engineering,2018,427(1). DOI: 10.1088/1757-899X/427/1/012003.
[4]	王鹏,曹现刚,夏晶,等. 基于机器视觉的多机械臂煤矸石分拣机器人系统研究[J]. 工矿自动化,2019,45(9):47-53. WANG Peng,CAO Xiangang,XIA Jing,et al. Research on multi-manipulator coal and gangue sorting robot system based on machine vision[J]. Industry and Mine Automation,2019,45(9):47-53.
[5]	侯晓松,李强. 智能机器人系统在煤矸分选工艺中的研究与应用[J]. 中国煤炭,2024,50(9):92-98. HOU Xiaosong,LI Qiang. Research and application of intelligent robot system in coal gangue sorting process[J]. China Coal,2024,50(9):92-98.
[6]	ZHAO Guozhen,CHANG Fengyi,CHEN Jiaxin,et al. Research and prospect of underground intelligent coal gangue sorting technology:a review[J]. Minerals Engineering,2024,215. DOI: 10.1016/J.MINENG.2024.108818.
[7]	JIANG Zhigang,HE Kunzhong,ZHANG Dongming. A review of intelligent coal gangue separation technology and equipment development[J]. International Journal of Coal Preparation and Utilization,2024,44(9):1308-1324.
[8]	李德永,王国法,郭永存,等. 基于CFS−YOLO算法的复杂工况环境下煤矸图像识别方法[J]. 煤炭科学技术,2024,52(6):226-237. DOI: 10.12438/cst.2023-1967 LI Deyong,WANG Guofa,GUO Yongcun,et al. Image recognition method of coal gangue in complex working conditions based on CES-YOLO algorithm[J]. Coal Science and Technology,2024,52(6):226-237. DOI: 10.12438/cst.2023-1967
[9]	朱子祺,李创业,代伟. 基于G−RRT^算法的煤矸石分拣机器人路径规划[J]. 工矿自动化,2022,48(3):55-62. ZHU Ziqi,LI Chuangye,DAI Wei. Path planning of coal gangue sorting robot based on G-RRT^ algorithm[J]. Journal of Mine Automation,2022,48(3):55-62.
[10]	WU Qihan,LI Meng,QI Xiaozhi,et al. Coordinated control of a dual-arm robot for surgical instrument sorting tasks[J]. Robotics and Autonomous Systems,2019,112:1-12. DOI: 10.1016/j.robot.2018.10.007
[11]	张烨,马宏伟,王鹏,等. 煤矸石智能分拣机器人研究进展与关键技术[J]. 工矿自动化,2022,48(12):42-48,56. ZHANG Ye,MA Hongwei,WANG Peng,et al. Research progress and key technologies of intelligent coal-gangue sorting robot[J]. Journal of Mine Automation,2022,48(12):42-48,56.
[12]	邓辅秦,黄焕钊,谭朝恩,等. 结合遗传算法和滚动调度的多机器人任务分配算法[J]. 计算机应用,2023,43(12):3833-3839. DENG Fuqin,HUANG Huanzhao,TAN Chao′en,et al. Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling[J]. Journal of Computer Applications,2023,43(12):3833-3839.
[13]	薛舒心,马亚杰,姜斌,等. 基于联盟形成博弈的异构无人机集群分布式任务分配算法[J]. 中国科学:信息科学,2024,54(11):2657-2673. XUE Shuxin,MA Yajie,JIANG Bin,et al. Distributed task allocation algorithm for heterogeneous unmanned aerial vehicle swarm based on coalition formation game[J]. Scientia Sinica(Informationis),2024,54(11):2657-2673.
[14]	翟政,何明,徐鹏,等. 基于市场机制的无人集群任务分配研究综述[J]. 计算机应用研究,2023,40(7):1921-1928. ZHAI Zheng,HE Ming,XU Peng,et al. Research review of task allocation for unmanned swarm based on market mechanism[J]. Application Research of Computers,2023,40(7):1921-1928.
[15]	刘占省,杨煜垚,史国梁. 融合聚类算法与改进哈里斯鹰算法的建筑机器人任务分配方法[J]. 建筑结构,2024,54(20):89-97,42. LIU Zhansheng,YANG Yuyao,SHI Guoliang. Improved Harris Hawk algorithm combined with clustering algorithm for task assignment of construction robots[J]. Building Structure,2024,54(20):89-97,42.
[16]	李卓,徐哲,陈昕,等. OTAP:基于预测的机会群智感知多任务在线分配算法[J]. 工程科学与技术,2018,50(5):176-182. LI Zhuo,XU Zhe,CHEN Xin,et al. OTAP:online multi-task assignment algorithm with prediction for opportunistic crowd sensing[J]. Advanced Engineering Sciences,2018,50(5):176-182.
[17]	WANG Wenfei,LYU Maolong,RU Le,et al. Multi-UAV unbalanced targets coordinated dynamic task allocation in phases[J]. Aerospace,2022,9(9). DOI: 10.3390/AEROSPACE9090491.
[18]	NOV Y,WEISS G,ZHANG Hanqin. Fluid models of parallel service systems under FCFS[J]. Operations Research,2022,70(2):1182-1218. DOI: 10.1287/opre.2021.2102
[19]	曹现刚,吴旭东,王鹏,等. 面向煤矸分拣机器人的多机械臂协同策略[J]. 煤炭学报,2019,44(增刊2):763-774. CAO Xiangang,WU Xudong,WANG Peng,et al. Collaborative strategy of multi-manipulator for coal-gangue sorting robot[J]. Journal of China Coal Society,2019,44(S2):763-774.
[20]	董雅文,孙家祺,张宝锋,等. 煤矸分拣多机械臂任务分配问题研究[J]. 煤炭工程,2024,56(1):170-176. DONG Yawen,SUN Jiaqi,ZHANG Baofeng,et al. Study on task allocation for multiple manipulators of coal gangue sorting[J]. Coal Engineering,2024,56(1):170-176.
[21]	MA Hongwei,WEI Xiaorong,WANG Peng,et al. Multi-arm global cooperative coal gangue sorting method based on improved Hungarian algorithm[J]. Sensors,2022,22(20). DOI: 10.3390/S22207987.
[22]	WANG Peng,MA Hongwei,ZHANG Ye,et al. A cooperative strategy of multi-arm coal gangue sorting robot based on immune dynamic workspace[J]. International Journal of Coal Preparation and Utilization,2023,43(5):794-814. DOI: 10.1080/19392699.2022.2078808
[23]	黄炳香,刘长友,程庆迎. 低位综放开采顶煤放出率与含矸率的关系[J]. 煤炭学报,2007,32(8):789-793. DOI: 10.3321/j.issn:0253-9993.2007.08.002 HUANG Bingxiang,LIU Changyou,CHENG Qingying. Relation between top-coal drawing ratio and refuse content for fully mechanized top coal carving[J]. Journal of China Coal Society,2007,32(8):789-793. DOI: 10.3321/j.issn:0253-9993.2007.08.002
[24]	朱帝杰,陈忠辉. 综放开采顶煤采出率预测模型的构建与应用[J]. 煤炭学报,2019,44(9):2641-2649. ZHU Dijie,CHEN Zhonghui. A model for top coal recovery ratio assessment and its application in longwall top coal caving[J]. Journal of China Coal Society,2019,44(9):2641-2649.
[25]	王雯,赵凯南,杨林,等. 面向复杂场景的层次式任务规划方法[J/OL]. 系统工程与电子技术:1-13[2025-01-02]. http://kns.cnki.net/kcms/detail/11.2422.TN.20241010.0913.004.html. WANG Wen,ZHAO Kainan,YANG Lin,et al. A hierarchical task planning approach for complex environments[J/OL]. Systems Engineering and Electronics:1-13[2025-01-02]. http://kns.cnki.net/kcms/detail/11.2422.TN.20241010.0913.004.html.
[26]	王凡通,王凌,高雁凤,等. 基于改进NSGA−Ⅱ算法的多AGV多任务分配研究[J]. 现代电子技术,2024,47(9):157-163. WANG Fantong,WANG Ling,GAO Yanfeng,et al. Research on multi-AGV multi-task allocation based on improved NSGA-Ⅱalgorithm[J]. Modern Electronics Technique,2024,47(9):157-163.
[27]	王鹏,曹现刚,马宏伟,等. 基于余弦定理−PID的煤矸石分拣机器人动态目标稳准抓取算法[J]. 煤炭学报,2020,45(12):797-804. WANG Peng, CAO Xiangang, MA Hongwei, et al. Dynamic target steady and accurate grasping algorithm of gangue sorting robot based on cosine theorem-PID[J]. Journal of China Coal Society, 2020, 45(12): 4240-4247.
[28]	WU Xudong,CAO Xiangang,WANG Peng,et al. Multi-task allocation framework of coal gangue sorting robot system for the time-varying raw coal flow[J]. International Journal of Coal Preparation and Utilization,2024,44(6):715-739. DOI: 10.1080/19392699.2023.2217657

施引文献(13)

期刊类型引用(8)

1.	刘明淳，许勇，池永锋，杨权，陈智斌. 基于Chaos-LSTM深度学习网络的边坡变形预测算法. 有色金属(矿山部分). 2025(01): 89-97+123 . 百度学术
2.	田光，李硕. 露天矿复杂边坡支护关键技术研究与发展. 采矿技术. 2025(02): 171-175 . 百度学术
3.	杜昌华，宋景辉，李蕊，田涯. 露天煤矿含断层顺倾边坡渗流与稳定性分析. 露天采矿技术. 2024(02): 51-55 . 百度学术
4.	牛犇，张新伟，周玉，李婧，徐兴全，张一鸣. 基于连续-非连续元降雨工况三维边坡稳定性分析. 山东大学学报(工学版). 2023(01): 92-99 . 百度学术
5.	刘光伟，郭直清，刘威. 基于GJO-MLP的露天矿边坡变形预测模型. 工矿自动化. 2023(09): 155-166 . 本站查看
6.	于雷，闫岩，邓巧巧. 基于大数据的矿山边坡稳定性评价模型. 自动化技术与应用. 2022(05): 138-140+174 . 百度学术
7.	耿佳弟，陈五一，彭志松. 基于离散元的岩土基坑边坡渗流耦合计算仿真. 计算机仿真. 2021(04): 240-243+482 . 百度学术
8.	苏伟. 露天地下协同开采对矿山地下水渗流场的影响. 采矿技术. 2021(06): 64-68 . 百度学术