On single machine scheduling with resource constraint |
| |
Authors: | Lidong Wu Cong-Dian Cheng |
| |
Institution: | 1.Department of Computer Science,University of Texas at Dallas,Richardson,USA;2.College of Mathematics and Systems Science,Shenyang Normal University,Shenyang?,China |
| |
Abstract: | The single machine scheduling with resource constraint is a nonlinear combinatorial optimization problem in cloud computing applications. Given a set of jobs and certain resource, the problem is to find a permutation of jobs and a distribution of resource to optimize certain objective function. The processing time of each job is a nonlinear function with respect to the resource assigned to it. In this paper, we propose a naive algorithm and study a subproblem in the algorithm that suppose the permutation of jobs is also given, how to find a resource distribution to minimize the total weighted flow time. We found a polynomial-time optimal solution for a special case and an approximation solution in general case. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|