摘要
研究生产计划和控制中带交货期约束且子任务之间具有先序关系的资源选择问题,证明了该问题是NP完全问题,目前该问题还没有多项式时间求解算法.建立了该问题的非线性整数规划模型,分析了模型中目标函数和约束函数的单调性,并根据该单调性构造了分支定界求解算法.与招投标算法比较,表明分支定界算法具有求解问题的规模大、运算速度快的优越性.
In this paper, wc 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.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2006年第5期99-105,共7页
Systems Engineering-Theory & Practice
基金
陕西省自然科学基金(2004E202)
教育部春晖计划项目(Z2005-1-61004)
关键词
资源选择
交货期
非线性整数规划
分支定界算法
resource selection
due date
nonlinear integer programming
branch and bound
