Auction Mechanisms And Algorithms Implementation For Decentralized Capacity Allocation Problems

The machine capacity allocation problem is to study how to allocate machine capacity to pending orders according to the time dimension to optimize a given performance index.The traditional researches on the allocation of machine capability mainly focus on the perspective of global decision-making,and rarely consider the decentralized decision-making environment.In practice,when the orders to be processed come from individuals,and the customers’ order information are their private information,centralized decision making is no longer possible,and the equilibrium result of individual competition eventually leads to the price of anarchy(POA)of the capacity allocation.Therefore,it has important theoretical significance and application value to design a suitable decentralized decision-making mechanism to guide individual competition results towards global optimization.Auction mechanism,as a market-based resource allocation method,can realize the effective allocation of scarce resources in the case of decentralized decision-making.Therefore,we firstly make the decentralized decision-making models for capacity allocation problems that consider the characteristics of the delivery times of orders and the characteristics of machine environment,and design multiple rounds ascending auction mechanisms so as to optimize the global value of the decentralized system.In the design of the auction mechanism for the capacity allocation,the main challenges are as follows: how to design price,so that the manufacturer’s capacity can be efficiently allocated;and how to determine the final allocation,so that the auction ends within a reasonable time.To solve the above two problems,we conduct detailed research on the multi-round ascending auction mechanisms under different decentralized decision-making models.The main research contents and contributions are as follows:1.In the multi-round ascending auction mechanism of capacity allocation on single-machine.We design an adaptive pricing rule based on supply and demand to dynamically adjust the direction of auction;The winner determination problem in this mechanism is NP-complete,we design a dynamic programming algorithm to solve the problem in pseudo polynomial time.Numerical experimental results show that,compared with the first-come first-served processing strategy,the auction mechanism of capacity allocation problem on single machine can significantly improve the manufacturer’s revenue and the total revenue of the decentralized system.2.In the multi-round ascending auction mechanism of capacity allocation on parallel machines.When customer orders have due dates,the value of the time slots before the order’s due date is the same to the customer,so we design a linear discrimination pricing rule,which reflects the resource scarcity that is affected by both machine capacity and orders’ deadlines.It not only ensures the fairness,rationality and effectiveness of pricing,but also guides the customers to reveal truthful order information;The winner determination problem in this mechanism is NP-complete,we construct a heuristic algorithm based on Lagrangian relaxation technique to improve the computational efficiency and practical applicability of this problem.Numerical experimental results show that the auction mechanism of capacity allocation on parallel machines can significantly improve the price of anarchy of capacity allocation in decentralized decision-making environment.3.In the multi-round ascending auction mechanism of capacity allocation on parallel machines,when the customers’ orders have tardiness,the value of the time slots is not the same for the customer,so we design multiple pricing rules based on customers’ private value,and allow customers to bid by multiple bids.In this way,the customers will have the opportunity to express their opinions in more detail,and the probability of winning the bid will be increasing;The winner determination problem in this mechanism is a combinatorial optimization problem with NP-hard properties.We design a heuristic based on the Lagrangian relaxation technique to obtain a near-optimal solution in a reasonable time.Numerical experimental results show that,compared with the single-bid auction mechanism,the multi-round ascending auction mechanism that allows customers to make multiple bids can significantly improve the efficiency of capacity allocation in decentralized system.4.In the multi-round ascending auction mechanism of capacity allocation on parallel machines with inclusive processing set restrictions,we design a discriminatory pricing rule based on processing information of orders such as orders’ due dates and machine number,so as to reasonably describe the value of machine resources and guide customers to reveal truthful processing information of orders;The winner determination problem requires joint decisions of order acceptance and scheduling on multiple machines with inclusive processing set restrictions.We first establish the integer linear program model of the problem and design a heuristic algorithm based on optimization properties and Lagrangian relaxation techniques.Numerical experimental results show that an auction mechanism for the capacity allocation on parallel machines with inclusive processing set restrictions performs effectively and efficiently.This topic enriches the research ideas of the problem of decentralized decision-making in capacity allocation,and provides a more comprehensive and systematic design method for the auction mechanism of capacity allocation problem.