Research On Some Single Machine And Parallel Machine Sequencing Situations

In this thesis we study some sequencing situations by applying the cooperative game theory. In a sequencing situation, some jobs owned by different agents need to be pro-cessed on some machines. In this paper each agent owns one job, and takes the cost his jobs occurred for waiting and processing. The cost is often supposed to be linear function of the job’s completion time, and we study the weighted completion time cost in general. The agents cooperate to make decision of the final processing order among all feasible processing orders. By cooperation there is money compensation between the agents, in other words the total cost is reallocated among the agents by some way such that all the agents are satisfied. With properly defined characteristic function the related sequencing game is defined. There are two kinds of sequencing games. If an initial order is given, the agents cooperate to achieve a better processing order and make cost savings. Other-wise the agents cooperate to make total cost minimized. We mainly focus on sequencing situations without initial orders.The research is on properties of some sequencing games related to sequencing sit-uations we are interested in, and the design of cost allocation rules, and fairness of the allocated costs. It is organized in six parts. Chapter One is about basic knowledge of co-operative game theory and scheduling, and literature review of application of cooperative game theory to sequencing situation.Chapter Two mainly deals with the single machine sequencing situations without initial order. A cost allocation called the EWCS rule is proposed for the single machine sequencing situation without any constraints on jobs. The EWCS rule encourages the agents to choose an optimal processing order. We also generalized it to the single machine sequencing situation with chains precedence constraints.Chapter Three makes a study of the single machine sequencing situation with learn-ing effect, and the cost for each agent is the actual processing time. Let the initial order be identity permutation, then the related game is balanced since it is a permutation game. A single-valued solution is given. For the sequencing game without initial order, an assignment game is obtained, and a solution developed from a special core element is given.Chapter Four is on 2-sequencing situation. In this sequencing situation each agent owns exactly two jobs needing to be processed on two different machines, and the agent’s cost is the larger one of his two jobs’weighted completion times. If every agent has two jobs of the same length, the problem is simple. For the general problem, we decide the final processing order by heuristic algorithm, and a cost allocation rule being dependent on the processing order is designed.Chapter Five studies the m-sequencing situation, and since the related sequencing problem is NP-hard, we only give the formulation of Shapley value for two special cases: the one with identical processing time and the one with identical weight. The calculation of Shapley value can be finished in polynomial time. Chapter Six makes a conclusion for the thesis.