Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2024, Vol. 51 Issue (3): 321-327    DOI: 10.3785/j.issn.1008-9497.2024.03.010
数学与计算机科学     
一类加工需要额外资源的平行机调度问题的算法设计
江明月1,简苏平1,崔晓龙2,万龙2,董建明3()
1.浙江理工大学 计算机科学与技术学院（人工智能学院），浙江 杭州 310018
2.江西财经大学 信息管理学院，江西 南昌 330032
3.浙江工商大学 管理工程与电子商务学院，浙江 杭州 310018
Algorithm design of the parallel machine scheduling problem with additional resource constraints
Mingyue JIANG1,Suping JIAN1,Xiaolong CUI2,Long WAN2,Jianming DONG3()
1.School of Computer Science and Technology （School of Artificial Intelligence），Zhejiang Sci-Tech University，Hangzhou 310018，China
2.School of Information Management，Jiangxi University of Finance and Economics，Nanchang 330032，China
3.School of Management Engineering and E-Business，Zhejiang Gongshang University，Hangzhou 310018，China
 全文: PDF(1566 KB)   HTML( 0 )
摘要：

给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件，除需要机器资源外，还需要一个单位额外资源的问题，考虑额外资源的种类和数量有限，以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载，在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法；给出了一种有效的分支策略以避免重复分支，设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验，验证了算法的正确性和在不同参数配置下的有效性。
关键词： 平行机调度问题;  额外资源;  整数规划模型;  分支定界算法    
Abstract:

An exact algorithm is presented for a parallel machine scheduling problem with additional resources constraints. Specifically, the jobs need be processed on parallel machines, and the processing of each job requires a unit of some additional resources in addition to machine resource. The variety and amount of additional resources are limited, our goal is to make the optimal schedule of the problem so that the completion time of the final completed job is minimized. This problem originates from the field of earth observation satellite data download, and has been widely used in intelligent manufacturing and information processing. The integer programming model, the lower bound of the optimal solution and the branch and bound algorithm of the problem are given. An effective branching strategy is proposed to avoid repeated branching and a bound method is designed to improve the convergence rate of the algorithm. The correctness and the effectiveness of the algorithm under different parameter configuration are verified by a large number of numerical simulation experiments and a small-sized instance example.
Key words: parallel machine scheduling problem    additional resources    integer programming model    branch and bound algorithm
收稿日期: 2023-03-20 出版日期: 2024-05-07
CLC:  O 226  
基金资助: 国家自然科学基金面上项目(11971435);国家自然科学基金地区科学基金项目(12261039)
通讯作者: 董建明     E-mail: djm226@163.com
作者简介: 江明月（1985—），ORCID： https：//orcid.org/0000-0002-0758-1616，女，博士，副教授，主要从事算法设计和分析、软件调试和智能软件工程等研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
江明月
简苏平
崔晓龙
万龙
董建明

引用本文:

江明月,简苏平,崔晓龙,万龙,董建明. 一类加工需要额外资源的平行机调度问题的算法设计[J]. 浙江大学学报（理学版）, 2024, 51(3): 321-327.

Mingyue JIANG,Suping JIAN,Xiaolong CUI,Long WAN,Jianming DONG. Algorithm design of the parallel machine scheduling problem with additional resource constraints. Journal of Zhejiang University (Science Edition), 2024, 51(3): 321-327.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2024.03.010    或    https://www.zjujournals.com/sci/CN/Y2024/V51/I3/321

图1  分支方案示意
参数工件1工件2工件3工件4工件5

加工时间

资源种类

5

1

2

1

4

2

3

1

3

2
表1  小规模实例的输入参数
图2  小规模实例分支定界算法过程
图3  小规模实例的最优解加工示意
参数平均运行时间tˉ/s

m=3，n=10，λ=2，ρ=2，pj∈0,10

m=3，n=10，λ=2，ρ=2，pj∈10,20

m=3，n=10，λ=2，ρ=3，pj∈0,10

m=3，n=10，λ=2，ρ=3，pj∈10,20

m=3，n=10，λ=3，ρ=2，pj∈0,10

m=3，n=10，λ=3，ρ=2，pj∈10,20

83

137

126

158

84

176
表2  3台机器10个工件的实验结果
参数平均运行时间tˉ/s

m=4，n=15，λ=2，ρ=2，pj∈0,10

m=4，n=15，λ=2，ρ=2，pj∈10,20

m=4，n=15，λ=2，ρ=3，pj∈0,10

m=4，n=15，λ=2，ρ=3，pj∈10,20

m=4，n=15，λ=3，ρ=2，pj∈0,10

m=4，n=15，λ=3，ρ=2，pj∈10,20

189

208

196

244

211

243
表3  4台机器15个工件的实验结果
参数平均运行时间tˉ/s

m=5，n=30，λ=3，ρ=2，pj∈0,10

m=5，n=30，λ=3，ρ=2，pj∈10,20

m=5，n=30，λ=2，ρ=3，pj∈0,10

m=5，n=30，λ=2，ρ=3，pj∈10,20

m=5，n=30，λ=4，ρ=2，pj∈0,10

m=5，n=30，λ=4，ρ=2，pj∈10,20

263

301

286

307

318

356
表4  5台机器30个工件的实验结果
参数平均运行时间tˉ/s

m=6，n=50，λ=2，ρ=3，pj∈0,10

m=6，n=50，λ=2，ρ=3，pj∈10,20

m=6，n=50，λ=3，ρ=3，pj∈0,10

m=6，n=50，λ=3，ρ=3，pj∈10,20

m=6，n=50，λ=3，ρ=4，pj∈0,10

m=6，n=50，λ=3，ρ=4，pj∈10,20

397

435

466

503

521

539
表5  6台机器50个工件的实验结果
1 PINEDO M. 调度： 原理、算法和系统［M］. 张智海，译. 北京： 清华大学出版社，2005.
PINEDO M. Scheduling： Theory， Algorithms， and System［M］. Translated by ZHANG Z H. Beijing： Tsinghua University Press， 2005.
2 GAREY M R， JOHNSON D S. Complexity results for multiprocessor scheduling under resource constraints［J］. SIAM Journal on Computing， 1975， 4（4）： 397-411. DOI：10.1137/0204035
doi: 10.1137/0204035
3 SRIVASTAV A， STANGIER P. Tight approximations for resource constrained scheduling and bin packing［J］. Discrete Applied Mathematics， 1997， 79（1/2/3）： 223-245. DOI：10.1016/S0166-218X（97）00045-0
doi: 10.1016/S0166-218X（97）00045-0
4 CAKICI E， MASON S J. Parallel machine scheduling subject to auxiliary resource constraints［J］. Production Planning and Control， 2007， 18（3）： 217-225. DOI：10.1080/09537280601035836
doi: 10.1080/09537280601035836
5 ABDELJAOUED M A， SAADANI N E H， BAHROUN Z. Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints［J］. Operational Research， 2020， 20： 2109-2132. DOI：10.1007/s12351-018-0412-3
doi: 10.1007/s12351-018-0412-3
6 HEBRARD E， HUGUET M J， JOZEFOWIEZ N， et al. Approximation of the parallel machine scheduling problem with additional unit resources［J］. Discrete Applied Mathematics， 2016， 215： 126-135. DOI：10.1016/j.dam.2016.07.003
doi: 10.1016/j.dam.2016.07.003
7 ZHANG A， ZHEN T， CHEN Y， et al. An improved algorithm for parallel machine scheduling under additional resource constraints［J］. Optimization Letters， 2023， 17： 753-769. DOI：10.1007/s11590-022-01928-z
doi: 10.1007/s11590-022-01928-z
8 JANSSEN T， SWENNENHUIS C， BITAR A， et al. Parallel Machine Scheduling with a Single Resource Per Job［Z/OL］. （2018-11-16）［2023-03-19］. .
9 胡觉亮， 李志林， 董建明. 工件加工需要额外资源的平行机调度问题［J］. 浙江理工大学学报（自然科学版），2022， 47（5）： 791-797. DOI：10.3969/j.issn.1673-3851（n）.2022.05.020
HUN J L， LI Z L， DONG J M. The parallel machine scheduling problem for job processing requiring extra resources［J］. Journal of Zhejiang Sci-Tech University（Natural Science Edition）， 2022， 47（5）： 791-797.DOI：10.3969/j.issn.1673-3851（n）.2022. 05.020
doi: 10.3969/j.issn.1673-3851（n）.2022. 05.020
10 KELLERER H， STRUSEVICH V A. Scheduling parallel dedicated machines under a single non-shared resource［J］. European Journal of Operational Research， 2003， 147（2）： 345-364. DOI：10.1016/S0377-2217（02）00246-1
doi: 10.1016/S0377-2217（02）00246-1
[1] 华荣伟, 潘虹, 严甜海. 可移动周期性维护排序问题的算法研究[J]. 浙江大学学报（理学版）, 2023, 50(3): 303-309.