Multiple-project scheduling with controllable project duration and hard resource constraint: Some solvable cases

In many large-scale project scheduling problems, multiple projects are eith er taking place at the same time or scheduled into a tight sequence in orde r to efficiently share a common resource. One example of this is the comput ing resource allocation at an Application Service Provider (ASP) which prov ides data processing services for multiple paying customers. Typical servic es provided by ASPs are data mining, payroll processing, internet-based sto rage backup services and Customer Relation Management (CRM) services. The p rocessing mode of an ASP can be either batch or concurrent, depending on th e type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one custom er request at a time in order to minimize the context switching overhead. W hile the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to proce ss a service request depends on the computing resource allocated to that re quest. The related issue of achieving an optimal use of resources at ASPs l eads to problem of project scheduling with controllable project duration. In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project d uration and hard resource constraints. Two types of problems are considered . In type I, the duration of each project includes a constant and a term th at is inversely proportional to the amount of resource allocated. In type I I, the duration of each individual project is a continuous decreasing funct ion of the amount of resource allocated.