Scheduling Projects with Multi-Skilled Personnel by a Hybrid MILP/CP Benders Decomposition Algorithm

Haitao Li; Keith Womer

doi:10.1007/s10951-008-0079-3

Scheduling Projects with Multi-Skilled Personnel by a Hybrid MILP/CP Benders Decomposition Algorithm

Haitao Li, Keith Womer

University of Missouri-St. Louis

Research output: Contribution to journal › Article › peer-review

Abstract

We study an assignment type resource-con- strained project scheduling problem with resources being multi-skilled personnel to minimize the total staffing costs. We develop a hybrid Benders decomposition (HBD) algorithm that combines the complimentary strengths of both mixed-integer linear programming (MILP) and constraint programming (CP) to solve this NP-hard optimization problem. An effective cut-generating scheme based on temporal analysis in project scheduling is devised for resolving resource conflicts. The computational study shows that our hybrid MILP/CP algorithm is both effective and efficient compared to the pure MILP or CP method alone.

Original language	American English
Journal	Journal of Scheduling
Volume	12
DOIs	https://doi.org/10.1007/s10951-008-0079-3
State	Published - Jun 1 2009

Disciplines

Business Administration, Management, and Operations
Computer Engineering
Applied Mathematics
Theory and Algorithms
Computer Sciences

Access to Document

10.1007/s10951-008-0079-3License: Unspecified

Cite this

@article{c8a76a82a41f4234a73c13143cc44f23,

title = "Scheduling Projects with Multi-Skilled Personnel by a Hybrid MILP/CP Benders Decomposition Algorithm",

abstract = " We study an assignment type resource-con- strained project scheduling problem with resources being multi-skilled personnel to minimize the total staffing costs. We develop a hybrid Benders decomposition (HBD) algorithm that combines the complimentary strengths of both mixed-integer linear programming (MILP) and constraint programming (CP) to solve this NP-hard optimization problem. An effective cut-generating scheme based on temporal analysis in project scheduling is devised for resolving resource conflicts. The computational study shows that our hybrid MILP/CP algorithm is both effective and efficient compared to the pure MILP or CP method alone.",

author = "Haitao Li and Keith Womer",

year = "2009",

month = jun,

day = "1",

doi = "10.1007/s10951-008-0079-3",

language = "American English",

volume = "12",

journal = "Journal of Scheduling",

}

TY - JOUR

T1 - Scheduling Projects with Multi-Skilled Personnel by a Hybrid MILP/CP Benders Decomposition Algorithm

AU - Li, Haitao

AU - Womer, Keith

PY - 2009/6/1

Y1 - 2009/6/1

N2 - We study an assignment type resource-con- strained project scheduling problem with resources being multi-skilled personnel to minimize the total staffing costs. We develop a hybrid Benders decomposition (HBD) algorithm that combines the complimentary strengths of both mixed-integer linear programming (MILP) and constraint programming (CP) to solve this NP-hard optimization problem. An effective cut-generating scheme based on temporal analysis in project scheduling is devised for resolving resource conflicts. The computational study shows that our hybrid MILP/CP algorithm is both effective and efficient compared to the pure MILP or CP method alone.

AB - We study an assignment type resource-con- strained project scheduling problem with resources being multi-skilled personnel to minimize the total staffing costs. We develop a hybrid Benders decomposition (HBD) algorithm that combines the complimentary strengths of both mixed-integer linear programming (MILP) and constraint programming (CP) to solve this NP-hard optimization problem. An effective cut-generating scheme based on temporal analysis in project scheduling is devised for resolving resource conflicts. The computational study shows that our hybrid MILP/CP algorithm is both effective and efficient compared to the pure MILP or CP method alone.

UR - https://link-springer-com.ezproxy.umsl.edu/article/10.1007%2Fs10951-008-0079-3

UR - http://www.umsl.edu/~lihait/files/PSMPR-HBD-Published2009.pdf

U2 - 10.1007/s10951-008-0079-3

DO - 10.1007/s10951-008-0079-3

M3 - Article

VL - 12

JO - Journal of Scheduling

JF - Journal of Scheduling

ER -

Scheduling Projects with Multi-Skilled Personnel by a Hybrid MILP/CP Benders Decomposition Algorithm

Abstract

Disciplines

Access to Document

Other files and links

Cite this