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

工件尺寸不同的并行机批调度问题 被引量：1

Parallel-machine batch scheduling with non-identical job sizes
下载PDF
导出
摘要 考虑并行批加工机上不同尺寸工件的调度问题;目标是极小化最大完工时间.给出了一个(2+ε)-近似算法,ε>0可以任意小. The problem of scheduling jobs with non-identical sizes on parallel batehing machines is considered; the objective is to minimize the maximum completion time （makespan）. A （2 ＋ ε ）-approximation algorithm is presented, where ε〉 0 can be made arbitrarily small.
作者 杨振光 李曙光 王秀红
机构地区 鲁东大学数学与信息学院 山东大学数学与系统科学学院
出处 《山东大学学报（理学版）》 CAS CSCD 北大核心 2007年第4期63-66,共4页 Journal of Shandong University(Natural Science)
基金 国家自然科学基金资助项目(60373025)
关键词 近似算法 调度理论 批加工 最大完工时间 approximation algorithms scheduling theory batch processing makespan
分类号 O224 [理学—运筹学与控制论] TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献11

  • 1C Y Lee,R Uzsoy,L A Martin Vega.Efficient algorithms for scheduling semiconductor burn-in operations[J].Operations Research,1992,40:764～ 775.
  • 2C H Papadimitriou,K Steiglitz.Combinatorial optimization:algorithms and complexity[M].New Jersey:Prentice-Hall,Englewood Cliffs,1982.
  • 3P Brucker,A Gladky,H Hoogeveen,et al.Scheduling a batching machine[J].Journal of Scheduling,1998,1:31～54.
  • 4X Deng,C K Poon,Y Zhang.Approximation algorithms in batch processing[J].Journal of Combinatorial Optimization,2003,7(3):247 ～ 257.
  • 5M R Garey,D S Johnson.Computers and intractability:A guide to the theory of NP-completeness[M].New York:W H Freeman and Company,1979.
  • 6S Li,G Li,S Zhang.Minimizing makespan with release times on identical parallel batching machines[J].Discrete Applied Mathematics,2005,148(1):127～ 134.
  • 7R Uzsoy.A single batch processing machine with non-identical job sizes[J].International Journal of Production Research,1994,32:1 615 ～ 1 635.
  • 8G Zhang,X Cai,C Y Lee,et al.Minimizing makespan on a single batch processing machine with non-identical job sizes[J].Naval Rescarch Logistics,2001,48:226～240.
  • 9S Li,G Li,X Wang,et al.Minimizing makespan on a single batching machine with release times and non-identical job sizes[J].Operations Research Letters,2005,33:157～ 164.
  • 10L A Hall,D B Shmoys.Approximation schemes for constrained scheduling problems[A].Proceedings of the 30th annual IEEE Symposium on Foundations of Computer Science[C].North Carolina:IEEE Press,1989.134～ 139.

同被引文献19

  • 1庞新富,俞胜平,张志宇,郑秉霖,柴天佑.炼钢-连铸生产优化重调度方法[J].系统工程学报,2010,25(1):98-103. 被引量：26
  • 2Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615 - 1635.
  • 3Sung C S, Choung Y I. Minimizing makespan on a single bum-in oven in semiconductor manufacturing[J]. European Journal of Operational Research, 2000, 120(3): 559 - 574.
  • 4Dupont L, Flipo D C. Minimizing the makespan on a batch machine with nonidentical job sizes: An exact procesure[J]. Computers & Operations Research, 2002, 29(7): 807 - 819.
  • 5Sevaux M, Peres S D. Genetic algorithms to minimize the weighted number of late jobs on a single machine[J]. European Journal of Operational Research, 2003, 151(2): 296 - 306.
  • 6Koksalan M, Keha A B. Using genetic algorithms for single machine bicriteria scheduling problems[J]. European Journal of Operational Research, 2003, 145(3): 543 - 556.
  • 7Damodaran P, Manjeshwar P K, Sdhari K. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J]. International Journal of Production Economics, 2006, 103(2): 882 - 891.
  • 8Melouk S, Damodaran P, Chang P Y. Minimizing makespan for single machine batch processing with nonidentical job sizes using simulated annealing[J]. International Journal of Production Economic, 2004, 87(2): 141 - 147.
  • 9Parsa N R, Karimi B, Kashan A H. A branch and price algorithm to minimize makespan on a single batch processing machine withnon-identical job sizes[J]. Computers & Operations Research, 2010, 37(10): 1720- 1730.
  • 10Zhang G, Cai X, Lee C Y, et al. Minimizing makespan on a single batch processing machine[J]. Naval Research Logistics, 2001, 48(3): 226 - 240.

引证文献1

二级引证文献11

山东大学学报（理学版）
2007年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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