| How to allocate the scarce resources along a time horizon to individuals is a basic problem.Traditionally,it was often assumed that the resource provider was the global decision maker,the provider allocated the scarce resources according to his own objectives,while the demands of individuals were often ignored.However,in reality,the requirements of individuals are existence and diversified.As a result,conflicts among the resource provider and heterogeneous selfish individuals are unavoidable.In order to study the degree of conflicts,the concept of Price of Anarchy(POA)was proposed,which quantitatively describes the gap between the worst global result caused by individual selfishness and the optimal global result expected by the resource provider.Moreover,the issue of conflict has also prompted resource provider to devise more effective allocation mechanisms to meet increasingly diverse customer needs.This also means that,from the perspective of resource allocation optimization,resource providers should not only consider their own performance indicators,but also need to pay more attention to the demand side.In this paper,the above problems are abstracted into the research of price of anarchy and allocation mechanism for selfish customer in a single machine manufacturing environment.Considering each selfish customer has a single-unit product with identical processing length,and selfish customers’ utilities are heterogeneous,namely regular and non-regular function exist simultaneously,while the resource provider has independent optimization goals.In this paper,the model of single-machine scheduling with heterogeneous products is built,and the relationship between Nash equilibrium schedules and Pareto schedules is analyzed in depth.The relationship between N-person Pareto schedule set and N+1-person Pareto schedule set is also discussed.On the basis of these results,the Pareto schedules may lead to the worst-case performance bound(that is,Price of Anarchy)is analyzed.This paper reveals the conflict mechanism between heterogeneous customer and resource provider in the resource allocation problem.Based on the study of price of anarchy,in order to reflect the demands and unequal relationships among the parties,the resource allocation mechanism based on the Nash bargaining theory is established.Based on the Lagrangian relaxation method,three feasible scheduling schemes are given to solve the problem.The commercial software Local Solver is used to solve the original problem directly to measure the effectiveness of the Lagrangian relaxation method.Simulation results show that the Nash bargaining mechanism is efficient.The main contents and conclusions of this paper include the following four apects:(1)Based on the concepts of Nash equilibrium schedules and Pareto schedules,we prove that Pareto schedule set is a subset of Nash equilibrium schedule set in our model.On this basis,we discusse deeply the relationship between the POA caused by arbitrary NE schedule and Pareto schedule which is generated by EDD rule.In the context of static single machine,heterogeneous customer with single-unit product,and the performance index of the resource provider is the total completion time or makespan,the following theorem is proved by research: 1)There is a Nash equilibrium schedule according to EDD rule.2)There is a Nash equilibrium schedule with EDD rule which makes the performance index of resource providers the worst.3)The Nash equilibrium schedules with EDD rule must be Pareto schedules.4)There is a Pareto schedule with EDD rule is the schedule that makes the performance index of resource provider the worst.The relationship between N-person Pareto schedule set and N+1 person Pareto schedule set is also discussed.The results show that: 1)There is a Nash equilibrium schedule with EDD rule can maximizes overall performance.2)There is a optimal schedule of maximizes overall performance not only belong to the N+1 person Pareto schedule set,but also belong to the N-person Pareto schedule set.(2)Based on the above research results,we deduce and verify POAs,then explores the influence of heterogeneous customer groups on POAs.The results show that: 1)Whether the performance index of the resource provider is the total completion time or makespan,because of the limitation of a time horizon,the POAs will not be deteriorated indefinitely.In a fixed time horizon,the larger the number of customers,the smaller the POAs.When the customer groups are all composed of regular customers,any Nash equilibrium schedule is the optimal schedule for the resource provider.2)When the performance index of the resource provider is the total completion time,if the regular customer number is a fixed,the POA will be deteriorated to the worst and then be optimized gradually as the number of non-regular customer increase.3)When the performance index of the resource provider is the makespan,the larger the number of non-regular customers,the earlier the performance index of the resource provider is deteriorated.(3)Based on the above conclusions,it is urgent for resource provider to devises a efficient resource allocation mechanism,which can meet the diversified needs of customers while taking into account his own performance indicators.In this paper,a resource allocation mechanism based on the multi-person Nash bargaining theory is established to reflect the complex selfishness and unequal relationships among the parties.The Lagrangian relaxation method is used to design the resource allocation mechanism,and three kinds of feasible scheduling schemes are given for solving the constrained nonlinear optimization model.In order to evaluate the Lagrangian relaxation method,Local Solver is used to solve the original problem directly,which also provides the benchmark for the performance evaluation of resource providers.(4)In this paper,we focus on the influence of the bargaining power coefficient of each participant,the planning time horizon of the resource provider and three kinds of feasible scheduling schemes on final scheduling results.The simulation results show that: 1)With the increase of planning time horizon,all the feasible scheduling schemes make customers more likely to occupy their expected recourse.The larger the planning time horizon,the results of the three feasible schemes are closer to the Local Solver results.2)Although there are some merits and demerits of the three feasible schemes,and all schemes can solve the problem effectively.3)As the resource provider’s bargaining power increases,the performance index of the resource provider is gradually optimized,and the objective function value of the Nash bargaining model is gradually increased,while the performance index of the demander side is gradually deteriorated.4)When the Nash bargaining model reaches the optimal solution,the schedule scheme may not be unique.5)If the resource provider is particularly strong,the scheduling results of three kinds of feasible schemes will deviation with Local Solver results.6)For those customers who with larger bargaining power,tend to have more advantages and can occupy resources to optimize their performance indicators.The innovation of this paper are as follows: We consider the selfish customers with regular or nonregular utility functions,the relationship between Nash equilibrium schedules and Pareto schedules is analyzed,then gives the tight POAs bound with the total completion time or makespan as the central objective,the variation mechanism of the POAs is also analyzed.The Nash bargaining theory is used to model the resource allocation mechanism,which reflects the complex selfishness,unequal relationships of the parties,and the inner connection between the resource provider’s retained earning and POAs.The Nash equilibrium schedule,which satisfying Pareto optimality,is obtained.Some management insights are put forward for the supply system to better meet the diversity requirements. |
PDF Full Text Request