%0 Journal Article
%T A dual aggregated iterative algorithm for single machine scheduling problems<br>单机调度问题对偶集结迭代算法
%A ZUO Yan
%A XUE An-ke
%A WANG Jian-zhong
%A <br>左燕
%A 薛安克
%A 王建中
%J 控制理论与应用
%D 2010
%I 
%X The scheduling problem of minimizing the weighted completion time of n jobs with release dates on a single machine is strongly NP-hard. Its linear-programming relaxation based on time-indexed formulation provides a strong lower bound. However the number of constraints and variables can be large even for relative small instances. In this paper, a dual aggregated strategy is proposed to decrease the numbers of constraints by aggregating the dual multipliers with a decaying aggregation matrix. The structural properties of the aggregated model are also analyzed. An iterative method is proposed to improve the lower bound. Simulation results show that the dual aggregated iterative algorithm can reduce running time and improve lower bound. The application of these techniques still allows large-scale scheduling problems.
%K single machine scheduling
%K linear-programming relaxation
%K dual aggregation
%K time-indexed formulation<br>单机调度
%K 线性规划松弛
%K 对偶集结
%K 时间下标建模
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=970898A57DFC021F93AB51667BAED7F7&aid=99A993178991E862CA3208FDB1E372FC&yid=140ECF96957D60B2&vid=DB817633AA4F79B9&iid=59906B3B2830C2C5&sid=3F94E028184E4B65&eid=3CF1C8D14DE283F7&journal_id=1000-8152&journal_name=控制理论与应用&referenced_num=0&reference_num=0