Разработка решений для одной машины Всего Весовые Время завершения Проблема с эффектом обучения,
Эта статья рассматривает одной машины общего взвешенного времени завершения задачи календарного планирования с изучения эффекта. Как взвешенных кратчайшего времени обработки первых правило, не могут обеспечить оптимальное решение, в настоящем документе предлагается эффективный эвристический алгоритм поиска близкое к оптимальному решение и сравнивает выступления обоих методов с вычислительными экспериментами.
1. Введение
В традиционных задач планирования машина, раз дело обработки считаются постоянными для всех заданий. Однако, недавние эмпирические исследования в ряде отраслей промышленности подтвердили, что снижение удельных затрат, поскольку компании производить больше продукции и получить знания или опыт. Например, повторить обработку подобных задач повышает квалификации работников, рабочие могут выполнять установку, иметь дело с машиной операций и программного обеспечения, или для обработки сырья и комплектующих на более быстрыми темпами (Biskup [1]). Этот феномен известен как "обучение эффект".
Классически, взвешенный кратчайшего времени обработки первой (WSPT) правила [8] был применен для получения оптимального решения для общего взвешенного времени завершения в задаче планирования одной машины. Однако это правило не обеспечивает оптимальное решение при обучении эффект присутствует. Это правило тщательного изучения и оценки своей деятельности по отношению к другой предложенный эвристический алгоритм.
В предыдущих исследованиях, касающихся задач составления расписаний на одной машине с обучением соображений, Biskup [1] предполагалось, что время обработки задания является убывающей функцией от своей позиции в последовательности, рассмотрел две проблемы одной машины планирования, а также показал, что обе проблемы могут быть решена за полиномиальное время. Продолжая анализ [1] модель Biskup в, Mosheiov [5] отмечает, что некоторые проблемы с изучения эффекта являются более сложными, чем в традиционных проблемы и предложил контрпример, показывающий, что общее взвешенное проблема сроки завершения работ не может быть сведено к минимуму путем WSPT правило, в контексте обучения. Ли и др.. [4] рассматривается планирование би-критерия singlemachine проблемы с обучением соображений. Кроме того, Mosheiov [6] еще раз рассмотрел потока минимизации на параллельных идентичных машин. Mosheiov и Сидни [7] продлил настройки позволяют обучения в процессе производства, некоторые рабочие места быстрее, чем другие. Ли и Ву [3] далее рассматриваются задачи минимизации общего времени завершения в две машины с flowshop обучения эффект. Проблема в данном исследовании было упомянуто в работе Mosheiov [5] о контрпример, но насколько мне известно, он не был дополнительно обсужден в литературе ..
В остальной части этой статьи следующим образом. Справочная задачи календарного планирования осуществляется и 3 правила исключения для повышения эффективности поиска оптимального решения, предложенные в следующем разделе. Эвристический алгоритм, предложенный в разделе 3. Результаты расчетов для выполнения правила WSPT и эвристический алгоритм, предложенный представлены в разделе 4. Вывод содержится в последнем разделе.
2. Справочная информация и смежности свойства
3. Эвристические алгоритмы
Правило WSPT графики рабочих мест в порядке убывания W ^ J ^ к югу / к югу р J ^. Это правило изучал в отношении следующих предложенного алгоритма.
Эвристический алгоритм (ГА):
Шаг 1: Выполните кратчайшего времени обработки первой (SPT) правила с точки зрения обработки заданий раз, т. е. график работы в порядке убывания р, и пусть S обозначим результате расписание. Набор 51 в качестве исходного раствора.
Шаг 2: Проверьте прилегающих рабочих мест в таблице S от начала до конца: если условие W ^ J ^ к югу / к югу р J ^-ш ^ к югу J ^ / к югу р J ^ выполнено, поменять положение двух соседних рабочие места для создания новой последовательности.
Шаг 3: вычислить момент завершения новой последовательности и сравнить его с исходного раствора. Если новый один меньше, заменить исходную последовательность с новым 1. В противном случае, сохранить первоначальный 1.
Шаг 4: Повторите шаги 2 и 3, пока окончательного решения не найдено.
4. Вычислительный эксперимент
Для оценки выступлений правило WSPT и предлагаемые эвристический алгоритм, 120 моделирования создаются следующим образом. Вес и нормальной обработки раз оба взяты из равномерного распределения на отрезке [1, 10] (см. Фишера [2]). Четыре размера задачи тестирования, а именно, п = 6, 10, 14, 18. Для каждой проблемы размера, 10 симуляции генерируется случайным образом. Кривых обучения принимаются для 90%, 80% и 70%, которые дают
Для того, чтобы получить оптимальное решение, ветвей и связанных метод. Для этого алгоритма, среднего и максимального числа узлов сообщили. Для обоих эвристические алгоритмы, средней и максимальной процент ошибки записываются. Ошибка в процентах от раствора, полученного по правилу WSPT и алгоритм HA рассчитываются как E ^ югу WSPT = (V ^ ^ к югу WSPT-V *) / V * и Е к югу HA = (V ^ ^ к югу HA -V *) W *, соответственно, где V ^ югу WSPT ^ и V ^ ^ к югу HA обозначать общее взвешенное раз завершения решение, порожденное правило WSPT и метод HA и V * обозначает общее взвешенное раз завершения оптимальное расписание получены из ветвей и границ техники. В таблице 1 приведены результаты этих экспериментов.
В таблице 1, колонка 3 показывает, что для каждого учебного эффекта, среднее число узлов резко возрастает, как работа увеличивает размер п. Выступления столбец 4 аналогичны тем, которые в колонке 3. Столбцы 5 и 6 показывают, что производительность WSPT правило, не годится. Средние и максимальные проценты ошибка так высоки, как 202,54% и 421,98% соответственно. Сопоставляя это с колоннами 7 и 8, HA является значительным шагом вперед по правилу WSPT. Максимум средней процент ошибок и худшие максимальная ошибка процент HA только 0,51% и 3,02% соответственно. Оба они являются гораздо меньше, чем правило WSPT. Кроме того, можно отметить, что производительность HA не зависит от размера работы и обучения в силу.
5. Заключение
Эта статья направлена на решение проблем в использовании общего взвешенного времени завершения в одной машине, когда обучение эффект присутствует. Таблица 1 показывает, что эвристический HA вполне точной и превосходит WSPT правило, с большим отрывом. Результаты расчетов показывают, что число узлов изучить кажется растут экспоненциально, и, таким образом проблема будет предположить NP-трудно. Во многих реальных ситуациях производства, точные методы могут решить проблемы с ограниченным количеством рабочих мест. Предлагается эвристический алгоритм занимает O (N ^ 2 ^ SUP), чтобы обеспечить хорошее решение эффективным и экономичным способом.
Ссылки
[1] D. Biskup, Single-машина с расписанием обучения соображения, Европейский журнал исследование операций 115 (1999) 173-178.
[2] М.Л. Фишер, двойной алгоритм одна машина задачи календарного планирования, математическому программированию 11 (1971) 229-251.
[3] без оплаты Ли и C.C. Ву, сведение к минимуму общего времени завершения в две машины с flowshop изучения эффекта, Международный научный журнал "Экономика производства 88 (2004) 85-93.
[4] без оплаты Ли, C.C. Ву и ГП. Сена, би-критерия одной машины задачи календарного планирования с обучением соображений, Acta Informatica 40 (2004) 303-315.
[5] G. Mosheiov, планирование задач с изучения эффекта, Европейский журнал исследования операций 132 (2001) 687-693.
[6] G. Mosheiov, параллельный планирования машина с изучения эффекта, журнал Исследование Операций общества 52 (2001) 1165-1169.
[7] G. Mosheiov и Дж. Сидни, планирование с общей работы зависит от кривых обучения, Европейский журнал исследования операций 147 (2003) 665-670.
[8] W.L. Смит, различные оптимизаторы на одном этапе производства, Naval Research Логистика Ежеквартальный 3 (1956) 59-66.
Чин Ву Chia
Фэн Цзя университет, Тайвань
Контактный адрес электронной почты: <a <href="mailto:cchwu@fcu.edu.tw"> cchwu@fcu.edu.tw />
