Research On Several Optimal Resource Allocation And Scheduling Problems

Scheduling problem is an important combinational optimization problem. In this thesis, we study problems of three kinds of optimal resource allocation and sorting about discretely-divisible, continous-divisible and mixed of them. We will discuss the scheduling problem, polynomial-time algorithm of resource constrained scheduling problems are given in every parts.In the second chapter, a integer programming model is formulatedfor the discretely-divisible scheduling problem with P_m |ressh,p_j=1|C_max. A branch and bound algorithm is given.In the third chapter, a continous-divisible algorithm and specialexample about 1 | , chains |∑w_jc_j is given. we studythe complexity and prove that u^* is the optimal resource allocation.In the fourth chapter, we discuss a kind of problem aboutThe definition of the optimal scheduling and the optimal resource allocation about the mixed of discretely-divisible and continous-divisible are given. In the mean time , we discuss and prove a polynomial-time algorithm of finding the optimal resource constrained scheduling problems.