документ конференции-референт задачи о назначениях,

Назначение Документ конференции-Рецензент проблемы *

РЕЗЮМЕ

Организаторы конференции: часто встает вопрос: с учетом сбора представленных документов, выбрать подмножество, которые будут представлены на конференции. Основная работа нередко сводится к сборке пула экспертов и затем отправить представленной работе нескольких экспертов. В настоящей работе предлагается метод нахождения хорошие уступки бумаги отзывы. Важной особенностью решения мы находим, что каждый документ отправляется по крайней мере, один рецензент, который "в качестве эксперта по возможности" для этого документа. Одним из основных компонентов задачи моделируется как узкое версия capacitated проблема перегрузки.

Предметные области: задача о назначениях, Сетевой теории оптимизации и обслуживания.

ВВЕДЕНИЕ

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

В этой статье мы рассмотрим следующую задачу организатора: Как лучше назначить бумаги отзывы? Конечно, свободные цель организатора посылать друг документ экспертов, которые обладают опытом в данном вопросе бумаги. Эта цель может быть трудно достичь, если (1) Есть большое количество статей и отзывов; (2) существует широкий спектр различных предметных областях среди бумаг и (3) существует большое разнообразие видов экспертизы Среди рецензентов.

Стандартный метод решения этой проблемы является использование какой-то системе классификации документов и рецензентов. Например, каждый автор и рецензент может быть предложено классифицировать его или ее субъекта или опыт, выбрать несколько ключевых слов из списка поставляемых организатора. Организатор может затем пытаются присвоить бумаги отзывы с общим ключевым словам. Это может быть сделано в эвристический моды просто рассматривает документы в определенном порядке и присвоение каждой любой недостаточно оппонентом с общих ключевых слов. Это может привести к двум проблемам.

1. Это эвристический не гарантирует оптимальное решение, даже в смысле максимального числа заданий, с использованием ключевых слов совпадают. Даже оптимальное решение, которое увеличивает общее количество совпадений, может назначить какие-то бумаги на отзывы без каких-либо ключевое слово совпадают.

2. Это эвристический не рассматриваются следующие более тонкие вопрос: метод перекрытия слова достаточно сырой. Чтобы убедиться в этом, заметим, что некоторые пары слов может быть более похожи друг на друга, чем другие пары. Таким образом, две списки ключевых слов, не перекрываются может представлять бумаги и обозревателей, которые абсолютно разнородных или аналогичных достаточно разумные уступки предстоит сделать.

В этой статье мы представляем оптимизации подхода к решению бумаги - оппонентом уступки проблемы, стоящие перед организаторами конференции. Наше решение имеет две фазы. На первом этапе мы описываем способом количественной оценки уровня знаний и опыта каждой оппонентом для каждого документа. Этот метод является более совершенной, чем подсчет ключевое дублирование и обеспечивает решение задачи 2, упомянутых выше. Этот метод предполагает решение ряда малых транспортных проблем. Второй этап производит задачи с помощью уровня специалистов из первого этапа. Это не обычные задачи о назначениях (или capacitated перевалки проблемы). Вместо этого мы видим общую лучшее назначение, также гарантирует, что каждый документ присваивается, например, по крайней мере, один рецензент, который "в качестве эксперта по возможности" для этого документа. Этот метод может быть кратко описан в качестве узкого места версия capacitated проблема перегрузки. Этот этап адреса задачи I выше.

Остальная часть статья организована следующим образом. Следующий раздел содержит краткий обзор соответствующей работы в литературе. Третий раздел описывает нашу модель и решение техники. В следующем разделе описывается реализация данного метода для 1998 Decision Sciences Институт ежегодного совещания. Затем, обобщения и другие возможные применения модели обсуждаются, а затем заключение.

Задача о назначениях в литературе

Общая задача состоит в соотнесении назначение членов одной группы объектов (например, рабочих) к членам другой группы объектов (например, рабочих мест). Это один из самых известных и наиболее изученных особых случаях минимальный проблемы сетевых потоков затрат. Общие задачи о назначениях можно также рассматривать как частный случай транспортной задачи, в которых все поставки и требует равного 1. Ahuja, Magnanti и Орлин (1993) представил отличный обзор методов решения и приложения задачи о назначениях. Среди приложений, которые они перечисленных являются следующие: персонал назначения (Machol, 1970; Ewashko

Многопериодной задачи о назначениях добавляет сложности измерения времени уступки решения. Многие сотрудники планирования и планирования рабочей силы-приложений может быть решена как многопериодной задачи о назначениях с различными характеристиками моделей и подходов решения (Росс

МЕТОДОЛОГИЯ

Мы начинаем этот раздел с определением нашей задачи. Далее мы описываем нашу модель этой проблемы и наше решение техники.

Задачи исследования заключается в следующем. Дано множество (1,. . ., Г) рецензентов и множество (1,. . ., Р) бумаг, мы хотели бы присвоить бумаги отзывы так, чтобы удовлетворять следующим условиям.

(1,1) Каждый рецензент следует отнести не более трех работ;

(1.2) Каждая работа должна быть возложена на ровно три отзывы;

(1.3) по мере возможности, каждая статья должна быть возложена на отзывы, которые являются экспертами в этой газете.

Конечно, число "три" в (1,1) и (1.2) произвольно и может быть изменен в целом (хотя мы предположим, у нас достаточно, чтобы отзывы допустимое решение существует). Первая задача в нашем методе решения состоит в следующем.

Задача 1: Для каждого оппонентом я и бумаги J, определить количество Sij обозначающее "степень знаний" из обозревателей я для бумаги j. Чем выше число, тем лучше бумаги J подпадает опыт обозревателей I.

Теперь мы можем определить "вес назначения", который будет сумма чисел си для всех пар т в задании. Это наводит на мысль о нахождении уступки при решении максимальный вес-capacitated транспортную проблему в сети следующие:

(1.4) для каждого оппонента есть узел источника;

(1.5) для каждого документа есть сток;

(1,6) поставки в каждом узле источника меньше или равна 3 единиц;

(1.7) спроса на каждом сток равна 3 единиц;

(1,8) Существует дуги из каждого источника в узел я каждого / сток с весом с ^ т ^ к югу, создание (или верхняя граница) 1, и нижняя граница 0.

Оптимальное решение этой проблемы, которые являются неотъемлемой всегда существует, поэтому дуги при значении 1 в таком растворе определить задания. Тем не менее, возможные проблемы могут привести: бумаги могут быть переданы не оппонентом с "высокой степени" знаний и опыта для этой работы. Это может произойти из-за "глобальный" характер задачи оптимизации. Мы рассматриваем это, предоставляя процедур в течение следующих двух задач:

Задача 2: С учетом порога T, найти максимальный вес уступки, что каждый документ присваивается по крайней мере, один рецензент, чей опыт в этой работе больше или равна T, или показать, что такие уступки не существует;

Задача 3: Найдите наибольшее порога P, для которых существует возможные уступки в задаче 2. Это назначение является решением проблемы.

Иными словами, две задачи выше, обеспечивают решение следующих типа. Во-первых, найти самый высокий порог, чтобы каждый документ может быть отправлено как минимум 1 обозревателей, чей опыт больше или равна порогу. Тогда, с учетом того, оптимальное решение также обладает тем свойством, что сумма всех степеней опыт задание максимум.

Заметим, что задачи 2 и 3 являются обобщением задачи о назначениях узким местом. Проблема узкого назначения в основном проблемы путем замены "3" в условиях (1. 1) и (1,2) выше, с "1" (см. Ahuja и др.., 1993).

В остальных, мы предлагаем процедуры для выполнения задач 1, 2 и 3.

Порядок Задача 1

Мы используем три шага процедуры для выполнения задания 1. На первом этапе мы позволяем каждому оппонентом для классификации самого себя, и каждый автор классифицировать свои бумаги. Для этого мы рассмотрим стандартный набор категорий 11. . ., С) направлений исследований. В частности, каждый рецензент дается, скажем, 10 баллов, и поручил, чтобы раздать эти категории свыше, чтобы охарактеризовать его или ее сфере компетенции. Кроме того, каждый автор дается 10 очков, чтобы распространить на категории, чтобы охарактеризовать его или ее бумаги. Так, рецензент может передавать все 10 пунктов до 1 категории, если это является его единственной областью знаний или может разложил их на несколько категорий. То же самое касается каждого автора. Таким образом, для каждого рецензент я, мы получим вектор оппонентом классификация:

Каждый такой задачи линейного программирования является транспортная задача из источников, C индексируются А-С поглотителями проиндексированы 1. Каждый источник соответствует категории, равно как и каждой раковины. Первая группа ограничений говорит, что предложения на каждый источник число точек возложенных на соответствующие категории по оппонентом I. Вторая группа ограничений говорит, что спрос на каждой раковине количество баллов возложенных на соответствующие категории автор документ j. На практике это транспортная задача может быть сведена к транспортной задачи с меньшим количеством ограничений и переменных, где источники этих категорий получил положительный стоимости оппонентом я и раковины этих категорий данной положительное значение автор документ j. Переменных у ^ ^ Ы к югу будет иметь тенденцию быть большими оптимальное решение, если выполнены следующие условия: рецензент назначается значительное число указывает на категорию А, автор назначен значительное количество очков в категории 1 и категории А и Я схожи.

Номера с ^ т ^ к югу Полученные иметь некоторые интересные свойства. В частности, предположим, что R ^ югу я ^ (А) = P ^ югу J ^ (к) = 1,. . ., C, то есть, я оппонентом и бумаги J описываются одинаковыми векторов классификации. Тогда легко видеть, что S ^ ^ т к югу принимает максимально возможное значение. (Если степень сходства взяты из (0,..., 5) и рецензентов и авторов выделяются 10 точек, то это максимальное значение равно 50.) С другой стороны, если степень сходства между каждой категории выбранной рецензент и автор равно 0, то S ^ югу т = 0. Все номера между этими двумя крайностями возможны, значит, мы получим более тонкий показатель степени экспертизы оппонентом для бумаги, чем ключевое дублирования (как обсуждалось во введении).

Процедуры для задач 2 и 3

Задача 2 осуществляется за счет добавления новых структуру сети описаны в (1,4) (1,8) и, таким образом, превращая максимальный вес capacitated транспортную проблему в максимальный вес capacitated перевалки проблемы. Мы построим следующие сети N в спросе и предложении. Напомним, что T является пороговым значением, приведенным в Целевой 2 (см. рис я для примера такой сети).

Порядок Задача 2

Шаг 1: Форма N сети, описанной выше.

Шаг 2: Найти перевалки максимальный вес решение для N. Если решение положительно, то выход найти задание (как указано дуг с 1 единицу расхода), в противном случае исходной задачи в задаче 2 не имеет допустимое решение.

За отличное лечение перевалки проблемы (также называемый минимальный проблемы стоимости потока), как математические формулировки и решения методов, отсылая читателя к "Аль Ahuja и др. (1993).

Порядок Задача 3

Шаг 1: Установите T будет наименьшим значением с ^ т ^ к югу. Применение процедуры Задание 2.

Шаг 2: Установка ОТТ быть следующим наименьшим значением с ^ т ^ к югу. Применение процедуры Задание 2. Если возможно задание будет найден, повторите этот шаг. Если не возможно будет найдено решение, выход нашли уступки в предыдущей итерации.

Отметим, что использование промежуточных узлов и больших отрицательных масс-M в строительстве N дает нам тип "узкое место" решение, которое мы хотим. Также отметим, что максимальный вес capacitated перевалки проблемы определяется сети N может быть решена с помощью программного обеспечения минимального веса capacitated перевалки проблемы (или проблемы минимальной стоимости потока), просто изменяя признаки веса (в результате сеть не имеет отрицательного веса - ориентированных циклов). В заключение отметим, что Шаг 2 Порядка Задача 3 может быть эффективно реализованы с бинарный поиск (разделяй и властвуй).

ОСУЩЕСТВЛЕНИЕ

В этом разделе мы описываем конкретное применение методологии, предложенной в предыдущем разделе. Это ходатайство было в 1998 году ежегодное совещание Института Decision Sciences в Лас-Вегасе. Ежегодные заседания этой организации как правило, состоят около 1000 представлений бумаги, которые разделены на 12 функциональных направлениях. Мы применили наш метод для производства и оперативного управления (POM)-Производство трек, который всегда был одним из крупнейших треков, около 200 статей. Обычной практикой является организатором трек посылать друг бумаги 3 отзывы и обеспечить, чтобы каждый оппонент получает не более трех работ.

Первая задача применения нашей методики является строительство набор категорий для классификации документов и рецензентов. Мы сводный список из 48 категорий, используемых в журнале Decision Sciences операций и материально-технического обеспечения в список из 30 категорий для этой цели. Затем мы построили две опросные листы, по одному для авторов и один за отзывы. В марте 1998 года военнопленных Производство Трек получил отзывы от обозревателей 182 добровольцев, которые заполнили опросный лист. Трек организаторов затем заполнить бумаги обследования после краткого обзора каждой из 174 документов, представленных на беговую дорожку. (Кроме того, это могло бы быть сделано самими авторами.)

Следующим шагом было построить матрицу, содержащую "степень сходства" между категориями, то есть число W ^ ^ Ы к югу определены в предыдущем разделе. Они содержатся в 3000 "Близость" матрицы. Мы использовали шкале от 0 до 5, где 5 означает решительным сходство между двумя категориями. Эта близость матрица обеспечивает одно преимущество по сравнению с традиционным методом присвоения бумаги оппонентом по ключевому слову перекрытия, как описано во введении. Используя близость матрицы, наша методика дает возможность найти "почти эксперт" отзывы, когда "эксперты" не имеется.

С 182 по рассмотрению и 174 статей, мы должны были решить транспортные проблемы 31668 для получения степени компетентности для каждой пары бумага-референт. Мы записывали данные в Microsoft Excel 97, пишет макросы для организации ввода и вывода данных, а также решить транспортные проблемы с помощью макросов звонков в модуль Solver в Excel. Мы решили использовать Excel в связи с ее почти повсеместное наличие. Хотя число транспортных проблем огромен, эти проблемы являются полностью независимыми друг от друга, а значит, могут быть решены одновременно. Мы приобрели компьютерную лабораторию и бежали 18 Windows основе Pentium-133 персональных компьютеров в то же время. Каждый компьютер (за исключением 18-1) занимает 30 минут, чтобы решить транспортные проблемы требуется.

Мы записали все 31668 уровень знаний номера в матрице. Эта матрица дали весов на дугах сети N, которые были построены во время работы процедур для задач 2 и 3. Мы обнаружили, что среди 182 отзывы, около 50 обозревателей также представил документы Производство POM-Track. Чтобы избежать отправки бумаги собственной автора (ов), мы вручную назначен большой отрицательный вес всех таких комбинаций в матрице. Затем мы взяли этот пересмотренный матрицы и начала порога Т 25 (как предусмотрено бинарный поиск), а генерируются (с макроса Excel) сети N в форме, пригодной для ввода в SAS / программного обеспечения OR. (Опять же, мы выбрали SAS / или из-за его широкой доступности.) Каждая минимальная стоимость перевалки capacitated проблемы было более 40000 дуги, но он только взял версия Windows из SAS / или примерно 10 секунд, чтобы решить каждый. Использование бинарный поиск, мы быстро нашли, что наибольший порог, который признал возможным решение T = 30. Это решение гарантирует, что для каждого крайней мере на бумаге один из трех отзывы имел опыт уровня 30 или больше, и что это было невозможно, на экспертизу уровня 31. Решение было наилучшим по отношению к объективному предмету функции порог ограничения.

Потому что у нас было больше, чем отзывы документы, некоторые отзывы были назначены менее 3 статей в наше решение. Мы также рассмотрели вопрос о нахождении крупнейших порога, что каждый документ присваивается 2 обозревателей, имеющих опыт, который, по крайней мере (как больших, как) это значение. В этом случае, крупнейший порог, который признал возможным решением было 24. Это свидетельствует о компромиссе между требующих один эксперт оппонентом для каждого документа по сравнению с 2 требующие отзывы экспертов. 3-референт вариант этой задачи также дали пороге 24, хотя значение целевой функции высадили несколько ..

Обобщения и другие приложения

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

1. Число "три" в (1,1) и (1.2) может быть любое положительное число, и не должны быть одинаковыми для всех рецензентов и документы. Это повлияет на пункты 3 и 4 в строительстве Н.

2. Типа неравенства или равенства требует в (1,1) и (1.2) не имеет значения и не должны быть одинаковыми для всех рецензентов и статей. Это повлияет на пункты 3 и 4 в строительстве Н.

3. В задаче 2, требование "по крайней мере один" может быть "по меньшей мере г 'для некоторого натурального числа 1. Это позволит изменить нижнюю границу дуг в графе 7 к л в строительстве Н.

4. В задаче 2, требование "каждый документ" может быть заменено на "м все, кроме бумаги. То есть, задание может быть признано нецелесообразным, если не более, чем т бумаги относятся к отзывы, которые не выше порога T Это может позволить более высокий порог которые должны быть достигнуты в подавляющем большинстве статей. Это может быть достигнуто с процедурами, предоставлена в связи с использованием большого числа М. Чтобы убедиться в этом, заметим, что в п. 2 Порядка Целевая 2, решение всегда оказывается перевалки проблема, которая сводит к минимуму количество документы, которые относятся к отзывы, уровень специальных знаний и опыта, что бумага является менее порога. Таким образом, процедура Задача 3 может быть запущена, пока не возможно будет найдено решение в этом обобщенном смысле.

5. Использование 10 очков в классификации вектора является произвольным.

6. Описанная модель не учитывает уровень квалификации экспертов. Это может зависеть от опыта, ученое звание, или репутации. Тем не менее, добавки или множителя могут быть использованы, чтобы изменить уровень знаний и) ^ т соответственно. Например, предположим, мы классифицируем отзывы на три типа: студент / доцент, доцент; профессором. Мы могли бы назначить веса, скажем, 1, 2, 3, для соответствующих типов. Наконец, мы могли бы заменить каждого опыта уровень с ^ т ^ к югу с д * с ^ ^ т к югу, где А это вес для данного типа оппонентом I.

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

Консалтинг

Рассмотрим ситуацию с точки ряда проектов и число людей, которые должны быть назначены на эти проекты. Каждый проект требует определенное количество людей, и каждый человек должен быть назначен ряд проектов. навыки каждого человека можно охарактеризовать посредством распределения точек по некоторым категориям, а также требования по каждому проекту может быть охарактеризована распространение одинаковое количество очков за тот же категории. Экспертизы уровня каждого человека для каждого проекта могут быть рассчитаны с 1 Целевой нашей модели. Назначение людей на проекты могут осуществляться с использованием Задача 2 нашей модели, чтобы каждый проект указан по крайней мере один человек, который в качестве эксперта, как это возможно.

Работа интервью

Рассмотрим вопрос о присвоении выпускникам собеседование в университете. Каждая компания имеет право интервью определенное количество студентов, и каждый студент имеет право интервью с определенным количеством компаний. Во-первых, каждый студент распределяет определенное количество баллов за интервью компаний в соответствии со своими предпочтениями, и каждая компания распространяет одинаковое количество очков за студентов в соответствии с их предпочтениями. Простой вариант Целевой 1 нашей модели может быть использована для определения потенциала каждого студента - компания пары. Задача 2 нашей модели может быть использована для студентов назначить для интервьюеров, так что каждый студент получает в интервью, по крайней мере одна компания, в которой они сильно заинтересованы (это может быть сделано поочередно из точек компаний зрения).

Класс регистрации

Рассмотрим ситуацию, студентов запрашивающей курсов в процессе предварительной регистрации в университете. Во-первых, каждый учащийся получает некоторое количество баллов, чтобы распространить на курсы (больше очков, которые они дают, конечно, выше их предпочтений). Цель заключается в том, чтобы присвоить студентов на курсы, чтобы каждый студент получает 1 (или 2 и т.д.) курс (ы) с точки рейтинг выше порога, который сделал как можно больше. Каждый курс может также иметь способность студента. (Эта модель использует только 2 Целевой нашей модели.)

ВЫВОДЫ

В данной работе мы предложили две фазы оптимизации подхода к решению уступки конференции бумаги проблемы. Мы реализовали предложенный подход к помощи в организации производства POM-Трек 1998 года ежегодное совещание Института Decision Sciences. Мы обеспечили оптимальные решения для назначения 174 бумаг 182 отзывы в этом направлении. Эти решения обладают следующим свойством: для каждого документа, указанного числа (1, 2 или 3 в нашем случае) отзывы имеют уровень знаний, что выше порога, который является как можно больше. [В редакцию: 20 мая 1998. Принято: 16 октября 1998.]

* Авторы благодарят профессора Патрика Шеннон и Том Фостер колледж бизнеса и экономики, Бойсе государственный университет, г. Бойсе, штат Айдахо. Они были сопредседателями POM-Производство отслеживать 1998 Decision Sciences Институт ежегодного совещания и представил данные документы и отзывы, которые были проверены в модели.

Ссылки

Ahuja, Р. К., Magnanti, Т. Л.,

Аронсон, Е. J. (1986). Многопериодной задачи о назначениях: поток multicommonality сетевой модели и специализированных ветвей и границ, алгоритм. Европейский журнал исследования операций, 23, 367-381.

Bausch, Д. 0., Браун, Г. Хандли, DR, Рапп, SH,

Бектолд, С. Е.,

Carraresi П.,

Картер, М. В.,

Дерман, C.,

Ewashko, Т. А.,

Франц, Л. С.,

Франц, Л. С., Бейкер, Х. М., Леонг, Г. К.,

Гилберт, К. C.,

Хансен, П.,

Хорн, В. А. (1973). Снижение среднего течения времени, с параллельными машинами. Исследование операций, 21, 846-847.

Клингман Д.,

Краевский, Л. J., Рицман, Л. П.,

Machol, Р. Е. (1970). Применение задачи о назначениях. Исследование операций, 18, 745-746.

Мейсон, А. J.,

Маццола, J. Г.,

Росс, Г. Т.,

Шоуолтер, М. J.,

Дэвид и Джерри Хартвигсен Вей

Департамент ofManagement, Колледж делового администрирования, Университет Нотр-Дам, Нотр-Дам, IN46556-0399, адрес электронной почты: <a href="mailto:hartvigsen.1@nd.edu"> hartvigsen.1 nd.edu @ </> и <a href="mailto:jwei@nd.edu"> jwei@nd.edu </ A>

Ричард Czuchlewski

Департамент операций Researh и организации промышленного производства, Корнельский университет, Итака, штат Нью-Йорк 14853

Дэвид Хартвигсен является адъюнкт-профессор менеджмента в Колледже делового администрирования в Университете Нотр-Дам. Он получил докторскую степень по математике в Carnegie-Mellon University в 1984 году. Некоторые из журналов он опубликовал в это SIAM журнал по оптимизации SIAM журнал по дискретной математике, Orsa журнал по вычислительной и математики исследование операций. Он является членом сообщает, MPS, и АСУ.

Джерри Вей является адъюнкт-профессор по управлению операциями в Университете Нотр-Дам. Он получил степень бакалавра Национальный Университет Цинхуа в Тайване, ME из Рочестерского технологического института, а также докторскую степень в области управления операциями из Техаса

Ричард Czuchlewski в настоящее время работает на SABRE группы. Он получил степень магистра в исследовании операций из Корнельского университета в 1999 году и степень бакалавра по математике в Университете Нотр-Дам в 1998 году. Он является членом сообщает.