Solving large-scale resource allocation problems : formulations, solutions and case studies

Abstract

Resource allocation problems appear everywhere in our daily lives. Applications like the power scheduling, traffic management, airport runway time-slot arrangement, communication server allocation and cloud computing resource scheduling are all resource allocation problems. Resources in these problems could be continuous, e.g., the gas, water and electrical power, or discrete, e.g., the manpower and equipment. The objectives are to optimize some performance indices, e.g., the Quality of Service (QoS) involved in communication systems. Several major technical obstacles need to be overcome when we try to solve resource allocation problems efficiently. Firstly, the system dynamics and constraints involved in resource allocation problems are complex, which are hard to be modeled. Secondly, the numbers of decision variables and constraints are huge, which may lead to extremely high computational complexity. Thirdly, the nature of resources involved in these problems usually makes the computational benefits from the convexity unachievable. To overcome these difficulties, in this thesis I propose (1) a specific model of resource allocation problems; (2) a distributed / hierarchical computation structure to reduce the computational complexity; (3) some efficient algorithms for solving large resource allocation problems in specific application domains such as electrical power systems, urban traffic systems and air traffic systems. Our simulation results indicate that the proposed distributed or hierarchical computational architecture with heuristic algorithms is able to achieve good performance whilst reducing the computation complexity. This thesis is organized as follows. In Chapter 1, we first give a brief introduction about resource allocation problems, including the concepts, constraint sets, decision variables and objectives. In Chapter 2, a review on the methodologies for solving large resource allocation problems in air traffic systems, urban traffic systems and electrical power systems is proposed. Resource allocation issues on air traffic flow management, urban traffic signal control and power management in an electrical power system in a more electric engine / aircraft architecture are studied in Chapter 3, 4 and 5, respectively. Conclusions are drawn in Chapter 6, where some possible further works are listed.