浙江大学学报（理学版）2024，Vol.51Issue(3)：321-327,335,8.DOI:10.3785/j.issn.1008-9497.2024.03.010
一类加工需要额外资源的平行机调度问题的算法设计
Algorithm design of the parallel machine scheduling problem with additional resource constraints
摘要
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分类
数理科学引用本文复制引用
江明月,简苏平,崔晓龙,万龙,董建明..一类加工需要额外资源的平行机调度问题的算法设计[J].浙江大学学报（理学版）,2024,51(3):321-327,335,8.基金项目
国家自然科学基金面上项目(11971435) （11971435）
国家自然科学基金地区科学基金项目(12261039). （12261039）
