多代理生产调度问题的理论研究

发布时间：2018-08-02 13:12

【摘要】：生产调度是指对给定的一组工件和多台机器,在满足生产工艺的约束下,确定每台机器上工件的顺序与时间,以使得能源、资源或效率等指标达到最优。以往的调度研究主要集中在所有工件作为一个整体考虑一致的性能指标作为目标。但是随着经济的发展和人们消费水平的提高,顾客对商品的个性化和多样化的需求越来越高,传统的调度理论已不再适合这种新的需求情况下的调度问题。所以迫切需要研究考虑顾客多样性需求的多代理生产调度问题。多代理生产调度是指每个顾客的需求对应一个代理,所有代理竞争在共同的机器上同时加工各自的工件,使得每个代理的目标达到最优。本文以钢铁生产中不同生产阶段的工艺过程为背景,提炼出多代理生产调度中一系列问题。针对带有依赖于时间恶化工件的双代理单机调度问题、带有线性恶化工件的双代理单机批处理机调度问题、单机批处理机上多代理合作博弈问题、以及带有线性恶化工件的双代理两台机器车间调度问题进行了理论研究。对于上述问题,分别进行了复杂性分析；对于可解问题,给出了最优算法或分配机制；对于难解问题,给出了NP-难证明,对难解问题的特殊情况,分析了最优解的结构特征和性质,构造了多项式或伪多项式时间的求解方法。具体内容概括如下：1) 针对带有线性恶化工件和释放时间的双代理单机调度问题,考虑了工件释放时间相同与不同两种情况如下：(1)当工件释放时间相同时,针对最小化代理A的总加权拖期工件个数使得代理B工件完工时间的最大费用不超过一个给定上界的问题,证明了问题的NP-难性。对于代理B工件完工时间的最大费用为最大完工时间的特殊情况,分析了最优解性质,给出了伪多项式时间动态规划算法进行求解；对于代理A的所有工件具有相等权值特殊情况,通过分析可中断问题的最优解结构与性质,给出了求解问题的多项式时问最优算法。(2)当工件释放时间不同时,针对最小化代理A的总拖期工件个数使得代理B的总拖期工件个数不超过一个给定上界的问题,证明了问题在不同数量释放时间与工期情况下的NP-难性。对于所有工件具有一致的释放时间与工期,或同一代理的工件具有相同恶化率和一致的释放时间与工期两种特殊情况,分析了最优解性质,分别给出了多项式时间动态规划算法进行求解。2) 针对带有依赖于时间恶化的工件及机器维护的单机双代理调度问题,考虑了依赖于工件的学习效应与不依赖于工件的学习效应两种情况,其中工件的学习效应是指工件的加工时间随着加工位置的延后而减小,如下：(1)当依赖于工件的学习效应时,针对最小化工件提前惩罚、拖期惩罚、共同工期窗开始时间费用、以及工期窗大小费用之和问题,分析了最优解性质,将问题转换为指派问题,进而在多项式时间求得最优解。对于问题的三个特殊情况,分析了最优解的结构,分别给出了更为有效的求解方法。(2)当不依赖于工件的学习效应时,针对最小化总加权完工时间与最大延迟两个问题,分别证明了在满足一定条件下WSPT与EDD规则仍可求得问题的最优解。3) 针对带有线性恶化工件的双代理单机有界批处理机调度问题,基于工件的释放时间相同与不同,以及工件组批时两个代理的工件可以在同一批的兼容性与不可在同一批的不可兼容性,考虑了不同情况下目标函数为最小化代理A工件的最大完工时间(或总拖期工件个数)使得代理B工件的最大完工时间(或总拖期工件个数)不超过一个给定上界的八个不同问题的时间复杂性。对于可解问题,给出了多项式时间最优算法；对于难解问题,给出了Np-难证明,对难解问题的一般情况或特殊情况,分析了最优解性质,给出了伪多项式或多项式时间的求解方法。4) 针对带有线性恶化工件的双代理单机无界批处理机调度问题,基于工件组批时两个代理的工件可以在同一批的兼容性与不可在同一批的不可兼容性,考虑了工件释放时间相同与不同两种情况如下：(1)当工件释放时间相同时,针对最小化代理A工件完工时间的总费用使得代理B工件完工时间的最大费用(或总费用)不超过一个给定上界的问题,分析了问题的最优解性质,分别给出了动态规划算法求得最优解；(2)当工件释放时间不同时,针对最小化代理A工件的最大完工时间使得代理B工件的最大完工时间不超过一个给定上界的问题,分析了最优解的结构与性质,给出了最优解的求解方法。5) 针对单机批处理机上多代理生产调度的合作博弈问题,研究了多代理生产调度的最优解,设计了多代理合作节省费用的合理分配机制,证明了多代理合作博弈与工件合作博弈核的存在性。对于多代理生产调度的特殊情况,证明了对应的多代理合作博弈与工件合作博弈均为凸博弈。6) 针对带有线性恶化工件的双代理两台机器车间调度问题,分别考虑了流水车间、开放车间、以及异序作业车间环境下,目标函数为最小化代理A工件的最大完工时间使得代理B工件的最大完工时间不超过一个给定上界的问题时间复杂性。对于流水车间,证明了问题的NP-难性,对具有优势机器关系的两个特殊情况,分别给出了最优算法。对于开放车间与异序作业车间,分别证明了问题的NP-难性。
[Abstract]:Production scheduling refers to a given set of workpieces and machines which, under the constraints of the production process, determine the sequence and time of the workpieces on each machine, so as to achieve the optimal energy, resources, or efficiency. The previous scheduling research is mainly focused on all the workpieces as a whole to consider the consistent performance indicators as a target. However, with the development of economy and the improvement of people's consumption level, the demand for individuation and diversification of the customers is getting higher and higher. The traditional scheduling theory is no longer suitable for the scheduling problem under the new demand. Therefore, it is urgent to study the multi agent production scheduling problem considering the customer diversity demand. Degree is that each customer's requirements correspond to one agent. All agents compete on a common machine to process their own workpieces at the same time, making the target of each agent achieve the best. This paper, based on the process of different production stages in the steel production, extracts a series of problems in the multi agent production scheduling. The problem of double agent single machine scheduling for deteriorating workpieces with linear deteriorating two agent single machine batch processor scheduling problem, multi agent cooperative game problem on single machine batch machine and double agent two machine shop scheduling problem with linear deteriorating workpieces are studied in theory. For the solvable problem, the optimal algorithm or distribution mechanism is given; for the difficult problem, the NP- hard proof, the special case of the difficult problem, the structure characteristics and the properties of the optimal solution are analyzed, and the method of solving the polynomial or pseudo polynomial time is constructed. The specific internal capacity is summarized as follows: 1) for the linear deteriorating workpiece and The problem of the release time double agent single machine scheduling considers the same and different two cases of the same release time of the workpiece: (1) when the release time of the work piece is the same, the maximum cost of the total weighted tardiness of the agent A makes the maximum cost of the completion time of the agent B work no more than a given upper bound, which proves the NP- difficulty of the problem. For the special case of the maximum completion time of the completion time of the proxy B work piece, the properties of the optimal solution are analyzed and the pseudo polynomial time dynamic programming algorithm is given. For all the work pieces of the proxy A with the equal weight, the optimal solution structure and properties of the broken problem are analyzed. The optimal algorithm for solving the problem of polynomial time is asked. (2) when the release time of the work piece is different, the total tardiness of the agent A is not more than a given upper bound for minimizing the number of the total tardiness of the agent B, which proves the NP- difficulty of the problem in different amount of time and time. The release time and the duration of the work, or the same agent's workpiece with the same deterioration rate and the consistent release time and the period of the two special cases, analyze the optimal solution properties, give the polynomial time dynamic programming algorithm to solve.2 respectively, for the single machine and double agent scheduling problem with the time deteriorated workpiece and machine maintenance, The learning effect depends on the learning effect of the workpiece and the learning effect that does not depend on the work piece. The learning effect of the workpiece is that the processing time of the workpiece decreases with the delay of the processing position. As follows: (1) when it depends on the learning effect of the work piece, it is aimed at minimizing the penalty for the work piece, the tardiness penalty, and the beginning of the common time window. The problem of the inter cost and the sum of the size and cost of the time window, the optimal solution properties are analyzed, the problem is converted to the assignment problem, and then the optimal solution is obtained in polynomial time. For the three special cases, the structure of the optimal solution is analyzed, and the more effective solution method is given. (2) the needle is not dependent on the learning effect of the workpiece. In order to minimize the two problems of the total weighted completion time and the maximum delay, it is proved that the optimal solution.3 of the WSPT and EDD rules can still be obtained under certain conditions. The scheduling problem of a double agent single machine bounded batch processor with linear deteriorating jobs is based on the same and different release time based on the work piece, and two of the work group batch. The agent's workpiece can be compatible with the same batch and cannot be compatible in the same batch, considering that the maximum completion time (or the number of total tardiness artifacts) of the agent A workpiece in different circumstances makes the maximum completion time (or the number of total tardiness artifacts) of the proxy B workpiece not more than eight of a given upper bound. The time complexity of the same problem is given. For the solvable problem, a polynomial time optimal algorithm is given. For the difficult problem, the Np- hard proof is given, the general condition or special case of the difficult problem is given. The properties of the optimal solution are analyzed, the pseudo polynomial or the polynomial time solution method.4) is given for the double agent with the linear deteriorating work. The scheduling problem of single machine unbounded batch processor is based on the compatibility between the two agents and the non compatibility of the same batch in the same batch, considering the same release time and the two different situations as follows: (1) when the release time of the work piece is the same, the total cost of minimizing the completion time of the agent A work piece is minimized. The maximum cost (or total cost) of the completion time of the agent B is not more than a given upper bound, and the optimal solution properties of the problem are analyzed. The optimal solution of the dynamic programming algorithm is given respectively. (2) the maximum completion time of the agent A work is made to minimize the maximum completion time of the agent to make the maximum completion of the agent B workpiece. The structure and properties of a given upper bound are not exceeded, the structure and properties of the optimal solution are analyzed, and the solution method of the optimal solution.5) is given. In view of the cooperative game problem of the multi agent production scheduling on a single machine batch machine, the optimal solution of the multi agent production scheduling is studied, and the reasonable allocation mechanism of the multi generation rational cooperation and cost saving is designed. The existence of multi agent cooperative game and job cooperative game kernel. For the special situation of multi agent production scheduling, it is proved that the corresponding multi agent cooperative game and the job cooperative game are all convex game.6). For the double agent two machine shop scheduling problem with linear deteriorating workpieces, the flow shop and open shop are considered respectively. In the environment of the job shop, the objective function is to minimize the maximum completion time of the agent A job making the maximum completion time of the agent B workpiece not more than the time complexity of the problem of a given upper bound. For the flow shop, the NP- difficulty of the problem is proved, and the optimum for the two special cases with the dominant machine relationship is given. Algorithm. For open shop and heterogeneous job shop, the NP- difficulty of the problem is proved respectively.
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TB497

【相似文献】