Grid Branch-and-Bound for Permutation Flowshop

详细信息    查看全文

• 作者：Maciej Drozdowski (1) Maciej.Drozdowski@cs.put.poznan.pl
  Pawe? Marciniak (1)
  Grzegorz Pawlak (1) Grzegorz.Pawlak@cs.put.poznan.pl
  Maciej P?aza (1) Maciej.Plaza@gmail.com
• 关键词：branch ; and ; bound – flowshop – grid computing
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7204
• 期：1
• 页码：21-30
• 全文大小：207.9 KB
• 参考文献：1. B?k, S., B?a?ewicz, J., Pawlak, G., P?aza, M., Burke, E., Kendall, G.: A parallel branch-and-bound approach to the rectangular guillotine strip cutting problem. INFORMS J. on Computing 23, 15–25 (2011)
  2. Clausen, J.: Branch and bound algorithms - principles and examples, Technical Report, Department of Computer Science, University of Copenhagen (1999)
  3. Crainic, T., Le Cun, B., Roucairol, C.: Parallel Branch-and-Bound Algorithms. In: Talbi, E.-G. (ed.) Parallel Combinatorial Optimization, pp. 1–28. John Wiley & Sons (2006)
  4. ETSI: 2nd Grid Plugtests Report (2006), http://www.etsi.org/website/document/plugtestshistory/2005/2ndgridplugtestsreport.pdf
  5. Garey, M., Johnson, D., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117–129 (1976)
  6. Hejazi, S., Saghafian, S.: Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research 43, 2895–2929 (2005)
  7. Horn, J.: Bibliography on parallel branch-and-bound algorithms (1992), http://liinwww.ira.uka.de/bibliography/Parallel/par.branch.and.bound.html
  8. Johnson, S.M.: Optimal two-and-three-stage production schedules with set-up times included. Naval Research Logistics Quarterly 1, 61–68 (1954)
  9. Iyer, S., Saxena, B.: Improved genetic algorithm for the permutation flowshop scheduling problem. Computers & Operations Research 31, 593–606 (2004)
  10. Kohler, W., Steiglitz, K.: Enumerative and iterative computational approaches. In: Coffman Jr., E.G. (ed.) Computer and Job-Shop Scheduling Theory, pp. 229–287. Wiley, New York (1976)
  11. Lai, T.-H., Sahni, S.: Anomalies in parallel branch-and-bound algorithms. Communications of the ACM 27, 594–602 (1984)
  12. Lai, T.-H., Sprague, A.: Performance of Parallel Branch-and-Bound Algorithms. IEEE Transactions on Computers 34, 962–964 (1985)
  13. Nawaz, M., Enscore, E., Ham, I.: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega 11, 91–95 (1983)
  14. Reeves, C., Yamada, T.: Genetic algorithms, path relinking, and flowshop sequencing problem. Evolutionary Computation 6, 45–60 (1998)
  15. ProActive - Professional Open Source Middleware for Parallel, Distributed, Multi- core Programming, http://proactive.inria.fr/
  16. Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278–285 (1993)
  17. Taillard, E.: Scheduling instances (2008), http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html
• 作者单位：1. Institute of Computing Science, Poznań University of Technology, Piotrowo 2, 60-965 Poznań, Poland
• ISSN：1611-3349

文摘

Flowshop is an example of a classic hard combinatorial problem. Branch-and-bound is a technique commonly used for solving such hard problems. Together, the two can be used as a benchmark of maturity of parallel processing environment. Grid systems pose a number of hurdles which must be overcome in practical applications. We give a report on applying parallel branch-and-bound for flowshop in grid environment. Methods dealing with the complexities of the environment and the application are proposed, and evaluated.