Document Type
Technical Report
Publication Date
2002-05-23
Technical Report Number
WUCSE-2002-13
Abstract
We study a resource allocation problem, which is a central piece of a real-world crew scheduling problem. We first formulate the problem as a hybrid soft constraint satisfaction and optimization problem and show that its worst-case complexity is NP-complete. We then propose and study a set of decision and optimization modeling schemes for the problem. We consider the expressiveness of these modeling schemes for the problem. We consider the expressiveness of these modeling methods. Specifically, we experimentally investigate how these modeling schemes interplay with the best existing systematic search and local search methods. Our experimental results show that soft constraint techniques can be effective on large resource allocation problem instances, and an optimization approach is more efficient than a model checking approach based on decision models.
Recommended Citation
Zhang, Weixiong, "Modeling and Solving a Resource Allocation Problem with Soft Constraint Techniques" Report Number: WUCSE-2002-13 (2002). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/1131
Comments
Permanent URL: http://dx.doi.org/10.7936/K7668BH2