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

基于到达时间两台并行机上在线批调度 被引量：4

On-line batch scheduling with real time on two parallel machines
原文传递
导出
摘要 考虑两台同构并行机上在线批调度问题.每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断.目标函数是使调度的最大完成时间最小.给出了一个批在线调度RBLPT-算法,即选择当前批中加工时间之和最大的批按LPT规则调度.另外,利用反证法,对算法的最坏情况进行了分析. On-line batch scheduling problem on two parallel machines is considered.Every batch has uncertain ready time.Once a machine is available,some batch is determined and the jobs in it are scheduled.Non-preemptive is permitted for processing jobs with objective to minimize makespan.An on-line batch scheduling RBLPT-algorithm is given,choose the batch with the maximum sum of processing time and then schedule by LPT-rule（the longest processing time first rule）.By contradiction,the worst case is analyzed.
作者 霍满臣 唐立新
机构地区 沈阳工程学院数学教研室 东北大学流程工业综合自动化教育部重点实验室
出处 《控制与决策》 EI CSCD 北大核心 2009年第12期1826-1830,1835,共6页 Control and Decision
基金 高等学校学科创新引智计划项目(B08015) 国家杰出青年科学基金项目(70425003) 国家自然科学基金项目(60674084) 辽宁省教育厅项目(20060589)
关键词 最大完成时间 最坏情况比 同构并行机 最小反例 加工时间 Makespan Worst case ratio Identical parallel machine Minimum contrary example Processing time
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献11

  • 1Pinedo.调度:原理、算法和系统[M].第2版.北京:清华大学出版社,2005.
  • 2Sgall J. On-line scheduling, online algorithms: The state of the art[J]. Lecture Notes in Computer Science,1998, 1442(5): 196-231.
  • 3Tang L, Liu J, Rong A, et al. An effective heuristic algorithm to minimise stack shufles in selecting steel slabs from the slab yard for heating and rolling[J]. J of the Operational Research Society, 2001, 52(10): 1091- 1097.
  • 4Tang L X, Liu J Y, Rong A Y, et al. A review of planning and scheduling systems and methods for integrated steel production[J]. European J of Operational Research, 2001, 133(3): 1-20.
  • 5Lixin Tang, Jiyin Liu, Aiying Rong, et al. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan iron & steel complex [J]. European J of Operational Research, 2000, 124 (2): 267-282.
  • 6Graham R. Bounds for certain multiprocessing anomalies [J]. Bell System Technology Journal, 1966, 45 (2): 1563-1581.
  • 7Potts C N, Kovalyov M Y. Scheduling with batching: A review[J]. European J of Operational Research, 2000, 120(3) : 228-249.
  • 8Mikhail A Kubzin, Vitaly A Strusevich. Two-machine flow shop no-wait scheduling with a nonavailability interval[J]. Naval Research Logistics, 2004, 51 (4): 613-632.
  • 9Celia A Glass, Hans Kellerer. Parallel machine scheduling with job assignment restrietions[J]. Naval Research Logistics, 2007, 54(10): 250-258.
  • 10Xiuli Wang, Edwin Cheng T C. Machine scheduling with an availability constraint and job delivery coordination[J]. Naval Research Logistics, 2007, 54 (10) : 11-21.

二级参考文献7

  • 1Wang Changjun Xi Yugeng.Rolling optimization algorithm based on collision window for single machine scheduling problem[J].Journal of Systems Engineering and Electronics,2005,16(4):816-822. 被引量：4
  • 2R. Bellman,,A. O. Esogbue,I. Nabeshima.Mathematical Aspects of Scheduling and Applications[]..1982
  • 3A. H. G. Kan Rinnooy.Machine Scheduling Problems: Classi?cation, Complexity and Computations[]..1976
  • 4J. Riezebos,,G. J. C. Gaalman.Time lag size in multiple operations ?ow shop scheduling heuristics[].European Journal of Operational Research.1998
  • 5C. Chekuri,S. Khanna.Approximation algorithms for minimizing average weighted completion time[].Handbook of Scheduling: Algorithms Models and Performance Analysis.2004
  • 6L. A. Hall,A. S. Schulz,D. B. Shmoys, et al.Scheduling to minimize average completion time: off-line and online approximationalgorithms[].Mathematics of Operations Research.1997
  • 7Fleszar K,Hindi K S.Solving the resource-constrained project scheduling problem by a variable neighbourhood search[].European Journal of Operational Research.2004

共引文献1

同被引文献49

  • 1霍满臣,唐立新.面向流程工业的批在线调度问题[J].控制工程,2005,12(6):511-514. 被引量：8
  • 2Hoogeveen J A, Velde S L. Earliness-tardiness schedulingaround almost equal due dates [J]. Informs J on Computing,1997,9(1): 92-99.
  • 3De P, Ghosh J B, Wells C E. Due-dates assignment andearly/tardy scheduling on identical parallel machines[J].Naval Research Logistics, 1994, 41(1): 17-32.
  • 4Cheng T C E, Chen Z L. Parallel-machine schedulingproblems with earliness and tardiness penalties [J]. J ofOperational Research Society, 1994,45(6): 685-695.
  • 5Arkin E M, Silverberg E B. Scheduling jobs with fixed startand end times [J]. Discrete Applied Mathematics, 1987,18(1): 1-8.
  • 6Bouzina K I,Emmons H. Interval scheduling on identicalmachines[J]. J Global Optimization, 1996,9(3/4): 379-393.
  • 7Bruno J, Coffman E G,Sethi R. Scheduling independenttasks to reduce mean finishing time[J]. Communications ofthe ACM, 1974, 17(7): 382-387.
  • 8Bar-Noy A, Guha S,Naor J S, et al. Approximating thethroughput of multiple machines in real-timescheduling[J]. SIAM J on Computing, 2001; 31(2): 331-352.
  • 9Sivrikaya F, Ulusoy G. Parallel machine schedulingwith earliness and tardiness penalties[J]. Computers &Operations Research, 1999,26(8): 773-787.
  • 10Kaplan S, Rabadi G. Exact and heuristic algorithms forthe aerial refueling parallel machine scheduling problemwith due date-to-deadline window and ready times[J].Computers & Industrial Engineering, 2012, 62(1): 276-285.

引证文献4

二级引证文献18

控制与决策
2009年 第12期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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