一类带交货期约束的资源选择问题研究

研究生产计划和控制中带交货期约束且子任务之间具有先序关系的资源选择问题,证明了该问题是NP完全问题,目前该问题还没有多项式时间求解算法.建立了该问题的非线性整数规划模型,分析了模型中目标函数和约束函数的单调性,并根据该单调性构造了分支定界求解算法.与招投标算法比较,表明分支定界算法具有求解问题的规模大、运算速度快的优越性.

Research on Resource Selection with Due Date Constraint

In this paper,we consider the resource selection problem with due date constraint in production planning and control where the sub-tasks form a precedence network.We prove that this problem is NP-complete.Thus this problem cannot have any polynomial time solution algorithm at present.We establish a nonlinear integer-programming model for this problem,and prove the monotonicity properties of the objective function and constraint function in the model.Basing on our observations,we construct a Branch and Bound method to solve the problem.The Branch and Bound method is superiority compared with bidding algrithm in the scale and calculation speed to resolve this problem.