期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

平行机排序问题的列生成解法 被引量：4

COLUMN GENERATION FOR SOLVING PARALLEL MACHINE SCHEDULING PROBLEM
原文传递
导出
摘要 基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.然后,结合动态规划和分枝定界技术,对大规模排序问题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.
作者 罗守成 陈峰 唐国春
机构地区 上海第二工业大学经济管理学院 上海交通大学
出处 《系统科学与数学》 CSCD 北大核心 2008年第6期739-746,共8页 Journal of Systems Science and Mathematical Sciences
基金 国家自然科学基金(10371071) 上海市教委科研基金(04RE16)资助课题
关键词 排序 整数规划 列生成 Scheduling, integer programming, column generation
分类号 O223 [理学—运筹学与控制论] TU991.4 [建筑科学—市政工程]
  • 相关文献

参考文献11

  • 1罗守成,张峰,唐国春.单机排序问题的数学规划表示[J].应用数学与计算数学学报,2000,14(2):77-82. 被引量：9
  • 2Phillips C A, Schulz A S, Shmoys D B, Stein C and Wein J. Improved bounds on relaxations of a parallel machine scheduling problem. Journal of Combinatorial Optimization, 1998, 1: 413-426.
  • 3Skutella M. Semidefinite relaxations for parallel machine scheduling. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998: 472-481.
  • 4Schulz A S and Skutella M. Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math., 2002, 15(4): 450-469.
  • 5朱道立.大系统优化理论与应用[M].上海:上海交通大学出版社,1987.120-139.
  • 6Chen Z L and Powell W B. A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research, 1999, 116: 220-232.
  • 7Chan L M A and A Muriel D Simchi-Levi. Parallel machine scheduling, linear programming, and parameter list scheduling heuristics. Operations Research, 1998, 46: 729-741.
  • 8Cattrysse D, Salomon M, Kuik R and van Wassenhove L N. A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup times. Management Science, 1993, 39(4): 477-486.
  • 9Vance P H. Branch-and-price: Column generation for solving huge integer programs. Operations Research, 1998, 46: 316-329.
  • 10Maxjan van den Akker, Han Hoogeveen and Steefvan de Velde. Combining column generation and lagrangean relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing, 2002, 14(1): 37-51.

二级参考文献6

  • 1[1]Goemans,M.X.and D.P.Williamson,.Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of Association for Computing Machinery,42(1995),1115-1145.
  • 2[2]Goemans,M.X.,Semidefinite programming in combinatorial optimization,Mathematical Programming,79(1997),143-161.
  • 3[3]Hall,L.A.,A.S.Schulz,D.B.Shmoys and J.Wein,Scheduling to minimize average completion time:Off-line and on-line approximation algorithms,Mathematics of Operations Research,22(1997),513-544.
  • 4[4]Phillips,C.,C.Stein and J.Wein,Minimizing average completion time in the presence of release dates,Mathematical Programming,82(1998),199-223.
  • 5[5]Phillips,C.A.,A.S.Schulz,D.B.Shmoys,C.Stein and J.Wein,Improved bounds on relaxations of a parallel machine scheduling problem,Journal of Combinatorial Optimization,1(1998),413-426.
  • 6[6]Skutella,Martin,Semidefinite relaxations for parallel machine scheduling,Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science,November,1998,472-481.

共引文献19

同被引文献50

  • 1高振,唐立新,汪定伟.列生成解大规模NP-hard整数与组合优化问题[J].信息与控制,2003,32(z1):604-607. 被引量：1
  • 2王伟玲,马正元,王玉生.生产调度问题研究的动态与趋势[J].组合机床与自动化加工技术,2005(5):109-112. 被引量：10
  • 3王莹,刘军.车站调度作业计划仿真建模的研究[J].铁路计算机应用,2005,14(9):1-4. 被引量：3
  • 4Schmidt G.Scheduling with limited machine availability[J].European Journal of Operational Research,2000,121(1):1-15.
  • 5Ma Y,Chu C,Zuo C.A survey of scheduling with deterministic machine availability constraints[J].Computers & Industrial Engineering,2009,In Press,Corrected Proof.
  • 6Lee C Y,Chen Z L.Scheduling jobs and maintenance activities on parallel machines[J].Naval Research Logistics,2000,47(2):145-165.
  • 7Vickson R G.Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine[J].Operations Research,1980,28(5):1155-1167.
  • 8Chen Z L.Simultaneous job scheduling and resource allocation on parallel machines[J].Annals of Operations Research,2004,129(1-4):135-153.
  • 9Wang J B,Xia Z Q.Single machine scheduling problems with controllable processing times and total absolute differences penalties[J].European Journal of Operational Research,2007,177(1):638-645.
  • 10Pinedo M.Scheduling:Theory,Algorithms,and Systems[M].New Jersey:Prentice Hall,Englewood Cliffs,1995.

引证文献4

二级引证文献17

系统科学与数学
2008年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部