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

带到达时间分批排序问题的数学模型 被引量：3

Formulating the batch scheduling with release time as a mathematical programming model
在线阅读 下载PDF
导出
摘要 建立数学规划模型来研究排序问题是一件有意义的工作.本文对单机分批带到达时间的最大完工时间排序问题1|B,rj|Cmax(属NP-困难,LIU Z H等)建立了它的0-1整数规划模型;利用统计软件SAS中的LP过程编程对此模型进行了数值求解实验,得到了按此数学模型计算机能求得最优解的该问题的规模. It is a useful work to construct a mathematical programming model for studying the scheduling problem. In this paper a 0 - 1 programming model is formulated for the scheduling problem with release time on single batch processing machine minimizing makespan 1|B , rj | Cmax, (an NP-hard problem Liu et al (2000)). According to this model numerical tests are made and the sizes of computable instances are obtained.
作者 姜冠成
机构地区 苏州大学数学科学学院
出处 《苏州大学学报（自然科学版）》 CAS 2005年第2期22-27,共6页 Journal of Soochow University(Natural Science Edition)
关键词 排序问题 到达时间 数学模型 最大完工时间 数学规划模型 整数规划模型 NP-困难 数值求解 LP过程 统计软件 模型计算 SAS 最优解 batch scheduling makespan release time mathematical programming SAS
分类号 O223 [理学—运筹学与控制论] TN929.53 [电子电信—通信与信息系统]
  • 相关文献

参考文献10

二级参考文献23

  • 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.
  • 7DYER M E, WOLSEY L A. Formulatingthe single machine sequencing problem with release dates as a mixed integer program[J].Discrete Applied Mathematics, 1990, 26: 252-270.
  • 8GOEMANS M X, WILLIAMSON D P. Improved approximation algorithms for maximum cut andsatisfiability problems using semidefinite programming[J]. Journal of Association forComputing Machinery, 1995, 42:1115-1145.
  • 9GOEMANS M X, WEIN J M, WILLIAMSON D P. A 1.47-approximation algorithm for apreemptive singlemachine scheduling problem[J]. Operations Research Letters, 2000, 26:149-154.
  • 10HALL L A, SCHULZ A S, SHMOYS D B, WEIN J. Scheduling to minimize average completiontime: Offline and on-line approximation algorithms[J]. Mathematics of Operation Research,1997, 22(3): 513-544.

共引文献26

同被引文献91

引证文献3

二级引证文献15

苏州大学学报（自然科学版）
2005年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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