A branch-and-price algorithm for the generalized assignment problem

被引：239

作者：

Savelsbergh, M ^{[1
]}

机构：

[1] Georgia Inst Technol, Atlanta, GA 30332 USA

来源：

OPERATIONS RESEARCH | 1997年 / 45卷 / 06期

关键词：

D O I：

10.1287/opre.45.6.831

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The generalized assignment problem examines the maximum profit assignment of jobs to agents such that each job is assigned to precisely one agent subject to capacity restrictions on the agents. A new algorithm for the generalized assignment problem is presented that employs both column generation and branch-and-bound to obtain optimal integer solutions to a set partitioning formulation of the problem.

引用

收藏

页码：831 / 841

页数：11

相关论文

共 20 条

[1]

ANBIL RR, 1991, COC9105 GEORG I TECH

[2] A SURVEY OF ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM [J].

CATTRYSSE, DG ;

VANWASSENHOVE, LN .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 60 (03) :260-272

[3] A SET PARTITIONING HEURISTIC FOR THE GENERALIZED ASSIGNMENT PROBLEM [J].

CATTRYSSE, DG ;

SALOMON, M ;

VANWASSENHOVE, LN .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 72 (01) :167-174

[4] A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].

DESROCHERS, M ;

DESROSIERS, J ;

SOLOMON, M .

OPERATIONS RESEARCH, 1992, 40 (02) :342-354

[5] A COLUMN GENERATION APPROACH TO THE URBAN TRANSIT CREW SCHEDULING PROBLEM [J].

DESROCHERS, M ;

SOUMIS, F .

TRANSPORTATION SCIENCE, 1989, 23 (01) :1-13

[6] A MULTIPLIER ADJUSTMENT METHOD FOR THE GENERALIZED ASSIGNMENT PROBLEM [J].

FISHER, ML ;

JAIKUMAR, R ;

VANWASSENHOVE, LN .

MANAGEMENT SCIENCE, 1986, 32 (09) :1095-1103

[7] SET-PARTITIONING PROBLEM - SET COVERING WITH EQUALITY CONSTRAINTS [J].

GARFINKEL, RS ;

NEMHAUSER, GL .

OPERATIONS RESEARCH, 1969, 17 (05) :848-+

[8] A LINEAR-PROGRAMMING APPROACH TO THE CUTTING-STOCK PROBLEM [J].

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1961, 9 (06) :849-859

[9]

GU Z, 1994, LEC9407 GEORG I TECH

[10] AN IMPROVED DUAL BASED ALGORITHM FOR THE GENERALIZED ASSIGNMENT PROBLEM [J].

GUIGNARD, M ;

ROSENWEIN, MB .

OPERATIONS RESEARCH, 1989, 37 (04) :658-663