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

Keywords

• parallel machine scheduling problem(平行机调度问题)
• additional resources(额外资源)
• integer programming model(整数规划模型)
• branch and bound algorithm(分支定界算法)