Страница публикации

A Branch-and-Cut Algorithm for the Multilevel Generalized Assignment Problem

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Avella P., Boccia M., Vasilyev I .

Журнал: IEEE Access

Язык публикации: english

Том: 1

Номера страниц: 475-479

Количество страниц: 5

Год публикации: 2013

Отчетный год: 2013

DOI: 10.1109/ACCESS.2013.2273268

Аннотация: The multilevel generalized assignment problem (MGAP) consists of minimizing the assignment cost of a set of jobs to machines, each having associated therewith a capacity constraint. Each machine can perform a job with different efficiency levels that entail different costs and amount of resources required. The MGAP was introduced in the context of large manufacturing systems as a more general variant of the well-known generalized assignment problem, where a single efficiency level is associated with each machine. In this paper, we propose a branch-and-cut algorithm whose core is an exact separation procedure for the multiple-choice knapsack polytope induced by the capacity constraints and single-level execution constraints. A computational experience on a set of benchmark instances is reported, showing the effectiveness of the proposed approach.

Индексируется WOS: Q1

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет