摘要
具有项目投标价格和完工时间因素的带工期约束的伙伴选择问题是企业动态联盟的基本问题,证明了该问题是NP完全问题。为设计求解该问题的分支定界算法,建立了非线性整数规划模型。证明了模型中目标函数和约束函数的单调性,并利用单调性给出了判断问题无解和问题最优解已知的条件,构造了收缩求解区域的二分法。实验表明,基于这些结果所构造的分支定界算法是有效的。
The partner selection problem with bid cost and completion time factors with a due date constraint is a fundamental problem in virtual enterprises. This problem was proved to be a NP-complete problem. To develop a branch and bound method for this problem, a nonlinear integer-programming model was constructed. Monotone properties of objective function and constraint function were proved in this model. By the properties, a necessary and sufficient condition was found to determine an infeasible problem, and a sufficient condition was established to determine a problem with a known optimal solution. Moreover, a binary search method was designed to shrink sub-boxes generated by the method. Numerical experiments showed that the branch and bound method with these techniques was effective.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2006年第8期1340-1344,共5页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(50475039
10301009)~~
关键词
虚拟企业
伙伴选择
非线性整数规划
分支定界算法
virtual enterprises
partner selection
nonlinear integer-programming
branch and bound method
