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

Algorithm design of the parallel machine scheduling problem with additional resource constraints

作　　者：江明月[1] 简苏平 崔晓龙 万龙[2] 董建明 JIANG Mingyue;JIAN Suping;CUI Xiaolong;WAN Long;DONG Jianming(School of Computer Science and Technology(School of Artificial Intelligence),Zhejiang Sci-Tech University,Hangzhou 310018,China;School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330032,China;School of Management Engineering and E-Business,Zhejiang Gongshang University,Hangzhou 310018,China)

机构地区：[1]浙江理工大学计算机科学与技术学院(人工智能学院),浙江杭州310018 [2]江西财经大学信息管理学院,江西南昌330032 [3]浙江工商大学管理工程与电子商务学院,浙江杭州310018

出　　处：《浙江大学学报（理学版）》2024年第3期321-327,335,共8页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金面上项目(11971435);国家自然科学基金地区科学基金项目(12261039).

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

关 键 词：平行机调度问题 额外资源 整数规划模型 分支定界算法 

分 类 号：O226[理学—运筹学与控制论]