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

工件加工时间的可控排序问题 被引量：1

Scheduling problem with discretely controllable processing times
下载PDF
导出
摘要 讨论离散加工时间可控的排序问题P｜dis_cpt，pmtn｜ n∑j=1Cjtj＋Cmax,应用线性规划松弛方法得到其性能比为e/e-1（≈1.583）多项式时间近似算法. Abstract： The problem ofP｜dis_cpt,pmtn｜ n∑j=1Cjtj＋Cmax with discretely controllable processing times is discussed. A e/e-1（≈1.583）- approximation algorithm is obtained by linear programming relaxation.
作者 徐玲 张峰
机构地区 上海第二工业大学理学院
出处 《上海师范大学学报（自然科学版）》 2007年第4期34-39,共6页 Journal of Shanghai Normal University(Natural Sciences)
基金 国家自然科学基金(10371071) 上海市教委项目(07zz178).
关键词 排序 平行机 线性规划松弛 近似算法 scheduling parallel machines linear programming relaxation approximation algorithm
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献9

  • 1VICKSON R G.Choosing the job sequence and processing times to minimize total processing plus flow cost on single machine[J].Operations Research,1980,28:1155-1167.
  • 2NOWICKI E,ZDRZALKA S.A survey of results for sequencing problems with controllable processing times[J].Discrete Applied Mathematica,1990,26:271 -287.
  • 3HUANG W,ZHANG F.An O(n2) algorithm for a controllable machine scheduling problem[J].IMA J Math Appl in Business Industry,1999,10:15-26.
  • 4ZHANG F,TANG G,CHEN Z L.A 3/2-approximation algorithm for parallel machine scheduling with controllable proceasing times[J].Oper Res Lett,2001,29:41 -47.
  • 5张峰,唐国春.可控排序问题的凸二次规划松弛近似算法[J].自然科学进展（国家重点实验室通讯）,2001,11(11):1151-1156. 被引量：7
  • 6张峰.凸二次规划松弛方法研究离散加工时间可控排序问题[J].科学技术与工程,2002,2(2):59-61. 被引量：1
  • 7CHEN Z L,LU Q,TANG G.Single machine scheduling with discretely controllable processing times[J].Oper Res Lett,1997,21:69 -76.
  • 8HONGEVEEN H,SKUTELLA M,WOEGINGER G J.Preemptive scheduling with rejection[J].Math Programming,2003,94:361 -374.
  • 9LAWLER E L,LENSTRA J K,RINNOOY KAN A H G,et al.Sequencing and scheduling:Algorithm and complexity[A].GRAVES S C,RINNOOY KAN A H G,ZIPKIN P H(eds.).Logistics of Production and Inventory,Handbook in Operations Research and Management Science 4,Amsterdam,1993:445 -522.

二级参考文献11

  • 1[1]Skutella M. Semidefinite relaxations for parallel machine scheduling. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science;November,1998;472 - 481
  • 2[3]张峰,唐国春,陈志龙.A 3/2-approximation algorithm for parallel mach ine scheduling with controllable processing times. O R Letters,2001;1 1:41 - 47
  • 3[4]Chen Bo,Potts C N,Woeginger G J. A review of machine scheduling:complexity algorithms and approximability. Handbook of Combinatorial Optimization, Eds Du D Z,Paradalos P M.Kluwer Academic Publishers,1998:21 - 169
  • 4[5]Vickson R G. Choosing the job sequence and processing times to minimize total processing plus flow cost on single machine.Operations Research,1980;28:1155 - 1167
  • 5[6]Grotschel M,Lovasz L,Schrijver A.Geometric algorithms and combinatorial optimization. volume 2 of Algorithms and Combinatorics. Berlin:Springer, 1988
  • 6Goemans M X, et al. Irmproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of Association for Computing Machinery, 1995, 42:1115
  • 7Skutella M. Semidefinite relaxations for parallel machine scheduling. Proceedings of the 39th Annual IEEE Symposium on Foundations ofComputer Science, November, 1998. 472
  • 8Vickson R G. Choosing the job sequence and processing times to minimize total processing plus flow cost on single machine. OperationsResearch, 1980, 28:1155
  • 9Chen Bo, et al. A review of machine scheduling: Complexity algorithms and approximability, Handbook of Combinatorial Optimization.Du D Z, et al. eds. Kluwer: Academic Publishers, 1998. 21～169
  • 10Grotschel M, et al. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Berlin,Springer, 1988

共引文献6

同被引文献12

  • 1柏孟卓,唐国春.加工时间可控的同时加工排序问题[J].上海第二工业大学学报,2006,23(1):15-20. 被引量：5
  • 2张树霞,曹志刚,张玉忠.离散加工时间的可控排序问题(英文)[J].运筹学学报,2007,11(2):59-64. 被引量：4
  • 3B.Chen,C.N.potts,and G.J.Woegiger.1998.A Review of Machine Scheduling:Complexity,Algorithms,and Approximability[J].Operations Research Letters,1997(21):69-76.
  • 4N.G.Hall,M.A.Lesaoana,C.N.Potts,Scheduling with fixed delivery dates[J].Operations Research,2001(49):134-144.
  • 5C.L.Li,G.Vairaktarakis,C.Y.Lee,Machine scheduling with deliveries to multiple customer locations[J].European Journal of Operational Research,2005(164):39-51.
  • 6Z.M.Cheng and D.H.Xu.Parallel Machine Scheduling Problem With Preemptions and Release Times to Minimize Total Completion Time[J].2007(16):77-84.
  • 7B.Chen,C.Y.Lee.Logistics scheduling with batching and transportation[J].European Journal of Operational Research,2008,189(3):871-876.
  • 8Qi X.A logistics scheduling model:inventory cost reduction by batching[J].Naval Research Logistics(NRL),2005,52(4):312-320.
  • 9Wang X,Cheng T C E.Logistics scheduling to minimize inventory and transport costs[J].International Journal of Production Economics,2009,121(1):266-273.
  • 10Wang H.Two-stage logistics scheduling with two-mode transportation[J].To appear in Naval Research Logistics.2003.

引证文献1

二级引证文献1

上海师范大学学报（自然科学版）
2007年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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