平行机排序问题的列生成解法  

COLUMN GENERATION FOR SOLVING PARALLEL MACHINE SCHEDULING PROBLEM

作　　者：罗守成[1] 陈峰[2] 唐国春[1] 

机构地区：[1]上海第二工业大学经济管理学院,上海201209 [2]上海交通大学,上海200030

出　　处：《系统科学与数学》2008年第6期739-746,共8页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(10371071);上海市教委科研基金(04RE16)资助课题

摘　　要：基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.然后,结合动态规划和分枝定界技术,对大规模排序问题P||∑w_jC_j提出一类求解精确(最优)解的列生成算法.According to the technique of linear relaxation of integer programming, a column generation principle is investigated for large scale total weighted completion time scheduling problems. Moreover, for the large scale scheduling problem P｜｜∑ωjCj, a class of column generation algorithms are presented based on the dynamic programming and branch and bound methods.

关 键 词：排序 整数规划 列生成 

分 类 号：O223[理学—运筹学与控制论] TU991.4[理学—数学]