Theoretical Research On Multi-agent Production Scheduling Problems

Production scheduling is to determine the sequence and time of jobs on each machine meeting the constraints of production process, so as to optimize the objective, such as energy, resources, or efficiency for given a set of jobs and multiple machines. Previous work mostly focused on the scheduling that all jobs are considered as a whole with consistent performance index. However, with the development of economy and the improvement of people's consumption level, the individuation and diversification customer demand for goods is higher and higher, and the traditional scheduling theory is no longer suitable for the scheduling problem of the new demand situation. Therefore, it is necessary to research on the multi-agent scheduling problem with diversity customer demand.Multi-agent production scheduling refers to each customer demand corresponds to one agent, and all agents compete for the common machine to process respective jobs at the same time, and to optimize the objective of each agent. In this dissertation, based on the different production stages in the iron and steel production process as background, we refine a series of problems of the multi-agent production scheduling. For two-agent scheduling problem with time-dependent deteriorating jobs on a single machine, two-agent scheduling problem with linear deteriorating jobs on a single batching machine, multi-agent cooperation game problem on a single batching machine, and two-agent scheduling problem with linear deteriorating jobs on two-machine shop settings, we carry on the theoretical research. For the above problems, we analyze the complexity, respectively; for the solvable problems, we provide optimal algorithms or allocation mechanism; for the intractable problems, we give the proofs of NP-hardness and for some special cases of intractable problems, we analyze the structure characteristics and properties of the optimal solution, and construct the polynomial or pseudo-polynomial time algorithms to solve them. The content is summarized as follows:1) For the two-agent single machine scheduling problems with linear deteriorating jobs and release dates, we consider the identical and different job release dates cases, as follows:(1) When the jobs have identical release dates, for minimizing the total weighted number of tardy jobs of agent?A subject to an upper bound on the maximum of regular functions of agent B, we prove that the problem is NP-hard. For the maximum of regular functions of agent B is equal to the makespan, we analyze the properties of the optimal solution and present a pseudo-polynomial time dynamic programming algorithm to solve it. For All jobs of agent A have the same weights, by analyzing the structure characteristics and properties of the optimal solution for the preemptive problem, we give a polynomial time optimal algorithm to solve it. (2) When the jobs have different release dates, for minimizing the number of tardy jobs of agent A subject to an upper bound on the number of tardy jobs of agent B, we prove that the problem is NP-hard under the condition of different number of release dates and due dates. For all the jobs have agreeable release dates and due dates, or the jobs of each agent have the same deteriorating rates and agreeable release dates and due dates, we analyze the properties of the optimal solution and present polynomial time dynamic programming algorithms to solve them, respectively.2) For the two-agent single machine scheduling problems with time-dependent deteriorating jobs and machine maintenance activity, we consider the job-dependent and job-independent learning effects, where the job learning effect is that the processing time of job is reduced with the deferred processing position, as follows:(1) When the jobs have job-dependent learning effects, for minimizing the sum of earliness, tardiness, due-window starting time, and due-window size costs, we analyze the properties of the optimal solution and transform the problem into assignment problem, and then provide a polynomial time algorithm to solve it. For its three special cases, we also give more efficient algorithms to solve them by analyzing the structure characteristics the optimal solution, respectively. (2) When the jobs have job-independent learning effects, for minimizing the total weighted completion time and the maximum lateness, we prove that the WSPT and EDD rules can still obtain the optimal solution under certain conditions, respectively.3) For the two-agent single bounded batching machine scheduling problems with linear deteriorating jobs, based on the identical or different release dates of the jobs, and the compatibility that the two agents' jobs can be processed in the same batch or the incompatibility that the two agents' jobs can not be processed in the same batch, we analyze the time complexity of eight different problems under the different situations for the common objective functions:minimizing the makespan (or the number of tardy jobs) of agent A subject to an upper bound on the makespan (or the number of tardy jobs) of agent B. For the solvable problems, we give polynomial time optimal algorithms. For the intractable problems, we give the proofs of NP-hardness, and for some general problems or special cases, we analyze the properties of the optimal solution and give the pseudo-polynomial or polynomial time algorithms to solve them.4) For the two-agent single unbounded batching machine scheduling problems with linear deteriorating jobs, based on the compatibility or the incompatibility of the two agents' jobs, we consider the identical and different job release dates cases, as follows:(1) When the jobs have identical release dates, for minimizing the sum of regular functions of agent A subject to an upper bound on the maximum of regular functions (or the sum of regular functions) of agent B, we analyze the properties of the optimal solution and present dynamic programming algorithms to solve the problems, respectively. (2) When the jobs have different release dates, for minimizing the makespan of agent A subject to an upper bound on the makespan of agent B, we analyze the structure characteristics and properties of the optimal solution, and give an optimal method to obtain the optimal solution.5) For the multi-agent single batching machine scheduling cooperative games, we consider the optimal solution of multi-agent scheduling, design the reasonable allocation mechanism for the cost savings of multi-agent cooperation, and prove the existence of core for the corresponding multi-agent and job cooperative games. For a special case of multi-agent scheduling, we prove that the corresponding multi-agent and job cooperative games are all convex games.6) For the two-agent two-machine shop settings scheduling problems with linear deteriorating jobs, we consider minimizing the makespan of agent A subject to an upper bound on the makespan of agent B on flow shop, open shop, and job shop scheduling environments, respectively. For flow shop scheduling environment, we prove that the problem is NP-hard, and for two special cases of machines with dominance, we present optimal algorithms, respectively. For open shop and job shop scheduling environments, we prove that the problems are all NP-hard, respectively.