Разработка и исследование бионических методов упаковки тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Потарусов, Роман Валерьевич

• Потарусов, Роман Валерьевич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Потарусов, Роман Валерьевич

ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ АЛГОРИТМОВ И МЕТОДОВ ОПТИМИЗАЦИИ УПАКОВКИ ОДНОМЕРНЫХ ЭЛЕМЕНТОВ В БЛОКИ.

1.1. Математическая формулировка задачи упаковки блоков.

1.2. Приближенные алгоритмы.

1.3. Редукционная процедура С. Мартелло и П. Тота.

1.4. Точные алгоритмы.

1.5. Мета-эвристические методы решения задачи упаковки блоков.

1.6. Эвристики,' о'снованные на минимальной остаточной вместимости блока.

1.7. Процедура повышения качества решения А.Алвима и Ф. Гловера.

1.8. Алгоритм моделирования отжига.

1.9. Алгоритм поиска при переменном соседстве.

1.10. Выводы.

2. РАЗРАБОТКА АРХИТЕКТУРЫ ГИБРИДНОГО ГЕНЕТИЧЕСКОГО ПОИСКА.

2.1. Разработка архитектуры гибридного генетического поиска для задачи упаковки блоков.

2.2. Разработка методов гибридного генетического поиска, основанных на моделях эволюции.

2.3. Выводы.

3. РАЗРАБОТКА КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.

3.1. Распараллеливание эволюционных вычислений в алгоритмах упаковки

3.2. Целевая функция.

3.3. Кодирование решений.

3.4. Создание начальной популяции.

3.5. Гибридный параллельный генетический алгоритм решения задачи упаковки блоков.

3.6. Общая процедура гибридного параллельного генетического алгоритма

3.7. Разработка и анализ модифицированных генетических операторов, ориентированных на решение задачи упаковки блоков.

3.8. Разработка алгоритмов локального поиска, ориентированных на решение задачи упаковки блоков.

3.9. Теоретические оценки временной и пространственной сложности разработанных алгоритмов.

3.10. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННОГО

КОМПЛЕКСА ГИБРИДНЫХ АЛГОРИТМОВ.

4.1. Требования к программным продуктам, реализующим генетические алгоритмы.

4.2. Основные характеристики программного комплекса «ВРРЬувА».

4.3. Структура программного комплекса «ВРРЬуСА».

4.4. Цель экспериментального исследования.

4.5. Планирование эксперимента.

4.6. Результаты экспериментальных исследований.

4.7. Область применения разработанных алгоритмов.

4.8. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование бионических методов упаковки»

Задача упаковки одномерных элементов в блоки (далее, задача упаковки блоков) - ЫР-сложная комбинаторная оптимизационная задача [1]. В задаче упаковки блоков целью является скомбинировать элементы в блоки заданной вместимости так, чтобы минимизировать общее количество блоков [2-5].

Задача упаковки блоков является распространенной производственной задачей. Она решается при производстве стали, стекла, бумаги, дизайне СБИС, составлении бюджета и т.д [2]. Рассматриваемая задача упаковки одномерных элементов в блоки является ИР-полной.

Несмотря на высокую изученность задачи, существование огромного количества различных методов ее решения, для ряда контрольных (тестовых) задач оптимальное решение не получено. Более того, на данный момент не существует универсального алгоритма, способного одинаково эффективно решать все тестовые задачи, представленные в литературе.

Ввиду вышеизложенного, задача упаковки блоков является АКТУАЛЬНОЙ ПРОБЛЕМОЙ комбинаторной оптимизации, стоящей перед специалистами в различных областях производства.

Результатом непрекращающегося поиска наиболее эффективных методов упаковки стало использование бионических методов и алгоритмов, в том числе эволюционных и генетических алгоритмов (ГА). Впервые предложенные американским ученым-исследователем Дж. Холландом в 1975 году, ГА основаны на аналогии в принципах адаптации биологических и технических систем [б]. Они представляют собой мощный оптимизационный метод, моделирующий естественный процесс эволюции в качестве средства достижения оптимума, и основаны на селекции лучших альтернативных решений из полученного набора (популяции) решений. Сравнительно недавно он начал широко применяться для решения задач в самых различных областях, в том числе для решения задачи упаковки блоков [7-43].

Достоинства ГА, в сравнении с другими подходами к решению задач комбинаторной оптимизации [7-43], заключаются в том, что они работают с набором (популяцией) начальных решений, распараллеливая процесс поиска оптимальных и квазиоптимальных решений. ГА позволяют избежать попадания в локальные оптимумы, при этом комбинируя и наследуя элементы наиболее качественных решений.

Недостатки ГА, применяемых для решения задачи упаковки блоков [7-43], заключаются в низкой степени учета особенностей задачи, что приводит к излишним требованиям по объему памяти, времени работы ГА и к ухудшению качества получаемых решений.

Результаты экспериментальных исследований доказали высокую эффективность генетических алгоритмов упаковки блоков, а на отдельных контрольных задачах — их безусловное превосходство над существующими методами решения.

ЦЕЛЫО диссертационной работы является разработка и исследование комплекса гибридных генетических алгоритмов упаковки одномерных элементов в блоки, способных получать квазиоптимальные и оптимальные решения рассматриваемой задачи.

Для достижения поставленной цели были решены следующие задачи:

1. Разработка архитектуры гибридного генетического поиска, основанной на стратегии «эволюция — локальный поиск»;

2. Построение и исследование гибридного параллельного генетического алгоритма упаковки блоков, позволяющего получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

3. Разработка алгоритмов локального поиска, позволяющих повысить качество решений, получаемых гибридным генетическим алгоритмом;

4. Построение проблемпо-ориентированных модифицированных генетических операторов, позволяющих получать допустимые решения задачи упаковки одномерных элементов в блоки;

5. Создание программного комплекса «ВРР Ьу ОА», позволяющего автоматизировать процесс решения задачи упаковки блоков.

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании теории принятия решений, элементов теории множеств, элементов теории алгоритмов, элементов теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

1. Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция - локальный поиск»;

2. Построен гибридиый параллельный генетический алгоритм упаковки, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

3. Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

4. Разработаны алгоритмы локального поиска, позволяющие повысить качество решений, получаемых при помощи методов гибридного генетического поиска;

5. Построены проблемно-ориентированные модифицированные генетические операторы для параллельного гибридного генетического алгоритма упаковки, позволяющие получать допустимые решения рассматриваемой задачи.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

• гибридный параллельный генетический алгоритм упаковки блоков;

• программный комплекс упаковки блоков.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе № 12354 «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска». Кроме того, материалы диссертации использованы в учебном процессе кафедры САПР ТТИ ЮФУ при чтении лекций и проведении лабораторных работ по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась па международных научно-технических конференциях AIS'06, CAD-2006 (нос. Дивноморское, 2006), 4-ой международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007), международных научно-технических конференциях AIS'07, CAD-2007 (пос. Дивноморское, 2007).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 7 печатных работах.

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложения. Работа содержит 145 страниц, включая 55 рисунков, 23 таблицы, список использованной литературы из 133 наименований, 3 страницы приложений и актов об использовании.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Потарусов, Роман Валерьевич

4.8. Выводы

1. Выделены объекты исследования: гибридный параллельный генетический алгоритм для задачи упаковки блоков, алгоритмы локального поиска;

2. Для выделенных объектов исследования выполнены следующие действия: поставлена цель исследования; построен план проведения экспериментов;

3. Описаны основные недостатки и определены требования к программным продуктам, реализующим ГА;

4. Разработан программный комплекс «BPPbyGA», позволяющий исследовать построенный комплекс гибридных алгоритмов упаковки. Программное обеспечение реализовано в среде Microsoft Visual Studio. NET версии 2005 в рамках объектно-ориентировапиого подхода, что

5. Описана структура программного комплекса «ВРРЬуОА», состав и принцип действия основных блоков программного комплекса;

6. Проведены серии экспериментов; выполнена статистическая обработка экспериментальных данных. Результаты исследования позволили уточнить теоретические оценки временной и пространственной сложности алгоритмов, по которым можно адекватно оценить разработанные алгоритмы. Эмпирические оценки сложности совпадают с теоретическими;

7. Проведено сравнение экспериментальных данных разработанных алгоритмов и их аналогов. Результаты экспериментов показали, что применение гибридного параллельного генетического алгоритма для решения задачи упаковки позволяет получать квазиоптимальные и оптимальные решения задачи для всех тестовых задач, доступных в литературе;

8. Отмечены особенности и определены области применения разработанных алгоритмов.

ЗАКЛЮЧЕНИЕ

1. Представлены области применения и дана постановка задачи упаковки одномерных элементов в блоки, указан класс задачи. Проведен анализ существующих подходов к решению задачи упаковки. На основе проведенного анализа в качестве перспективного для решения задачи упаковки одномерных элементов в блоки выбран гибридный генетический метод.

2. Разработана архитектура гибридного генетического поиска, основанная на стратегии «эволюция — локальный поиск»;

3. Построен и исследован гибридный параллельный генетический алгоритм упаковки, позволяющий получать квазиоптимальные и оптимальные решения рассматриваемой задачи;

4. Разработаны методы гибридного генетического поиска, основанные на моделях эволюции Ж. Ламарка и Г. де Фриза, позволяющие создавать различные по качеству решения рассматриваемой задачи, тем самым частично решая проблему преждевременной сходимости поиска к локально оптимальному решению;

5. Разработаны алгоритмы локального поиска, позволяющие повысить качество решений, получаемых гибридным генетическим алгоритмом;

6. Построены проблемно-ориентированные модифицированные генетические операторы для гибридного параллельного генетического алгоритма упаковки, позволяющие получать допустимые решения рассматриваемой задачи.

7. Создан программный комплекс «BPPbyGA» для ЭВМ типа IBM PC на языке программирования С++ в среде программирования Microsoft Visual Studio. NET.

8. Проведены серии экспериментов, выполнена статистическая обработка экспериментальных данных. Результаты экспериментов показали, что применение гибридного параллельного генетического алгоритма для

132 решения задачи упаковки позволяет получать квазиоптимальные и оптимальные решения задачи для всех тестовых задач, доступных в Интернет. Достоинством разработанного комплекса алгоритмов, помимо его эффективности, является способность ускорять получение оптимального (близкого к оптимальному) решения за счет распараллеливания процесса поиска, методов гибридного генетического поиска на основе известных моделей эволюций, эффективных алгоритмов локального поиска, применения проблемно-ориентированных генетических операторов.

Список литературы диссертационного исследования кандидат технических наук Потарусов, Роман Валерьевич, 2008 год

1. Garey, М. R. and Johnson, D. S. Computers and 1.tractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. 1979.

2. Bischoff E. E. and Wäscher. G. Cutting and packing. European Journal of Operational Research, 84, 1995, 503-505.

3. Martello, S. and Toth, P. An Upper Bound for the Zero-one Knapsack Problem and a Branch and Bound Algorithm, European Journal of Operational Research. 1, 1975, 169-175.

4. Martello, S. and Toth, P. Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990a, ISBN: 0-471-92420-2.

5. Martello, S. and Toth, P. Lower Bounds and Reduction Procedures for the Bin Packing Problem, Discrete Applied Mathematics. 28, 1990b, 59-70.

6. Holland, J. H. Adaptation in Natural and Artificial Systems, University- of Michigan Press, 1975.

7. Beasley, D., Bull, D. R. and Martin, R. R. An Overview of Genetic Algorithms: Part 1, Fundamentals, University Computing. 15, 1993, 58-69.

8. Coley, D. A. An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Publishing Co. Pte. Ltd., 1999.

9. Davis, L. D. Genetic Algorithms and Simulated Annealing, Pitman, London, 1987.

10. Davis, L. D. Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.

11. Forrest, S. Genetic Algorithms: Principles of Natural Selection Applied to Computation. Science. 261, 1993, 872-878.

12. Fraser, A. S. Simulation of Genetic Systems by Automatic Digital Computers, Aust. J. Biol. Sei. 10, 1957, 484-499.

13. Gladkov L., Kureychik V. M., Kureychik V. V. Genetic algorithms. Edited by. Kureychik V. M. Rostizdat, Rostov-on-Don, 2004.

14. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

15. Han, L., Kendall, G. and Cowling, P. An Adaptive Length Chromosome Iiyperheuristic Genetic Algorithm for a Trainer Scheduling Problem, 4th Asia-Pacific Conference on Simulated Evolution and Learning SEAL'02., 2002, 267271.

16. Kitano, H. Designing Neural Networks Using Genetic Algorithms with Graph Generation System, Complex Systems. 4, 1990, 461-476.

17. Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs, 3rd. Ed., Springer, 1996.

18. Mitchell, M. An Introduction to Genetic Algorithms, Massachusetts Institute of Technology, 1996.

19. Moscato, P. On Evolution, Search, Optimisation, Genetic Algorithms and Martial Arts: Towards Mcmetic Algorithms, Technical Report Caltech Concurrent Computation Program, Report 826, California Institute of Technology, Pasadena, California, USA, 1989.

20. Back, T. Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996.

21. Back, T., Fogel, D. and Michalewicz, Z. Handbook of Evolutionary Computation, Institute of Physics Publishing and Oxford University Press, 1997.

22. Bremermann, H. J. Optimisation Through Evolution and Re-Combination. In: Yovits,M., Sawbi,G., and Goldstein,G. (Eds.), Self-Organising Systems, Washington, Spartan, 1962.

23. Emelianov V., Kureychik Y. M. and Kureychik V. V. Theory and practice of evolutionary modelling. "Fizmatlit", Moscow, 2003.

24. Fogel, D. B. Evolutionary Computation: The Fossil Record, IEEE Press, 1998.

25. Fogel, D. B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press, 2000.

26. Hart, E., Ross, P. and Nelson, J. A. Solving a Real-World Problem Using An Evolving Heuristically Driven Schedule Builder, Evolutionary Computing. 6, 1998,61-80.

27. Hart, W. E., Krasnogor, N., and Smith, J. E. Recent Advances in Memetic Algorithms and Related Search Technologies, Springer, 2003.

28. Yao, X. Evolutionary Computation: Theory and Applications, World Scientific, 1999.

29. Birrattari, M., Paquete, L., Stutzle, T. and Varrentrapp, K. Classification of Metaheuristics and Design of Experiments for the Analysis of Components, Technical Report AIDA-01-05, FG Intellektik, FB Informatik, TU Darmstadt, Germany, 2001.

30. Blum, C. and Roli, A. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison, ACM Computing Surveys. 35, 2003, 268-303.

31. Burke, E. and Kendall, G. Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Kluwer Academic Publishers, Boston, Dordrecht, London, 2005.

32. Dorigo, Marco, Optimization, Learning, and Natural Algorithms, PhD Thesis, Politécnico di Milano, Italy, 1992.

33. Feo, T. A. and Resende, M. G. C. A Probabilistic Heuristic for a Computational Difficult Set Covering Problem, Operations Research Letters. 8, 1989, 67-71.

34. Feo, T. A. and Resende, M. G. C. Greedy Randomized Adaptive Search Procedures, Journal of Global Optimization. 6, 1995, 109-133.

35. Glover, F. and Kochenberger, G. A. Handbook of Mela-Heuristics, Kluwer, 2003, ISBN: 1-4020-7263-5.

36. Michalewicz, Z. and Fogcl, D. B. How To Solve It: Model Heuristics, SpringerVerlag, 2000.

37. Nemhauser, G. L. and Wolsey, L. A. Linear and Combinatorial Optimization, Wiley, 1988.

38. Osman, I. II. and Kelly, J. P. Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, 1996.

39. Osman, I. H. and Laporte, G. Metaheursitics: A Bibliography, Annals of Operations Research. 63, 1996, 513-623.

40. Reeves, C. Modern Heuristic Techniques For Combinatorial Problems, McGraw-Hill, 1995, ISBN: 0-07-709239-2.

41. Coffman, E. G., Garcy, M. R., and Johnson, D. S. Approximation Algorithms for Bin Packing. In: Hochbaum,D.S. (Ed.), Approximation Algorithms for NPhard Problems, PWS Publishing, 1997, pp. 46-93.

42. Johnson D.S., Demers A., Ullman J.D., Garey M.R. and Graham R.L. A worst ease performance bounds for simple one-dimensional packing algorithms. SIAM Journal of Computing 3, 1974, 299- 325.

43. Beasley, J. E. OR-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1990, 1069-107.

44. Ibarra, О. H. and Kim, С. E. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of ACM. 22, 1975, 463-468.

45. Hillier, F. S. and Lieberman, G. J. Introduction to Operations Research, McGraw-Hill, 8th ed. 2005, ISBN: 0-07-252744-7.

46. Sahni, S. Approximate Algorithms for the 0-1 Knapsack Problem, Journal of ACM. 22, 1976, 115-124.

47. Scholl, A., Klein, R. and Jürgens, С. BISON: A Fast Hybrid Procedure for Exactly Solving the One-dimensional Bin Packing Problem, Computers & Operations Research. 24, 1997, 627-645.

48. Потарусон P.B., Курейчик B.M. Проблема одномерной упаковки элементов. Известия ТРТУ, №8, 2006, - с. 88 - 93.

49. Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки. Анализ и обзор эвристических алгоритмов. ПИТИС, Таганрог, ТРТУ 2006, с.37-47.

50. Потарусов Р.В., Курейчик В.М. Задача одномерной упаковки и ее использование при решении задачи маршрутизации автотранспорта. Сборник трудов международных научно-технических конференций AIS'06, CAD'06, 2006,-с. 56-61.

51. Valerio de Carvalho, J. M. Exact Solution of Bin-packing Problems Using Column Generation and Branch-and-bound, Annals of Operations Research. 86, 1999, 629-659.

52. Falkenauer, E. A Hybrid Grouping Genetic Algorithm for Bin Pacing, Journal of Heuristics. 2, 1996, 5-30.

53. Falkenauer, E. Genetic Algorithms and Grouping Problems, John Wiley & Sons Ltd, 1998.

54. Lim, A., Rodrigues, В. and Zhang, X. Metaheuristics With Local Search Techniques for Retail Shelf-Space Optimization, Management Science. 50, 2004, 117-131.i

55. Lourenco, H. R., Martin, О. C., and Stutzle, T. Iterated Local Search. In: Glover,F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 321-354.

56. Потарусов P.B. Гибридный параллельный группирующий генетический алгоритм для решения задачи упаковки блоков. Известия ЮФУ, № 4, 2008, - с. 42-45.

57. Потарусов Р.В., Курейчик В.М. Модифицированные генетические операторы'. Сборник трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», 28-30 мая, Коломна, 2007.

58. Потарусов Р.В. Гибридный генетический поиск для задачи упаковки блоков. Известия ЮФУ. Технические науки, № 2, 2007, с. 30-35.

59. Potarusov, R., Kureychilc, V., Goncalves, G. and Allaoui Ii. Solving the Bin Packing Problem with Algorithm of Genetic Search with Migration.

60. Potarusov, R., Kureychik, V., Goncalves, G. and Allaoui 11. Solving the Bin Packing Problem with Hybrid Parallel Genetic Algorithm. The paper has been submitted to the INCOM'09 International Conference, Moscow, June 3-5, 2009.

61. Resende, M. G. C. and Ribeiro, C. C. Greedy Randomized Adaptive Search Procedures. In: Glover F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 219-249.

62. Taillard, E. D., Gambardella, L. M., Gendreau, M. and Potvin, J. Adaptive Memory Programming: A Unified View of Metaheuristies, European Journal of Operational Research. 135,2001, 1-16.

63. Voss, S., Martello, S., and Osman, I. H. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, 1999.

64. Voudouris, C. and Tsang, E.P.K. Guided Local Search. Technical Report CSM-247, Department of Computer Science, University of Essex, 1997.

65. Voudouris, C. and Tsang, E. P. K. Guided Local Search. In: Glover F. and Kochenbergcr,G. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 185218.

66. Levine J. and F. Ducatelle. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, 2003.

67. Dorigo, M., Vittorio, M. and Alberto, C. Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man and Cybernetics Part B : Cybernetics. 26, 1996, 29-41.

68. Dorigo, M. and Stutzle, T. The Ant Colony Optimisation Metaheuristic: Algorithms, Applications and Advances. In: Glover F. and Kochenberger,G. (Eds.), Handbook of Metaheuristies, Kluwer, 2003, pp. 457-474.

69. Gambardclla, L. M. and Dorigo, M. Ant Colony System Hybridised with a New Local Search for the Sequential Ordering Problems, INFORMS Journal on Computing. 12, 2000, 237-255.

70. Gupta, J. N. D. and Ho, J. C. A New Hcuristic Algorithm for the One-dimensional Bin-packing Problem, Production Planning & Control. 10, 1999, 598-603.

71. Fleszar, K. and Hindi, K. S. New Heuristics for One-dimensional Bin-packing, Computers & Operations Research. 29, 2002, 821-839.

72. Bai, R. An investigation of novel approaches for optimizing retail shelf space allocation. Ph. D thesis. School of Computer Science & Information Technology. The University of Nottingham, Nottingham, UK, 2005.

73. Alvim Adriana C. F., Glover Fred S., Ribeiro Celso C., and Aloise Dario J. Local search for the bin packing problem. Journal of Heuristics, 10, 2004, 205-229.

74. Glover F. and Laguna, M. Tabu Search. In: Reeves,C.R. (Ed.), Modem Heuristic Techniques for Combinatorial Problems, McGraw-Hill, 1995, pp. 21-69.

75. Glover, F., Laguna, M., and Marti, R. Scatter Search and Path Relinking. In: Glover,F. and Kochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 1-37.

76. Glover, F. Heuristics for Integer Programming using Surrogate Constraints, Decisions Science, 8, 1977, 155-166.

77. Glover, F. Tabu Search Part I, ORSA Journal on Computing, 1, 1989, 190-206.

78. Glover, F. Tabu Search Part II, ORSA Journal on Computing, 2, 1990, 4-32.

79. Glover, F. and Laguna, M. Tabu Search, Kluwer Academic Publishers, 1997.

80. Aarts, E. H. L. and van Laarhoven, P. J. M. Statistical Cooling: A General Approach to Combinatorial Optimization Problems, Phillips Journal of Research. 40, 1985, 193-226.

81. Dowsland, IC. A. Some Experiments with Simulated Annealing Techniques for Packing Problems, European Journal of Operational Research. 68, 1993, 389399.

82. Fisher, Ii. and Thompson, G. L. Probabilistic Learning Combinations of Local Job-shop Scheduling Rules, Factory Scheduling Conference, Carnegie Institute of Technology. May, 1961, 10-12.

83. Gabriele, G. A. and Ilagsdell, K. M. The Generalized Reduced Gradient Method: A Reliable Tool for Optimal Design, AMSE Journal of Engineering for Industry. 99, 1977, 384-400.

84. Fujiwara, O. and Perera, U. L. J. S. R. EOQ Models for Continuously Deteriorating Products Using Linear and Exponential Penalty Costs, European Journal of Operational Research. 70, 1993, 104-114.

85. Gendreau, M. Recent Advances in Tabu Search. In: Ribeiro,C.C. and Hansen,P. (Eds.), Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, 2002, pp. 369-377.

86. Gendreau, M., Hertz, A. and Laporte, G. A Tabu Search Heuristic for the Vehicle Routing Problem, Management Science. 40, 1994, 1276-1290.

87. Giri, B. C., Pal, S., Goswami, A. and Chaudhuri, K. S. An Inventory Model for Deteriorating Items with Stock-dependent Demand Rate, European Journal of Operational Research. 95, 1996, 604-610.

88. Goyal, S. K. and Giri, B. C. Recent Trends in Modeling of Deteriorating Inventory, European Journal of Operational Research. 134, 2001, 1-16.

89. Gruen, T. and Shah, R. Determinants and Outcomes of Plan Objectivity and Implementation in Category Management Relationships, Journal of Retailing. 76, 2000,483-510.

90. Hart, C. and Davies, M. The Location and Merchandising of Non-food in Supermarkets, International Journal of Retail & Distribution Management. 24, 1996, 17-25.

91. Hollier, R. Ii. and Mak, K. L. Inventory Replenishing Policies for Deteriorating Items in a Declining Market, International Journal of Production Research. 21, 1983, 813-826.

92. Hwang, H., Choi, B. and Lee, M.-J. A Model for Shelf Space Allocation and Inventory Control Considering Location and Inventory Level Effects on Demand, International Journal of Production Economics. In Press, 2005.

93. Ibbotson, J. Personal Correspondence, Retail Vision, 2002.

94. Jain, K. and Silver, E. A. Lot Sizing for a Product Subject to Obsolescence or Perishability, European Journal of Operational Research. 75, 1994, 287-295.

95. Kaelbling, L. P., Littman, M. L. and Moore, A. W. Reinforcement Learning: A Survey, Journal of Artificial Intelligence Research. 4, 1996, 237-285.

96. Kar, S., Bhunia, A. K. and Maiti, M. Inventory of Multi-deteriorating Items Sold From Two Shops Under Single Management with Constraints on Space and Investment, Computers & Operations Research. 28, 2001, 1203-1221.

97. Kendall, G. and Mohamad, M. Channel Assignment Optimisation Using a Hyper-heuristic, In the Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems (CIS), Singapore, 1-3 December 2004, 2004a, 790-795.

98. Kendall, G. and Mohamad, M. Channel Assignment In Cellular Communication Using A Great Deluge Ilyper-heuristic, In the Proceedings of the 2004 IEEE International Conference on Network (ICON2004), Singapore, 16-19 November 2004, 2004b, 769-773.

99. Kendall, G. and Mohd Ilussin, N. An Investigation of a Tabu Search Based Hyper-heuristic for Examination Timetabling. In: Kendal 1,G., Burke,E., and Petrovic,S. (Eds.), Selected Papers from MISTA 2003, ICluwer Academic Publisher, 2005, 309-328.

100. Kendall, G. and Mohd I-Iussin, N. An Investigation of a Tabu Search Based Hyper-heuristic for Examination Timetabling. In: Kendall,G., Burke,E., and Petrovic,S. (Eds.), Selected Papers from MISTA 2003, Kluwer Academic Publisher, 2004a.

101. Kotzan, J. and Evanson, R. Responsiveness of Drug Store Sales to Shelf Space Allocations, Journal of Marketing Research. 6, 1969, 465-469.

102. Lasdon, L. S., Waren, A. D., Jain, A. and Ratner, M. Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming, ACM Transactions on Mathematical Software. 4, 1978, 34-50.

103. Levy, M. and Weitz, B. Retailing Management, Homewood, IL., 1992, ISBN: 0256-05989-6.

104. Lundy, M. and Mees, A. Convergence of an Annealing Algorithm, Mathematical Programming. 34, 1986, 111-124.

105. Mazzola, J. B. and Schantz, R. Ii. Single-facility Resource Allocation Under Capacity-based Economics and Diseconomies of Scope, Management Science. 41, 1995, 669-689.

106. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. Ii. and Teller, E. Equation of State Calculation by Fast Computing Machines, Journal of Chemical Physics. 21, 1953, 1087-1091.

107. Mockus, J. A Set of Examples of Global and Discrete Optimization: Application of Baycsian Heuristic Approach, Kluwer Academic Publishers, Dordrecht-London-Boston, 2000.

108. Moscato, P. and Cotta, C. A Gentle Introduction to Memetic Algorithms. In: Glover,F. and ICochenberger,G.A. (Eds.), Handbook of Metaheuristics, Kluwer, 2003, pp. 105-144.

109. Petch, R. J. and Salhi, S. A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Applied Mathematics, 133, 2004, 69-92.

110. Rao, R. L. and Iyengar, S. S. Bin-packing by Simulated Annealing, Computers & Mathematics with Applications. 27, 1994, 71-82.

111. Ross, P., Schulenburg, S., Marin-Blazquez, J.G., and Hart, E. Hyper Heuristics: Learning to Combine Simple Heuristics in Bin-packing Problems, Proceeding of the Genetic and Evolutionary Computation Conference, GECC02002, New York, US, 2002, 942-948.

112. Smith, J. Co-evolving Memetie Algorithms: Initial Investigations. In: Parallel Problem Solving from Nature VII, PPSN 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002, pp. 537-546.

113. Toth, P. Dynamic Programming Algorithms for the Zero-one Knapsack Problem, Computing. 25, 1980, 29-45.

114. Urban, T. An Inventory-Theoretic Approach to Product Assortment and Shelf-Space Allocation, Journal of Retailing. 74, 1998, 15-35.

115. Wang, C.J. and Tsang, E.P.K. Solving Constraint Satisfaction Problems Using Neural-networks, Proceedings of the IEE Second International Conference on Artificial Neural Networks, 1991, 295-299.

116. Wang, C. J. and Tsang, E. P. K. A Cascadable VLSI Design for GENET. In: Delgado-Frias, J.G. and Moore, W.R. (Eds.), VLSI for Neural Networks and Artificial Intelligence, New York, Plenum Press, 1994, pp. 187-196.

117. Yang, M.-H. An Efficient Algorithm to Allocate Shelf Space, European Journal of Operational Research. 131,2001, 107-118.

118. Yang, M.-H. and Chen, W.-C. A Study on Shelf Space Allocation and Management, International Journal of Production Economics. 60, 1999, 309-317.

119. Zufryden, F. A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation, Journal of Operations Research Society. 37, 1986,413-422.

120. Ross, P. Hyper-Heuristics. In: Burke, E. and Kendall, G. (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer, 2005, pp. 529-556.

121. Gutin, G. Exponential Neighbourhood Local Search for the Traveling Salesman Problem, Computer & Operations Research. 26, 1999, 313-320.

122. Ahuja, R. K., Orlin, J. B. and Sharma, D. Very Large Scale Neighbourhood Search, International Transaction in Operational Research. 7, 2000, 301-317.

123. Bellman, R. Dynamic Programming, Princeton University Press, 1957.

124. Dantzig, G. B. Linear Programming and Extensions, Princeton University Press, Princeton, 1963.

125. Hansen, P. and Maldenovic, N. Variable Neighbourhood Search: Principles and Applications, European Journal of Operational Research. 130, 2001, 449-467.

126. Hansen, P. and Maldenovic, N. Variable Neighbourhood Search. In: Glover F. and Kochenberger,G. (Eds.), Handbook of Mcta-Heuristies, Kluwer, 2003, pp. 145-184.

127. Mladenovic, N. and Hansen, P. Variable Neighbourhood Search, Computers & Operations Research. 11, 1997, 1097-1100.

128. Cantu-Paz, E. A Summary of research on Parallel Genetic Algorithms. 1995, IlliGAL Report No. 95007.