Article ID: | iaor2008718 |
Country: | United Kingdom |
Volume: | 8 |
Issue: | 2 |
Start Page Number: | 135 |
End Page Number: | 143 |
Publication Date: | Mar 2005 |
Journal: | Journal of Scheduling |
Authors: | Barcia Paulo, Cerdeira J. Orestes |
The k-track assignment problem is a scheduling problem in which a collection of jobs, represented by intervals, are to be processed by k machines. Two different jobs can be processed by the same machine only if the corresponding intervals do not overlap. We give a compact formulation of the problem and state some polyhedral results for the associated polytope, working in the more general context where job compatibility stems not necessarily from intervals but rather from an arbitrary strict partial order.