Research Of Multi-objective Production Scheduling Problem Based On Game Theory

Scheduling problem is the problem which researching how to allocate single or multiple resources to tasks, which are waiting to be processed, and some objective functions are optimized. Production scheduling is the important component of modern manufacturing industry and the key technology of implementing the computer integrated manufacturing system. The appropriate scheduling result can not only improve the production efficiency and the utilization rate of resources, but also bring remarkable economic benefit and social benefit.In general, manufacturing enterprises arrange process order according to due date, the efficiency of machines and inventory situation in traditional research of production scheduling. But in modern manufacturing industry, every customers have their personality requirements, such as due date, degree of satisfaction, processing cost and so on, the scheduling schemes given by manufacturing enterprises are hardly to meet each customer’s individual needs. In real life, there are some situations in which customers participate in scheduling arrangements through the cooperative or competitive mechanism.This dissertation discusses the multi-objective scheduling problem based on the demand of customers, researches to solve multi-objective scheduling problem using game theory according to the advantage of game theory in solving the constrained optimization problem with multiple player and multiple objective. Cooperative game theory, noncooperative game theory and evolutionary game theory are used to analysis multi-objective scheduling problem based on the demand of customers and build the corresponding game model, some customer-driven scheduling optimization algorithms are researched.The main contributions of this dissertation can be summarized as follows:(1) It comprehensively summarizes the research results of production scheduling and game theory, overviews research status of solving multi-objective scheduling problem using game theory, elucidates the feasibility and research thought on solving multi-objective scheduling problem using game theory.(2) Basic theory of cooperative game and core allocation method in cooperative game is introduced. The cooperative game model of production scheduling based on the demand of customers is built using cooperative game theory, and then the solution of multi-objective scheduling problem is converted to seek the maximum cost savings in cooperative coalition. The existence of cooperative game scheduling solution is analysised and necessary and sufficient conditions are proved. The relation of cooperative game scheduling solution and core allocation in game theory is discussed. The relation of cooperative game scheduling solution set with all scheduling solution set, feasible scheduling solution set and Pareto scheduling solution set is compared.(3) Four types of scheduling problem, including basic single machine scheduling problem, single machine scheduling problem with due date and lateness penalties, flow shop scheduling problem on processing time associated with workstage, hybrid flow shop scheduling with identical stage processing time, are described and corresponding cooperative game models are built, then they are proved be balanced. After analyzing existing core allocation methods, three types of core allocation methods, including proportion gain allocation methods, weighted marginal cost allocate rule on predecessors and followers, equal saving cost allocation methods, are put forward and proved that they are core allcation method. Scheduling examples show that the built models are effective and the proposed cost allocation methods can adapt to allocation of the saving cost in the corresponding cooperation game, cost allocation results are fair and reasonable.(4) Draw lessons from market price competition principle in economics, price competition mechanism of customers under cost constraints is used to determine process priority in single machine sceduling task with cost constraints. Customers bidding strategy is analyzed using noncooperative game method. Single machine sceduling task with cost constraints is analyzed. Noncooperative game models of single machine sceduling with cost cost constraints based complete information is defined using noncooperative game theroy, and payoffs function of players is defined, then solving of single machine sceduling problem with cost cost constraints is converted to seek Nash equilibrium solution based on corresponding constraints. Under noncooperative game framework, an example shows the process of determining process priority by price competition mechanism of customers and validity of obtaining scheduling order that can meet customer cost constraint by noncooperative game way.(5) Single machine scheduling problem with cost constraints and due date is analyzed and noncooperative game models of single machine sceduling with cost cost constraints and due date based complete information is defined using noncooperative game theory. Price competition mechanism is designed, all customers give expected processing start time and quoteprice according their cost constraints and due date. A conflict resolution mechanism is designed if process conflict occurs. The process of solving Nash equilibrium solution of this scheduling game is given. An example shows the validity of the proposed noncooperative game model and solving algorithm using price competition mechanism.(6) Aiming at a type of no-wait flow shop scheduling problem with fuzzy due date, scheduling model of this scheduling problem is researched based on the optimization object of maximum integrated satisfaction degree on customers, and a sort of scheduling model based evolution game is put forward and established on the premise of bounded rationality, in this scheduling model, scheduling task model is mapped to game model, manufacturing tasks of customers correspond to players, sequences of all manufacturing tasks correspond to strategy sets, customer satisfaction degree on finishing time of manufacturing task corresponds to payoff function. Then solving of this sceduling problem is converted to seek evolution game equilibrium point. A heuristic genetic algorithm is given to seek evolution game equilibrium point, evolutionary efficiency is improved because of joining heuristic competitive strategy in evolution process. Computational experiment shows that the proposed scheduling model based evolution game is effective, the proposed solving algorithm can get evolution stable equilibrium point by repeated game and adjusting their strategy dynamically.This dissertation studies multi-objective production scheduling problem considering customers cost optimization, several scheduling game models are built using cooperative game way or noncooperative game way according to the existence of cooperative mechanism, sovling methodes of scheduling solution are researched in game theory framework. Multiple examples show validity of the proposed scheduling game model and sovling methodes of scheduling solution. The theory and way proposed in this dissertation give a new thought of solving multi-objective production scheduling problem, which is helpful to push the development of production scheduling theory, improve the performance of scheduling solution, widen the application field, and has important theory significance and positive practical significance.