Please wait a minute...
浙江大学学报（理学版）
Journal of Zhejiang University (Science Edition)  2024, Vol. 51 Issue (3): 321-327    DOI: 10.3785/j.issn.1008-9497.2024.03.010
Mathematics and Computer Science     
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
Download: HTML( 0 )   PDF(1566KB)
Export: BibTeX | EndNote (RIS)      

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     
Received: 20 March 2023      Published: 07 May 2024
CLC:  O 226  
Corresponding Authors: Jianming DONG     E-mail: djm226@163.com
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Mingyue JIANG
Suping JIAN
Xiaolong CUI
Long WAN
Jianming DONG
Cite this article:

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.

URL:

https://www.zjujournals.com/sci/EN/Y2024/V51/I3/321


一类加工需要额外资源的平行机调度问题的算法设计

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


关键词： 平行机调度问题,  额外资源,  整数规划模型,  分支定界算法 
Fig.1 Branch scheme process figure
参数工件1工件2工件3工件4工件5

加工时间

资源种类

5

1

2

1

4

2

3

1

3

2
Table 1 Input parameter values for small-sized instance
Fig.2 The process of B&B algorithm for small-sized instance
Fig.3 Processing diagram for the optimal schedule of the small-sized instance
参数平均运行时间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
Table 2 Experimental results of 10 jobs on 3 machines
参数平均运行时间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
Table 3 Experimental results of 15 jobs on 4 machines
参数平均运行时间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
Table 4 Experimental results of 30 jobs on 5 machines
参数平均运行时间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
Table 5 Experimental results of 50 jobs on 6 machines
[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] Rongwei HUA, Hong PAN, Tianhai YAN. Scheduling problem with flexible periodic maintenance activities on two parallel machines[J]. Journal of Zhejiang University (Science Edition), 2023, 50(3): 303-309.