Multi-Agent Scheduling Based On Combinatorial Auction

With the acceleration of manufacturing globalization, the optimal allocation of manufacturing resources has expanded to the whole district, the whole country, and even all over the world. Under the support of information technology and advanced manufacturing technology, many advanced manufacturing modes have emerged, such as Application Service Provider, Agile Manufacturing, Network Manufacturing, Service-Oriented Manufacturing, Cloud Manufacturing, and so on. In order to reduce the cost and improve the efficiency from design phase to manufacturing phase, collaboration among enterprises and resource sharing in the whole society are emphasized. Since the enterprises in the value chain are heterogeneous, distributed, and autonomous, how to organize diffirent manufacturing resources efficiently has attracted great attention. The goal of centralized utilization of distributed resources and distributed service of centralized resources has become a hotspot in the field of manufacturing.By employing Multi-Agent technology, this dissertation aims to study the above problems through collaboration and coordination among enterprises, as well as global optimization. The dissertation includes three research points:(a) the negotiation mechanism of Multi-Agent scheduling problem;(b) Multi-Agent scheduling problem with controllable processing times using linear resource consumption function; and (c) Multi-Agent scheduling problem with controllable processing times using convex resource consumption function. More specifically, this study can be summarized as follows:Firstly, considering the heterogeneity, distributivity, and autonomy, an iterative combinatorial auction mechanism is proposed to resolve Multi-Agent single machine scheduling problem. A requirement-based bidding language is employed. By combining the general form of combinatorial auction and the modeling technology of machine scheduling, the model for the winner determination problem (WDP) is formulated, in whose objectives both the system revenue and the machine utilization level are taken into account. While failing in the current round, a bidder can increase her bidding price or relax her temporal constraints in order to remain in the next round of the auction. Experimental results show that the proposed scheduling scheme outperforms the traditional combinatorial auction-based mechanism by effectively enhancing the machine utilization level without reducing the system revenue.Secondly, a Multi-Agent parallel machine scheduling problem with controllable processing times is concerned. To deal with this problem, an iterative combinatorial auction is designed. A WDP model is formulated to allocate the resource more effectively, in which the controllable processing times are incorporated using a linear resource consumption function. To accelerate the convergence of auction, an adapted price updating mechanism based on sub-gradient method is employed. Experimental results show that the proposed scheduling scheme outperforms the traditional mechanism without controllable processing times by effectively enhancing the machine utilization level and the system revenue.Lastly, the resource consumption function is expanded to convex function, so the WDP model is a kind of nonlinear mixed integer program model. To resolve the WDP model, a two phase method is proposed which is composed of processing scheme decision and optimizing resource allocation. A branch and bound (B&B) algorithm is designed to deal with medium and small scale problems, and a genetic algorithm (GA) is designed to deal with large scale problem. Experimental results show that the B&B algorithm can obtain an optimal or near-optimal solution in acceptable time, while the GA algorithm can obtain near-opitimal solution in short time. And the scheduling scheme also outperforms the traditional mechanism with uncontrollable processing times.