|
|||||
|
|
Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements |
|
| Authors: | Jill R. Hardin George L. Nemhauser Martin W.P. Savelsbergh |
| Affiliation: | aDepartment of Statistical Sciences and Operations Research, Virginia Commonwealth University, 1001 West Main Street, P.O. Box 843083, Richmond, VA 23284-3083, United States;bSchool of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, NW, Atlanta, GA 30332-0205, United States |
| Abstract: | We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities. |
| Keywords: | Resource-constrained scheduling Multiprocessor scheduling Time-indexed formulation Valid inequalities Lifting |
| 本文献已被 ScienceDirect 等数据库收录！ | |