Я работаю над проектом по реализации и тестированию проблемы NP-Hard / Complete. У меня была общая идея сделать что-нибудь с расписанием, и я много читал о проблеме Job Shop. Я знаю, что есть известные тестовые примеры / тесты из библиотеки OR. У меня есть код (Java) для чтения в тестовом экземпляре и хранения его данных. Теперь я чувствую себя застрявшим в петле, пытаясь найти алгоритм / способ создания расписания, а затем представить оптимальное расписание. Я читаю много научных статей, но обычно немного теряюсь в них, особенно со сложной системой обозначений. Хотел бы я найти больше примеров псевдокода. Я знаю, что это классическая проблема, и мне интересно, есть ли у кого-нибудь предложения по прямым классическим решениям для работы магазина - особенно те, которые также имеют примеры псевдокода. Мне не нужно проводить оригинальные исследования для этого проекта. Мне просто нужно научиться применять известную технику для решения проблемы NP-Hard, написать код, запустить тест, представить экспериментальные результаты и прокомментировать их. Мы будем очень благодарны за любой совет или помощь.
«Необходимо выполнить ряд работ, и каждая работа состоит из использования нескольких машин в течение определенного периода времени. Проблема состоит в том, чтобы найти наилучшее планирование для выполнения всех работ на всех различных машинах в кратчайшие сроки. . "
Пример экземпляра проблемы:
Каждая строка в разделе данных задает задание 10 парами последовательных чисел. Каждая пара чисел определяет одну задачу задания, которая представляет обработку задания на машине. Для каждой пары первое число определяет машину, на которой она выполняется, а второе число - продолжительность. Порядок 10 пар определяет последовательность задач для работы.
«Экземпляр Лоуренса 10х10» (Таблица 6, экземпляр 4); также называется (seta4) или (A4) (Applegate and Cook; 1991) -10 машин с номерами 0-9-10 строк = 10 заданий - оптимально: 842
2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89
4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21
9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71
1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55
6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50
7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52
6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95
0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8
5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75
9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26
