Parallel machines scheduling in the presence of heterogeneous selfish customers

We address the parallel machines scheduling problems when selling to a selfish customer population with heterogeneous time utility functions. The manufacturer, owning parallel machines resource, has some independent objective. Because of customers´ selfishness, anarchistic competition would worsen the manufacturer´s performance, and then, cause “Price of Anarchy”. On the other hand, the optimization of the manufacturer´s objective would also deteriorate some customers´ waiting costs greatly (and then, will harm seller himself in long term). In this paper, noncooperative game is used to model above multi-person multi-objective problem in parallel machine environment. Price of Anarchy is analyzed. To balance each participant´s performance, a coordination mechanism which could generate an efficient schedule is provided by choosing payment to motivate all selfish customers to act as the manufacturer wishes. Numerical experiments on proposed coordination mechanism are given at last.