基于改进DP算法的具有优先序的变速机最小化成本调度

研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加工成本与机器使用成本之和的变速机调度问题.为该问题建立了DP模型,通过启发式规则和常规动态规划方法相结合、引入工件完工时间界限并保存每一步函数值,得到改进的DP算法,数值实验显示该算法具有较强的寻优能力和稳定性.

Scheduling of unrelated machines to minimize costs with precedence constraints based on amended DP algorithm

Scheduling of unrelated machines to minimize total costs of processing jobs and using machines subject to arbitrary standard precedence constraints is considered in this paper under the assumption that only one job is processed on one machine at the same time. A DP model is constructed for the problem, and an amended DP algorithm is derived through combining heuristic rule with conventional dynamic programming, introducing the bound of every job completion time and saving every function value. Numerical experiments are conducted to show that the algorithm has strong optimization capability and stability.