期刊文献+

Dominance property based tabu search for single machine scheduling problems with family setups

Dominance property based tabu search for single machine scheduling problems with family setups
下载PDF
导出
摘要 The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average. The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.
机构地区 Dept. of Automation
出处 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2009年第6期1233-1238,共6页 系统工程与电子技术(英文版)
基金 supported by the Major State Basic Research Development Program of China (973 Program)(2002CB312205) the National Natural Science Foundation of China (60574077 60874071 60834004) the National High Technology Research and Development Program of China (863 Program) (2007AA04Z102)
关键词 single machine family setups tabu search dominance property. single machine, family setups, tabu search, dominance property.
  • 相关文献

参考文献14

  • 1Baker K R. Heuristic procedures for scheduling job families with setups and due dates. Naval Research Logistics, 1999, 46(8): 978- 991.
  • 2Cheng T C E, Ng C T, Yuan J J. Single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard. Journal of Scheduling, 2003, 6(5): 483-490.
  • 3Lu L F, Yuan J J. The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard. European Journal of Operational Research, 2007, 177(2): 1302 -1309.
  • 4Mehta S V, Uzsoy R. Minimizing total tardiness on a batch processing machine with incompatible job families. HE Transactions, 1998, 30(2): 165- 178.
  • 5Baptiste P. Batching identical jobs. Mathematical Methods of Operations Research, 2000, 52(3): 355-367.
  • 6Mathirajan M, Sivakumar A I. A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. International Journal of Advanced Manufacturing Technology, 2006, 29(9-10): 990- 1001.
  • 7Van Der Zee D J, Van Harten A, Schuur P. On-line scheduling of multi-server batch operations. IIE Transactions, 2001, 33(7): 569 -586.
  • 8Schutten J M J, Van deValde S L, Zijm W H M. Single machine scheduling with release dates, due-dates and family setup times. Management Science, 1996, 42(8): 1165-1174.
  • 9Hariri A M A, Potts C N. Single machine scheduling with batch setup times to minimize maximum lateness. Annals of Operations Research, 1997, 70:75- 92.
  • 10Baker K R, Magazine M J. Minimizing maximum lateness with job families. European Journal of Operational Research, 2000, 127(1): 126 -139.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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