排序问题的线性规划松弛方法  

Linear Programming Relaxation for Scheduling Problems

作　　者：贺向阳[1] 王洁明[1] 唐国春[1] 

机构地区：[1]上海第二工业大学理学院,上海201209

出　　处：《运筹与管理》2006年第2期8-12,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(10371071);上海市自然科学基金资助项目(03ZR14039);上海市教委科研项目(04RB06)

摘　　要：本文研究排序问题的线性规划松弛方法,对单台机器排序问题1|prec|ΣwjCj介绍基于三个确定性线性规划松弛的2—近似算法,对平行机排序问题R|rij|(wjCj介绍基于随机线性规划松弛的2—近似算法。这后一个算法对排序问题R|(wjCj|是3/2—近似算法.In this article we study linear programming relaxation for scheduling problems, and propose a 2-approximation algorithm based on relaxation of 3 linear prograrns for the single machine scheduling problem 1 ｜ prec｜ ∑wjCj and a 2-approximation algorithm based on random relaxation of a linear program for the parallel machine scheduling problem R ｜ rij ｜ ∑wjCj. The later is a 3/2-approximation algorithm for the problem R ｜｜ ∑wjCj.

关 键 词：运筹学 排序 线性规划 松弛 

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